Designing a graph study program

[andrea]

On 10 Mag, 16:52, Alexander Schliep <schl... at molgen.mpg.de> wrote:
> andrea <kerny... at gmail.com> writes:
> > On 9 Mag, 09:10, Alexander Schliep <schl... at molgen.mpg.de> wrote:
> >> Check outhttp://gato.sf.net(LGPLlicense). It does exactly what you
> >> want to do and there is a binary for MacOS X. Algorithms are implemented
> >> using Gato's graph class and rudimentary visualizations you get for free
> >> by replacing standard data structures (e.g., a vertex queue) by
> >> animated ones (AnimatedVertexQueue).
>
> > Very very nice well done!
>
> Thanks.
>
> > I'd like to do something similar, just to learn something new...
>
> Gato is open source and I'd be happy to collaborate. There are quite a
> few areas (e.g. SVG export, displays for data structure contents, more
> complete 3D support, polygon edges, running backwards?) which need
> work.
>
> > Could you explain me how you designed it?? How is the step mechanism
> > done??
>
> The algorithm is executed by a subclass of the Python debugger (see
> Gato.py).  A Tk event mechanism is used to step to the next line if
> you are in running mode. Otherwise the user steps manually. The
> visualizations are done with animated data structures, which animate
> changes to their internal state with respect to the graph: e.g., when
> you add or remove v to/from an AnimatedVertexQueue it changes v's
> color.
>
> Tk has a canvas which does object-oriented drawing. A line is not
> just a bunch of pixels but rather an object which you can move,
> scale, has callbacks. I dislike Tcl, but Tk is amazing, even it
> it looks 1980s.
>
> There is a paperhttp://algorithmics.molgen.mpg.de/preprints/2000-CATBox-MTCM.pdf
> describing the ideas.
>
> Best,
> Alexander

Ok thanks a lot for the explanation Alexander...

Well I changed my implementation of edges and nodes to this:

class node:
	"""nodi di un grafo"""
	def __init__(self, label, color=None, parent=None, distance=None):
		self.label = label
		self.color = color
		self.parent = parent
		self.distance = distance

	def __eq__(self,y):
		"""uguaglianza fra nodi"""
		return self.label == y.label

	def __repr__(self):
		"""docstring for __repr__"""
		return str(self.label)


class edge: # CHANGED tutta la gestione di nodi e lati
	"""lato di un grafo"""
	def __init__(self, u, v, directed=False, w=1):
		"due lati ed eventualmente il peso associato"
		self.u = u
		self.v = v
		self.w = w
		self.directed = directed


	def __repr__(self):
		"""docstring for __repr__"""
		if self.directed:
			sym = " --> "
		else:
			sym = " --- "
		return str(self.u) + sym + str(self.v)

	def __eq__(self,y):
		if self.directed != y.directed:
			return False
		r = (self.u == y.u and self.v == y.v)
		l = (self.v == y.u and self.u == y.v)
		if self.directed: # gia controllato che non siano diversi
			return r
		else:
			return r or l


Does it make sense??
But now I have some troubles with all the rest ;)
For example this code

def make_adj_list(self,nodes,edges):
		"""crea la lista di adiacenza"""
		adj_list = {}
		for v in nodes:
			adj_list[v] = []
       ...
builds an adjacency list of the graph, but now the object Node is not
hashable of course!
How do I manage this? I think I can use the label
adj_list[v.label] = [u.label, etc etc]
but then I need another dictionary to go from labels to objects, it's
not difficult but look ugly to me, other solutions??

Thanks a lot