--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/planemo/lib/python3.7/site-packages/networkx/algorithms/cycles.py	Fri Jul 31 00:32:28 2020 -0400
@@ -0,0 +1,624 @@
+#    Copyright (C) 2010-2019 by
+#    Aric Hagberg <hagberg@lanl.gov>
+#    Dan Schult <dschult@colgate.edu>
+#    Pieter Swart <swart@lanl.gov>
+#    All rights reserved.
+#    BSD license.
+#
+# Authors: Jon Olav Vik <jonovik@gmail.com>
+#          Dan Schult <dschult@colgate.edu>
+#          Aric Hagberg <hagberg@lanl.gov>
+#          Debsankha Manik <dmanik@nld.ds.mpg.de>
+"""
+========================
+Cycle finding algorithms
+========================
+"""
+
+from collections import defaultdict
+from itertools import tee
+
+import networkx as nx
+from networkx.utils import not_implemented_for, pairwise
+
+__all__ = [
+    'cycle_basis', 'simple_cycles',
+    'recursive_simple_cycles', 'find_cycle',
+    'minimum_cycle_basis',
+]
+
+
+@not_implemented_for('directed')
+@not_implemented_for('multigraph')
+def cycle_basis(G, root=None):
+    """ Returns a list of cycles which form a basis for cycles of G.
+
+    A basis for cycles of a network is a minimal collection of
+    cycles such that any cycle in the network can be written
+    as a sum of cycles in the basis.  Here summation of cycles
+    is defined as "exclusive or" of the edges. Cycle bases are
+    useful, e.g. when deriving equations for electric circuits
+    using Kirchhoff's Laws.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+    root : node, optional
+       Specify starting node for basis.
+
+    Returns
+    -------
+    A list of cycle lists.  Each cycle list is a list of nodes
+    which forms a cycle (loop) in G.
+
+    Examples
+    --------
+    >>> G = nx.Graph()
+    >>> nx.add_cycle(G, [0, 1, 2, 3])
+    >>> nx.add_cycle(G, [0, 3, 4, 5])
+    >>> print(nx.cycle_basis(G, 0))
+    [[3, 4, 5, 0], [1, 2, 3, 0]]
+
+    Notes
+    -----
+    This is adapted from algorithm CACM 491 [1]_.
+
+    References
+    ----------
+    .. [1] Paton, K. An algorithm for finding a fundamental set of
+       cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518.
+
+    See Also
+    --------
+    simple_cycles
+    """
+    gnodes = set(G.nodes())
+    cycles = []
+    while gnodes:  # loop over connected components
+        if root is None:
+            root = gnodes.pop()
+        stack = [root]
+        pred = {root: root}
+        used = {root: set()}
+        while stack:  # walk the spanning tree finding cycles
+            z = stack.pop()  # use last-in so cycles easier to find
+            zused = used[z]
+            for nbr in G[z]:
+                if nbr not in used:   # new node
+                    pred[nbr] = z
+                    stack.append(nbr)
+                    used[nbr] = set([z])
+                elif nbr == z:          # self loops
+                    cycles.append([z])
+                elif nbr not in zused:  # found a cycle
+                    pn = used[nbr]
+                    cycle = [nbr, z]
+                    p = pred[z]
+                    while p not in pn:
+                        cycle.append(p)
+                        p = pred[p]
+                    cycle.append(p)
+                    cycles.append(cycle)
+                    used[nbr].add(z)
+        gnodes -= set(pred)
+        root = None
+    return cycles
+
+
+@not_implemented_for('undirected')
+def simple_cycles(G):
+    """Find simple cycles (elementary circuits) of a directed graph.
+
+    A `simple cycle`, or `elementary circuit`, is a closed path where
+    no node appears twice. Two elementary circuits are distinct if they
+    are not cyclic permutations of each other.
+
+    This is a nonrecursive, iterator/generator version of Johnson's
+    algorithm [1]_.  There may be better algorithms for some cases [2]_ [3]_.
+
+    Parameters
+    ----------
+    G : NetworkX DiGraph
+       A directed graph
+
+    Returns
+    -------
+    cycle_generator: generator
+       A generator that produces elementary cycles of the graph.
+       Each cycle is represented by a list of nodes along the cycle.
+
+    Examples
+    --------
+    >>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
+    >>> G = nx.DiGraph(edges)
+    >>> len(list(nx.simple_cycles(G)))
+    5
+
+    To filter the cycles so that they don't include certain nodes or edges,
+    copy your graph and eliminate those nodes or edges before calling
+
+    >>> copyG = G.copy()
+    >>> copyG.remove_nodes_from([1])
+    >>> copyG.remove_edges_from([(0, 1)])
+    >>> len(list(nx.simple_cycles(copyG)))
+    3
+
+
+    Notes
+    -----
+    The implementation follows pp. 79-80 in [1]_.
+
+    The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$
+    elementary circuits.
+
+    References
+    ----------
+    .. [1] Finding all the elementary circuits of a directed graph.
+       D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
+       https://doi.org/10.1137/0204007
+    .. [2] Enumerating the cycles of a digraph: a new preprocessing strategy.
+       G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.
+    .. [3] A search strategy for the elementary cycles of a directed graph.
+       J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS,
+       v. 16, no. 2, 192-204, 1976.
+
+    See Also
+    --------
+    cycle_basis
+    """
+    def _unblock(thisnode, blocked, B):
+        stack = set([thisnode])
+        while stack:
+            node = stack.pop()
+            if node in blocked:
+                blocked.remove(node)
+                stack.update(B[node])
+                B[node].clear()
+
+    # Johnson's algorithm requires some ordering of the nodes.
+    # We assign the arbitrary ordering given by the strongly connected comps
+    # There is no need to track the ordering as each node removed as processed.
+    # Also we save the actual graph so we can mutate it. We only take the
+    # edges because we do not want to copy edge and node attributes here.
+    subG = type(G)(G.edges())
+    sccs = [scc for scc in nx.strongly_connected_components(subG)
+            if len(scc) > 1]
+
+    # Johnson's algorithm exclude self cycle edges like (v, v)
+    # To be backward compatible, we record those cycles in advance
+    # and then remove from subG
+    for v in subG:
+        if subG.has_edge(v, v):
+            yield [v]
+            subG.remove_edge(v, v)
+
+    while sccs:
+        scc = sccs.pop()
+        sccG = subG.subgraph(scc)
+        # order of scc determines ordering of nodes
+        startnode = scc.pop()
+        # Processing node runs "circuit" routine from recursive version
+        path = [startnode]
+        blocked = set()  # vertex: blocked from search?
+        closed = set()   # nodes involved in a cycle
+        blocked.add(startnode)
+        B = defaultdict(set)  # graph portions that yield no elementary circuit
+        stack = [(startnode, list(sccG[startnode]))]  # sccG gives comp nbrs
+        while stack:
+            thisnode, nbrs = stack[-1]
+            if nbrs:
+                nextnode = nbrs.pop()
+                if nextnode == startnode:
+                    yield path[:]
+                    closed.update(path)
+#                        print "Found a cycle", path, closed
+                elif nextnode not in blocked:
+                    path.append(nextnode)
+                    stack.append((nextnode, list(sccG[nextnode])))
+                    closed.discard(nextnode)
+                    blocked.add(nextnode)
+                    continue
+            # done with nextnode... look for more neighbors
+            if not nbrs:  # no more nbrs
+                if thisnode in closed:
+                    _unblock(thisnode, blocked, B)
+                else:
+                    for nbr in sccG[thisnode]:
+                        if thisnode not in B[nbr]:
+                            B[nbr].add(thisnode)
+                stack.pop()
+#                assert path[-1] == thisnode
+                path.pop()
+        # done processing this node
+        H = subG.subgraph(scc)  # make smaller to avoid work in SCC routine
+        sccs.extend(scc for scc in nx.strongly_connected_components(H)
+                    if len(scc) > 1)
+
+
+@not_implemented_for('undirected')
+def recursive_simple_cycles(G):
+    """Find simple cycles (elementary circuits) of a directed graph.
+
+    A `simple cycle`, or `elementary circuit`, is a closed path where
+    no node appears twice. Two elementary circuits are distinct if they
+    are not cyclic permutations of each other.
+
+    This version uses a recursive algorithm to build a list of cycles.
+    You should probably use the iterator version called simple_cycles().
+    Warning: This recursive version uses lots of RAM!
+
+    Parameters
+    ----------
+    G : NetworkX DiGraph
+       A directed graph
+
+    Returns
+    -------
+    A list of cycles, where each cycle is represented by a list of nodes
+    along the cycle.
+
+    Example:
+
+    >>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
+    >>> G = nx.DiGraph(edges)
+    >>> nx.recursive_simple_cycles(G)
+    [[0], [2], [0, 1, 2], [0, 2], [1, 2]]
+
+    See Also
+    --------
+    cycle_basis (for undirected graphs)
+
+    Notes
+    -----
+    The implementation follows pp. 79-80 in [1]_.
+
+    The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$
+    elementary circuits.
+
+    References
+    ----------
+    .. [1] Finding all the elementary circuits of a directed graph.
+       D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
+       https://doi.org/10.1137/0204007
+
+    See Also
+    --------
+    simple_cycles, cycle_basis
+    """
+    # Jon Olav Vik, 2010-08-09
+    def _unblock(thisnode):
+        """Recursively unblock and remove nodes from B[thisnode]."""
+        if blocked[thisnode]:
+            blocked[thisnode] = False
+            while B[thisnode]:
+                _unblock(B[thisnode].pop())
+
+    def circuit(thisnode, startnode, component):
+        closed = False  # set to True if elementary path is closed
+        path.append(thisnode)
+        blocked[thisnode] = True
+        for nextnode in component[thisnode]:  # direct successors of thisnode
+            if nextnode == startnode:
+                result.append(path[:])
+                closed = True
+            elif not blocked[nextnode]:
+                if circuit(nextnode, startnode, component):
+                    closed = True
+        if closed:
+            _unblock(thisnode)
+        else:
+            for nextnode in component[thisnode]:
+                if thisnode not in B[nextnode]:  # TODO: use set for speedup?
+                    B[nextnode].append(thisnode)
+        path.pop()  # remove thisnode from path
+        return closed
+
+    path = []              # stack of nodes in current path
+    blocked = defaultdict(bool)  # vertex: blocked from search?
+    B = defaultdict(list)  # graph portions that yield no elementary circuit
+    result = []            # list to accumulate the circuits found
+
+    # Johnson's algorithm exclude self cycle edges like (v, v)
+    # To be backward compatible, we record those cycles in advance
+    # and then remove from subG
+    for v in G:
+        if G.has_edge(v, v):
+            result.append([v])
+            G.remove_edge(v, v)
+
+    # Johnson's algorithm requires some ordering of the nodes.
+    # They might not be sortable so we assign an arbitrary ordering.
+    ordering = dict(zip(G, range(len(G))))
+    for s in ordering:
+        # Build the subgraph induced by s and following nodes in the ordering
+        subgraph = G.subgraph(node for node in G
+                              if ordering[node] >= ordering[s])
+        # Find the strongly connected component in the subgraph
+        # that contains the least node according to the ordering
+        strongcomp = nx.strongly_connected_components(subgraph)
+        mincomp = min(strongcomp, key=lambda ns: min(ordering[n] for n in ns))
+        component = G.subgraph(mincomp)
+        if len(component) > 1:
+            # smallest node in the component according to the ordering
+            startnode = min(component, key=ordering.__getitem__)
+            for node in component:
+                blocked[node] = False
+                B[node][:] = []
+            dummy = circuit(startnode, startnode, component)
+    return result
+
+
+def find_cycle(G, source=None, orientation=None):
+    """Returns a cycle found via depth-first traversal.
+
+    The cycle is a list of edges indicating the cyclic path.
+    Orientation of directed edges is controlled by `orientation`.
+
+    Parameters
+    ----------
+    G : graph
+        A directed/undirected graph/multigraph.
+
+    source : node, list of nodes
+        The node from which the traversal begins. If None, then a source
+        is chosen arbitrarily and repeatedly until all edges from each node in
+        the graph are searched.
+
+    orientation : None | 'original' | 'reverse' | 'ignore' (default: None)
+        For directed graphs and directed multigraphs, edge traversals need not
+        respect the original orientation of the edges.
+        When set to 'reverse' every edge is traversed in the reverse direction.
+        When set to 'ignore', every edge is treated as undirected.
+        When set to 'original', every edge is treated as directed.
+        In all three cases, the yielded edge tuples add a last entry to
+        indicate the direction in which that edge was traversed.
+        If orientation is None, the yielded edge has no direction indicated.
+        The direction is respected, but not reported.
+
+    Returns
+    -------
+    edges : directed edges
+        A list of directed edges indicating the path taken for the loop.
+        If no cycle is found, then an exception is raised.
+        For graphs, an edge is of the form `(u, v)` where `u` and `v`
+        are the tail and head of the edge as determined by the traversal.
+        For multigraphs, an edge is of the form `(u, v, key)`, where `key` is
+        the key of the edge. When the graph is directed, then `u` and `v`
+        are always in the order of the actual directed edge.
+        If orientation is not None then the edge tuple is extended to include
+        the direction of traversal ('forward' or 'reverse') on that edge.
+
+    Raises
+    ------
+    NetworkXNoCycle
+        If no cycle was found.
+
+    Examples
+    --------
+    In this example, we construct a DAG and find, in the first call, that there
+    are no directed cycles, and so an exception is raised. In the second call,
+    we ignore edge orientations and find that there is an undirected cycle.
+    Note that the second call finds a directed cycle while effectively
+    traversing an undirected graph, and so, we found an "undirected cycle".
+    This means that this DAG structure does not form a directed tree (which
+    is also known as a polytree).
+
+    >>> import networkx as nx
+    >>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
+    >>> try:
+    ...    nx.find_cycle(G, orientation='original')
+    ... except:
+    ...    pass
+    ...
+    >>> list(nx.find_cycle(G, orientation='ignore'))
+    [(0, 1, 'forward'), (1, 2, 'forward'), (0, 2, 'reverse')]
+
+    """
+    if not G.is_directed() or orientation in (None, 'original'):
+        def tailhead(edge):
+            return edge[:2]
+    elif orientation == 'reverse':
+        def tailhead(edge):
+            return edge[1], edge[0]
+    elif orientation == 'ignore':
+        def tailhead(edge):
+            if edge[-1] == 'reverse':
+                return edge[1], edge[0]
+            return edge[:2]
+
+    explored = set()
+    cycle = []
+    final_node = None
+    for start_node in G.nbunch_iter(source):
+        if start_node in explored:
+            # No loop is possible.
+            continue
+
+        edges = []
+        # All nodes seen in this iteration of edge_dfs
+        seen = {start_node}
+        # Nodes in active path.
+        active_nodes = {start_node}
+        previous_head = None
+
+        for edge in nx.edge_dfs(G, start_node, orientation):
+            # Determine if this edge is a continuation of the active path.
+            tail, head = tailhead(edge)
+            if head in explored:
+                # Then we've already explored it. No loop is possible.
+                continue
+            if previous_head is not None and tail != previous_head:
+                # This edge results from backtracking.
+                # Pop until we get a node whose head equals the current tail.
+                # So for example, we might have:
+                #  (0, 1), (1, 2), (2, 3), (1, 4)
+                # which must become:
+                #  (0, 1), (1, 4)
+                while True:
+                    try:
+                        popped_edge = edges.pop()
+                    except IndexError:
+                        edges = []
+                        active_nodes = {tail}
+                        break
+                    else:
+                        popped_head = tailhead(popped_edge)[1]
+                        active_nodes.remove(popped_head)
+
+                    if edges:
+                        last_head = tailhead(edges[-1])[1]
+                        if tail == last_head:
+                            break
+            edges.append(edge)
+
+            if head in active_nodes:
+                # We have a loop!
+                cycle.extend(edges)
+                final_node = head
+                break
+            else:
+                seen.add(head)
+                active_nodes.add(head)
+                previous_head = head
+
+        if cycle:
+            break
+        else:
+            explored.update(seen)
+
+    else:
+        assert(len(cycle) == 0)
+        raise nx.exception.NetworkXNoCycle('No cycle found.')
+
+    # We now have a list of edges which ends on a cycle.
+    # So we need to remove from the beginning edges that are not relevant.
+
+    for i, edge in enumerate(cycle):
+        tail, head = tailhead(edge)
+        if tail == final_node:
+            break
+
+    return cycle[i:]
+
+
+@not_implemented_for('directed')
+@not_implemented_for('multigraph')
+def minimum_cycle_basis(G, weight=None):
+    """ Returns a minimum weight cycle basis for G
+
+    Minimum weight means a cycle basis for which the total weight
+    (length for unweighted graphs) of all the cycles is minimum.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+    weight: string
+        name of the edge attribute to use for edge weights
+
+    Returns
+    -------
+    A list of cycle lists.  Each cycle list is a list of nodes
+    which forms a cycle (loop) in G. Note that the nodes are not
+    necessarily returned in a order by which they appear in the cycle
+
+    Examples
+    --------
+    >>> G=nx.Graph()
+    >>> nx.add_cycle(G, [0,1,2,3])
+    >>> nx.add_cycle(G, [0,3,4,5])
+    >>> print([sorted(c) for c in nx.minimum_cycle_basis(G)])
+    [[0, 1, 2, 3], [0, 3, 4, 5]]
+
+    References:
+        [1] Kavitha, Telikepalli, et al. "An O(m^2n) Algorithm for
+        Minimum Cycle Basis of Graphs."
+        http://link.springer.com/article/10.1007/s00453-007-9064-z
+        [2] de Pina, J. 1995. Applications of shortest path methods.
+        Ph.D. thesis, University of Amsterdam, Netherlands
+
+    See Also
+    --------
+    simple_cycles, cycle_basis
+    """
+    # We first split the graph in commected subgraphs
+    return sum((_min_cycle_basis(G.subgraph(c), weight) for c in
+                nx.connected_components(G)), [])
+
+
+def _min_cycle_basis(comp, weight):
+    cb = []
+    # We  extract the edges not in a spanning tree. We do not really need a
+    # *minimum* spanning tree. That is why we call the next function with
+    # weight=None. Depending on implementation, it may be faster as well
+    spanning_tree_edges = list(nx.minimum_spanning_edges(comp, weight=None,
+                                                         data=False))
+    edges_excl = [frozenset(e) for e in comp.edges()
+                  if e not in spanning_tree_edges]
+    N = len(edges_excl)
+
+    # We maintain a set of vectors orthogonal to sofar found cycles
+    set_orth = [set([edge]) for edge in edges_excl]
+    for k in range(N):
+        # kth cycle is "parallel" to kth vector in set_orth
+        new_cycle = _min_cycle(comp, set_orth[k], weight=weight)
+        cb.append(list(set().union(*new_cycle)))
+        # now update set_orth so that k+1,k+2... th elements are
+        # orthogonal to the newly found cycle, as per [p. 336, 1]
+        base = set_orth[k]
+        set_orth[k + 1:] = [orth ^ base if len(orth & new_cycle) % 2 else orth
+                            for orth in set_orth[k + 1:]]
+    return cb
+
+
+def _min_cycle(G, orth, weight=None):
+    """
+    Computes the minimum weight cycle in G,
+    orthogonal to the vector orth as per [p. 338, 1]
+    """
+    T = nx.Graph()
+
+    nodes_idx = {node: idx for idx, node in enumerate(G.nodes())}
+    idx_nodes = {idx: node for node, idx in nodes_idx.items()}
+
+    nnodes = len(nodes_idx)
+
+    # Add 2 copies of each edge in G to T. If edge is in orth, add cross edge;
+    # otherwise in-plane edge
+    for u, v, data in G.edges(data=True):
+        uidx, vidx = nodes_idx[u], nodes_idx[v]
+        edge_w = data.get(weight, 1)
+        if frozenset((u, v)) in orth:
+            T.add_edges_from(
+                [(uidx, nnodes + vidx), (nnodes + uidx, vidx)], weight=edge_w)
+        else:
+            T.add_edges_from(
+                [(uidx, vidx), (nnodes + uidx, nnodes + vidx)], weight=edge_w)
+
+    all_shortest_pathlens = dict(nx.shortest_path_length(T, weight=weight))
+    cross_paths_w_lens = {n: all_shortest_pathlens[n][nnodes + n]
+                          for n in range(nnodes)}
+
+    # Now compute shortest paths in T, which translates to cyles in G
+    start = min(cross_paths_w_lens, key=cross_paths_w_lens.get)
+    end = nnodes + start
+    min_path = nx.shortest_path(T, source=start, target=end, weight='weight')
+
+    # Now we obtain the actual path, re-map nodes in T to those in G
+    min_path_nodes = [node if node < nnodes else node - nnodes
+                      for node in min_path]
+    # Now remove the edges that occur two times
+    mcycle_pruned = _path_to_cycle(min_path_nodes)
+
+    return {frozenset((idx_nodes[u], idx_nodes[v])) for u, v in mcycle_pruned}
+
+
+def _path_to_cycle(path):
+    """
+    Removes the edges from path that occur even number of times.
+    Returns a set of edges
+    """
+    edges = set()
+    for edge in pairwise(path):
+        # Toggle whether to keep the current edge.
+        edges ^= {edge}
+    return edges