Graphisomorphism is one of the fundamental problems in mathematics as well as in complexity theory. Up to now (2009) it is not known, whether this problem belongs to P or NP.
Most practical algorithms for solving graphisomorphism relay on backtracking (VF/VF2 algorithm; see Amalfi Graph Database) or group theoretic approaches (see nauty). Unfortunately, these implementations are written in highly optimized C and therefore neither object-oriented nor user friendly.
Here we present a new fast graphisomorphism algorithm, called the Information-Theoretic Graphisomorphism-Algorithm (ITGI-Algorithm). It is written in object-oriented Java using the popular yfiles graph library. The ITGI algorithm can be freely downloaded here:
Currently it is under revision at the Journal of Discrete Algorithms [www].
The algorithm is based on the observation, that a graph mainly consists of edges. Therefore it uses vertex-invariants, so called marks, to perform a computation that heavily relies on edges. In this way an intermediate graph representation is computed in which each edge (hopefully) had an impact. By first comparing these representations, which can be precomputed, many non-isomorphism candidates can be filtered out. When comparing graphs for equality, the precomputed marks aid the matching process. To initialize the computation, so called classificator functions assign marks each node of the graph depending on some general properties. The classificators are:
We found also counter examples where the first four classificators (DC,CDC,LPC,SNPCC) failed to yield good runtimes. These graphs were regular graphs wherein each node has the same degree. But the BFSC, which incorporates global properties, resulted in a good runtime, despite its expensive computation time.
Here is a little code snipplet to show, how this Algorithms is used:
If you have any problems running this algorithm, please write to firstname.lastname@example.org.