Server IP : 85.214.239.14 / Your IP : 18.223.195.30 Web Server : Apache/2.4.62 (Debian) System : Linux h2886529.stratoserver.net 4.9.0 #1 SMP Tue Jan 9 19:45:01 MSK 2024 x86_64 User : www-data ( 33) PHP Version : 7.4.18 Disable Function : pcntl_alarm,pcntl_fork,pcntl_waitpid,pcntl_wait,pcntl_wifexited,pcntl_wifstopped,pcntl_wifsignaled,pcntl_wifcontinued,pcntl_wexitstatus,pcntl_wtermsig,pcntl_wstopsig,pcntl_signal,pcntl_signal_get_handler,pcntl_signal_dispatch,pcntl_get_last_error,pcntl_strerror,pcntl_sigprocmask,pcntl_sigwaitinfo,pcntl_sigtimedwait,pcntl_exec,pcntl_getpriority,pcntl_setpriority,pcntl_async_signals,pcntl_unshare, MySQL : OFF | cURL : OFF | WGET : ON | Perl : ON | Python : ON | Sudo : ON | Pkexec : OFF Directory : /proc/self/root/srv/automx/env/lib/python3.5/site-packages/sqlalchemy/util/ |
Upload File : |
# util/topological.py # Copyright (C) 2005-2020 the SQLAlchemy authors and contributors # <see AUTHORS file> # # This module is part of SQLAlchemy and is released under # the MIT License: http://www.opensource.org/licenses/mit-license.php """Topological sorting algorithms.""" from .. import util from ..exc import CircularDependencyError __all__ = ["sort", "sort_as_subsets", "find_cycles"] def sort_as_subsets(tuples, allitems, deterministic_order=False): edges = util.defaultdict(set) for parent, child in tuples: edges[child].add(parent) Set = util.OrderedSet if deterministic_order else set todo = Set(allitems) while todo: output = Set() for node in todo: if todo.isdisjoint(edges[node]): output.add(node) if not output: raise CircularDependencyError( "Circular dependency detected.", find_cycles(tuples, allitems), _gen_edges(edges), ) todo.difference_update(output) yield output def sort(tuples, allitems, deterministic_order=False): """sort the given list of items by dependency. 'tuples' is a list of tuples representing a partial ordering. 'deterministic_order' keeps items within a dependency tier in list order. """ for set_ in sort_as_subsets(tuples, allitems, deterministic_order): for s in set_: yield s def find_cycles(tuples, allitems): # adapted from: # http://neopythonic.blogspot.com/2009/01/detecting-cycles-in-directed-graph.html edges = util.defaultdict(set) for parent, child in tuples: edges[parent].add(child) nodes_to_test = set(edges) output = set() # we'd like to find all nodes that are # involved in cycles, so we do the full # pass through the whole thing for each # node in the original list. # we can go just through parent edge nodes. # if a node is only a child and never a parent, # by definition it can't be part of a cycle. same # if it's not in the edges at all. for node in nodes_to_test: stack = [node] todo = nodes_to_test.difference(stack) while stack: top = stack[-1] for node in edges[top]: if node in stack: cyc = stack[stack.index(node) :] todo.difference_update(cyc) output.update(cyc) if node in todo: stack.append(node) todo.remove(node) break else: node = stack.pop() return output def _gen_edges(edges): return set([(right, left) for left in edges for right in edges[left]])