springsuite: planemo/lib/python3.7/site-packages/networkx/algorithms/cycles.py comparison

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/cycles.py @ 1:56ad4e20f292 draft

"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"

author	guerler
date	Fri, 31 Jul 2020 00:32:28 -0400
parents
children

comparison

equal deleted inserted replaced

-:d30785e31577
+:56ad4e20f292
+#    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

Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/cycles.py @ 1:56ad4e20f292 draft