[networkx] Search a topology subgraph in a graph

[Guilhem Faure]

Hello,

I would like to search in a graph whether there is another graph inside for instance :
A = 1-2-3-4 (Graph 1)
B = 2-3-4 (Graph 2)

2-3-4 are the same.

I've already tried with isomorphic and GraphMatcher but I think that are not the appropriate functions.

Thank for you help,

Guilhem

[Aric Hagberg]

This works in NetworkX like this:

import networkx as nx

G1 = nx.Graph()
G1.add_edge(1,2)
G1.add_edge(2,3)

G2 = nx.Graph()
G2.add_edge(1,2)

M=nx.GraphMatcher(G1,G2)

print M.subgraph_is_isomorphic()

Aric

[Guilhem Faure]

Thank you very much for your answer it works.
And is there a solution to extract the isomorph subgraph in a graph object ?

Guilhem

--

You received this message because you are subscribed to the Google Groups "pygraphviz-discuss" group.
To post to this group, send email to pygraphvi...@googlegroups.com.
To unsubscribe from this group, send email to pygraphviz-disc...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pygraphviz-discuss?hl=en.

[Aric Hagberg]

On Fri, Dec 4, 2009 at 1:59 AM, Guilhem Faure <guilhe...@gmail.com> wrote:
> Thank you very much for your answer it works.
> And is there a solution to extract the isomorph subgraph in a graph object ?

I'm not sure exactly what you mean. Take a look at the subgraph()
method for Graph.

Aric

[Guilhem Faure]

If M.subgraph_is_isomorphic() is True it is possible to get the subgraph easely ?

G1 = nx.Graph()
G1.add_edge(1,2)
G1.add_edge(2,3)

G2 = nx.Graph()
G2.add_edge(1,2)

I want to have -> the common graph(s) is (1,2)
Is it possible easely without a comparison of each edge ?

Thank for your help,
Guilhem

Aric

[Aric Hagberg]

On Fri, Dec 4, 2009 at 8:41 AM, Guilhem Faure <guilhe...@gmail.com> wrote:
> If M.subgraph_is_isomorphic() is True it is possible to get the subgraph
> easely ?
> G1 = nx.Graph()
> G1.add_edge(1,2)
> G1.add_edge(2,3)
>
> G2 = nx.Graph()
> G2.add_edge(1,2)
>
> I want to have -> the common graph(s) is (1,2)
> Is it possible easely without a comparison of each edge ?
>

Well, don't you already have the subgraph?

In [8]: G2.edges()
Out[8]: [(1, 2)]

But if you want the subgraph from G1 you can

In [9]: H=G1.subgraph([1,2])

In [10]: H.edges()
Out[10]: [(1, 2)]

Aric