
From:  zhouda 
Subject:  Re: [igraph] an igraph isomorphism problem 
Date:  Sat, 24 Aug 2013 21:43:16 +0800 
Useragent:  Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130803 Thunderbird/17.0.8 
On 08/23/2013 11:08 PM, Tamás Nepusz
wrote:
Thank you, Tamas. it's so kind of you answering me so many questions.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'] ) 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 selfloops 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 multiedges and selfloops 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 multiedges due to the malfunctioning of the 'edge_color' options. I have tried Mathematicacombinatorica` package and the NetworkX, and they both have full support for multigraph calculation. unfortunately, they are just too slow. now I'm doing a project on finding all possible connected nonisomorphic vertexconservational(indegree==outdegree) 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) 
[Prev in Thread]  Current Thread  [Next in Thread] 