I'm a bit stuck with my graph problem and, not being an expert on the subject, I thought I'd turn to the internet for help. I have two graphs A and B and I want to check whether B is a subgraph of A. I tried to do this with igraph but it seems to be claiming that B is a subgraph of A, even when it is not. Here is an example that illustrates this:
from igraph import *
def func(g1, g2, e1, e2):
if g1.es[e1]["color"] == g2.es[e2]["color"]:
return True
else:
return False
a = Graph(4, directed=True)
a.add_edge(0,1,color=1)
a.add_edge(1,2,color=1)
a.add_edge(2,3,color=1)
a.add_edge(0,2,color=2)
a.add_edge(2,0,color=2)
a.add_edge(1,3,color=2)
a.add_edge(3,1,color=2)
b = Graph(2, directed=True)
b.add_edge(0,1,color=1)
b.add_edge(0,1,color=2)
b.add_edge(1,0,color=2)
t = a.get_subisomorphisms_vf2( other=b, edge_compat_fn=func)
print t
The program prints "[[0, 2], [1, 3]]"
I would think that B is not a subisomorphism of A because the color=1 line from vertex 0 does not connect to vertex 2 but igraph seems to ignore this. Am I doing something wrong or is this a bug in igraph? I'm using python-igraph 0.6.5 with Python 2.6.5
Edit: I think that color can be ignored here. My problem is that in graph A there is a link from the 0th vertex to the 1st vertex so B is not a subgraph because that would require that (in graph A) the 0'th vertex connects directly to the 2nd vertex.
Edit2: I suspect what I really want is a "induced subgraph isomorphism".