[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"]
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.
- [igraph] an igraph isomorphism problem, zhouda, 2013/08/21
- Re: [igraph] an igraph isomorphism problem, Gábor Csárdi, 2013/08/21
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/21
- Re: [igraph] an igraph isomorphism problem, Tamás Nepusz, 2013/08/22
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/23
- Re: [igraph] an igraph isomorphism problem,
Tamás Nepusz <=
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/24
- Re: [igraph] an igraph isomorphism problem, Tamás Nepusz, 2013/08/24
- Re: [igraph] an igraph isomorphism problem, zhouda, 2013/08/25