graph.py

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

#-----------------------------------------------------------------------
# graph.py
#-----------------------------------------------------------------------

import sys
import stdio
from instream import InStream

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

class Graph:

    # Construct a new Graph object. If a filename is specified,
    # populate the Graph object by reading data from the specified
    # file with the specified delimiter.
    def __init__(self, filename=None, delimiter=None):
        self._e = 0
        self._adj = dict()
        if filename is not None:
            instream = InStream(filename)
            while instream.hasNextLine():
                line = instream.readLine()
                names = line.split(delimiter)
                for i in range(1, len(names)):
                    self.addEdge(names[0], names[i])
                
    # Add an edge to self between vertex v and vertex w.
    def addEdge(self, v, w):
        if not self.hasVertex(v): self._adj[v] = set()
        if not self.hasVertex(w): self._adj[w] = set()
        if not self.hasEdge(v, w):
            self._e += 1
            self._adj[v].add(w)
            self._adj[w].add(v)
            
    # Return an iterable collection containing all neighbors of
    # vertex v in self.
    def adjacentTo(self, v):
        return iter(self._adj[v])
    
    # Return an iterable collection of all vertices in self.
    def vertices(self):
        return iter(self._adj)

    # Return True if vertex v is in self, and False otherwise.
    def hasVertex(self, v):
        return v in self._adj

    # Return True if v-w is an edge in self, and False otherwise.
    def hasEdge(self, v, w):
        return w in self._adj[v]
    
    # Return the number of vertices in self.
    def countV(self):
        return len(self._adj)
    
    # Return the number of edges in self.
    def countE(self):
        return self._e
    
    # Return the degree of vertex v of self.
    def degree(self, v):
        return len(self._adj[v])

    # Return a string representation of self.
    def __str__(self):
        s = ''
        for v in self.vertices():
            s += v + '  '
            for w in self.adjacentTo(v):
                s += w + ' '
            s += '\n'
        return s

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

# For testing. Accept string file as a command-line argument. Create a
# Graph object by reading from file. Write the Graph object to standard
# output.

def main():
    file = sys.argv[1]
    graph = Graph(file)
    stdio.writeln(graph)

if __name__ == '__main__':
    main()

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

# python graph.py tinygraph.txt
# A  G H B C 
# G  A C 
# H  A B 
# B  A H C 
# C  A G B