This repository was archived by the owner on Apr 14, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 9
Expand file tree
/
Copy pathgraph.py
More file actions
130 lines (106 loc) · 4 KB
/
graph.py
File metadata and controls
130 lines (106 loc) · 4 KB
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