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 with|V|=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.