Search code examples
algorithmlanguage-agnosticgraphgraph-theory

Any working example of VF2 algorithm?

I have been reading the VF2 algorithm for finding if two graphs are isomorphic but am somehow missing the big picture. Could be that I am missing the relevant background in this area but all I see is a bunch of rules that I need to use at each step, without seeing an intuitive explanation for why the steps are being carried out.

From basic Googling, it appears that this is considered one of the de facto algorithms for finding if two graphs are isomorphic but for some reason I am unable to find an explanation that is simple enough to understand at a high level. Or is this algorithm known by a different name?

In any case, is anyone aware of any running examples of how this algorithm works?

Solution

  • I am not sure that's what you're looking for, but the VF2 algorithm proceeds as below.

    Let's say you have 2 graphs: V and V' and you want to match V with V'

    The algorithm goes down a tree, at each step you try to match a next element of V with one of V' and you stop when you went through all the nodes in V' (when you find a leaf).

    Algorithm:

    • First step : match empty V with empty graph V'.
    • Second step : try to match one node in V with one node in V'
    • ...
    • Nth step : try to match one node in V with one new node in V', if you cannot go back one step in the tree and try a new match in the previous step.. and if you cant go back again etc...
    • ...
    • END : when you find a leaf, i.e when you went through all the nodes in V' or when you went through the whole tree without finding a leaf.

    Example

    Here is a example, the algorithm proceeds from left to right of the tree.

    "A <-> B" means Match node A of V with node B of V'

    enter image description here

    Hope I'm clear and that's what your looking for.