forked from AllenDowney/ThinkComplexity
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGraph4.py
More file actions
105 lines (84 loc) · 3.17 KB
/
Copy pathGraph4.py
File metadata and controls
105 lines (84 loc) · 3.17 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
class Queue(list):
"""this class is a subclass of list that maintains
a parallel dictionary so that it can check membership
in constant time. It maintains the equivalence of the
list and the dictionary by overriding pop and append;
using any other modifiers will break the invariant.
"""
def __init__(self, seq):
list.__init__(self, seq)
self.set = dict(zip(seq, seq))
def pop(self, i=-1):
return self.set.pop(list.pop(self, i))
def append(self, x):
list.append(self, x)
self.set[x] = x
def __contains__(self, x):
return x in self.set
class Graph(dict):
# old methods omitted...
def shortestPathTree(self, s):
"""form the shortest path tree from start node s by
labelling each vertex with its distance from s and
its predecessor in the path from s
"""
for v in self:
v.dist = None
v.p = None
s.dist = 0
queue = Queue([s])
while queue:
v = queue.pop(0)
for w, e in self[v].iteritems():
if w.dist is not None and w.dist < v.dist + e.length:
continue
w.dist = v.dist + e.length
w.p = v
if w not in queue: queue.append(w)
return [v for v in self if v.dist is not None]
def diameter(self):
"""find and return the diameter of the graph
"""
# choose an arbitrary start vertex and
# compute the shortest path tree
v = self.iterkeys().next()
vs = self.shortestPathTree(v)
# find the farthest vertex and use it as the
# start vertex for another shortest path tree
d, v = max([(v.dist, v) for v in vs])
self.shortestPathTree(v)
# find the farthest vertex again and return its distance
d, v = max([(v.dist, v) for v in vs])
return d
def charLength(self):
"""compute the characteristic length of the graph according
to the definition in Watts and Strogatz.
Precondition: the graph is connected.
"""
d = {}
# for each vertex v, d[v] is the list of other vertices
# and their distances
for v in self:
self.shortestPathTree(v)
d[v] = [w.dist for w in self if w is not v]
# join all the lists and return the average of all values
ds = sum(d.itervalues(), [])
return sum(ds) / len(ds)
def clusterCoef(self):
"""compute the cluster coefficient of the graph according
to the definition in Watts and Strogatz.
"""
d = {}
# for each vertex, d[v] is C_v, the cluster coefficient
for v in self:
set = self.outVertices(v) + [v]
d[v] = self.cluster(set)
# the cluster coefficient for the graph is the average of C_v
ds = d.itervalues()
return sum(ds) / len(d)
def cluster(self, set):
"return the fraction of edges among this set that exist"
k = len(set)
possible = k * (k-1.0)
edges = [1 for v in set for w in set if self.hasEdge(v, w)]
return len(v) / possible