Bispanning Graph Connectivity Testing Framework

This archive contains the source code developed alongside my diploma thesis "On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs". The source code is not a clean program which one can simply run, it is more a toolset for testing theories about bispanning graphs. Hence, many source code fragments which were written for specific hypothesis, which later turned out correct or incorrect, are still contained or were commented out.

Nevertheless, the code contains a reasonably elegant, efficient, and flexible framework to represent and analyze directed and undirected graphs, and to enumerate small graphs using nauty/geng. The framework outputs graphs in the graphviz format, which automatically layouts and draws graphs.

The source code version 0.5 is available for download from this webpage (browse source) or from a github repository, under the GNU General Public License Version 3.

The table below contains the number of bispanning graphs for three subsets of the class: all including parallel edges, only simple ones without parallel edges, and atomic ones, which are the most difficult. The link "list" points to a html table containing a list of all graphs, together with many graph-theoretic properties. The file "csv" is a CSV version of the html table, the file "base" contains an enumeration of all bispanning graphs, and the "tau3" file additionally the unique exchange graphs of each.

vertices	parallel edges	simple	atomic
2	1 - list (csv) / base / tau3	0	0
3	2 - list (csv) / base / tau3	0	0
4	9 - list (csv) / base / tau3	1 - list (csv) / base / tau3	1 - list (csv) / base / tau3
5	46 - list (csv) / base / tau3	2 - list (csv) / base / tau3	1 - list (csv) / base / tau3
6	380 - list (csv) / base / tau3	12 - list (csv) / base / tau3	4 - list (csv) / base / tau3
7	4229 - list (csv)	92 - list (csv) / base / tau3	15 - list (csv) / base / tau3
8	61103	1010 - list (csv) / base	109 - list (csv) / base
9	1077101	14957	1075 - list (csv) / base
10	22364980	275748	14506 - list (csv)

Compilation and Sample Run/Output

To compile the source code on Ubuntu Linux, install at least the following required packages:

sudo apt-get install build-essential g++ cmake libexpat-dev
sudo apt-get install libboost-regex-dev libboost-program-options-dev libigraph-dev graphviz

Then you need to build nauty/geng, which is a separate package to enumerate graphs:

tar xvzf nauty25r5.tar.gz
cd nauty25r5
./configure
make
cd ..

And then use cmake to build the bispanning graph framework, and copy geng and genbg over.

mkdir build
cmake ..
make
cd src/
cp ../../nauty25r5/geng .
cp ../../nauty25r5/genbg .

Once done building, you can enumerate bispanning graphs using the main play_bispanning program. Prior to running it, you have to add the directory containing geng to $PATH such that the program will find it.

export PATH=$PATH:.
./play_bispanning -h

The program play_bispanning takes a list of arguments, which determine which graphs are enumerate. A simple number, like "6", enumerates all small graphs with six vertices. Additionally, one can specify any combination of the following constraints: atomic, composite, triangle-free, square-free, general (for parallel edges), vconn=1, vconn=2, vconn=3, econn=2, econn=3, and maxdeg=4. The constraints must precede the simple number "6", since the number triggers processing.

The output of play_bispanning is determined by command line flags such as -g and -G, and it not mean to be read directly. Instead, it is input for the fdp graph layout tool, which is part of the graphviz program suite.

For example:

• ./play_bispanning -gG 6 | fdp -Tps -o bispanning-6-vertices.ps
  calculates the unique exchange graphs for all bispanning graphs with six vertices.
• ./play_bispanning -gG atomic 8 | fdp -Tps -o bispanning-8-vertices-atomic.ps
  calculates the unique exchange graphs for all atomic bispanning graphs with eight vertices.

Overview of the Source Code

• play_bispanning.cpp: The main program used to enumerate graph and apply algorithmic tests. See above for some examples.
• graph.h: A generic graph implementation with many simple super-generic algorithms like BFS. This is the base class for the more specific bispanning graph and edge exchange graph implementations. For calling more advanced graph algorithms, there exist three "bridges" to external libraries: graph_igraph.h to iGraph, e.g. for calculating vertex and edge connectivity, graph_boost.h for planarity testing, graph_eigen.h for calculating eigenvalues.
• bispanning.h: An instantiation of the generic graph for bispanning graphs. It contains algorithms to test whether a bispanning graph is atomic or composite, and methods to calculate the cuts and cycles.
• alg_bispanning.h: An implementation of Roskind and Tarjan's algorithm for finding two disjoint spanning trees in a graph.
• alg_game.h: An instantiation of the generic graph for the edge/base exchange graphs. It contains a simple algorithm to explore the edge/base exchange graph breadth-first and construct AlgGame which contains the result. This result is always tested for connectivity and optionally, the diameter is calculated.
• decomposition.h: Functions to test the composition theorems found in section 5 of the thesis.

Additional more general purpose code can be found in combinatorics.h and debug.h.

Exits

Written 2016-01-13 by Timo Bingmann