myGraph.py
2.16 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
131
132
133
134
class Graph:
"""
docstring for graph
"""
def __init__(self):
"""
use 0,1, 2, 3 as vertices
and label the vertices using their variable name
"""
self.vertices = []
self.edges = {} #from key to value (parent -> child)
self.parents = {} #the parents of the key, no label
self.edge_labelling = {}
self.vertice_labelling = {}
def add_edge(self, start, end, label = None):
if label == None:
for s, e in zip(start, end):
self.edges[s].append(e)
self.parents[e].append(s)
else:
for s, e, l in zip(start, end, label):
self.edges[s].append(e)
self.parents[e].append(s)
self.edge_labelling[(s, e)] = l
def add_vertice(self, vertice, label = None):
if label == None:
for v in vertice:
self.vertices.append(v)
self.edges[v] = []
self.parents[v] = []
else:
for v, l in zip(vertice, label):
self.vertices.append(v)
self.vertice_labelling[v] = l
self.edges[v] = []
self.parents[v] = []
def delete_verrtice(self, vertice):
pass
def delete_edge(self, start, end):
pass
def ford_bellman(self, s):
"""
input s is a vertice
output is a dict
Bellman Ford algorithm to calculate the shortest distance
"""
D = {}
inf = len(self.vertices)
for x in self.vertices:
if x in self.edges[s]:
D[x] = 1
else:
D[x] = inf
D[s] = 0
for i in xrange(len(self.vertices) - 2):
for v in self.vertices:
if v != s:
for u in self.vertices:
if v in self.edges[u]:
D[v] = min(D[v], D[u] + 1)
return D
def avg_dist(self):
s = 0
for v in self.vertices:
s += sum(self.ford_bellman(v).values())
return s * 1.0 / (len(self.vertices) ** 2 - len(self.vertices))
def make_undirected(self):
for v in self.vertices:
for w in self.vertices:
if (w in self.edges[v]) and (not v in self.edges[w]):
self.edges[w].append(v)
def fromParents(self, verts, pars):
"""
add edges whose parents have been given
"""
self.vertices = []
for v in verts:
self.add_vertice(v)
self.edges[v] = []
for v, par in zip(verts, pars):
for p in par:
self.add_edge(p, v)
def num_edges(self):
return sum(map(len, self.edges.values()))