-
Notifications
You must be signed in to change notification settings - Fork 0
/
graphcalc.py
84 lines (67 loc) · 2.36 KB
/
graphcalc.py
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
class Graph:
def __init__(self, graph):
self.graph = graph
self.points = {}
self.eccentricities = {}
self.width = 0
self.proximity = 0
self.key_vertex = '0'
def main(self):
"""Walk the matrix."""
for i, row in enumerate(self.graph):
self.curr_point = {}
for j, column in enumerate(row):
if column == 1 and j != i:
self.curr_point[str(j)] = 1
self.walk(j, [i], 2)
del self.curr_point[str(i)]
self.points[str(i)] = self.curr_point
self.get_eccentricities()
self.get_width()
self.get_proximity()
def walk(self, row_num, visited_rows, edges):
for j, column in enumerate(self.graph[row_num]):
if column == 1 and j != row_num:
if str(j) in self.curr_point:
if self.curr_point[str(j)] > edges:
self.curr_point[str(j)] = edges
else:
self.curr_point[str(j)] = edges
if j not in visited_rows:
self.walk(j, visited_rows+[row_num], edges+1)
def get_width(self):
for k, v in self.eccentricities.iteritems():
if v > self.width:
self.width = v
def get_proximity(self):
self.proximity = self.eccentricities['0']
for k, v in self.eccentricities.iteritems():
if v < self.proximity:
self.proximity = v
self.key_vertex = k
def get_eccentricities(self):
for k, v in self.points.iteritems():
maximum = 0
for vertex, edges in v.iteritems():
if int(edges) > maximum:
maximum = int(edges)
self.eccentricities[k] = maximum
# for x in i:
# print x
if __name__ == '__main__':
g = [ \
[0, 1, 0, 1], \
[1, 0, 1, 1], \
[0, 1, 0, 0], \
[1, 1, 0, 0] \
]
# for row in g:
# print row
expected_width = 2
expected_prox = 1
curr_graph = Graph(g)
curr_graph.main()
print "Width: %i" % curr_graph.width
print "Proximity: %i" % curr_graph.proximity
print "Key Vertex: V%i" % (int(curr_graph.key_vertex) + 1)
#print curr_graph.eccentricities