The GI-EXT program is available for download as a source code form (Windows/Linux) or as a (non-optimized) Windows executable. Regular graphs:Notes: 1. To use the parallel version (in openMP), you do not need to change the code; please follow these instructions. 2. Before trying very large graphs (more than 10000 vertices), please make sure that the RAM memory will not overflow on to disk storage (the OS can swap some pages on disk). GI-Ext might require about 30 X |V|² bytes of free RAM, i.e. one needs 30 X 100 MBytes = 3 GBytes for |V|=10000, 12 GBytes for |V|=20000, 27 GBytes for |V|=30000.... 300 GBytes for |V|=100.000. Graph Input Examples 1. Two 50% density regular graphs with |V|=2000 and the solution (isomorphism): reg2000G1.mat, reg2000G2.mat, reg2000G1G2Solution.txt - Download the above files and execute: ./gi-ext reg2000G1.mat reg2000G2.mat -SmySolutionFile.txt - The linux optimized version took 17 seconds, but the windows executable took between 20 seconds (AMD Athlon) to 32 seconds (Intel Core 2 @1.85Ghz) or 135 seconds (Intel Pentium 4 @ 2.8GHz)---the running speed depends on many CPU characteristics apart from the MHz clock rate. 2. Another two 2000-vertex regular graphs: reg2000H1.mat, reg2000H2.mat (the solution is h(n) = [V|-n) 3. Two regular graphs with |V|=3000 (density 50%) and the solution: reg3000G1.mat, reg2000H2.mat, reg3000G1G2Solution.txt - Solved in 56 seconds by the Linux version; - It is not possible to upload files larger than 10GBytes, but you can use the same program to generate larger regular graphs, see below. 4. Two regular graphs with |V|=1000 in the edge-list DIMACS graph format (see below): reg1000G1.col, reg1000G2.col, reg1000G1G2Solution.txt Strongly regular graphs: The McLaughlin graph with a vertex-permuted copy and the isomorphism: mclaughlinG1.col, mclaughlinG2.col, mclaughlinSolution.txt -attention: unlike the solution textfile, the input graphs are 0-indexed---they are built by simple modifications of edge-list graphs from [2] (used by permission) Pairs of graphs extracted from the graph database [1], used by permission (for research testing). - iso_b03m_m1000.A00 and iso_b03m_m1000.B00 - iso_m4Dr6_m1296.A00 and iso_m4Dr6_m1296.B00 - iso_r01_m1000.A00 and iso_r01_m1000.B00 Easy-to-Use GI-Ext Examples Very simple examples:1) ./gi-ext reg3000G1.mat reg3000G2.mat -tests two graphs for isomorphism, the extension determines the graph type, e.g. ".mat" is a very simple adjaceny matrix format (text file), see below. 2) ./gi-ext iso_m4Dr6_m1296.A00 iso_m4Dr6_m1296.B00 -Siso_m4Dr6_m1296Solution.txt -generates the solution file containing the isomorphism of this two graphs: iso_m4Dr6_m1296Solution.txt 3) ./gi-ext mclaughlinG1.col mclaughlinG2.col -SmclauglinSolution.txt - the output is analyzed here. Slightly more complicated example: 4) ./gi-ext 1000 -G 1000regG1.col -H 1000regG2.col -Ssolution.txt generates two random regular graphs with 1000 vertices and tests them for isomorphism. After this, it saves both graphs and the isomorphism solution. 5) ./gi-ext without argments shows all possible options. The times required to execute example 4) with |V| (the first argument) from 1000 to 20000: Times1000-20000.txt Supported Input Formats [1] De Santo et. al, A large database of graphs and its use for benchmarking graph isomorphism algorithms, Pattern Recognition Letters, 24:8.mat adjaceny matrix format (but put only (|V|-1) lines of elements, those bellow the diagonal), see this example: adjacencyMatrixFormat.mat .col Dimacs graph standard format, basically a list of edges (it is enough to give any of (a,b) and (b,a); the first vertex can be 0 or 1); see this example: myciel3.col This format is useful because one can easily swap two vertices with a command like: sed -e "s/123/TMP/g;s/456/123/g;s/TMP/456/g" -i reg1000G1.col #pay attention not to change the field "number of vertices/edges" with this command. .A00 The format used in the graph database [1] (same as for B00, A01, B01, A02, etc.) References The actual graphs are available at http://amalfi.dis.unina.it/graph/ [2] http://people.csse.uwa.edu.au/gordon/constructions/mclaughlin/index.html Other software: bliss saucy nauty Contact: daniel.porumbel AT gmail DOT.DOT com |
