Can someone explain the steps of the VF2 algorithm for graph isomorphism in simple words? I am learning this algorithm, but it is harsh without a working example. Can someone lead me the right direction? Thank you.
I will try to give you a quick explaination of my previous answer to this question :
Any working example of VF2 algorithm?
I will use the same example as the one in my previous answer :

The 2 graphs above are V and V' .(V' is not in the drawing but it's the one on the right)
The VF2 algorithm is described in the graph.
Step by step
I want to know if V and V' are isomorphic.
I will use the following notations : XV is the node X in V
In the VF2 algorithm I will try to match each node in V with a node in V'.
step 1 :
I match empty V with empty V' : it always works
step 2 : I can match 1V with 1V',2V' or 3V'
I match 1V with 1V' : it always works
step 3 :
I can match 2V with 2V' or 3V'
I match 2V with 2V' : it works because {1V 2V} and {1V' 2V} are isomorphic
step 4 :
I try to match 3V with a node in V' : I cannot! {it would be possible if there were an edge between node 3 and 2 in V', and no edge between 3 and 1)
So I go back to step 2
step 5:
I match 2V with 3V'
step 6:
same as step 4
I go back to step 2. there is no solution in step 2 , I go back to step 1
step 7:
I match 1V with 2V'
step 8:
I match 2V with 1V'
step 9 :
I match 3V with 3V'
it works I matched {1V 2V 3V} with { 2V' 1V' 3V'}
The graphs are isomorphic.
If I test all the solution and it never works the graph would not be isomorphic.
Hope this helps
About your question on "matching", have a look at the wikipedia article on graph isomorphism :
http://en.wikipedia.org/wiki/Graph_isomorphism
this is a good example of a function f that matches graph G and H :

Hope you can better understand this algorithm with this illustration.
-
Thanks for your explanation but i don't understand the meaning of matching like in step 2 you have written that "I match 1V witch 1V' : it always works" how 1V can be successfully matched with 1V' as both of them have different degree. Can you please tell me further about the exact meaning of matching the nodes. I mean what are the conditions that should satisfy so that we can say that the node in graph one is successfully matched with some node in graph 2. Nov 18 2011 at 21:42
-
Can you tell me how you are matching a node with other i mean what is the meaning of matching or if any one else can explain that point. Nov 19 2011 at 18:47
-
@AbdulSamad matching is like chosing a function f:G=(V,E)->G'=(V',E') such that for any point in node or edge in G return new node and edge in G' . I will try to clarify that for you if it's not clear later today when I have time Nov 20 2011 at 14:04
-
@AbdulSamad I edited my post to give an illustration of what is meant by matching . If you have anymore question don't hesitate to ask. Nov 20 2011 at 20:22
-
1@RickyBobby "I match 2V with 2V' : it works because {1V 2V} and {1V' 2V} are isomorphic" were you meaning to say {1V 2V} and {1V' 2V'} are isomorphic? Because {1V' 2V} are not even in the same graph so there is no edge between them.– ZyooOct 14 2014 at 17:13
high-level overview of the VF algorithm is presented:
PROCEDURE Match(s)
INPUT: an intermediate state s; the initial state s0 has M(s0)=
OUTPUT: the mappings between the two graphs
IF M(s) covers all the nodes of G2 THEN
OUTPUT M(s)
ELSE
Compute the set P(s) of the pairs candidate for inclusion in M(s)
FOREACH (n, m) P(s)
IF F(s, n, m) THEN
Compute the state s´ obtained by adding (n, m) to M(s)
CALL Match(s )
END IF
END FOREACH
Restore data structures
END IF
END PROCEDURE