igraph-help
[Top][All Lists]

## Re: [igraph] an igraph isomorphism problem

 From: Tamás Nepusz Subject: Re: [igraph] an igraph isomorphism problem Date: Fri, 23 Aug 2013 17:08:46 +0200

```> the simplify() function indeed distinguishes a lot of different graphs. but
> it seems the edge_color argument does not work as expected. see this example:
Ah, hang on, the problem is not with the edge_color1 argument but the fact that
I passed loops=False to simplify(), which keeps the loop edges -- but the
isomorphism functions do not handle these either. This can probably be resolved
with using vertex colors as well as edge colors, where the idea is that a
vertex with a loop edge of multiplicity k will get color #k and then we allow a
vertex to match only those vertices from the other graph that has the same
color. So:

def prepare_graph(graph):
graph.es["multiplicity"] = 1
graph.vs["multiplicity"] = 0
graph.simplify(multiple=True, loops=False, combine_edges="sum")
loop_edges = [edge.index for edge in graph.es if edge.source == edge.target]
sources = [edge.source for edge in graph.es if edge.source == edge.target]
graph.vs[sources]["multiplicity"] = graph.es[loop_edges]["multiplicity"]
graph.es[loop_edges].delete()

g = igraph.Graph( [ (0,1), (1,0), (0,0), (0,0), (0,0), (1,1) ], directed=True )
g1 = igraph.Graph( [ (0,1), (1,0), (0,1), (1,0), (0,0), (1,1) ], directed=True )
prepare_graph(g)
prepare_graph(g1)
print g.isomorphic_vf2( g1, color1=g.vs['multiplicity'],
color2=g1.vs['multiplicity'], edge_color1=g.es['multiplicity'],
edge_color2=g1.es['multiplicity'] )

--
T.

```