'''graph.py Jeff Ondich, 26 Jan 2009 Some graph utilities. To specify a graph for use by this program, put it in a text file whose format is: Directed? N [# of nodes, to be indexed 0, 1, 2,..., N-1] node node weight node node weight ... For example, the directed graph with edges 0 -> 1 -> 2 -> 0 and no weights could be represented like so: Directed 3 0 1 0 1 2 0 2 0 0 whereas the undirected graph with edges 0 <-> 1 <-> 2 <-> 0 and no weights could look like this: Undirected 3 1 0 0 2 0 0 1 2 0 ''' import sys class GraphFormatError(Exception): def __init__(self, value): self.value = value def __str__(self): return repr(self.value) class Graph: def __init__(self): self.nNodes = 0 self.isDirected = False self.adjacencyLists = [] def load(self, inFile, inFileName=''): '''Loads a graph from the specified open file object inFile. The inFileName parameter is used only to provide sufficiently descriptive error messages. The expected file format is described in the comment at the top of this source file.''' lineNumber = 0 # Is this graph directed? line = inFile.readline().strip() lineNumber += 1 self.isDirected = (line == 'Directed') # The number of nodes in the graph. line = inFile.readline().strip() lineNumber += 1 if line and line.isdigit() and int(line) > 0: self.nNodes = int(line) self.adjacencyLists = [] for k in range(self.nNodes): self.adjacencyLists.append([]) else: message = 'Invalid node count: %s, line %d' % (inFileName, lineNumber) raise GraphFormatError(message) # The graph's edges. for line in inFile: fields = line.strip().split() if len(fields) != 3: message = 'Edge format error: %s, line %d\n' % (inFileName, lineNumber) message = 'Wrong number of fields.' raise GraphFormatError(message) try: node1 = int(fields[0]) if node1 < 0 or node1 >= self.nNodes: message = 'Edge format error: %s, line %d\n' % (inFileName, lineNumber) message = 'First field (node index) is out of range.' raise GraphFormatError(message) except Exception, e: message = 'Edge format error: %s, line %d\n' % (inFileName, lineNumber) message = 'First field must be a non-negative integer node index.' raise GraphFormatError(message) try: node2 = int(fields[1]) if node2 < 0 or node2 >= self.nNodes: message = 'Edge format error: %s, line %d\n' % (inFileName, lineNumber) message = 'Second field (node index) is out of range.' raise GraphFormatError(message) except Exception, e: message = 'Edge format error: %s, line %d\n' % (inFileName, lineNumber) message = 'Second field must be a non-negative integer node index.' raise GraphFormatError(message) try: weight = float(fields[2]) except Exception, e: message = 'Edge format error: %s, line %d\n' % (inFileName, lineNumber) message = 'Third field must be a real number weight.' raise GraphFormatError(message) adjList = self.adjacencyLists[node1] adjList.append([node2, weight]) if not self.isDirected: self.adjacencyLists[node2].append([node1, weight]) def __str__(self): s = '' if self.isDirected: s += 'Directed\n' else: s += 'Undirected\n' s += 'Number of nodes: %d\n' % self.nNodes s += 'Edges:\n' for k in range(len(self.adjacencyLists)): for item in self.adjacencyLists[k]: if self.isDirected or item[0] >= k: s += '%d -> %d (weight=%f)\n' % (k, item[0], item[1]) return s def breadthFirstSearch(self, startNode): '''Returns a list of "layers" describing the results of a breadth-first search of the graph starting at startNode. Layer 0 = [startNode], Layer 1 = [nodes 1 step from startNode], etc. For example, for a complete graph on three nodes and startNode = 1, this function will return [[1], [0, 2]].''' if startNode < 0 or startNode >= self.nNodes: return [] visited = [False] * self.nNodes visited[startNode] = True previousLayer = [startNode] layers = [previousLayer] while len(previousLayer) > 0: currentLayer = {} for node in previousLayer: for neighbor, weight in self.adjacencyLists[node]: if not visited[neighbor]: visited[neighbor] = True currentLayer[neighbor] = 0 previousLayer = currentLayer.keys() if len(previousLayer) > 0: layers.append(previousLayer) return layers def getTopologicalSort(self): '''If the graph is directed, this method returns a list of the graph's node indices, in topological order. Otherwise, the method returns the empty list.''' pass def getShortestPaths(self, startNode): '''This method uses Dijkstra's Algorithm to compute the shortest paths from startNode to all the other nodes in the graph. The method returns a list of paths, one per node in the graph. Each path is a three-element list consisting of the destination node, the total distance, and a list of the nodes along the path. For example, suppose startNode = 2, and the path shortest path from startNode to node 4 goes from 2 to 5 to 1 to 4 with a total distance of 37.2, then the path corresponding to node 4 would be: [4, 37.2, [2, 5, 1, 4]] ''' pass if __name__ == '__main__': if len(sys.argv) != 2: sys.stderr.write('Usage: %s graphfile\n' % sys.argv[0]) sys.exit(1) # Instantiate a graph and print it out graph = Graph() graphFile = open(sys.argv[1]) graph.load(graphFile, sys.argv[1]) print graph # Do a breadth-first search starting at node 0, # and print out the resulting list of layers. bfsResults = graph.breadthFirstSearch(0) layerNumber = 0 for layer in bfsResults: print 'L%d: ' % layerNumber, for node in layer: print node, print layerNumber += 1