panthema / 2016 / 0114-diploma-thesis / program

Bispanning Graph Connectivity Testing Framework

Posted on 2016-01-14 18:30 by Timo Bingmann at Permlink.

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 bispanning-2-vertices-parallel-edges.pdf / tau3 bispanning-uegraph-2-vertices-parallel-edges.pdf 0 0
3 2 - list (csv) / base bispanning-3-vertices-parallel-edges.pdf / tau3 bispanning-uegraph-3-vertices-parallel-edges.pdf 0 0
4 9 - list (csv) / base bispanning-4-vertices-parallel-edges.pdf / tau3 bispanning-uegraph-4-vertices-parallel-edges.pdf 1 - list (csv) / base bispanning-4-vertices.pdf / tau3 bispanning-uegraph-4-vertices.pdf 1 - list (csv) / base bispanning-4-vertices-atomic.pdf / tau3 bispanning-uegraph-4-vertices-atomic.pdf
5 46 - list (csv) / base bispanning-5-vertices-parallel-edges.pdf / tau3 bispanning-uegraph-5-vertices-parallel-edges.pdf 2 - list (csv) / base bispanning-5-vertices.pdf / tau3 bispanning-uegraph-5-vertices.pdf 1 - list (csv) / base bispanning-5-vertices-atomic.pdf / tau3 bispanning-uegraph-5-vertices-atomic.pdf
6 380 - list (csv) / base bispanning-6-vertices-parallel-edges.pdf / tau3 bispanning-uegraph-6-vertices-parallel-edges.pdf 12 - list (csv) / base bispanning-6-vertices.pdf / tau3 bispanning-uegraph-6-vertices.pdf 4 - list (csv) / base bispanning-6-vertices-atomic.pdf / tau3 bispanning-uegraph-6-vertices-atomic.pdf
7 4229 - list (csv) 92 - list (csv) / base bispanning-7-vertices.pdf / tau3 bispanning-uegraph-7-vertices.pdf 15 - list (csv) / base bispanning-7-vertices-atomic.pdf / tau3 bispanning-uegraph-7-vertices-atomic.pdf
8 61103 1010 - list (csv) / base bispanning-8-vertices.pdf 109 - list (csv) / base bispanning-8-vertices-atomic.pdf
9 1077101 14957 1075 - list (csv) / base bispanning-9-vertices-atomic.pdf
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
cd ..

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

mkdir build
cmake ..
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:

Overview of the Source Code

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


Written 2016-01-13 by Timo Bingmann