User:Blue sky 22/sandbox

An efficient graph isomorphism algorithm for matching large graph was first presented by Luigi P. Cordella, Pasquale Foggia, Carlo Sansone and Mario Vento in 2004. This improved version of graph algorithm is named as VF2 graph isomorphism algorithm and it solves effectively the graph isomorphism problem on Attributed Relational Graph. This algorithm has less Time complexity and Spatial complexity and specially suited for achieving better performance on large graphs.

Definitions

Given two graphs G₁= (N₁, B₁) and G₂= (N₂, B₂), a mapping M, defined as M being the subset of (N₁ X N₂). M has isomorphism if it is Bijection that maintains branch structure of G₁ and G₂. It is assumed that the input graphs will be Directed graph. The graph matching process will be described through State space representation(SSR). The partial mapping solution M(s) relates to each of the states, s. M(s) identifies two subgraph G₁(s) and G₂(s). The Projection of M(s) onto N₁ and N₂ are denoted respectively as M₁(s) and M₂(s). Sets of branches of G₁(s) and G₂(s) denoted by respectively B₁(s) and B₂(s). F(s,n,m) is a Boolean function for pruning of Search tree.

Algorithm

1. At the initial stage s₀, the mapping function M(s₀) = empty.
2. The algorithm computes P(s), set of candidate node pairs to be added to current state s.
3. For each pairs of P(s), feasibility rules are calculated.
   1. If F(s,n,m) returns true with pair p = (n,m), the successor state, s' = s ⋃ p is computed.
   2. The whole process is recursively applied to s'.
4. The algorithm uses depth first strategy for exploring the search graph in State Space Representation.

Pseudocode

 1  Procedure  Match(State):
 2      Input:   Intermediate state s with initialization state s0 , M(s0) = empty;   
 3      Output:  The mapping between two graphs G1 and G2;
 4             
 5          If All nodes of G2 are covered by mapping function M(s)    
 6               Then output M(s);
 7          Else do:
 8               Calculate the candidate pair set P(s) for consideration into M(s);
 9               For each (n, m) belonging to the set P(s)
 10                  If F(s, n, m) = true;
 11                      Then compute new state s' = s ⋃ p' ;
 12                           Call Match (s');
 13                  End If
 14              End For each  
 15              Restoration of Data Structures; 
 16         End If
 17  End Procedure;

Proof of Correctness

The process of finding the mapping function is described by means of State Space Representation. Each set of partial mapping solution M(s) is only a subset of M with corresponding state being s. A transition from any particular state s to its successor state s', represents addition of a pair (n, m) of matched nodes to the partial graph associated to s in SSR. Only a small subset of SSR states will be consistent with the anticipated isomorphism ted category. It can easily be deducted that, in case of graph isomorphism, the consistency condition will be that, the partial graphs G₁(s) and G₂(s) associated with mapping function M(s) are isomorphic. To generate only the consistent states, this algorithm introduces a set of rules for consistency verification.

Since the algorithm uses the depth first search strategy, a state can become reachable in multiple paths. To avoid this confusion in the matching process, a special procedure for producing a node successor is used. The algorithm simply ignores any pair (n_i,m_j) from P(s) if P(s) already contains such a node because the order of node insertion in M(s) does not impact the resulting state. This makes sure that the algorithm generates unique states.

Time Complexity

The membership test of various set requires a constant time. So the computation of P(s) can be done in worst case in $|N_{1}|+|N_{2}|$ time. Calculation of F(s, n, m) can be done in time proportional to branches involving n and m. Time complexity of this algorithm is computed considering the following scenario that this algorithm, in best case visits N states and in worst case it explores N! states making the time complexity Θ$(N^{2})$ for the best case and Θ $(N!N)$ for the worst case consideration.

The memory requirement is also quite lower than other existing algorithms for graph isomorphism. The depth first strategy ensures that, there can be at most N states in a memory at a time. Since each state needs a constant amount of memory, the total memory requirement of the algorithm is Θ$(N)$ with some additional constant factor.

Comparison with Related Algorithms

A backtracking algorithm for graph isomorphism proposed by Ullmann, significantly reduces the search space size and is still one of the efficient graph isomorphism algorithm but has more time complexity than our discussed algorithm. In best case Ullmann algorithm takes Θ $(N^{3})$ time and in worst case Θ$(N!N^{2})$. Another graph isomorphism algorithm, Nauty algorithm, transforms the whole graph into canonical form before checking for isomorphism. Though being efficient, there is couple of cases where this algorithm takes exponential running time whereas our discussed deterministic matching method takes much less computational time and less memory.

Applications

This graph isomorphism algorithm has its important implication in pattern analysis and recognition. It is used in finding defect in texture, dividing the texture into several pieces and then apply the algorithm on individual pieces. This is also applied in automated circuit design for the verification of equivalence circuits. In organic chemistry, this algorithm can be applied for detecting whether two molecules are identical. Other applications include: language pattern matching, parsing applications etc.

See also

• Graph isomorphism
• Graph homomorphism
• Graph traversal
• Graph (data structure)
• Graph automorphism problem
• Graph canonization
• Topological ordering

Notes

• A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison Wesley, 1974.

• L.P. Cordella, P. Foggia, C. Sansone, and M. Vento, “Subgraph Transformations for the Inexact Matching of Attributed Relational Graphs,” Computing, vol. 12, pp. 43-52, 1998.

References

Category:Graph theory Category:Graph algorithms