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
|
"""Simplistic implementation of a 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 add_node(self, node):
"""Add a new node to the graph
:return: the newly added node"""
self.nodes.append(node)
return node
def del_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)])
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 visit_input_inclusive_depth_first(self, node, visitor=lambda n: True ):
"""Visit all input nodes of the given node, depth first, calling visitor
for each node on our way. If the function returns False, the traversal
will not go any deeper, but continue at the next branch
It will return the actual input node in the end !"""
nodes = node.in_nodes[:]
seen = set()
# depth first
while nodes:
n = nodes.pop()
if n in seen:
continue
seen.add(n)
# only proceed in that direction if visitor is fine with it
if visitor(n):
nodes.extend(n.in_nodes)
# END call visitor
# END while walking
visitor(node)
|
