UnDirected Graph Cycle Detection: C++ wrapper over Boost Graph Library (BGL)
C++ wrapper over Boost Graph Library (aka BGL), provides a mean to detect cycles in an undirected graph.
For example, with the following graph generated by the included sample program:
This code will give you the three cycles as three sets of vertices.
These are sorted with the smallest vertex in first position, and such as the second vertices is always smaller than the last one (see notes):
1-6-5-4-3-2-1-6-5-4-13-14-7-3-2-3-7-14-13-4-
#include "udgcd.hpp" in your application (all-in-one file).Call udgcd::findCycles(). It will return a set of paths that are cycles (1):
auto cycles = udgcd::findCycles<my_graph_type,my_vertex_type>( graph );
Just to check, you may call udgcd::printPaths() to print out the cycles:
udgcd::printPaths( std::cout, cycles, "cycles" );
(1) The type of the returned value is actually std::vector<std::vector<my_vertex_type>>
See included sample programs.
To check without writing any code, you can also try the program read_graph.cpp
make run, no other dependency than BGL.Just fetch the file udgcd.hpp above and store it where you want. Or use the provided target of makefile (if you clone the whole repo):make install (might require sudo).
This will copy the file in /usr/local/include/
Some additional apps are included, that are build by the makefile:
read_graph.cpp: reads graph from a text file given as argument, computes its cycles, prints them and generate the corresponding dot file.random_test.cpp: generates a random graph computes its cycles, prints them and generate the corresponding dot file.sample_?.cpp: C++ apps that build a graph and computes its cycles.make help):make (no targets) : builds the included demos appsmake run : builds and runs all the included demo programsmake runsam : builds and runs the read_graph.cpp program and runs it on all provided data samples, in folder samples/make doc : builds the doxygen reference file (needs doxygen installed). Useful if you want to dive into the code…Demos
build/bin/sample_X.This will generate a random graph with 15 nodes and 25 vertices, and will check for cycles. Print a lot of additional info.
$ build/bin/random_test 15 25
The program read_graph.cpp (build an run by make runsam) will generate a dot file that can be rendered as an image with Graphviz.
So if Graphviz/Dot is installed, you can try make svg: this will call Graphivz on all the dot files in the out folder.
Some datafiles are included in the samples folder.
For example, this:
$ build/bin/read_graph samples/graph_0.txt
will produce these two dot files in the out folder:
graph_0_0.dotgraph_0_color_1.dot
The first one is the raw graph, the second holds the cycles expressed as additional edges.
They can be rendered graphically with $ make svg, that will produce theses two files:
The algorithm involved here is pretty simple, but probably not very efficient, thus slow for large graphs.
Three steps are involved: first we need to check if there is at least one cycle.
Is this is true, we explore the graph to find it/them.
It can be considered as a variant of the Horton Algorithm.
The first step is done by a Depth First Search (DFS), with boost::undirected_dfs()
with passing a visitor of class CycleDetector, inherited from
boost::dfs_visitor.
This object holds a set of vertices that are part of an edge on which back_edge() is called (called here “source vertices”).
If this happens, it means that a cycle has been encountered.
The second step is done by exploring recursively the graph, by starting from each of the sourece vertices.
This step is the most time-consuming.
The third steps does some post-processing:
sort cycles by decreasing length, and do Gaussian Elimination to retain a Minimal Cycle Basis (MCB).
In the output vector, the paths can be sorted if the symbol UDGCD_NORMALIZE_CYCLES is defined.
This requires the < operator defined for the vertices.
Sorting is done such as:
As an example, say you have a raw cycle expressed as
6-2-1-4, it is released as 1-2-6-4 (and not 1-4-6-2).
You can use whatever edge and vertices types, the coloring needed by the algorithm is handled by providing color maps as external properties.
So if you have no special needs on vertices and edge properties, you can use something as trivial as this:
using graph_t = boost::adjacency_list<boost::vecS,boost::vecS,boost::undirectedS>;
But you can also have some user properties, defines as bundled properties. For example:
struct my_Vertex{int v1;std::string v2;float v3;};struct my_Edge{int e1;std::string e2;};
Then your graph type definition will become:
using graph_t = boost::adjacency_list<boost::vecS, // edge containerboost::vecS, // vertex containerboost::undirectedS, // type of graphmy_Vertex, // vertex typemy_Edge>;