Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / cycles.py @ 5cef0f13

History | View | Annotate | Download (21.6 KB)

1
#    Copyright (C) 2010-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
#
8
# Authors: Jon Olav Vik <jonovik@gmail.com>
9
#          Dan Schult <dschult@colgate.edu>
10
#          Aric Hagberg <hagberg@lanl.gov>
11
#          Debsankha Manik <dmanik@nld.ds.mpg.de>
12
"""
13
========================
14
Cycle finding algorithms
15
========================
16
"""
17

    
18
from collections import defaultdict
19
from itertools import tee
20

    
21
import networkx as nx
22
from networkx.utils import not_implemented_for, pairwise
23

    
24
__all__ = [
25
    'cycle_basis', 'simple_cycles',
26
    'recursive_simple_cycles', 'find_cycle',
27
    'minimum_cycle_basis',
28
]
29

    
30

    
31
@not_implemented_for('directed')
32
@not_implemented_for('multigraph')
33
def cycle_basis(G, root=None):
34
    """ Returns a list of cycles which form a basis for cycles of G.
35

36
    A basis for cycles of a network is a minimal collection of
37
    cycles such that any cycle in the network can be written
38
    as a sum of cycles in the basis.  Here summation of cycles
39
    is defined as "exclusive or" of the edges. Cycle bases are
40
    useful, e.g. when deriving equations for electric circuits
41
    using Kirchhoff's Laws.
42

43
    Parameters
44
    ----------
45
    G : NetworkX Graph
46
    root : node, optional
47
       Specify starting node for basis.
48

49
    Returns
50
    -------
51
    A list of cycle lists.  Each cycle list is a list of nodes
52
    which forms a cycle (loop) in G.
53

54
    Examples
55
    --------
56
    >>> G = nx.Graph()
57
    >>> nx.add_cycle(G, [0, 1, 2, 3])
58
    >>> nx.add_cycle(G, [0, 3, 4, 5])
59
    >>> print(nx.cycle_basis(G, 0))
60
    [[3, 4, 5, 0], [1, 2, 3, 0]]
61

62
    Notes
63
    -----
64
    This is adapted from algorithm CACM 491 [1]_.
65

66
    References
67
    ----------
68
    .. [1] Paton, K. An algorithm for finding a fundamental set of
69
       cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518.
70

71
    See Also
72
    --------
73
    simple_cycles
74
    """
75
    gnodes = set(G.nodes())
76
    cycles = []
77
    while gnodes:  # loop over connected components
78
        if root is None:
79
            root = gnodes.pop()
80
        stack = [root]
81
        pred = {root: root}
82
        used = {root: set()}
83
        while stack:  # walk the spanning tree finding cycles
84
            z = stack.pop()  # use last-in so cycles easier to find
85
            zused = used[z]
86
            for nbr in G[z]:
87
                if nbr not in used:   # new node
88
                    pred[nbr] = z
89
                    stack.append(nbr)
90
                    used[nbr] = set([z])
91
                elif nbr == z:          # self loops
92
                    cycles.append([z])
93
                elif nbr not in zused:  # found a cycle
94
                    pn = used[nbr]
95
                    cycle = [nbr, z]
96
                    p = pred[z]
97
                    while p not in pn:
98
                        cycle.append(p)
99
                        p = pred[p]
100
                    cycle.append(p)
101
                    cycles.append(cycle)
102
                    used[nbr].add(z)
103
        gnodes -= set(pred)
104
        root = None
105
    return cycles
106

    
107

    
108
@not_implemented_for('undirected')
109
def simple_cycles(G):
110
    """Find simple cycles (elementary circuits) of a directed graph.
111

112
    A `simple cycle`, or `elementary circuit`, is a closed path where
113
    no node appears twice. Two elementary circuits are distinct if they
114
    are not cyclic permutations of each other.
115

116
    This is a nonrecursive, iterator/generator version of Johnson's
117
    algorithm [1]_.  There may be better algorithms for some cases [2]_ [3]_.
118

119
    Parameters
120
    ----------
121
    G : NetworkX DiGraph
122
       A directed graph
123

124
    Returns
125
    -------
126
    cycle_generator: generator
127
       A generator that produces elementary cycles of the graph.
128
       Each cycle is represented by a list of nodes along the cycle.
129

130
    Examples
131
    --------
132
    >>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
133
    >>> G = nx.DiGraph(edges)
134
    >>> len(list(nx.simple_cycles(G)))
135
    5
136

137
    To filter the cycles so that they don't include certain nodes or edges,
138
    copy your graph and eliminate those nodes or edges before calling
139

140
    >>> copyG = G.copy()
141
    >>> copyG.remove_nodes_from([1])
142
    >>> copyG.remove_edges_from([(0, 1)])
143
    >>> len(list(nx.simple_cycles(copyG)))
144
    3
145

146

147
    Notes
148
    -----
149
    The implementation follows pp. 79-80 in [1]_.
150

151
    The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$
152
    elementary circuits.
153

154
    References
155
    ----------
156
    .. [1] Finding all the elementary circuits of a directed graph.
157
       D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
158
       https://doi.org/10.1137/0204007
159
    .. [2] Enumerating the cycles of a digraph: a new preprocessing strategy.
160
       G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.
161
    .. [3] A search strategy for the elementary cycles of a directed graph.
162
       J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS,
163
       v. 16, no. 2, 192-204, 1976.
164

165
    See Also
166
    --------
167
    cycle_basis
168
    """
169
    def _unblock(thisnode, blocked, B):
170
        stack = set([thisnode])
171
        while stack:
172
            node = stack.pop()
173
            if node in blocked:
174
                blocked.remove(node)
175
                stack.update(B[node])
176
                B[node].clear()
177

    
178
    # Johnson's algorithm requires some ordering of the nodes.
179
    # We assign the arbitrary ordering given by the strongly connected comps
180
    # There is no need to track the ordering as each node removed as processed.
181
    # Also we save the actual graph so we can mutate it. We only take the
182
    # edges because we do not want to copy edge and node attributes here.
183
    subG = type(G)(G.edges())
184
    sccs = [scc for scc in nx.strongly_connected_components(subG)
185
            if len(scc) > 1]
186

    
187
    # Johnson's algorithm exclude self cycle edges like (v, v)
188
    # To be backward compatible, we record those cycles in advance
189
    # and then remove from subG
190
    for v in subG:
191
        if subG.has_edge(v, v):
192
            yield [v]
193
            subG.remove_edge(v, v)
194

    
195
    while sccs:
196
        scc = sccs.pop()
197
        sccG = subG.subgraph(scc)
198
        # order of scc determines ordering of nodes
199
        startnode = scc.pop()
200
        # Processing node runs "circuit" routine from recursive version
201
        path = [startnode]
202
        blocked = set()  # vertex: blocked from search?
203
        closed = set()   # nodes involved in a cycle
204
        blocked.add(startnode)
205
        B = defaultdict(set)  # graph portions that yield no elementary circuit
206
        stack = [(startnode, list(sccG[startnode]))]  # sccG gives comp nbrs
207
        while stack:
208
            thisnode, nbrs = stack[-1]
209
            if nbrs:
210
                nextnode = nbrs.pop()
211
                if nextnode == startnode:
212
                    yield path[:]
213
                    closed.update(path)
214
#                        print "Found a cycle", path, closed
215
                elif nextnode not in blocked:
216
                    path.append(nextnode)
217
                    stack.append((nextnode, list(sccG[nextnode])))
218
                    closed.discard(nextnode)
219
                    blocked.add(nextnode)
220
                    continue
221
            # done with nextnode... look for more neighbors
222
            if not nbrs:  # no more nbrs
223
                if thisnode in closed:
224
                    _unblock(thisnode, blocked, B)
225
                else:
226
                    for nbr in sccG[thisnode]:
227
                        if thisnode not in B[nbr]:
228
                            B[nbr].add(thisnode)
229
                stack.pop()
230
#                assert path[-1] == thisnode
231
                path.pop()
232
        # done processing this node
233
        H = subG.subgraph(scc)  # make smaller to avoid work in SCC routine
234
        sccs.extend(scc for scc in nx.strongly_connected_components(H)
235
                    if len(scc) > 1)
236

    
237

    
238
@not_implemented_for('undirected')
239
def recursive_simple_cycles(G):
240
    """Find simple cycles (elementary circuits) of a directed graph.
241

242
    A `simple cycle`, or `elementary circuit`, is a closed path where
243
    no node appears twice. Two elementary circuits are distinct if they
244
    are not cyclic permutations of each other.
245

246
    This version uses a recursive algorithm to build a list of cycles.
247
    You should probably use the iterator version called simple_cycles().
248
    Warning: This recursive version uses lots of RAM!
249

250
    Parameters
251
    ----------
252
    G : NetworkX DiGraph
253
       A directed graph
254

255
    Returns
256
    -------
257
    A list of cycles, where each cycle is represented by a list of nodes
258
    along the cycle.
259

260
    Example:
261

262
    >>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
263
    >>> G = nx.DiGraph(edges)
264
    >>> nx.recursive_simple_cycles(G)
265
    [[0], [2], [0, 1, 2], [0, 2], [1, 2]]
266

267
    See Also
268
    --------
269
    cycle_basis (for undirected graphs)
270

271
    Notes
272
    -----
273
    The implementation follows pp. 79-80 in [1]_.
274

275
    The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$
276
    elementary circuits.
277

278
    References
279
    ----------
280
    .. [1] Finding all the elementary circuits of a directed graph.
281
       D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
282
       https://doi.org/10.1137/0204007
283

284
    See Also
285
    --------
286
    simple_cycles, cycle_basis
287
    """
288
    # Jon Olav Vik, 2010-08-09
289
    def _unblock(thisnode):
290
        """Recursively unblock and remove nodes from B[thisnode]."""
291
        if blocked[thisnode]:
292
            blocked[thisnode] = False
293
            while B[thisnode]:
294
                _unblock(B[thisnode].pop())
295

    
296
    def circuit(thisnode, startnode, component):
297
        closed = False  # set to True if elementary path is closed
298
        path.append(thisnode)
299
        blocked[thisnode] = True
300
        for nextnode in component[thisnode]:  # direct successors of thisnode
301
            if nextnode == startnode:
302
                result.append(path[:])
303
                closed = True
304
            elif not blocked[nextnode]:
305
                if circuit(nextnode, startnode, component):
306
                    closed = True
307
        if closed:
308
            _unblock(thisnode)
309
        else:
310
            for nextnode in component[thisnode]:
311
                if thisnode not in B[nextnode]:  # TODO: use set for speedup?
312
                    B[nextnode].append(thisnode)
313
        path.pop()  # remove thisnode from path
314
        return closed
315

    
316
    path = []              # stack of nodes in current path
317
    blocked = defaultdict(bool)  # vertex: blocked from search?
318
    B = defaultdict(list)  # graph portions that yield no elementary circuit
319
    result = []            # list to accumulate the circuits found
320

    
321
    # Johnson's algorithm exclude self cycle edges like (v, v)
322
    # To be backward compatible, we record those cycles in advance
323
    # and then remove from subG
324
    for v in G:
325
        if G.has_edge(v, v):
326
            result.append([v])
327
            G.remove_edge(v, v)
328

    
329
    # Johnson's algorithm requires some ordering of the nodes.
330
    # They might not be sortable so we assign an arbitrary ordering.
331
    ordering = dict(zip(G, range(len(G))))
332
    for s in ordering:
333
        # Build the subgraph induced by s and following nodes in the ordering
334
        subgraph = G.subgraph(node for node in G
335
                              if ordering[node] >= ordering[s])
336
        # Find the strongly connected component in the subgraph
337
        # that contains the least node according to the ordering
338
        strongcomp = nx.strongly_connected_components(subgraph)
339
        mincomp = min(strongcomp, key=lambda ns: min(ordering[n] for n in ns))
340
        component = G.subgraph(mincomp)
341
        if len(component) > 1:
342
            # smallest node in the component according to the ordering
343
            startnode = min(component, key=ordering.__getitem__)
344
            for node in component:
345
                blocked[node] = False
346
                B[node][:] = []
347
            dummy = circuit(startnode, startnode, component)
348
    return result
349

    
350

    
351
def find_cycle(G, source=None, orientation=None):
352
    """Returns a cycle found via depth-first traversal.
353

354
    The cycle is a list of edges indicating the cyclic path.
355
    Orientation of directed edges is controlled by `orientation`.
356

357
    Parameters
358
    ----------
359
    G : graph
360
        A directed/undirected graph/multigraph.
361

362
    source : node, list of nodes
363
        The node from which the traversal begins. If None, then a source
364
        is chosen arbitrarily and repeatedly until all edges from each node in
365
        the graph are searched.
366

367
    orientation : None | 'original' | 'reverse' | 'ignore' (default: None)
368
        For directed graphs and directed multigraphs, edge traversals need not
369
        respect the original orientation of the edges.
370
        When set to 'reverse' every edge is traversed in the reverse direction.
371
        When set to 'ignore', every edge is treated as undirected.
372
        When set to 'original', every edge is treated as directed.
373
        In all three cases, the yielded edge tuples add a last entry to
374
        indicate the direction in which that edge was traversed.
375
        If orientation is None, the yielded edge has no direction indicated.
376
        The direction is respected, but not reported.
377

378
    Returns
379
    -------
380
    edges : directed edges
381
        A list of directed edges indicating the path taken for the loop.
382
        If no cycle is found, then an exception is raised.
383
        For graphs, an edge is of the form `(u, v)` where `u` and `v`
384
        are the tail and head of the edge as determined by the traversal.
385
        For multigraphs, an edge is of the form `(u, v, key)`, where `key` is
386
        the key of the edge. When the graph is directed, then `u` and `v`
387
        are always in the order of the actual directed edge.
388
        If orientation is not None then the edge tuple is extended to include
389
        the direction of traversal ('forward' or 'reverse') on that edge.
390

391
    Raises
392
    ------
393
    NetworkXNoCycle
394
        If no cycle was found.
395

396
    Examples
397
    --------
398
    In this example, we construct a DAG and find, in the first call, that there
399
    are no directed cycles, and so an exception is raised. In the second call,
400
    we ignore edge orientations and find that there is an undirected cycle.
401
    Note that the second call finds a directed cycle while effectively
402
    traversing an undirected graph, and so, we found an "undirected cycle".
403
    This means that this DAG structure does not form a directed tree (which
404
    is also known as a polytree).
405

406
    >>> import networkx as nx
407
    >>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
408
    >>> try:
409
    ...    nx.find_cycle(G, orientation='original')
410
    ... except:
411
    ...    pass
412
    ...
413
    >>> list(nx.find_cycle(G, orientation='ignore'))
414
    [(0, 1, 'forward'), (1, 2, 'forward'), (0, 2, 'reverse')]
415

416
    """
417
    if not G.is_directed() or orientation in (None, 'original'):
418
        def tailhead(edge):
419
            return edge[:2]
420
    elif orientation == 'reverse':
421
        def tailhead(edge):
422
            return edge[1], edge[0]
423
    elif orientation == 'ignore':
424
        def tailhead(edge):
425
            if edge[-1] == 'reverse':
426
                return edge[1], edge[0]
427
            return edge[:2]
428

    
429
    explored = set()
430
    cycle = []
431
    final_node = None
432
    for start_node in G.nbunch_iter(source):
433
        if start_node in explored:
434
            # No loop is possible.
435
            continue
436

    
437
        edges = []
438
        # All nodes seen in this iteration of edge_dfs
439
        seen = {start_node}
440
        # Nodes in active path.
441
        active_nodes = {start_node}
442
        previous_head = None
443

    
444
        for edge in nx.edge_dfs(G, start_node, orientation):
445
            # Determine if this edge is a continuation of the active path.
446
            tail, head = tailhead(edge)
447
            if head in explored:
448
                # Then we've already explored it. No loop is possible.
449
                continue
450
            if previous_head is not None and tail != previous_head:
451
                # This edge results from backtracking.
452
                # Pop until we get a node whose head equals the current tail.
453
                # So for example, we might have:
454
                #  (0, 1), (1, 2), (2, 3), (1, 4)
455
                # which must become:
456
                #  (0, 1), (1, 4)
457
                while True:
458
                    try:
459
                        popped_edge = edges.pop()
460
                    except IndexError:
461
                        edges = []
462
                        active_nodes = {tail}
463
                        break
464
                    else:
465
                        popped_head = tailhead(popped_edge)[1]
466
                        active_nodes.remove(popped_head)
467

    
468
                    if edges:
469
                        last_head = tailhead(edges[-1])[1]
470
                        if tail == last_head:
471
                            break
472
            edges.append(edge)
473

    
474
            if head in active_nodes:
475
                # We have a loop!
476
                cycle.extend(edges)
477
                final_node = head
478
                break
479
            else:
480
                seen.add(head)
481
                active_nodes.add(head)
482
                previous_head = head
483

    
484
        if cycle:
485
            break
486
        else:
487
            explored.update(seen)
488

    
489
    else:
490
        assert(len(cycle) == 0)
491
        raise nx.exception.NetworkXNoCycle('No cycle found.')
492

    
493
    # We now have a list of edges which ends on a cycle.
494
    # So we need to remove from the beginning edges that are not relevant.
495

    
496
    for i, edge in enumerate(cycle):
497
        tail, head = tailhead(edge)
498
        if tail == final_node:
499
            break
500

    
501
    return cycle[i:]
502

    
503

    
504
@not_implemented_for('directed')
505
@not_implemented_for('multigraph')
506
def minimum_cycle_basis(G, weight=None):
507
    """ Returns a minimum weight cycle basis for G
508

509
    Minimum weight means a cycle basis for which the total weight
510
    (length for unweighted graphs) of all the cycles is minimum.
511

512
    Parameters
513
    ----------
514
    G : NetworkX Graph
515
    weight: string
516
        name of the edge attribute to use for edge weights
517

518
    Returns
519
    -------
520
    A list of cycle lists.  Each cycle list is a list of nodes
521
    which forms a cycle (loop) in G. Note that the nodes are not
522
    necessarily returned in a order by which they appear in the cycle
523

524
    Examples
525
    --------
526
    >>> G=nx.Graph()
527
    >>> G.add_cycle([0,1,2,3])
528
    >>> G.add_cycle([0,3,4,5])
529
    >>> print(nx.minimum_cycle_basis(G))
530
    [[0, 1, 2, 3], [0, 3, 4, 5]]
531

532
    References:
533
        [1] Kavitha, Telikepalli, et al. "An O(m^2n) Algorithm for
534
        Minimum Cycle Basis of Graphs."
535
        http://link.springer.com/article/10.1007/s00453-007-9064-z
536
        [2] de Pina, J. 1995. Applications of shortest path methods.
537
        Ph.D. thesis, University of Amsterdam, Netherlands
538

539
    See Also
540
    --------
541
    simple_cycles, cycle_basis
542
    """
543
    # We first split the graph in commected subgraphs
544
    return sum((_min_cycle_basis(c, weight) for c in
545
                nx.connected_component_subgraphs(G)), [])
546

    
547

    
548
def _min_cycle_basis(comp, weight):
549
    cb = []
550
    # We  extract the edges not in a spanning tree. We do not really need a
551
    # *minimum* spanning tree. That is why we call the next function with
552
    # weight=None. Depending on implementation, it may be faster as well
553
    spanning_tree_edges = list(nx.minimum_spanning_edges(comp, weight=None,
554
                                                         data=False))
555
    edges_excl = [frozenset(e) for e in comp.edges()
556
                  if e not in spanning_tree_edges]
557
    N = len(edges_excl)
558

    
559
    # We maintain a set of vectors orthogonal to sofar found cycles
560
    set_orth = [set([edge]) for edge in edges_excl]
561
    for k in range(N):
562
        # kth cycle is "parallel" to kth vector in set_orth
563
        new_cycle = _min_cycle(comp, set_orth[k], weight=weight)
564
        cb.append(list(set().union(*new_cycle)))
565
        # now update set_orth so that k+1,k+2... th elements are
566
        # orthogonal to the newly found cycle, as per [p. 336, 1]
567
        base = set_orth[k]
568
        set_orth[k + 1:] = [orth ^ base if len(orth & new_cycle) % 2 else orth
569
                            for orth in set_orth[k + 1:]]
570
    return cb
571

    
572

    
573
def _min_cycle(G, orth, weight=None):
574
    """
575
    Computes the minimum weight cycle in G,
576
    orthogonal to the vector orth as per [p. 338, 1]
577
    """
578
    T = nx.Graph()
579

    
580
    nodes_idx = {node: idx for idx, node in enumerate(G.nodes())}
581
    idx_nodes = {idx: node for node, idx in nodes_idx.items()}
582

    
583
    nnodes = len(nodes_idx)
584

    
585
    # Add 2 copies of each edge in G to T. If edge is in orth, add cross edge;
586
    # otherwise in-plane edge
587
    for u, v, data in G.edges(data=True):
588
        uidx, vidx = nodes_idx[u], nodes_idx[v]
589
        edge_w = data.get(weight, 1)
590
        if frozenset((u, v)) in orth:
591
            T.add_edges_from(
592
                [(uidx, nnodes + vidx), (nnodes + uidx, vidx)], weight=edge_w)
593
        else:
594
            T.add_edges_from(
595
                [(uidx, vidx), (nnodes + uidx, nnodes + vidx)], weight=edge_w)
596

    
597
    all_shortest_pathlens = dict(nx.shortest_path_length(T, weight=weight))
598
    cross_paths_w_lens = {n: all_shortest_pathlens[n][nnodes + n]
599
                          for n in range(nnodes)}
600

    
601
    # Now compute shortest paths in T, which translates to cyles in G
602
    start = min(cross_paths_w_lens, key=cross_paths_w_lens.get)
603
    end = nnodes + start
604
    min_path = nx.shortest_path(T, source=start, target=end, weight='weight')
605

    
606
    # Now we obtain the actual path, re-map nodes in T to those in G
607
    min_path_nodes = [node if node < nnodes else node - nnodes
608
                      for node in min_path]
609
    # Now remove the edges that occur two times
610
    mcycle_pruned = _path_to_cycle(min_path_nodes)
611

    
612
    return {frozenset((idx_nodes[u], idx_nodes[v])) for u, v in mcycle_pruned}
613

    
614

    
615
def _path_to_cycle(path):
616
    """
617
    Removes the edges from path that occur even number of times.
618
    Returns a set of edges
619
    """
620
    edges = set()
621
    for edge in pairwise(path):
622
        # Toggle whether to keep the current edge.
623
        edges ^= {edge}
624
    return edges