# smallworld.py

Below is the syntax highlighted version of smallworld.py from §4.5 Case Study: Small World.

```#-----------------------------------------------------------------------
# smallworld.py
#-----------------------------------------------------------------------

import sys
import stdio
import instream
from graph import Graph
from pathfinder import PathFinder

#-----------------------------------------------------------------------

# Return the average degree of graph.

def averageDegree(graph):
return 2.0 * graph.countE() / graph.countV()

#-----------------------------------------------------------------------

# Return the average path length of graph.

def averagePathLength(graph):
total = 0
for v in graph.vertices():
pf = PathFinder(graph, v)
for w in graph.vertices():
total += pf.distanceTo(w)
return 1.0 * total / (graph.countV() * (graph.countV() - 1))

#-----------------------------------------------------------------------

# Return the clustering coefficient of graph.

def clusteringCoefficient(graph):
total = 0
for v in graph.vertices():
possible = graph.degree(v) * (graph.degree(v) - 1)
actual = 0
for u in graph.adjacentTo(v):
for w in graph.adjacentTo(v):
if graph.hasEdge(u, w):
actual += 1
if possible > 0:
total += 1.0 * actual / possible

#-----------------------------------------------------------------------

# Test client.

def main():

graphFile = sys.argv[1]
delimiter = sys.argv[2]

graph = Graph(graphFile, delimiter)

vertexCount = graph.countV()
edgeCount = graph.countE()
stdio.writef('%d vertices, %d edges\n', vertexCount, edgeCount)

avgDegree = averageDegree(graph)
stdio.writef('average degree         = %7.3f\n', avgDegree)

avgPathLength = averagePathLength(graph)
stdio.writef('average path length    = %7.3f\n', avgPathLength)

clusteringCoef = clusteringCoefficient(graph)
stdio.writef('clustering coefficient = %7.3f\n', clusteringCoef)

if __name__ == '__main__':
main()

#-----------------------------------------------------------------------

# python smallworld.py tinygraph.txt " "
# 5 vertices, 7 edges
# average degree         =   2.800
# average degree         =   1.300
# clustering coefficient =   0.767

```

Copyright © 2000–2015, Robert Sedgewick, Kevin Wayne, and Robert Dondero.
Last updated: Fri Oct 20 20:45:16 EDT 2017.