| # -*- 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(list(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, |
| next(G.nodes_iter())))==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. |
| |
| Graph, node, and edge attributes are copied to the subgraphs. |
| """ |
| cc=connected_components(G) |
| graph_list=[] |
| for c in cc: |
| graph_list.append(G.subgraph(c).copy()) |
| 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 list(nx.single_source_shortest_path_length(G,n).keys()) |
| |
| |
