Repository navigation
Expand file tree
/
Copy pathgraph.py
More file actions
104 lines (84 loc) · 2.49 KB
/
Copy pathgraph.py
File metadata and controls
104 lines (84 loc) · 2.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
# data structure of graph
import unittest
class Edge:
def __init__(self, v, w):
self.v = v
self.w = w
class Graph:
def __init__(self, vertexs):
self.vertexs = vertexs
def setEdge(self, v, w):
pass
def hasPath(self, v, w):
pass
# class GraphInMatrix(Graph):
# # def __init__(self):
# # pass
# def setEdge(self, v, w):
# self.matrix = [[0 for col in range(cols)] for row in range(rows)]
# pass
# def hasPath(self, v, w):
# return False
class GraphInList(Graph):
def __init__(self, vertexs):
Graph.__init__(self, vertexs)
self.edgeSet = []
for i in range(0, vertexs):
self.edgeSet.append([])
def setEdge(self, v, w):
exists = False
for x in self.edgeSet[v]:
if x == w:
exists = True
break
if not exists:
self.edgeSet[v].append(w)
self.edgeSet[w].append(v)
def edgeCount(self):
cnt = 0
for i in range(0, self.vertexs):
cnt += len(self.edgeSet[i])
return cnt/2
def hasPath(self, v, w):
return len(self.getPath(v, w))>0
def getPath(self, v, w):
path = []
if self._getPath(v, w, [v,], path):
path.insert(0, v)
return path
def _getPath(self, v, w, nodes, path):
ns = self.edgeSet[v]
for x in ns:
if x == w:
path.append(w)
return True
for x in ns:
if not nodes.__contains__(x):
nodes.append(x)
if self._getPath(x, w, nodes, path):
path.insert(0, x)
return True
return False
class GraphTest(unittest.TestCase):
def setUp(self):
vCnt = 10
self.g = GraphInList(vCnt)
self.g.setEdge(0, 1)
self.g.setEdge(0, 5)
self.g.setEdge(0, 8)
self.g.setEdge(1, 3)
self.g.setEdge(4, 9)
self.g.setEdge(5, 6)
self.g.setEdge(6, 9)
self.g.setEdge(7, 8)
def testInitGraphVertexs(self):
assert self.g.vertexs == 10
def testInitGraphEdges(self):
assert self.g.edgeCount() == 8
def testHasPath(self):
assert self.g.hasPath(0, 2) == False
assert self.g.getPath(0, 9) == [0, 5, 6, 9], self.g.getPath(0, 9)
if __name__ == '__main__':
suite = unittest.makeSuite(GraphTest,'test')
runner = unittest.TextTestRunner()
runner.run(suite)