Imperative Graph Implementations.
Signature of imperative graphs.
Edges may be labeled or not:
Vertices may be concrete or abstract:
How to choose between concrete and abstract vertices for my graph implementation?
Usually, if you fall into one of the following cases, use abstract vertices:
In other cases, it is certainly easier to use concrete vertices.
Imperative Directed Graphs.
Bidirectional graphs use more memory space (at worse the double) that standard concrete directional graphs. But accessing predecessors is in O(1) amortized instead of O(max(|V|,|E|)) and removing a vertex is in O(D*ln(D)) instead of O(|V|*ln(D)). D is the maximal degree of the graph.
Imperative graphs implemented as adjacency matrices.
Vertices are integers in
A vertex label is the vertex itself.
Edges are unlabeled.
Creation. graphs are not resizeable: size is given at creation time.
make must be used instead of
remove_vertex have no effect.
clear only removes edges, not vertices.