# -*- coding: utf-8 -*-
"""
Connected components.
"""
__authors__ = "\n".join(['Eben Kenah',
'Aric Hagberg (hagberg@lanl.gov)'
'Christopher Ellison'])
# Copyright (C) 2004-2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__ = ['number_connected_components',
'connected_components',
'connected_component_subgraphs',
'is_connected',
'node_connected_component',
]
import networkx as nx
def connected_components(G):
"""Return nodes in connected components of graph.
Parameters
----------
G : NetworkX Graph
An undirected graph.
Returns
-------
comp : list of lists
A list of nodes for each component of G.
See Also
--------
strongly_connected_components
Notes
-----
The list is ordered from largest connected component to smallest.
For undirected graphs only.
"""
if G.is_directed():
raise nx.NetworkXError,\
"""Not allowed for directed graph G.
Use UG=G.to_undirected() to create an undirected graph."""
seen={}
components=[]
for v in G:
if v not in seen:
c=nx.single_source_shortest_path_length(G,v)
components.append(c.keys())
seen.update(c)
components.sort(key=len,reverse=True)
return components
def number_connected_components(G):
"""Return number of connected components in graph.
Parameters
----------
G : NetworkX Graph
An undirected graph.
Returns
-------
n : integer
Number of connected components
See Also
--------
connected_components
Notes
-----
For undirected graphs only.
"""
return len(connected_components(G))
def is_connected(G):
"""Test graph connectivity
Parameters
----------
G : NetworkX Graph
An undirected graph.
Returns
-------
connected : bool
True if the graph is connected, false otherwise.
Examples
--------
>>> G=nx.path_graph(4)
>>> print nx.is_connected(G)
True
See Also
--------
connected_components
Notes
-----
For undirected graphs only.
"""
if G.is_directed():
raise nx.NetworkXError(\
"""Not allowed for directed graph G.
Use UG=G.to_undirected() to create an undirected graph.""")
if len(G)==0:
raise nx.NetworkXPointlessConcept(
"""Connectivity is undefined for the null graph.""")
return len(nx.single_source_shortest_path_length(G,
G.nodes_iter().next()))==len(G)
def connected_component_subgraphs(G):
"""Return connected components as subgraphs.
Parameters
----------
G : NetworkX Graph
An undirected graph.
Returns
-------
glist : list
A list of graphs, one for each connected component of G.
Examples
--------
Get largest connected component as subgraph
>>> G=nx.path_graph(4)
>>> G.add_edge(5,6)
>>> H=nx.connected_component_subgraphs(G)[0]
See Also
--------
connected_components
Notes
-----
The list is ordered from largest connected component to smallest.
For undirected graphs only.
"""
cc=connected_components(G)
graph_list=[]
for c in cc:
graph_list.append(G.subgraph(c))
return graph_list
def node_connected_component(G,n):
"""Return nodes in connected components of graph containing node n.
Parameters
----------
G : NetworkX Graph
An undirected graph.
n : node label
A node in G
Returns
-------
comp : lists
A list of nodes in component of G containing node n.
See Also
--------
connected_components
Notes
-----
For undirected graphs only.
"""
if G.is_directed():
raise nx.NetworkXError,\
"""Not allowed for directed graph G.
Use UG=G.to_undirected() to create an undirected graph."""
return nx.single_source_shortest_path_length(G,n).keys()
|