[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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 )
print g.isomorphic_vf2( g1, color1=g.vs['multiplicity'], 
color2=g1.vs['multiplicity'], edge_color1=g.es['multiplicity'], 
edge_color2=g1.es['multiplicity'] )


reply via email to

[Prev in Thread] Current Thread [Next in Thread]