On 08/23/2013 11:08 PM, Tamás Nepusz
wrote:
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'] )
Thank you, Tamas. it's so kind of you answering me so many
questions.but still I found some problems. the color1 and color2 arguments work fine, however 'edge_color' seems not working at all. you can use the 'return_mapping_12=True' argument in isomorphic_vf2() to check these 2 graphs,
using g1.isomorphic_vf2( g2, ... ... , return_mapping_12=True ), we'll get this result: (True,[3,2,1],None), because their in and out degrees match. but the edge multiplicities do not match at all. that means edge_color1 and edge_color2 options are ignored for some unknown reason( is that possible to be a bug? ).
but I somehow figured another way to distinguish those 2 graphs:
-----------------------------------
def is_isomorphic( g1, g2 ) :
g1.vs['mult'] = 0
edges = g1.get_edgelist()
sources = [ i for i, j in edges if i == j ] # find self-loops
g1.vs[sources]['mult'] = [ edges.count((p,p)) for p in sources ]
g2.vs['mult'] = 0
edges = g2.get_edgelist()
sources = [ i for i, j in edges if i == j ]
g2.vs[sources]['mult'] = [ edges.count((p,p)) for p in sources ]
return g1.isomorphic_vf2( g2, color1=g1.vs['mult'], color2=g2.vs['mult'] )
-----------------------------------
the key is that I do not remove multi-edges and self-loops so that degrees of vertices won't change. and this time this function gives the correct result for the 2 graphs above. but still, there are exceptions:
these 2 graphs are not isomorphic, but "is_isomorphic()" defined above gives 'True' because it cannot distinguish those multi-edges due to the malfunctioning of the 'edge_color' options.
I have tried Mathematica-combinatorica` package and the NetworkX, and they both have full support for multi-graph calculation. unfortunately, they are just too slow. now I'm doing a project on finding all possible connected non-isomorphic vertex-conservational(in-degree==out-degree) MultiDiGraphs for given number of vertices and edges. I may face tens of billions of graphs, so igraph is my only choice and hope. I'm wondering why it doesn't have native support for multigraphs.
Anyway, thank you very much, and sorry for bothering you again and again.
--
周达，Day Zhou
Interdisciplinary Center for Theoretical Study (ICTS)
University of Science and Technology of China (USTC)