Repository navigation
Expand file tree
/
Copy pathgraph.py
More file actions
117 lines (102 loc) · 3.49 KB
/
Copy pathgraph.py
File metadata and controls
117 lines (102 loc) · 3.49 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
# 6.00.2x Problem Set 5
# Graph optimization
#
# A set of data structures to represent graphs
#
class Node(object):
def __init__(self, name):
self.name = str(name)
def getName(self):
return self.name
def __str__(self):
return self.name
def __repr__(self):
return self.name
def __eq__(self, other):
return self.name == other.name
def __ne__(self, other):
return not self.__eq__(other)
def __hash__(self):
# Override the default hash method
# Think: Why would we want to do this?
return self.name.__hash__()
class Edge(object):
def __init__(self, src, dest):
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def __str__(self):
return '{0}->{1}'.format(self.src, self.dest)
class WeightedEdge(Edge):
def __init__(self, src, dest, td, od):
Edge.__init__(self, src, dest)
self.td = td
self.od = od
# else :
# raise ValueError('total distance is smaller outdoor distance')
def getTotalDistance(self) :
return self.td
def getOutdoorDistance(self) :
return self.od
def __str__(self) :
return '{0}->{1} ({2}, {3})'.format(self.src, self.dest, self.td, self.od)
class Digraph(object):
"""
A directed graph
"""
def __init__(self):
# A Python Set is basically a list that doesn't allow duplicates.
# Entries into a set must be hashable (where have we seen this before?)
# Because it is backed by a hashtable, lookups are O(1) as opposed to the O(n) of a list (nifty!)
# See http://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset
self.nodes = set([])
self.edges = {}
def addNode(self, node):
if node in self.nodes:
# Even though self.nodes is a Set, we want to do this to make sure we
# don't add a duplicate entry for the same node in the self.edges list.
raise ValueError('Duplicate node')
else:
self.nodes.add(node)
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
if not(src in self.nodes and dest in self.nodes):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.nodes
def __str__(self):
res = ''
for k in self.edges:
for d in self.edges[str(k)]:
res = '{0}{1}->{2}\n'.format(res, k, d)
return res[:-1]
class WeightedDigraph(Digraph):
def __init__(self):
Digraph.__init__(self)
def addEdge(self, wedge):
src = wedge.getSource()
dest = wedge.getDestination()
td = float(wedge.getTotalDistance())
od = float(wedge.getOutdoorDistance())
if not(src in self.nodes and dest in self.nodes):
raise ValueError('Node not in graph')
self.edges[src].append([dest, td, od])
def childrenOf(self,node) :
t = []
for edge in self.edges[node] :
t.append(edge[0])
return t
def __str__(self):
t = ''
for e in self.edges :
for we in self.edges[e]:
t = '{0}{1}->{2} ({3}, {4})\n'.format(t, e, we[0], we[1], we[2])
return t[:-1]