igraph misidentifying subisomorphism?

Question

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".

Korbonits Korbonits · Accepted Answer · 2014-06-20T17:40:59

Recall the definition of a subgraph:

A graph G' whose graph vertices and graph edges form subsets of the graph vertices and graph edges of a given graph G.

What appears to be happening here is that your directed multigraph is not being recognized with igraph (I don't know igraph well-enough to know whether directed multigraphs are supported). It appears that your second edge on graph B from (0,1, color=2) is just a reassigned color from (0,1, color=1).

igraph api - get_subisomorphisms_vf2

If this is true, then your output t makes total sense. Those are two subgraph isomorphisms indeed. Isomorphism here doesn't respect edge colorings unless you do so explicitly. If you want it to, you'll have to update your code to add edge_color1 and edge_color2 when you call get_subisomorphisms_vf2.

What are your requirements? What problem(s) are you trying to solve?

igraph misidentifying subisomorphism?

2 Answers