[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**: |
Thu, 22 Aug 2013 10:25:52 +0200 |

>* 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"])
--
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* **<=**
**Re: [igraph] an igraph isomorphism problem**, *zhouda*, `2013/08/23`
**Re: [igraph] an igraph isomorphism problem**, *Tamás Nepusz*, `2013/08/23`
**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`