Re: [igraph] an igraph isomorphism problem

[Tamás Nepusz]

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