Skip to content

Instantly share code, notes, and snippets.

@Cilyan
Created August 6, 2015 16:31
Show Gist options
  • Save Cilyan/4d158d85099f4d07bb6c to your computer and use it in GitHub Desktop.
Save Cilyan/4d158d85099f4d07bb6c to your computer and use it in GitHub Desktop.
Simple utility to resolve dependencies between arbitrary (but hashable) objects.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class DependencyGraph(object):
"""
Handle a dependency graph. Using :py:meth:`insert`, you add objects
to the graph and connect them with their dependencies, and the
:py:meth:`resolve` function will yield them back so that any object
comes after all its dependencies.
"""
class Node(object):
def __init__(self, obj):
self.obj = obj
# Keep ordering for reproducibility, but use an underlying set
# for uniqueness checks, in case the list gets big
# ( x in s is O(1) for set, but O(n) for lists )
self.dependencies = []
self.depsset = set()
def get_obj(self):
return self.obj
def add_dependency(self, dep):
if dep not in self.depsset:
self.dependencies.append(dep)
self.depsset.add(dep)
def get_dependencies(self):
return self.dependencies
def __init__(self):
# The root of the tree is a special node that depends on all nodes
# of the graph and serves as bootstrap for the DFS
self.root = self.Node(None)
self.nodes = {None: self.root}
def _get_node(self, obj):
# Get a node based on its obj. If the node doesn't exist, it is
# created and added to the graph.
if not obj in self.nodes:
node = self.nodes[obj] = self.Node(obj)
self.root.add_dependency(node)
else:
node = self.nodes[obj]
return node
def insert(self, obj, parent=None):
"""
Insert a relation in the graph. If `obj` doesn't depend on
anything, `parent` can be left to `None`. Both `obj` and
`parent` are inserted in the graph if they do not exist, but they
will not be duplicated. Both `obj` and `parent` must be hashable.
"""
pnode = self._get_node(parent)
node = self._get_node(obj)
if pnode is not self.root:
node.add_dependency(pnode)
def resolve(self):
"""
Yield all objects in the graph so that any object comes after its
dependencies. Raises :py:class:`RuntimeError` if a cyclic dependency
is found.
"""
already_raised = set()
already_visited = set()
def dep_resolve(node):
already_visited.add(node)
for dep in node.get_dependencies():
if not dep in already_raised:
if dep in already_visited:
raise RuntimeError(
"Cyclic dependency detected: {!r} and {!r}".format(
node.get_obj(), dep.get_obj()
)
)
# yield from is only available from python 3.3
for obj in dep_resolve(dep):
yield obj
if node not in already_raised:
already_raised.add(node)
if node is not self.root:
yield node.get_obj()
for obj in dep_resolve(self.root):
yield obj
def test():
graph = DependencyGraph()
graph.insert("A", "B")
graph.insert("C", "D")
graph.insert("A", "C")
graph.insert("B", "C")
graph.insert("D", None)
graph.insert("E", "F")
graph.insert("F", "G")
graph.insert("H", "I")
graph.insert("E", "I")
graph.insert("F", "J")
for pkg in graph.resolve():
print(pkg)
try:
graph.insert("J", "F")
list(graph.resolve())
except RuntimeError as e:
print("Cyclic dependency detection OK")
else:
raise RuntimeError("Cyclic dependency was not detected !")
return 0
if __name__ == '__main__':
test()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment