Struct adj_matrix

Struct Documentation

struct adj_matrix

Implementation of adjacency matrix representation of a “static” graph.

Static in the sense that the # of vertices in the graph cannot be changed after initialization. Graphs can be both weighted/unweighted, directed/undirected, per configuration. However, you can’t have an undirected graph that is weighted.

Sentinel values in the matrix used for detecting if an edge exists are 0 for undirected graphs, and NAN for directed graphs, so don’t use those values for valid edges (though why would you?).

Pros: Removing edges takes O(1). Queries like “is there an edge from vertex u

to vertex v” are efficient and can be done in O(1).

Cons: Consumes O(V^2) space, regardless of # edges (i.e. don’t use this for sparse graphs). Also you cannot use this data structure if the max # of edges in the graph is not known a priori.

Public Members

bool_t is_directed

Is the graph directed?

bool_t is_weighted

Is the graph weighted?

size_t n_edges

Number of edges currently in the graph

size_t elt_size

Size of elements in bytes (only used to make edge queries a bit faster.)

size_t n_vertices

Numer of vertices in the graph

struct matrix matrix

Underlying matrix implementation handle.

uint32_t flags

Configuration flags. Valid flags are:

All other flags are ignored.