ioftools / networkxMiCe / networkxmaster / networkx / algorithms / minors.py @ 5cef0f13
History  View  Annotate  Download (17.2 KB)
1 
# minors.py  functions for computing minors of graphs


2 
#

3 
# Copyright 2015 Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>.

4 
# Copyright 2010 Drew Conway <drew.conway@nyu.edu>

5 
# Copyright 2010 Aric Hagberg <hagberg@lanl.gov>

6 
#

7 
# This file is part of NetworkX.

8 
#

9 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

10 
# information.

11 
"""Provides functions for computing minors of a graph."""

12 
from itertools import chain 
13 
from itertools import combinations 
14 
from itertools import permutations 
15 
from itertools import product 
16  
17 
import networkx as nx 
18 
from networkx import density 
19 
from networkx.exception import NetworkXException 
20 
from networkx.utils import arbitrary_element 
21  
22 
__all__ = ['contracted_edge', 'contracted_nodes', 
23 
'identified_nodes', 'quotient_graph'] 
24  
25 
chaini = chain.from_iterable 
26  
27  
28 
def equivalence_classes(iterable, relation): 
29 
"""Returns the set of equivalence classes of the given `iterable` under

30 
the specified equivalence relation.

31 

32 
`relation` must be a Booleanvalued function that takes two argument. It

33 
must represent an equivalence relation (that is, the relation induced by

34 
the function must be reflexive, symmetric, and transitive).

35 

36 
The return value is a set of sets. It is a partition of the elements of

37 
`iterable`; duplicate elements will be ignored so it makes the most sense

38 
for `iterable` to be a :class:`set`.

39 

40 
"""

41 
# For simplicity of implementation, we initialize the return value as a

42 
# list of lists, then convert it to a set of sets at the end of the

43 
# function.

44 
blocks = [] 
45 
# Determine the equivalence class for each element of the iterable.

46 
for y in iterable: 
47 
# Each element y must be in *exactly one* equivalence class.

48 
#

49 
# Each block is guaranteed to be nonempty

50 
for block in blocks: 
51 
x = arbitrary_element(block) 
52 
if relation(x, y):

53 
block.append(y) 
54 
break

55 
else:

56 
# If the element y is not part of any known equivalence class, it

57 
# must be in its own, so we create a new singleton equivalence

58 
# class for it.

59 
blocks.append([y]) 
60 
return {frozenset(block) for block in blocks} 
61  
62  
63 
def quotient_graph(G, partition, edge_relation=None, node_data=None, 
64 
edge_data=None, relabel=False, create_using=None): 
65 
"""Returns the quotient graph of `G` under the specified equivalence

66 
relation on nodes.

67 

68 
Parameters

69 


70 
G : NetworkX graph

71 
The graph for which to return the quotient graph with the

72 
specified node relation.

73 

74 
partition : function or list of sets

75 
If a function, this function must represent an equivalence

76 
relation on the nodes of `G`. It must take two arguments *u*

77 
and *v* and return True exactly when *u* and *v* are in the

78 
same equivalence class. The equivalence classes form the nodes

79 
in the returned graph.

80 

81 
If a list of sets, the list must form a valid partition of

82 
the nodes of the graph. That is, each node must be in exactly

83 
one block of the partition.

84 

85 
edge_relation : Boolean function with two arguments

86 
This function must represent an edge relation on the *blocks* of

87 
`G` in the partition induced by `node_relation`. It must

88 
take two arguments, *B* and *C*, each one a set of nodes, and

89 
return True exactly when there should be an edge joining

90 
block *B* to block *C* in the returned graph.

91 

92 
If `edge_relation` is not specified, it is assumed to be the

93 
following relation. Block *B* is related to block *C* if and

94 
only if some node in *B* is adjacent to some node in *C*,

95 
according to the edge set of `G`.

96 

97 
edge_data : function

98 
This function takes two arguments, *B* and *C*, each one a set

99 
of nodes, and must return a dictionary representing the edge

100 
data attributes to set on the edge joining *B* and *C*, should

101 
there be an edge joining *B* and *C* in the quotient graph (if

102 
no such edge occurs in the quotient graph as determined by

103 
`edge_relation`, then the output of this function is ignored).

104 

105 
If the quotient graph would be a multigraph, this function is

106 
not applied, since the edge data from each edge in the graph

107 
`G` appears in the edges of the quotient graph.

108 

109 
node_data : function

110 
This function takes one argument, *B*, a set of nodes in `G`,

111 
and must return a dictionary representing the node data

112 
attributes to set on the node representing *B* in the quotient graph.

113 
If None, the following node attributes will be set:

114 

115 
* 'graph', the subgraph of the graph `G` that this block

116 
represents,

117 
* 'nnodes', the number of nodes in this block,

118 
* 'nedges', the number of edges within this block,

119 
* 'density', the density of the subgraph of `G` that this

120 
block represents.

121 

122 
relabel : bool

123 
If True, relabel the nodes of the quotient graph to be

124 
nonnegative integers. Otherwise, the nodes are identified with

125 
:class:`frozenset` instances representing the blocks given in

126 
`partition`.

127 

128 
create_using : NetworkX graph constructor, optional (default=nx.Graph)

129 
Graph type to create. If graph instance, then cleared before populated.

130 

131 
Returns

132 


133 
NetworkX graph

134 
The quotient graph of `G` under the equivalence relation

135 
specified by `partition`. If the partition were given as a

136 
list of :class:`set` instances and `relabel` is False,

137 
each node will be a :class:`frozenset` corresponding to the same

138 
:class:`set`.

139 

140 
Raises

141 


142 
NetworkXException

143 
If the given partition is not a valid partition of the nodes of

144 
`G`.

145 

146 
Examples

147 


148 
The quotient graph of the complete bipartite graph under the "same

149 
neighbors" equivalence relation is `K_2`. Under this relation, two nodes

150 
are equivalent if they are not adjacent but have the same neighbor set::

151 

152 
>>> import networkx as nx

153 
>>> G = nx.complete_bipartite_graph(2, 3)

154 
>>> same_neighbors = lambda u, v: (u not in G[v] and v not in G[u]

155 
... and G[u] == G[v])

156 
>>> Q = nx.quotient_graph(G, same_neighbors)

157 
>>> K2 = nx.complete_graph(2)

158 
>>> nx.is_isomorphic(Q, K2)

159 
True

160 

161 
The quotient graph of a directed graph under the "same strongly connected

162 
component" equivalence relation is the condensation of the graph (see

163 
:func:`condensation`). This example comes from the Wikipedia article

164 
*`Strongly connected component`_*::

165 

166 
>>> import networkx as nx

167 
>>> G = nx.DiGraph()

168 
>>> edges = ['ab', 'be', 'bf', 'bc', 'cg', 'cd', 'dc', 'dh', 'ea',

169 
... 'ef', 'fg', 'gf', 'hd', 'hf']

170 
>>> G.add_edges_from(tuple(x) for x in edges)

171 
>>> components = list(nx.strongly_connected_components(G))

172 
>>> sorted(sorted(component) for component in components)

173 
[['a', 'b', 'e'], ['c', 'd', 'h'], ['f', 'g']]

174 
>>>

175 
>>> C = nx.condensation(G, components)

176 
>>> component_of = C.graph['mapping']

177 
>>> same_component = lambda u, v: component_of[u] == component_of[v]

178 
>>> Q = nx.quotient_graph(G, same_component)

179 
>>> nx.is_isomorphic(C, Q)

180 
True

181 

182 
Node identification can be represented as the quotient of a graph under the

183 
equivalence relation that places the two nodes in one block and each other

184 
node in its own singleton block::

185 

186 
>>> import networkx as nx

187 
>>> K24 = nx.complete_bipartite_graph(2, 4)

188 
>>> K34 = nx.complete_bipartite_graph(3, 4)

189 
>>> C = nx.contracted_nodes(K34, 1, 2)

190 
>>> nodes = {1, 2}

191 
>>> is_contracted = lambda u, v: u in nodes and v in nodes

192 
>>> Q = nx.quotient_graph(K34, is_contracted)

193 
>>> nx.is_isomorphic(Q, C)

194 
True

195 
>>> nx.is_isomorphic(Q, K24)

196 
True

197 

198 
The blockmodeling technique described in [1]_ can be implemented as a

199 
quotient graph::

200 

201 
>>> G = nx.path_graph(6)

202 
>>> partition = [{0, 1}, {2, 3}, {4, 5}]

203 
>>> M = nx.quotient_graph(G, partition, relabel=True)

204 
>>> list(M.edges())

205 
[(0, 1), (1, 2)]

206 

207 
.. _Strongly connected component: https://en.wikipedia.org/wiki/Strongly_connected_component

208 

209 
References

210 


211 
.. [1] Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj.

212 
*Generalized Blockmodeling*.

213 
Cambridge University Press, 2004.

214 

215 
"""

216 
# If the user provided an equivalence relation as a function compute

217 
# the blocks of the partition on the nodes of G induced by the

218 
# equivalence relation.

219 
if callable(partition): 
220 
# equivalence_classes always return partition of whole G.

221 
partition = equivalence_classes(G, partition) 
222 
return _quotient_graph(G, partition, edge_relation, node_data,

223 
edge_data, relabel, create_using) 
224  
225 
# If the user provided partition as a collection of sets. Then we

226 
# need to check if partition covers all of G nodes. If the answer

227 
# is 'No' then we need to prepare suitable subgraph view.

228 
partition_nodes = set().union(*partition)

229 
if len(partition_nodes) != len(G): 
230 
G = G.subgraph(partition_nodes) 
231 
return _quotient_graph(G, partition, edge_relation, node_data,

232 
edge_data, relabel, create_using) 
233  
234  
235 
def _quotient_graph(G, partition, edge_relation=None, node_data=None, 
236 
edge_data=None, relabel=False, create_using=None): 
237 
# Each node in the graph must be in exactly one block.

238 
if any(sum(1 for b in partition if v in b) != 1 for v in G): 
239 
raise NetworkXException('each node must be in exactly one block') 
240 
if create_using is None: 
241 
H = G.__class__() 
242 
else:

243 
H = nx.empty_graph(0, create_using)

244 
# By default set some basic information about the subgraph that each block

245 
# represents on the nodes in the quotient graph.

246 
if node_data is None: 
247 
def node_data(b): 
248 
S = G.subgraph(b) 
249 
return dict(graph=S, nnodes=len(S), nedges=S.number_of_edges(), 
250 
density=density(S)) 
251 
# Each block of the partition becomes a node in the quotient graph.

252 
partition = [frozenset(b) for b in partition] 
253 
H.add_nodes_from((b, node_data(b)) for b in partition) 
254 
# By default, the edge relation is the relation defined as follows. B is

255 
# adjacent to C if a node in B is adjacent to a node in C, according to the

256 
# edge set of G.

257 
#

258 
# This is not a particularly efficient implementation of this relation:

259 
# there are O(n^2) pairs to check and each check may require O(log n) time

260 
# (to check set membership). This can certainly be parallelized.

261 
if edge_relation is None: 
262 
def edge_relation(b, c): 
263 
return any(v in G[u] for u, v in product(b, c)) 
264 
# By default, sum the weights of the edges joining pairs of nodes across

265 
# blocks to get the weight of the edge joining those two blocks.

266 
if edge_data is None: 
267 
def edge_data(b, c): 
268 
edgedata = (d for u, v, d in G.edges(b  c, data=True) 
269 
if (u in b and v in c) or (u in c and v in b)) 
270 
return {'weight': sum(d.get('weight', 1) for d in edgedata)} 
271 
block_pairs = permutations(H, 2) if H.is_directed() else combinations(H, 2) 
272 
# In a multigraph, add one edge in the quotient graph for each edge

273 
# in the original graph.

274 
if H.is_multigraph():

275 
edges = chaini(((b, c, G.get_edge_data(u, v, default={})) 
276 
for u, v in product(b, c) if v in G[u]) 
277 
for b, c in block_pairs if edge_relation(b, c)) 
278 
# In a simple graph, apply the edge data function to each pair of

279 
# blocks to determine the edge data attributes to apply to each edge

280 
# in the quotient graph.

281 
else:

282 
edges = ((b, c, edge_data(b, c)) for (b, c) in block_pairs 
283 
if edge_relation(b, c))

284 
H.add_edges_from(edges) 
285 
# If requested by the user, relabel the nodes to be integers,

286 
# numbered in increasing order from zero in the same order as the

287 
# iteration order of `partition`.

288 
if relabel:

289 
# Can't use nx.convert_node_labels_to_integers() here since we

290 
# want the order of iteration to be the same for backward

291 
# compatibility with the nx.blockmodel() function.

292 
labels = {b: i for i, b in enumerate(partition)} 
293 
H = nx.relabel_nodes(H, labels) 
294 
return H

295  
296  
297 
def contracted_nodes(G, u, v, self_loops=True): 
298 
"""Returns the graph that results from contracting `u` and `v`.

299 

300 
Node contraction identifies the two nodes as a single node incident to any

301 
edge that was incident to the original two nodes.

302 

303 
Parameters

304 


305 
G : NetworkX graph

306 
The graph whose nodes will be contracted.

307 

308 
u, v : nodes

309 
Must be nodes in `G`.

310 

311 
self_loops : Boolean

312 
If this is True, any edges joining `u` and `v` in `G` become

313 
selfloops on the new node in the returned graph.

314 

315 
Returns

316 


317 
Networkx graph

318 
A new graph object of the same type as `G` (leaving `G` unmodified)

319 
with `u` and `v` identified in a single node. The right node `v`

320 
will be merged into the node `u`, so only `u` will appear in the

321 
returned graph.

322 

323 
Notes

324 


325 
For multigraphs, the edge keys for the realigned edges may

326 
not be the same as the edge keys for the old edges. This is

327 
natural because edge keys are unique only within each pair of nodes.

328 

329 
Examples

330 


331 
Contracting two nonadjacent nodes of the cycle graph on four nodes `C_4`

332 
yields the path graph (ignoring parallel edges)::

333 

334 
>>> G = nx.cycle_graph(4)

335 
>>> M = nx.contracted_nodes(G, 1, 3)

336 
>>> P3 = nx.path_graph(3)

337 
>>> nx.is_isomorphic(M, P3)

338 
True

339 

340 
>>> G = nx.MultiGraph(P3)

341 
>>> M = nx.contracted_nodes(G, 0, 2)

342 
>>> M.edges

343 
MultiEdgeView([(0, 1, 0), (0, 1, 1)])

344 

345 
>>> G = nx.Graph([(1,2), (2,2)])

346 
>>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)

347 
>>> list(H.nodes())

348 
[1]

349 
>>> list(H.edges())

350 
[(1, 1)]

351 

352 
See also

353 


354 
contracted_edge

355 
quotient_graph

356 

357 
Notes

358 


359 
This function is also available as `identified_nodes`.

360 
"""

361 
H = G.copy() 
362 
# edge code uses G.edges(v) instead of G.adj[v] to handle multiedges

363 
if H.is_directed():

364 
in_edges = ((w if w != v else u, u, d) 
365 
for w, x, d in G.in_edges(v, data=True) 
366 
if self_loops or w != u) 
367 
out_edges = ((u, w if w != v else u, d) 
368 
for x, w, d in G.out_edges(v, data=True) 
369 
if self_loops or w != u) 
370 
new_edges = chain(in_edges, out_edges) 
371 
else:

372 
new_edges = ((u, w if w != v else u, d) 
373 
for x, w, d in G.edges(v, data=True) 
374 
if self_loops or w != u) 
375 
v_data = H.nodes[v] 
376 
H.remove_node(v) 
377 
H.add_edges_from(new_edges) 
378  
379 
if 'contraction' in H.nodes[u]: 
380 
H.nodes[u]['contraction'][v] = v_data

381 
else:

382 
H.nodes[u]['contraction'] = {v: v_data}

383 
return H

384  
385  
386 
identified_nodes = contracted_nodes 
387  
388  
389 
def contracted_edge(G, edge, self_loops=True): 
390 
"""Returns the graph that results from contracting the specified edge.

391 

392 
Edge contraction identifies the two endpoints of the edge as a single node

393 
incident to any edge that was incident to the original two nodes. A graph

394 
that results from edge contraction is called a *minor* of the original

395 
graph.

396 

397 
Parameters

398 


399 
G : NetworkX graph

400 
The graph whose edge will be contracted.

401 

402 
edge : tuple

403 
Must be a pair of nodes in `G`.

404 

405 
self_loops : Boolean

406 
If this is True, any edges (including `edge`) joining the

407 
endpoints of `edge` in `G` become selfloops on the new node in the

408 
returned graph.

409 

410 
Returns

411 


412 
Networkx graph

413 
A new graph object of the same type as `G` (leaving `G` unmodified)

414 
with endpoints of `edge` identified in a single node. The right node

415 
of `edge` will be merged into the left one, so only the left one will

416 
appear in the returned graph.

417 

418 
Raises

419 


420 
ValueError

421 
If `edge` is not an edge in `G`.

422 

423 
Examples

424 


425 
Attempting to contract two nonadjacent nodes yields an error::

426 

427 
>>> import networkx as nx

428 
>>> G = nx.cycle_graph(4)

429 
>>> nx.contracted_edge(G, (1, 3))

430 
Traceback (most recent call last):

431 
...

432 
ValueError: Edge (1, 3) does not exist in graph G; cannot contract it

433 

434 
Contracting two adjacent nodes in the cycle graph on *n* nodes yields the

435 
cycle graph on *n  1* nodes::

436 

437 
>>> import networkx as nx

438 
>>> C5 = nx.cycle_graph(5)

439 
>>> C4 = nx.cycle_graph(4)

440 
>>> M = nx.contracted_edge(C5, (0, 1), self_loops=False)

441 
>>> nx.is_isomorphic(M, C4)

442 
True

443 

444 
See also

445 


446 
contracted_nodes

447 
quotient_graph

448 

449 
"""

450 
if not G.has_edge(*edge): 
451 
raise ValueError('Edge {0} does not exist in graph G; cannot contract' 
452 
' it'.format(edge))

453 
return contracted_nodes(G, *edge, self_loops=self_loops)
