diff options
Diffstat (limited to 'lib/sqlalchemy')
| -rw-r--r-- | lib/sqlalchemy/orm/unitofwork.py | 27 | ||||
| -rw-r--r-- | lib/sqlalchemy/sql/util.py | 2 | ||||
| -rw-r--r-- | lib/sqlalchemy/topological.py | 113 |
3 files changed, 33 insertions, 109 deletions
diff --git a/lib/sqlalchemy/orm/unitofwork.py b/lib/sqlalchemy/orm/unitofwork.py index bb3bb4fb2..16a01bdc1 100644 --- a/lib/sqlalchemy/orm/unitofwork.py +++ b/lib/sqlalchemy/orm/unitofwork.py @@ -215,30 +215,13 @@ class UOWTransaction(object): ).difference(cycles) # execute actions - sort = topological.sort(self.dependencies, postsort_actions) - print "------------------------" - print self.dependencies - print sort - if cycles: - # organize into a tree so that groups of nodes can be - # merged together, allowing better maintenance of insert - # ordering and other things - (head, children) = topological.organize_as_tree(self.dependencies, sort) - stack = [(head, children)] - - head.execute(self) - while stack: - node, children = stack.pop() - if children: - related = set([n[0] for n in children]) - while related: - n = related.pop() - n.execute_aggregate(self, related) - - stack += children + for set_ in topological.sort_as_subsets(self.dependencies, postsort_actions): + while set_: + n = set_.pop() + n.execute_aggregate(self, set_) else: - for rec in sort: + for rec in topological.sort(self.dependencies, postsort_actions): rec.execute(self) diff --git a/lib/sqlalchemy/sql/util.py b/lib/sqlalchemy/sql/util.py index 4d0071978..dda5d2d28 100644 --- a/lib/sqlalchemy/sql/util.py +++ b/lib/sqlalchemy/sql/util.py @@ -22,7 +22,7 @@ def sort_tables(tables): visitors.traverse(table, {'schema_visitor':True}, {'foreign_key':visit_foreign_key}) - return topological.sort(tuples, tables) + return list(topological.sort(tuples, tables)) def find_join_source(clauses, join_to): """Given a list of FROM clauses and a selectable, diff --git a/lib/sqlalchemy/topological.py b/lib/sqlalchemy/topological.py index 7253cdc4d..2ae631fb5 100644 --- a/lib/sqlalchemy/topological.py +++ b/lib/sqlalchemy/topological.py @@ -33,61 +33,48 @@ class _EdgeCollection(object): self.parent_to_children[parentnode].add(childnode) self.child_to_parents[childnode].add(parentnode) - def has_parents(self, node): - return node in self.child_to_parents and bool(self.child_to_parents[node]) - def outgoing(self, node): - """an iterable returning all nodes reached via node's outgoing edges""" - return self.parent_to_children[node] + + def incoming(self, node): + return self.child_to_parents[node] - def pop_node(self, node): - """Remove all edges where the given node is a parent. - - Return the collection of all nodes which were children of the - given node, and have no further parents. - """ - - children = self.parent_to_children.pop(node, None) - if children is not None: - for child in children: - self.child_to_parents[child].remove(node) - if not self.child_to_parents[child]: - yield child - def __iter__(self): - for parent, children in self.parent_to_children.iteritems(): - for child in children: + for parent in self.parent_to_children: + for child in self.outgoing(parent): yield (parent, child) def __repr__(self): return repr(list(self)) +def sort_as_subsets(tuples, allitems): + output = set() + + todo = set(allitems) + edges = _EdgeCollection(tuples) + while todo: + for node in list(todo): + if not todo.intersection(edges.incoming(node)): + output.add(node) + + if not output: + raise CircularDependencyError( + "Circular dependency detected: cycles: %r all edges: %r" % + (find_cycles(tuples, allitems), edges)) + + todo.difference_update(output) + yield output + output = set() + def sort(tuples, allitems): """sort the given list of items by dependency. 'tuples' is a list of tuples representing a partial ordering. """ - edges = _EdgeCollection(tuples) - nodes = set(allitems) - - queue = [] - for n in nodes: - if not edges.has_parents(n): - queue.append(n) - - output = [] - while nodes: - if not queue: - raise CircularDependencyError("Circular dependency detected: cycles: %r all edges: %r" % - (find_cycles(tuples, allitems), edges)) - node = queue.pop() - output.append(node) - nodes.remove(node) - for childnode in edges.pop_node(node): - queue.append(childnode) - return output + for set_ in sort_as_subsets(tuples, allitems): + for s in set_: + yield s def find_cycles(tuples, allitems): # straight from gvr with some mods @@ -115,49 +102,3 @@ def find_cycles(tuples, allitems): node = stack.pop() return output - -def organize_as_tree(tuples, allitems): - """Given a list of sorted nodes from a topological sort, organize the - nodes into a tree structure, with as many non-dependent nodes - set as siblings to each other as possible. - - returns nodes as tuples (item, children). - """ - - nodes = allitems - edges = _EdgeCollection(tuples) - children = util.defaultdict(list) - - if not nodes: - return None - # a list of all currently independent subtrees as a tuple of - # (root_node, set_of_all_tree_nodes, set_of_all_cycle_nodes_in_tree) - # order of the list has no semantics for the algorithmic - independents = [] - # in reverse topological order - for node in reversed(nodes): - # nodes subtree and cycles contain the node itself - subtree = set([node]) - # get a set of dependent nodes of node and its cycles - nodealldeps = edges.outgoing(node) - if nodealldeps: - # iterate over independent node indexes in reverse order so we can efficiently remove them - for index in xrange(len(independents) - 1, -1, -1): - child, childsubtree = independents[index] - # if there is a dependency between this node and an independent node - if (childsubtree.intersection(nodealldeps)): - # prepend child to nodes children - # (append should be fine, but previous implemetation used prepend) - children[node][0:0] = [(child, children[child])] - # merge childs subtree and cycles - subtree.update(childsubtree) - # remove the child from list of independent subtrees - independents[index:index+1] = [] - # add node as a new independent subtree - independents.append((node, subtree)) - # choose an arbitrary node from list of all independent subtrees - head = independents.pop()[0] - # add all other independent subtrees as a child of the chosen root - # used prepend [0:0] instead of extend to maintain exact behaviour of previous implementation - children[head][0:0] = [(i[0], children[i[0]]) for i in independents] - return (head, children[head]) |