A simple header only library for directed graphs.
graph<VT, ET>: A directed graph with internal vertex data of type
VT and internal edge data of
(v,w) are not unique. Edges adjacent to vertex
v are cached and returned at zero cost.
A collection of algorithms that operate on a graph
find_vertex(G, d)– Find a vertex with matching internal data in
dijkstra(G, v, w)– Dijkstra’s pathfinding from
search(G, v, pred)– Breadth first search finding the first vertex matching
path_exists(G, v, w)– Breadth first search to determine if a path from
will_cycle(G, v, w)– Check if creating edge
(v,w)will cycle by checking for path from
tarjan_scc(G)– Return a graph where
Vcontains strongly connected clusters of vertices in
tarjan_scc(G)and check if there is only one cluster
tarjan_scc(G)and check if there are no clusters
get_random(n, m, Gv, Ge)– Generate a random graph with
|V|=n, |E|=m, with generator functions
ERef are essentially handles to vertices and edges that can be derefenced to access the underlying
ET user data objects.
ERefs 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.