Subversion Repositories programming

#!/usr/bin/env python

__author__    = "Ira W. Snyder (devel@irasnyder.com)"

__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"

__license__   = "GNU GPL v2 (or, at your option, any later version)"

# Fix for the lame version of python on the school's computers (v2.1)

try:

	(True, False)

except NameError:

	(True, False) = (1, 0)

# Make sure not to try graphviz if it's not installed (school again)

no_graphviz = False

try:

	import yapgvb

except:

	no_graphviz = True

import Graph

class Key:

	"""A class that makes a unique key for each pair of vertices."""

	def __init__ (self, v1, v2):

		self.__key = [v1, v2]

		self.__key.sort ()

	def __eq__ (self, rhs):

		return (self.__key[0] == rhs.__key[0]) and (self.__key[1] == rhs.__key[1])

class DrawGraph:

	"""A class that will draw an unweighted, undirected graph given the vertices and

	edges in the same form that is used for the Graph class."""

	def __init__ (self, name, graph):

		"""Constructor"""

		self.__name = str(name)

		self.__graph = graph

	def render_stupid (self, prop=None):

		"""Print the graph using the not very good method of telling whether

		   we go up,down,left,right between every node."""

		if prop == None:

			raise ValueError # no propery given

		g = self.__graph

		added = True

		count = 0

		while added:

			added = False

			for v in g.vertices.keys():

				if g.get_vertex_value (v) == str(count):

					print getattr (g.vertices[v].raw_obj, prop),

					added = True

			count += 1

		print # nothing, to end the getattr() print above

		print '%d nodes in the solution' % len(g.vertices)

	def render_graphviz (self, filename, layout_engine='neato'):

		"""Draw the graph given into the file given. This will render

		to SVG, PNG, and JPG."""

		if no_graphviz:

			raise ValueError # no yapgvb / graphviz installed!

		dg = yapgvb.Graph (self.__name)

		g = self.__graph

		visited = []

		for v in g.vertices:

			node = dg.add_node (str(v), label=str(v),

					shape=g.get_vertex_shape(v), fontsize=14)

			for c in g.get_children (v):

				k = Key (v, c)

				if k not in visited:

					node_c = dg.add_node (str(c), label=str(c),

							shape=g.get_vertex_shape (c),

							fontsize=14)

					edge = dg.add_edge (node, node_c)

					edge.color = g.get_edge_color (v, c)

					edge.label = g.get_edge_label (v, c)

					visited.append (k)

		# Do the rendering

		dg.layout (layout_engine)

		dg.render (filename)

def main ():

	vertices = ['a', 'b', 'c', 'd', 'e']

	edges = ( ['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'a'], ['b', 'c'],

			['b', 'e'], ['e', 'b'], ['e', 'c'], ['e', 'd'],

			['d', 'a'], ['d', 'c'], ['d', 'e'], ['c', 'a'],

			['c', 'b'], ['c', 'd'], ['c', 'e'] )

	print 'Drawing graph g1.svg'

	g1 = Graph.Graph (vertices, edges)

	DrawGraph ('g1', g1).render_graphviz ('g1.svg')

	vertices = range (11)

	edges = ( [0, 1], [0, 9], [0, 8], [8, 10], [8, 7], [9, 6], [9, 5],

			[6, 7], [1, 4], [1, 3], [1, 2], [2, 0] )

	print 'Drawing graph g2.svg'

	g2 = Graph.Graph (vertices, edges)

	DrawGraph ('g2', g2).render_graphviz ('g2.svg')

	vertices = range (3)

	edges = ( [0, 1], [1, 2], [2, 0] )

	print 'Drawing graph g3.svg'

	g3 = Graph.Graph (vertices, edges)

	DrawGraph ('g3', g3).render_graphviz ('g3.svg')

if __name__ == '__main__':

	main ()