GI-EXT: Graph Isomorphism using EXTended graphs

Algorithm from the paper: Isomorphism Testing using Polynomial-Time Graph Extensions. Journal of Mathematical Modelling and Algorithms, in press. (pdf draft, doi) Springer© 

Download:

       - (non-optimized) Windows executable download;
       - source code download (Windows/Linux).

1. Usage

Very simple examples (see also Section 2 to download the graphs):
     1) ./gi-ext reg3000G1.mat reg3000G2.mat           
          -tests two graphs for isomorphism (the extension ".mat" indicates a very simple adjacency matrix format (text file), see Section 3 below for downloads)
     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 usage:
     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 (see also the times required to execute this command with |V| (the first argument) from 1000 to 20000: Times1000-20000.txt)
     5) ./gi-ext without arguments shows all possible options.

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.


2. Graph Input Examples

Regular graphs
:
  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, reg3000G2.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
3. Supported Input Formats

.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

[1] De Santo et. al, A large database of graphs and its use for benchmarking graph isomorphism algorithms, Pattern Recognition Letters, 24:8
    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 univ-artois DOT.DOT fr

Č
ċ
ď
Times1000-20000.txt
(1k)
Daniel Porumbel,
Mar 1, 2009, 8:40 AM
ċ
ď
adjacencyMatrixFormat.mat
(0k)
Daniel Porumbel,
Feb 24, 2009, 4:03 AM
ċ
ď
iso_b03m_m1000.A00
(5k)
Daniel Porumbel,
Feb 26, 2009, 6:00 AM
ċ
ď
iso_b03m_m1000.B00
(5k)
Daniel Porumbel,
Feb 26, 2009, 6:00 AM
ċ
ď
iso_m4Dr6_m1296.A00
(11k)
Daniel Porumbel,
Feb 26, 2009, 5:59 AM
ċ
ď
iso_m4Dr6_m1296.B00
(11k)
Daniel Porumbel,
Feb 26, 2009, 5:59 AM
ċ
ď
iso_m4Dr6_m1296Solution.txt
(12k)
Daniel Porumbel,
Feb 26, 2009, 8:05 AM
ċ
ď
iso_r01_m1000.A00
(197k)
Daniel Porumbel,
Feb 26, 2009, 5:58 AM
ċ
ď
iso_r01_m1000.B00
(197k)
Daniel Porumbel,
Feb 26, 2009, 5:58 AM
ċ
ď
mclaughlinG1.col
(138k)
Daniel Porumbel,
Feb 24, 2009, 4:13 AM
ċ
ď
mclaughlinG2.col
(138k)
Daniel Porumbel,
Feb 24, 2009, 4:15 AM
ċ
ď
mclaughlinSolution.txt
(2k)
Daniel Porumbel,
Feb 24, 2009, 4:17 AM
ą
ď
Daniel Porumbel,
Feb 25, 2009, 1:15 PM
ċ
ď
reg1000G1.col
(4779k)
Daniel Porumbel,
Feb 17, 2009, 5:27 AM
ċ
ď
reg1000G1G2Solution.txt
(8k)
Daniel Porumbel,
Feb 17, 2009, 5:36 AM
ċ
ď
reg1000G2.col
(4779k)
Daniel Porumbel,
Feb 24, 2009, 4:14 AM
ċ
ď
reg2000G1.mat
(3906k)
Daniel Porumbel,
Feb 17, 2009, 3:13 AM
ċ
ď
reg2000G1G2Solution.txt
(17k)
Daniel Porumbel,
Feb 17, 2009, 3:06 AM
ċ
ď
reg2000G2.mat
(3906k)
Daniel Porumbel,
Feb 17, 2009, 3:20 AM
ċ
ď
reg2000H1.mat
(3906k)
Daniel Porumbel,
Feb 17, 2009, 5:22 AM
ċ
ď
reg2000H2.mat
(3906k)
Daniel Porumbel,
Feb 17, 2009, 5:23 AM
ċ
ď
reg3000G1.mat
(8789k)
Daniel Porumbel,
Feb 17, 2009, 5:20 AM
ċ
ď
reg3000G1G2Solution.txt
(27k)
Daniel Porumbel,
Feb 17, 2009, 5:22 AM
ċ
ď
reg3000G2.mat
(8789k)
Daniel Porumbel,
Feb 17, 2009, 5:21 AM
Comments