Subversion Repositories programming

Rev

Rev 391 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 391 Rev 395
Line 2... Line 2...
2 
 
 2 
 
3 
__author__    = "Ira W. Snyder (devel@irasnyder.com)"
 3 
__author__    = "Ira W. Snyder (devel@irasnyder.com)"
4 
__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"
 4 
__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"
5 
__license__   = "GNU GPL v2 (or, at your option, any later version)"
 5 
__license__   = "GNU GPL v2 (or, at your option, any later version)"
6 
 
 6 
 
- 
 
 7 
# Fix for the lame version of python on the school's computers (v2.1)
- 
 
 8 
try:
- 
 
 9 
	(True, False)
- 
 
 10 
except NameError:
- 
 
 11 
	(True, False) = (1, 0)
- 
 
 12 
 
- 
 
 13 
# Make sure not to try graphviz if it's not installed (school again)
- 
 
 14 
no_graphviz = False
- 
 
 15 
try:
- 
 
 16 
	import yapgvb
- 
 
 17 
except:
- 
 
 18 
	no_graphviz = True
- 
 
 19 
 
7 
import Graph
 20 
import Graph
8 
import yapgvb
 - 
 
9 
 
 21 
 
10 
class Key (object):
 22 
class Key:
11 
	"""A class that makes a unique key for each pair of vertices."""
 23 
	"""A class that makes a unique key for each pair of vertices."""
12 
 
 24 
 
13 
	def __init__ (self, v1, v2):
 25 
	def __init__ (self, v1, v2):
14 
		self.__key = [v1, v2]
 26 
		self.__key = [v1, v2]
15 
		self.__key.sort ()
 27 
		self.__key.sort ()
16 
 
 28 
 
17 
	def __eq__ (self, rhs):
 29 
	def __eq__ (self, rhs):
18 
		return (self.__key[0] == rhs.__key[0]) and (self.__key[1] == rhs.__key[1])
 30 
		return (self.__key[0] == rhs.__key[0]) and (self.__key[1] == rhs.__key[1])
19 
 
 31 
 
20 
 
 32 
 
21 
class DrawGraph (object):
 33 
class DrawGraph:
22 
	"""A class that will draw an unweighted, undirected graph given the vertices and
 34 
	"""A class that will draw an unweighted, undirected graph given the vertices and
23 
	edges in the same form that is used for the Graph class."""
 35 
	edges in the same form that is used for the Graph class."""
24 
 
 36 
 
25 
	def __init__ (self, name, graph):
 37 
	def __init__ (self, name, graph):
26 
		"""Constructor"""
 38 
		"""Constructor"""
27 
		self.__name = str(name)
 39 
		self.__name = str(name)
28 
		self.__graph = graph
 40 
		self.__graph = graph
29 
 
 41 
 
- 
 
 42 
	def render_stupid (self, prop=None):
- 
 
 43 
		"""Print the graph using the not very good method of telling whether
- 
 
 44 
		   we go up,down,left,right between every node."""
- 
 
 45 
		if prop == None:
- 
 
 46 
			raise ValueError # no propery given
- 
 
 47 
 
- 
 
 48 
		g = self.__graph
- 
 
 49 
		added = True
- 
 
 50 
		count = 0
- 
 
 51 
 
- 
 
 52 
		while added:
- 
 
 53 
			added = False
- 
 
 54 
 
- 
 
 55 
			for v in g.vertices.keys():
- 
 
 56 
				if g.get_vertex_value (v) == str(count):
- 
 
 57 
					print getattr (g.vertices[v].raw_obj, prop),
- 
 
 58 
					added = True
- 
 
 59 
 
- 
 
 60 
			count += 1
- 
 
 61 
 
- 
 
 62 
		print # nothing, to end the getattr() print above
- 
 
 63 
		print '%d nodes in the solution' % len(g.vertices)
- 
 
 64 
 
30 
	def render_graph (self, filename, layout_engine=yapgvb.engines.neato):
 65 
	def render_graphviz (self, filename, layout_engine=yapgvb.engines.neato):
31 
		"""Draw the graph given into the file given. This will render
 66 
		"""Draw the graph given into the file given. This will render
32 
		to SVG, PNG, and JPG."""
 67 
		to SVG, PNG, and JPG."""
- 
 
 68 
 
- 
 
 69 
		if no_graphviz:
- 
 
 70 
			raise ValueError # no yapgvb / graphviz installed!
- 
 
 71 
 
33 
		dg = yapgvb.Graph (self.__name)
 72 
		dg = yapgvb.Graph (self.__name)
34 
		g = self.__graph
 73 
		g = self.__graph
35 
 
 74 
 
36 
		visited = []
 75 
		visited = []
37 
 
 76 
 
Line 64... Line 103...
64 
			['d', 'a'], ['d', 'c'], ['d', 'e'], ['c', 'a'],
 103 
			['d', 'a'], ['d', 'c'], ['d', 'e'], ['c', 'a'],
65 
			['c', 'b'], ['c', 'd'], ['c', 'e'] )
 104 
			['c', 'b'], ['c', 'd'], ['c', 'e'] )
66 
 
 105 
 
67 
	print 'Drawing graph g1.svg'
 106 
	print 'Drawing graph g1.svg'
68 
	g1 = Graph.Graph (vertices, edges)
 107 
	g1 = Graph.Graph (vertices, edges)
69 
	DrawGraph ('g1', g1).render_graph ('g1.svg')
 108 
	DrawGraph ('g1', g1).render_graphviz ('g1.svg')
70 
 
 109 
 
71 
	vertices = range (11)
 110 
	vertices = range (11)
72 
	edges = ( [0, 1], [0, 9], [0, 8], [8, 10], [8, 7], [9, 6], [9, 5],
 111 
	edges = ( [0, 1], [0, 9], [0, 8], [8, 10], [8, 7], [9, 6], [9, 5],
73 
			[6, 7], [1, 4], [1, 3], [1, 2], [2, 0] )
 112 
			[6, 7], [1, 4], [1, 3], [1, 2], [2, 0] )
74 
 
 113 
 
75 
	print 'Drawing graph g2.svg'
 114 
	print 'Drawing graph g2.svg'
76 
	g2 = Graph.Graph (vertices, edges)
 115 
	g2 = Graph.Graph (vertices, edges)
77 
	DrawGraph ('g2', g2).render_graph ('g2.svg')
 116 
	DrawGraph ('g2', g2).render_graphviz ('g2.svg')
78 
 
 117 
 
79 
	vertices = range (3)
 118 
	vertices = range (3)
80 
	edges = ( [0, 1], [1, 2], [2, 0] )
 119 
	edges = ( [0, 1], [1, 2], [2, 0] )
81 
 
 120 
 
82 
	print 'Drawing graph g3.svg'
 121 
	print 'Drawing graph g3.svg'
83 
	g3 = Graph.Graph (vertices, edges)
 122 
	g3 = Graph.Graph (vertices, edges)
84 
	DrawGraph ('g3', g3).render_graph ('g3.svg')
 123 
	DrawGraph ('g3', g3).render_graphviz ('g3.svg')
85 
 
 124 
 
86 
 
 125 
 
87 
if __name__ == '__main__':
 126 
if __name__ == '__main__':
88 
	main ()
 127 
	main ()
89 
 
 128