graph
A simple header only library for directed graphs.
graph.hpp
graph<VT, ET>
: A directed graph with internal vertex data of type VT
and internal edge data of ET
. Edges (v,w)
are not unique. Edges adjacent to vertex v
are cached and returned at zero cost.
graph_algorithms.hpp
A collection of algorithms that operate on a graph G
.

find_vertex(G, d)
– Find a vertex with matching internal data inO(V)

dijkstra(G, v, w)
– Dijkstra’s pathfinding fromv
tow

search(G, v, pred)
– Breadth first search finding the first vertex matchingpred

path_exists(G, v, w)
– Breadth first search to determine if a path fromv
tow
exists 
will_cycle(G, v, w)
– Check if creating edge(v,w)
will cycle by checking for path fromw
tov

tarjan_scc(G)
– Return a graph whereV
contains strongly connected clusters of vertices inG

is_strongly_connected(G)
– Runtarjan_scc(G)
and check if there is only one cluster 
cycles(G)
– Runtarjan_scc(G)
and check if there are no clusters 
get_random(n, m, Gv, Ge)
– Generate a random graph withV=n, E=m
, with generator functions
VRef
and ERef
VRef
and ERef
are essentially handles to vertices and edges that can be derefenced to access the underlying VT
and ET
user data objects. VRef
s and ERef
s are valid for as long as they are present in their owning graph. This means the owning graph can be modified without invalidating references. They are invalidated when removed from the graph, or when the owning graph is destructed. Derefencing them after they are invalidated is undefined behavior.