3

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

2 Answers 2

2

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?

4
  • Thank you for your comment. I only want to identify whether B is a subgraph of A (the vertices are indistinguishable) whilst taking the colour into account. I know that igraph isn't overwriting the second edge --- when I print the graph it shows it correctly, with lines of both colours. But I don't know whether there is a problem with the subisomorphism code. I'm not sure colour is very important here actually --- my problem is that in graph A the 0'th vertex connects to vertices 1 and 2 so it cannot have a two-vertex graph as a subisomorphism.
    – djangology
    Jun 20, 2014 at 17:55
  • You're welcome! Did you try adding edge_color1 and edge_color2 per the api params?
    – Korbonits
    Jun 20, 2014 at 17:58
  • Sorry I think colour is irrelevant to the discussion. I tried get_subisomorphisms_vf2( other=b, edge_color1=a.es["color"], edge_color2 = b.es["color"], edge_compat_fn=func) but I get the same results.
    – djangology
    Jun 20, 2014 at 18:04
  • 2
    This is the right answer, igraph ignores multiple edges when calculating subgraph isomorphisms. Jun 21, 2014 at 20:36
0

Thanks everybody for your input. It seems that igraph ignore multiple edges but a workaround is described here http://lists.nongnu.org/archive/html/igraph-help/2013-08/msg00038.html .

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.