Check when a graph is a subgraph of another graph in igraph

1
votes

I want to check whether a given subgraph G is the subgraph of another larger graph G' using igraph. Please notd this is not a subgraph isomorphism problem since I want the answer to be False if the labelling of any of the vertices or edges is different. I want the answer to be True if and only if both graphs have the same edge and vertex labels and G is a subgraph of G'. How do I accomplish this in igraph? Thanks.

1
graphigraph
this may be same as checking whether the automorphism group of one graph is a subgroup of another graph's automorphism group – vidyarthi

1 Answers

1
votes

Not sure what you mean by vertex/edge labels, but note that the VF2 subisomorphism algorithm in igraph supports vertex/edge colors; two vertices or edges are allowed to match iff their colors are the same. If you are using igraph from Python, check the subisomorphic_vf2 method of the Graph class. If you are using igraph from R, check the graph.subisomorphic.vf2 function. Both of these are backed by the igraph_subisomorphic_vf2 function in the C layer.

Update: since you have strings as labels and not integers (which the VF2 isomorphism algorithm would expect), you have to convert them to integer indices first. Otherwise, VF2 should be able to do what you need. An example in the Python interface of igraph:

>>> g = Graph.Formula("A --> B --> C")
>>> g2 = Graph.Formula("A --> B")
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,1])
[[0, 1]]
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,2])
[]