Pregraphs

Home Welcome Authors Gunnar Brinkmann Nico Van Cleemput Tomaž Pisanski

Introduction Here you will find the generator and related programs described in the paper G.Brinkmann, N. Van Cleemput and T. Pisanski, Generation of various classes of trivalent graphs, Theoretical Computer Science, Volume 502, 2 september 2013, p.16-29, doi: 10.1016/j.tcs.2012.01.018 The generator and filters Download The pregraphs project is released under the GNU General Public License (GPL) with the following copyright notice Copyright (C) 2010-2011 Universiteit Gent This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A copy of the GNU General Public License can be found in the file LICENSE.txt provided with the source distribution of this program (see the META-INF directory in the source jar). This license can also be found on the GNU website at http://www.gnu.org/licenses/gpl.html. If you did not receive a copy of the GNU General Public License along with this program, contact the lead developer, or write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. You can download the source files here: pregraphs-sources.zip/pregraphs-sources.tar.gz. You can also visit the GitHub page of this project. Build Extract the file you downloaded above into a directory named pregraphs. Download nauty from the nauty page. Extract the files of nauty into a directory named nauty inside the pregraphs directory. Open a terminal and cd into the nauty directory. Run ./configure. In the terminal cd to the pregraphs directory and run make. There are some special make targets which you might want to use: 64bit Makes pregraps-64 which can generate larger pregraphs, but should be slower for graphs smaller than 32 vertices. profile Makes pregraps-profile which can be used to profile pregraphs. debug Makes pregraps-debug which can be used to debug pregraphs. complete Makes all the default targets plus some utility programs. Besides these targets there are several flags that can be set to make pregraphs print out more detailed statistics and/or debugging information about the generation process. The most general of these two are _PROFILE and _DEBUG. If you like to see huge amounts of texts scrolling on your window, then use these flags, but otherwise these flags just make the program slower and aren't useful unless you're modifying the program. For more detail you'll have to look at the header files. Usage The program pregraphs calculates pregraphs of a given order n. Usage: ./pregraphs [options] n The n stands for the desired number of vertices. Valid options: -h Print help and return. -i Causes pregraphs to print extra info about the generated structures. -L Allow loops. -S Allow semi-edges. -M Allow multi-edges. -C Only generate 3-edge-colourable pregraphs. -B Only generate bipartite pregraphs. -q Only generate pregraphs that have a 2-factor where each component is the quotient of a 4-cycle. -4 Only generate pregraphs that have a 2-factor where each component is a 4-cycle. -P Only generate the corresponding pregraph primitives. -I Only start the generation from the files provided by the input file (see -F). -f file Specifies the output file. If absent, the output is written to standard out. -F file Specifies the input file. If absent, the input is taken from standard in. This option is only used if -I is used. -o c Specifies the export format where c is one of c pregraph code (or multicode if -P is used) h human-readable output in tabular format n no output : only count (default) -m r:m[:d] Split the generation into several parts. This basically means that at depth d a counter will be kept and the program will only continue beyond this point if the counter mod m is equal to r. Special measures are taken if some graphs are already outputted before depth d. The default for d is 0. Examples If you want to count all bipartite multigraphs with 4 vertices you use the following command: ./pregraphs -MB 4 The output will then be: Generating bipartite multigraphs with 4 vertices. Found 1 pregraph with 4 vertices. CPU time: 0.0 seconds. If you want to view this graph as a simple table, you can use the output option and write the graph to a table: ./pregraphs -MB -oh 4 The output will then be: Generating bipartite multigraphs with 4 vertices. ============================== | Graph number: 1 | | Number of vertices: 4 | ============================== | 1 || 4 | 2 | 2 || | 2 || 1 | 3 | 1 || | 3 || 2 | 4 | 4 || | 4 || 3 | 1 | 3 || ============================== Found 1 pregraph with 4 vertices. CPU time: 0.0 seconds. If you want to store this graph in a file named bipartite_multigraph.code, you write the following: ./pregraphs -MB -oc 4 > bipartite_multigraph.code If you want to check whether this graph has a 2-factor where each component is a quotient of a 4-cycle, you can do this using: ./pregraphs -MBq -oc 4 The output will then be: Generating bipartite multigraphs with 4 vertices and filtering graphs that have a 2-factor where each component is a quotient of a 4-cycle. Found 1 pregraph with 4 vertices. CPU time: 0.0 seconds. Utility programs The pregraphs project also includes several small utility programs which might come in handy when working with the generator and/or the filter programs. We just list a small description of the programs here. If you need help using them, please contact us. pgfilter This program can be used to filter out certain ranges of pregraphs from the output of one of the programs. It can also be used to filter out a specific pregraph. The filtered pregraphs can be outputted in pregraph_code or as human-readable tables. admissable_c This program can be used to filter out the pregraphs with a 2-factor where each of the components is a quotient of a 4-cycle from the output of one of the programs. This is a standalone version of the filter used when invoking pregraphs with the -q option. c4cover This program can be used to filter out the pregraphs with a 2-factor where each of the components is a 4-cycle from the output of one of the programs. This is a standalone version of the filter used when invoking pregraphs with the -4 option. has3edgecolouring This program can be used to filter out the 3-edge-colourable pregraphs from the output of one of the programs. This is the program that was used to test the -C option of pregraphs. This program also has the option to export the non-3-edge-colourable pregraphs, which isn't possible with pregraphs. Besides that option this filter has the same options as admissable_c and c4cover. bipartite This program can be used to filter out the bipartite pregraphs from the output of one of the programs. This is the program that was used to test the -C option of pregraphs. This program also has the option to export the not bipartite pregraphs, which isn't possible with pregraphs. Besides that option this filter has the same options as admissable_c and c4cover. The format pregraph_code The standard output format for the generator and the filters is pregraph_code. This code is based upon multicode. It is a binary code structured as follows. The convention is to give the filename the extension .code. The file starts with a header this header is one of >>pregraph_code<<, >>pregraph_code le<< or >>pregraph_code be<<. The first two headers mean that little endian is used, the third that big endian is being used (see later). If the graph contains less than 255 vertices, then the first entry is the order of the graph. Then to each vertex x there is a list of neighbours of x with higher numbers than x. The vertices are numbered from 1 to n (where n is the order of the graph). If a vertex is incident with semi-edges, than n+1 is added to the list for each semi-edge that is incident with x. Each list is closed by a zero. It is possible that some lists are empty. If the graph contains 255 or more vertices, then the first entry is a zero. After that the same format as with the smaller graphs is used, but now each entry consists of two bytes instead of one byte. These two-byte-numbers are in little endian or big endian depending on the header of the file. After the last entry the following graph follows immediately. Pregraph Viewer Files containing pregraphs encoded in the pregraph_code format can be viewed using the program Pregraph Viewer. This program uses Java (5.0 or later) and is available for Windows and UNIX (GNU Linux and Mac OS X). Pregraph Viewer for Windows (installer) Pregraph Viewer for Mac OS X (disk image) Pregraph Viewer for Unix (extract the file and run the script) Source distribution GitHub page Pregraph Viewer should be quite self-explanatory. Look closely, because the initial window is relatively small! Pregraph Viewer is released under the GNU General Public License (GPL) with the following copyright notice Copyright (C) 2010-2011 Universiteit Gent This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A copy of the GNU General Public License can be found in the file LICENSE.txt provided with the source distribution of this program (see the META-INF directory in the source jar). This license can also be found on the GNU website at http://www.gnu.org/licenses/gpl.html. If you did not receive a copy of the GNU General Public License along with this program, contact the lead developer, or write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. Pregraph Viewer uses the following open source software: GraphIO: GraphIO-1.0.jar, GraphIO-1.0.src.jar, GraphIO-1.0.javadoc.jar, Apache Ant (at least version 1.6.5) JDOM (at least version 1.0) Launch4j (at least version 3.0.0-pre2 or later) Nsis (at least version 2.0.6 or later) JarBundler Embedded pregraphs Pregraph Viewer introduces a new file format: embedded pregraphs. When opening a pregraph_code file Pregraph Viewer tries to embed that graph using a random embedder and a force directed embedder. You can rearrange these embedding using the mouse. Afterwards you might want to save these changed embeddings. You can do this by using the menu item Save list of embedded pregraphs. This uses an XML-based format to store the graphs. The default extension for these files is .epxml. The root element is embeddedpregraphs. This element contains one or more embeddedpregraph elements. Each of these contains exactly one vertices element and one edges element. For each vertex there should be a vertex element in the vertices element describing the position of the vertex. For each semi-edge there should be a semiedgevertex element in the vertices element describing the end point of the semi-edge. For each loop there should be a loopvertex element in the vertices element describing the tip of the loop. Each of these elements has three attributes: an X attribute giving the horizontal position, an Y attribute giving the vertical position, and an id attribute giving an unique non-zero number for the vertex. All numbers from 1 to the order of the graph + the number of semi-edges + the number of loops need to be used. For each edge there should be an edge element in the edges element. Each of these elements has three attributes: a vertex1 attribute and vertex2 attribute giving the two vertices incident with this edge (use the id's to identify the vertices) and a multiplicity attribute giving the multiplicity of the edge. For loops use the vertex that is incident with the loop and the loop vertex describing the tip of the loop. For semi-edges use the vertex incident with the semi-edge and the semi-edge vertex describing the end point of the semi-edge. Remarks If you download any of these files, we would appreciate to receive an e-mail which lets us know that you have done so.