[Top][All Lists]

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

Re: [igraph] an igraph isomorphism problem

From: zhouda
Subject: Re: [igraph] an igraph isomorphism problem
Date: Fri, 23 Aug 2013 12:28:45 +0800
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130803 Thunderbird/17.0.8

On 08/22/2013 04:25 PM, Tamás Nepusz wrote:
Thank you very much. 
but does that mean igraph cannot handle multigraph isomorphism?
It can, with a trick. You have to collapse multiple edges into a single edge and assign the original edge count to the new edge as an edge attribute. Then you can use the edge_color1 and edge_color2 arguments of isomorphic_vf2 to disallow matching an edge to another with a different multiplicity. E.g.:

# Construct the graphs
g1 = igraph.Graph([(0,1),(1,0),(0,0),(1,1)], directed=True)
g2 = igraph.Graph([(0,1),(1,0),(0,1),(1,0)], directed=True)

# Declare that each edge in the graph has a multiplicity of 1 (because we still have multiple edges)
g1.es["multiplicity"] = 1
g2.es["multiplicity"] = 1

# Collapse the multiple edges into a single one and sum the multiplicities
g1.simplify(multiple=True, loops=False, combine_edges="sum")
g2.simplify(multiple=True, loops=False, combine_edges="sum")

# Now check whether they are isomorphic, considering the multiplicities
print g1.isomorphic_vf2(g2, edge_color1=g1.es["multiplicity"], edge_color2=g2.es["multiplicity"])

Thank you, that really helped a lot!
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:
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 )

g.es['multiplicity'] = 1
g1.es['multiplicity'] = 1

g.simplify(multiple=True, loops=False, combine_edges='sum' )
g1.simplify(multiple=True, loops=False, combine_edges='sum' )

print g.isomorphic_vf2( g1, edge_color1=g.es['multiplicity'], edge_color2=g1.es['multiplicity'] )
the result is still True, but should be False. Here's the graphs:
graph 1
graph 2


周达,Day Zhou

Interdisciplinary Center for Theoretical Study (ICTS)

University of Science and Technology of China (USTC)

reply via email to

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