Home Original page

ANNOUNCE PySomorph - a subgraph and graph isomorphism library

Brian Kelley bkelley at wi.mit.edu
Wed Oct 17 18:04:36 EDT 2001 
vf graph isomorphism library 0.9

You can download this package from
http://staffa.wi.mit.edu/people/kelley/

This is a python binding to the VF graph isomorphism library available
from http://amalfi.dis.unina.it/

There are three kinds of graph isomorphism performed

1 Graph Isomorphism
  - are two graphs G and H identical

2 SubGraph Isomorphism
  - is a graph G contained in a graph H maintaining edge
    counts.

    This means that matched nodes must have the same
    number of edges, for example the following two
    graphs will not match
    
        G         H
     a     c   a'----c'
      \   /     \   /
       \ /       \ /
        b         b'

    since a and a' do not have the same number of edges.

3 Subgraph Monomorphism
 - is a graph G contained in a graph H without maintaining
   edge counts

   This means that graph G matches graph H


There are three basic implementations:

Ullman - the granddaddy of graph ismorphisms, there are two variations
         of this matcher

 matchUll - graph isomorphism
 matchUllSub - subgraph isomophism


VF - The VF algorithm
 matchVF - graph isomorphism
 matchVFSub - subgraph isomorphism
 matchVFMono - monomorphism

VF2 - The VF2 algorithsm
 matchVF2 - graph isomorphism
 matchVF2Sub - subgraph isomorphism
 matchVF2Mono - monomorphism

For a better description of the algorithm see the docs directory under
vflib-2.0.

Basic usage:

I Creating a graph

 Graphs are created using vflib.ARGEdit()

 ARGEdit has two functions
  ARGEdit.InsertNode(object) -> returns the inserted node index
  ARGEdit.InsertEdge(index1, index2, object)

 Nodes and edges are typed.  In both cases "object" must support
 equivalence replationships.  You can use None for untyped graphs.

 Nodes and edges can be arbitrary python objects so the equivalence
 relationships can be quite complex.

II making a matching object

 A matching object is created using vflib.GraphMatcher(graph)
   where graph is an ARGEdit object.

 matcher = vflib.GraphMatcher(graph)

 a GraphMatcher object has match functions that support the
 following interface

  matcher.match(graph, maxcount)
 
 maxcount is a limit on how many matches to search.  For example

 matcher.match(graph, -1) -> returns all matches
 matcher.match(graph, 1) -> returns only the first match
 
 a matching object supports the following matches (see above for
  descriptions):

  matcher.matchVF(graph, maxcount)
  matcher.matchVFSub(graph, maxcount)
  matcher.matchVFMono(graph, maxcount)
 
  matcher.matchVF2(graph, maxcount)
  matcher.matchVF2Sub(graph, maxcount)
  matcher.matchVF2Mono(graph, maxcount)

  matcher.matchUll(graph, maxcount)
  matcher.matchUllSub(graph, maxcount)

 each matching function returns a list of matches in the following
 form.

 [ ( nodes1, edges1 ), ( nodes2, edges2 ) ... ]

 the nodes and edges returned are nodes and edges of the
 target graph that are isomorphic matches of the matcher graph.
 The nodes are mapped in order of the nodes and
 edges of the matcher graph.
 
 For example:
  G = vflib.ARGEdit()
  G.InsertNode(1)
  G.InsertNode(2)
  G.InsertEdge(0,1, "first edge")

  H = vflib.ARGEdit()
  H.InsertNode(2)
  H.InsertNode(1)
  H.InsertEdge(1,0, "first edge")

  matcher = vflib.GraphMatcher(G)
  print matcher.matchVF(H, -1)
  -> [((1, 2), ('first edge',))]

 Confused?  Let's be more explicit.  I'll create an object that
 can tell exactly what node it is and still match the integers.

 class Wrapper:
  def __init__(self, data, nodeid):
   self.data = data
   self.nodeid = nodeid

  def __eq__(self, other):
   return self.data == other.data

  def __repr__(self):
   return "Wrapper(data=%s,nodeid=%s)"%(self.data,self.nodeid)


  G = vflib.ARGEdit()
  G.InsertNode(Wrapper(1, nodeid=0))
  G.InsertNode(Wrapper(2, nodeid=1))
  G.InsertEdge(0,1, "first edge")

  H = vflib.ARGEdit()
  H.InsertNode(Wrapper(2, nodeid=2))
  H.InsertNode(Wrapper(1, nodeid=1))
  H.InsertEdge(1,0, "first edge")

  matcher = vflib.GraphMatcher(G)
  print matcher.matchVF(H, -1)
  -> [((Wrapper(1,1), Wrapper(2,2)), ('first edge',))]

 Now we can see that the order of the matches is indeed the
 order of the matching graph G.  We can also see the power
 of using python objects to form the graph!
 
 This code is located in test_objects.py

 For a good example of how to make graphs and compare them, see
 test_vf.py which performs a check on the monoisomorphic
 routines.

NOTES:

There can only be two edges between any two nodes a and b.
The edge from a to b and the edge from b to a.

KNOWN BUGS:

1. Apparently the GraphMatcher class is kind of picky if the underlying
   graph goes away and is reference collected.

 G = vflib.ARGEdit()
 matcher = vflib.GraphMatcher(G)
 del graph

 matcher.matchVF(H)

 will fail with something like:
  Traceback (most recent call last):

    File "<stdin>", line ?, in ?

  RuntimeError: unidentifiable C++ exception


 The fix for this problem is known and will be updated in the next
 version.  Fortunately the program will not crash at this point.

2.  Error reporting is a little screwy
   >>> import vflib
   >>> G = vflib.ARGEdit()
   >>> G.InsertNode(1)
   0
   >>> G.InsertNode(2)
   1
   >>> G.InsertEdge("hello", "there", None)
   Traceback (most recent call last):
     File "<stdin>", line 1, in ?
   TypeError: an integer is required

  It doesn't really tell you where an integer is required...

3. No linux port yet...
More information about the Python-list mailing list