The script generate.pyx in this directory generates minimally 3-connected
graphs with a given cubic minor as a "root" graph; the default root graph is
the prism graph with 6 vertices and 9 edges. The code in this repository
implements the procedures documented in "Constructing Minimally 3-connected
graphs", by João Paulo Costalonga, Robert Kingan and Sandra Kingan..
This program is written in Python version 3.6. It uses a few packages that require special installation.
Cython is an extension to Python programming language that causes source code to be translated into optimized C/C++ code and compiled at runtime, which results in faster program execution. Cython is the reason why all source code files in this repository are named with .pyx, instead of .py, extensions.
pynauty is a Python/C extension module that allows the functionality in Brendan McKay and Adolfo Piperno's nauty system to be accessed from Python. Note that in order to install pynauty, you must first download and compile nauty itself. Installation instructions can be found here.
This program uses pynauty to generate graph certificates, which are used in turn to eliminate newly generated graphs that are isomorphic to graphs already generated.
igraph is a collection of network analysis tools; this [program uses igraph's Python implementation to enumerate the simple paths [between two vertices in a graph.
On some platforms, python-igraph may need to be compiled from source. Installation instructions can be found on the python-igraph home page.
Once you have the prerequisite packages installed, set your PYTHONPATH
environment variable to include this directory. The script generate.pyx
carries out all operations necessary to generate minimally 3-connected graphs
with a specific cubic minor that involve:
- Creating n-vertex, m-edge graphs from n-vertex, (m-1)-edge graphs
- Creating n-vertex, m-edge graphs from (n-1)-vertex, (m-1)-edge graphs
This script expects to find the input files from previous runs in the current directory that it needs for its current operations, named according to the convention used in the script when saving files. For instance, using the default set of instructions, if the program were run to generate 11-vertex, 18-edge graphs, it would expect to find the following files already present from previous runs:
- m3c-11-17-B.txt.gz
- m3c-11-17-A1.txt.gz
- m3c-11-17-A2.txt.gz
- m3c-11-17-A3.txt.gz
- m3c-10-17-B.txt.gz
- m3c-10-17-A1.txt.gz
- m3c-10-17-C.txt.gz
Source graphs of type A0 are implicitly assumed to be from the "root" collection, and the default root graph is the prism graph.
For example, the following sequence of commands (on a Linux/Unix system) will
generate all minimally 3-connected 6-, 7- and 8-vertex graphs with a prism
minor (assuming that the environment variable M3C has been set to the top
directory of this repository and that the Python interpreter command is
python):
python $M3C/generate.pyx -r pr -f $M3C/root.json 10 6
python $M3C/generate.pyx -r pr -f $M3C/root.json 11 6
python $M3C/generate.pyx -r pr -f $M3C/root.json 12 6
python $M3C/generate.pyx -r pr -f $M3C/root.json 13 6
python $M3C/generate.pyx -r pr -f $M3C/root.json 11 7
python $M3C/generate.pyx -r pr -f $M3C/root.json 12 7
python $M3C/generate.pyx -r pr -f $M3C/root.json 13 7
python $M3C/generate.pyx -r pr -f $M3C/root.json 14 7
python $M3C/generate.pyx -r pr -f $M3C/root.json 15 7
python $M3C/generate.pyx -r pr -f $M3C/root.json 12 8
python $M3C/generate.pyx -r pr -f $M3C/root.json 13 8
python $M3C/generate.pyx -r pr -f $M3C/root.json 14 8
python $M3C/generate.pyx -r pr -f $M3C/root.json 15 8
python $M3C/generate.pyx -r pr -f $M3C/root.json 16 8
python $M3C/generate.pyx -r pr -f $M3C/root.json 17 8
python $M3C/generate.pyx -r pr -f $M3C/root.json 18 8The program will generate a log detailing its actions, and will output the graphs in files named according to the current values of n, m and the type of graph being generated. Note that only the graphs in the output files containing "A1", "A2", or "A3" in the name are minimally 3-connected; the graphs in the files with "B" and "C" in the name are intermediate graphs generated as part of a multi-step procedure.
The minimally 3-connected graphs generated by the program are stored in files in
the g6-output directory in this repository. Each output file is stored in
graph6 format. The files
are organized by type, number of vertices and number of edges; for example, the
file m3c-07-11-A1.g6 contains graphs with 7 vertices and 11 edges of type A1.
The number of graphs in each file is listed in the table below:
| Type | Vertices | Edges | Count |
|---|---|---|---|
| A1 | 7 | 11 | 3 |
| A2 | 8 | 12 | 4 |
| A1 | 8 | 13 | 11 |
| A3 | 8 | 14 | 1 |
| A1 | 9 | 14 | 19 |
| A1 | 9 | 15 | 29 |
| A3 | 9 | 15 | 1 |
| A1 | 9 | 16 | 5 |
| A3 | 9 | 17 | 1 |
| A2 | 10 | 15 | 14 |
| A1 | 10 | 16 | 130 |
| A1 | 10 | 17 | 108 |
| A1 | 10 | 18 | 21 |
| A3 | 10 | 18 | 3 |
| A1 | 10 | 19 | 5 |
| A3 | 10 | 19 | 1 |
| A3 | 10 | 20 | 1 |
| A1 | 11 | 17 | 138 |
| A1 | 11 | 18 | 756 |
| A2 | 11 | 18 | 2 |
| A3 | 11 | 18 | 1 |
| A1 | 11 | 19 | 463 |
| A1 | 11 | 20 | 115 |
| A3 | 11 | 20 | 1 |
| A1 | 11 | 21 | 24 |
| A3 | 11 | 21 | 4 |
| A1 | 11 | 22 | 5 |
| A3 | 11 | 22 | 1 |
| A3 | 11 | 23 | 1 |
| A2 | 12 | 18 | 57 |
| A1 | 12 | 19 | 1823 |
| A1 | 12 | 20 | 4588 |
| A2 | 12 | 20 | 1 |
| A1 | 12 | 21 | 2480 |
| A2 | 12 | 21 | 2 |
| A3 | 12 | 21 | 9 |
| A1 | 12 | 22 | 666 |
| A3 | 12 | 22 | 3 |
| A1 | 12 | 23 | 150 |
| A3 | 12 | 23 | 2 |
| A1 | 12 | 24 | 26 |
| A3 | 12 | 24 | 7 |
| A1 | 12 | 25 | 5 |
| A3 | 12 | 25 | 2 |
| A3 | 12 | 26 | 1 |
Contact Robert Kingan at robertkingan@gmail.com or Sandra Kingan at skingan@brooklyn.cuny.edu.