ANNOUNCE PySomorph - a subgraph and graph isomorphism library
Brian Kelley
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...