/usr/lib/python2.7/dist-packages/networkx/algorithms/components/connected.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 | # -*- 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())
|