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 old version on school computers

from PyCompat import *

import Graph

if have_yapgvb():

	import yapgvb

class Key (object):

	"""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 (object):

	"""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.

		NOTE: This tells us HOW each node was generated, not the path taken

		through the graph. Use render_graphviz() for a MUCH improved visualization"""

		if prop == None:

			raise ValueError # no propery given

		g = self.__graph

		# Get the vertices sorted in the order in which they were added to

		# the graph.

		sorted_vertices = [(int (g.get_vertex_value (v)), g.vertices[v].raw_obj)

					for v in g.vertices.keys()]

		sorted_vertices.sort()

		for v in sorted_vertices:

			print getattr (v[1], prop),

		print

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

	def render_graphviz (self, filename, layout_engine=yapgvb.engines.neato):

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

		to SVG, PNG, and JPG."""

		if not have_yapgvb():

			raise ValueError # must have yapgvb installed

		dg = yapgvb.Graph (self.__name)

		g = self.__graph

		visited = []

		for v in g.vertices.keys():

			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 ()