Subversion Repositories programming

Rev

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

Rev 376 Rev 379
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 
class Edge (object):
- 
 
 8 
	def __init__ (self, color='black', label=''):
- 
 
 9 
		self.color = color
- 
 
 10 
		self.label = label
- 
 
 11 
 
7 
class Graph:
 12 
class Graph:
8 
	"""Class that will handle weighted, undirected graphs. It can have
 13 
	"""Class that will handle weighted, undirected graphs. It can have
9 
	   arbitrary data stored at each vertex. Note that the simple way
 14 
	   arbitrary data stored at each vertex. Note that the simple way
10 
	   of creating a graph does not allow you to assign data, you must
 15 
	   of creating a graph does not allow you to assign data, you must
11 
	   do it manually."""
 16 
	   do it manually."""
Line 32... Line 37...
32 
		"""Add a vertex to the graph"""
 37 
		"""Add a vertex to the graph"""
33 
		if self.has_vertex (label):
 38 
		if self.has_vertex (label):
34 
			raise ValueError
 39 
			raise ValueError
35 
 
 40 
 
36 
		# Create vertex and set the value
 41 
		# Create vertex and set the value
37 
		self.set_value (label, data)
 42 
		self.set_vertex_value (label, data)
38 
 
 43 
 
39 
	def add_edge (self, v1, v2, weight=1):
 44 
	def add_edge (self, v1, v2, color='black', label=''):
40 
		"""Add an edge from v1 to v2 (undirected)"""
 45 
		"""Add an edge from v1 to v2 (undirected)"""
41 
 
 46 
 
42 
		key = self.__get_key (v1, v2)
 47 
		key = self.__get_key (v1, v2)
43 
 
 48 
 
44 
		if self.has_vertex (v1) and self.has_vertex (v2):
 49 
		if self.has_vertex (v1) and self.has_vertex (v2):
45 
			self.edges[key] = weight
 50 
			self.edges[key] = Edge (color, label)
46 
		else:
 51 
		else:
47 
			raise ValueError
 52 
			raise ValueError
48 
 
 53 
 
49 
	def has_edge (self, v1, v2):
 54 
	def has_edge (self, v1, v2):
50 
		"""Check if an edge exists in this graph"""
 55 
		"""Check if an edge exists in this graph"""
Line 75... Line 80...
75 
					if i != v:
 80 
					if i != v:
76 
						children.add (i)
 81 
						children.add (i)
77 
 
 82 
 
78 
		return list(children)
 83 
		return list(children)
79 
 
 84 
 
80 
	def set_value (self, v, data):
 85 
	def set_vertex_value (self, v, data):
81 
		"""Store some data at a vertex"""
 86 
		"""Store some data at a vertex"""
82 
		self.vertices[v] = data
 87 
		self.vertices[v] = data
83 
 
 88 
 
84 
	def get_value (self, v):
 89 
	def get_vertex_value (self, v):
85 
		"""Get the data at a vertex"""
 90 
		"""Get the data at a vertex"""
86 
		return self.vertices[v]
 91 
		return self.vertices[v]
87 
 
 92 
 
- 
 
 93 
	def set_edge_color (self, v1, v2, color):
- 
 
 94 
		if not self.has_edge (v1, v2):
- 
 
 95 
			raise ValueError
- 
 
 96 
 
- 
 
 97 
		key = self.__get_key (v1, v2)
- 
 
 98 
		self.edges[key].color = color
- 
 
 99 
 
- 
 
 100 
	def get_edge_color (self, v1, v2):
- 
 
 101 
		if not self.has_edge (v1, v2):
- 
 
 102 
			raise ValueError
- 
 
 103 
 
- 
 
 104 
		key = self.__get_key (v1, v2)
- 
 
 105 
		return self.edges[key].color
- 
 
 106 
 
- 
 
 107 
	def get_edge_label (self, v1, v2):
- 
 
 108 
		if not self.has_edge (v1, v2):
- 
 
 109 
			raise ValueError
- 
 
 110 
 
- 
 
 111 
		key = self.__get_key (v1, v2)
- 
 
 112 
		return self.edges[key].label
- 
 
 113 
 
- 
 
 114 
	def set_edge_label (self, v1, v2, label):
- 
 
 115 
		if not self.has_edge (v1, v2):
- 
 
 116 
			raise ValueError
- 
 
 117 
 
- 
 
 118 
		key = self.__get_key (v1, v2)
- 
 
 119 
		self.edges[key].label = label
- 
 
 120 
 
88 
 
 121 
 
89 
################################################################################
 122 
################################################################################
90 
###                      Tests are below this point                          ###
 123 
###                      Tests are below this point                          ###
91 
################################################################################
 124 
################################################################################
92 
 
 125