Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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 Boolean-valued 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 non-empty
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
       self-loops 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 self-loops 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)