[pygraphviz-discuss] Topology Comparison

[Guilhem Faure]

Hello everyone,

I have 2 questions and I do not know if there exists a solution with (py)Graphviz.
I know that (py)Graphviz is for Graph Visualisation but I would like to know if some functions to analyse graph are implemented inside.

I built a dynamical graph and first I need to know how many subgraph I have.

i.e : 
import pygraphviz as p
G = p.AGraph()
G.add_edge("A","B")
G.add_edge("B","C")
G.add_edge("H","E")
G.add_edge("E","Y")
G.add_edge("Y","I")

I obtain : 
A-B-C
H-E-Y-I

In this case I have 2 subgraphs. Is there a solution to find that quickly with (py)Graphviz ? Is it possible to get from G the subgraph A-B-C and H-E-Y-I ? I precise that I do not know which will be subgraph when I build the graph so I can't use the subgraph function when I build G.

My other question is about the topology comparison of these subgraph. Is (py)Graphviz able to that ?

if not, can you advice me a perfomant library to that ?

Thank you very much for your help,

Guilhem

[Aric Hagberg]

I think you are looking for connected components.
NetworkX has algorithms for that:

In [20]: import networkx as nx

In [21]: G=nx.Graph()

In [22]: G.add_edge("A","B")

In [23]: G.add_edge("B","C")

In [24]: G.add_edge("H","E")

In [25]: G.add_edge("E","Y")

In [26]: G.add_edge("Y","I")

In [27]: nx.connected_components(G)
Out[27]: [['Y', 'H', 'E', 'I'], ['A', 'C', 'B']]

There is an isomorphism checker:

In [28]: N1,N2=nx.connected_component_subgraphs(G)

In [29]: nx.is_isomorphic(N1,N2)
Out[29]: False

Aric

[Guilhem Faure]

Hello Aric,

Thank you very much for your explanation. It works perfectly well! I'll use Networkx for graph algorithms from now on.

Guilhem