/usr/lib/python3/dist-packages/async/graph.py is in python3-async 0.6.2-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | # Copyright (C) 2010, 2011 Sebastian Thiel (byronimo@gmail.com) and contributors
#
# This module is part of async and is released under
# the New BSD License: http://www.opensource.org/licenses/bsd-license.php
"""Simplistic implementation of a graph"""
__all__ = ('Node', 'Graph')
class Node(object):
"""A Node in the graph. They know their neighbours, and have an id which should
resolve into a string"""
__slots__ = ('in_nodes', 'out_nodes', 'id')
def __init__(self, id=None):
self.id = id
self.in_nodes = list()
self.out_nodes = list()
def __str__(self):
return str(self.id)
def __repr__(self):
return "%s(%s)" % (type(self).__name__, self.id)
class Graph(object):
"""A simple graph implementation, keeping nodes and providing basic access and
editing functions. The performance is only suitable for small graphs of not
more than 10 nodes !"""
__slots__ = "nodes"
def __init__(self):
self.nodes = list()
def __del__(self):
"""Deletes bidericational dependencies"""
for node in self.nodes:
node.in_nodes = None
node.out_nodes = None
# END cleanup nodes
# otherwise the nodes would keep floating around
def add_node(self, node):
"""Add a new node to the graph
:return: the newly added node"""
self.nodes.append(node)
return node
def remove_node(self, node):
"""Delete a node from the graph
:return: self"""
try:
del(self.nodes[self.nodes.index(node)])
except ValueError:
return self
# END ignore if it doesn't exist
# clear connections
for outn in node.out_nodes:
del(outn.in_nodes[outn.in_nodes.index(node)])
for inn in node.in_nodes:
del(inn.out_nodes[inn.out_nodes.index(node)])
node.out_nodes = list()
node.in_nodes = list()
return self
def add_edge(self, u, v):
"""Add an undirected edge between the given nodes u and v.
:return: self
:raise ValueError: If the new edge would create a cycle"""
if u is v:
raise ValueError("Cannot connect a node with itself")
# are they already connected ?
if u in v.in_nodes and v in u.out_nodes or \
v in u.in_nodes and u in v.out_nodes:
return self
# END handle connection exists
# cycle check - if we can reach any of the two by following either ones
# history, its a cycle
for start, end in ((u, v), (v,u)):
if not start.in_nodes:
continue
nodes = start.in_nodes[:]
seen = set()
# depth first search - its faster
while nodes:
n = nodes.pop()
if n in seen:
continue
seen.add(n)
if n is end:
raise ValueError("Connecting u with v would create a cycle")
nodes.extend(n.in_nodes)
# END while we are searching
# END for each direction to look
# connection is valid, set it up
u.out_nodes.append(v)
v.in_nodes.append(u)
return self
def input_inclusive_dfirst_reversed(self, node):
"""Return all input nodes of the given node, depth first,
It will return the actual input node last, as it is required
like that by the pool"""
stack = [node]
seen = set()
# depth first
out = list()
while stack:
n = stack.pop()
if n in seen:
continue
seen.add(n)
out.append(n)
# only proceed in that direction if visitor is fine with it
stack.extend(n.in_nodes)
# END call visitor
# END while walking
out.reverse()
return out
|