[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Maximum Common Subgraph
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Maximum Common Subgraph |
Date: |
Fri, 11 Mar 2011 20:18:01 +0100 |
Hi,
> Thanks for your reply. Given the following example and the following
> background info
> http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
>
> g1 = Graph.Formula("A--B, A--E")
> g2 = Graph.Formula("A--B, A--C")
>
> Shouldn't the sub isomorphism problem return "A--B".
Well, the maximum common subgraph isomorphism problem should, but this is not
what is implemented in igraph_subisomorphic_vf2. The subgraph isomorphism
problem is as follows:
"In theoretical computer science, the subgraph isomorphism problem is a
computational task in which two graphs G and H are given as input, and one must
determine whether G contains a subgraph that is isomorphic to H."
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
> The current code base seems to require that the whole graph g2 matches some
> subgraph g1. Is this the intended behavior?
Yes, it is.
> Is there a way to enumerate all possible subgraphs from a given graph?
Yes, there is, but you would have to write some code yourself; basically, you
have to iterate over the powerset of the vertices and construct a subgraph for
each element of the powerset. (Well, you may skip the empty graph or subgraphs
with one vertex only as they are not really of any interest to you I guess).
Basically the solution is something along the lines of:
from itertools import powerset
def all_subgraphs(graph):
for vertices in powerset(range(graph.vcount()):
yield graph.subgraph(vertices)
Cheers,
--
Tamas
- Re: [igraph] Maximum Common Subgraph, (continued)
- Re: [igraph] Maximum Common Subgraph, Mark Galea, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Tamas Nepusz, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Mark Galea, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Tamas Nepusz, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Mark Galea, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Tamas Nepusz, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Mark Galea, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Mark Galea, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Tamas Nepusz, 2011/03/11
- Re: [igraph] Maximum Common Subgraph, Mark Galea, 2011/03/11
- Re: [igraph] Maximum Common Subgraph,
Tamás Nepusz <=
- Re: [igraph] Maximum Common Subgraph, Mark Galea, 2011/03/11