README for graphisomorphismalgorithm-svn-1.5.6.zip
===============================
In this version, I am very glad to say that two kind of difficult graph (http://pallini.di.uniroma1.it/library/here_dim/f-lex.zip,
http://pallini.di.uniroma1.it/library/misc/dim/Aff25.zip) can be solved in polynomial complexity. (To test graph Aff25, please in linux OS, unzip graphisomorphismalgorithm-svn-1.5.6.zip, open command line window, into nauty folder, then run "./TestNauty -v 1600 -t 6 -c 50 -f Aff25 -m")
so I believe the graph isomorphism is a P issue.
This is a test program for VFLib, Nauty, MatrixGraph, version 1.5.6
Although MatrixGraph is not the fastest algorithm, we tested MatrixGraph is not of polynomial time for some special graph, but we believe we can make it of polynomial time.
Warnings:
======
I put the vflib2 and Nauty here, only for testing our algorithm with vflib2 and Nauty. If it create some side effect or any
infringement, please let me know, we will remove it.
History:
Version: 1.5.6 ---------------------2015/12/13
Test result:
============
Some old test result listed below:
let non-direct graph vertices count is n,
a) MatrixGraph compared with VFLib2:
...................................
for almost every graph MatrixGraph is faster than VFLib2
except for some sparse graph now
b) MatrixGraph compared with Nauty:
...................................
MatrixGraph is as fast as Nauty for random graph. for example, we use "TestEach(1000, 800, 3, 0.5f,false,false);" or "TestEach(1000, 800, 0, 0.5f,false,false);" in TestNauty.cpp
Nauty is as fast as MatrixGraph for most regular graph now. for example, we use "TestEach(1000, 800, 1, 0.5f,false,false);" in TestNauty.cpp.
For almost some difficult graph, MatrixGraph is faster than Nauty, such as graphs in http://pallini.di.uniroma1.it/library/here_dim/f-lex.zip
c) MatrixGraph compared with Traces:
...................................
MatrixGraph is as fast as Traces for random graph. for example, we use "TestEach(1000, 800, 3, 0.5f,false,false);" or "TestEach(1000, 800, 0, 0.5f,false,false);" in TestNauty.cpp
MatrixGraph consume about 5-10 times time than Traces for most regular graph now. for example, we use "TestEach(1000, 800, 1, 0.5f,false,false);" in TestNauty.cpp.
For most of difficult graph, MatrixGraph is slower than Traces.
The following file folder are included:
===========================================
File Folder Description
---------------------- ---------------------------------------------------------
.\matrix_graph - Matrix graph lib to judge isomorphism of Two graph
.\nauty - Nauty graph lib to judge isomorphism of Two graph
.\vflib2 - Vflib graph lib to judge isomorphism of Two graph
.\project\vflib2\windows - Test program project(misrosoft visual studio project) to compare Vflib graph lib with Matrix graph lib when judging isomorphism of Two graph
The following file are important:
====================================
File name Description
---------------------- ---------------------------------------------------------
.\nauty\nauty_my_gm.mk - Make file(linux) of test program for comparing nauty graph lib with Matrix graph lib when judging isomorphism of Two graph
