Re: Designing a graph study program
On 10 Mag, 16:52, Alexander Schliep <[EMAIL PROTECTED]> wrote: > andrea <[EMAIL PROTECTED]> writes: > > On 9 Mag, 09:10, Alexander Schliep <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
andrea <[EMAIL PROTECTED]> writes: > On 9 Mag, 09:10, Alexander Schliep <[EMAIL PROTECTED]> wrote: >> Check outhttp://gato.sf.net(LGPL license). 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 paper http://algorithmics.molgen.mpg.de/preprints/2000-CATBox-MTCM.pdf describing the ideas. Best, Alexander -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
On 9 Mag, 09:10, Alexander Schliep <[EMAIL PROTECTED]> wrote: > andrea <[EMAIL PROTECTED]> writes: > > Well then I wanted to draw graphs and I found that pydot is working > > really nicely. > > BUT I'd like to do this, an interactive program to see ho the > > algorithms works... > > For example in the breath search first, every time the algorithm > > colors a node, the program should redraw the graphs. Which modules > > should I use for graphics (I use macosX and I'd like something cross > > platforms). > > Check outhttp://gato.sf.net(LGPL license). 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). > > There is a Springer textbook forthcoming. We are also starting to collect > contributed algorithms, which we would like to make available from > our website. > > Full disclosure: I am the author of Gato > > Best, > Alexander Very very nice well done! I'd like to do something similar, just to learn something new... Could you explain me how you designed it?? How is the step mechanism done?? Any advices? -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
andrea <[EMAIL PROTECTED]> writes: > Well then I wanted to draw graphs and I found that pydot is working > really nicely. > BUT I'd like to do this, an interactive program to see ho the > algorithms works... > For example in the breath search first, every time the algorithm > colors a node, the program should redraw the graphs. Which modules > should I use for graphics (I use macosX and I'd like something cross > platforms). Check out http://gato.sf.net (LGPL license). 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). There is a Springer textbook forthcoming. We are also starting to collect contributed algorithms, which we would like to make available from our website. Full disclosure: I am the author of Gato Best, Alexander -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
In <[EMAIL PROTECTED]>, andrea wrote: > Interesting but what do you mean for two graph-implementatio that > share the same interface?? > I don't have abstract classes or interfaces in python, am I wrong? You are thinking of some kind of types or enforcements. If two classes have some methods with the same names and the same semantics they share the same interface. And a class that isn't meant to be instantiated or doesn't implement all methods is an abstract class. Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
On 8 Mag, 13:55, "Diez B. Roggisch" <[EMAIL PROTECTED]> wrote: > > Ok thank you very much I'll try with that. > > But I have some design doubts, I'd like to keep the algorithm (for > > example bfs) as clean as possible, being independent from the drawing > > methods. > > And how could I make it step through algorithms without having a more > > complicated code? Maybe using threads? > > Along the lines of what Marc said: > > Use two graph-implementations that share the same interface regarding the > algorithms, but one will emit events to some observer for each operation on > the graph - edge/node adding/removal, attribute changing and so forth. > > Thus the algorithm is kept clean, and all that you can visualize anyway is > available to you. > > diez Interesting but what do you mean for two graph-implementatio that share the same interface?? I don't have abstract classes or interfaces in python, am I wrong? Thanks -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
> Ok thank you very much I'll try with that. > But I have some design doubts, I'd like to keep the algorithm (for > example bfs) as clean as possible, being independent from the drawing > methods. > And how could I make it step through algorithms without having a more > complicated code? Maybe using threads? Along the lines of what Marc said: Use two graph-implementations that share the same interface regarding the algorithms, but one will emit events to some observer for each operation on the graph - edge/node adding/removal, attribute changing and so forth. Thus the algorithm is kept clean, and all that you can visualize anyway is available to you. diez -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
In <[EMAIL PROTECTED]>, andrea wrote: > But I have some design doubts, I'd like to keep the algorithm (for > example bfs) as clean as possible, being independent from the drawing > methods. > And how could I make it step through algorithms without having a more > complicated code? Maybe using threads? Create an API that informs some "observer" about actions like visiting a node, traversing or adding an egde and so on. This way you can register callbacks that translate between the graph and the GUI. If you don't want to change the algorithm or graph and node classes this notification can be injected by wrapper classes to some degree. For very fine grained observation of an algorithm you might try to implement a step by step debugger. Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
On 8 Mag, 13:02, "Diez B. Roggisch" <[EMAIL PROTECTED]> wrote: > > Well then I wanted to draw graphs and I found that pydot is working > > really nicely. > > BUT I'd like to do this, an interactive program to see ho the > > algorithms works... > > For example in the breath search first, every time the algorithm > > colors a node, the program should redraw the graphs. Which modules > > should I use for graphics (I use macosX and I'd like something cross > > platforms). > > Use the bundled Tkinter. I've implemented a similar thing back in my under > graduation days using TCL/Tk, and Tk is perfectly suited for that task. > > Diez Ok thank you very much I'll try with that. But I have some design doubts, I'd like to keep the algorithm (for example bfs) as clean as possible, being independent from the drawing methods. And how could I make it step through algorithms without having a more complicated code? Maybe using threads? Thanks -- http://mail.python.org/mailman/listinfo/python-list
Re: Designing a graph study program
> > Well then I wanted to draw graphs and I found that pydot is working > really nicely. > BUT I'd like to do this, an interactive program to see ho the > algorithms works... > For example in the breath search first, every time the algorithm > colors a node, the program should redraw the graphs. Which modules > should I use for graphics (I use macosX and I'd like something cross > platforms). Use the bundled Tkinter. I've implemented a similar thing back in my under graduation days using TCL/Tk, and Tk is perfectly suited for that task. Diez -- http://mail.python.org/mailman/listinfo/python-list
Designing a graph study program
I'm studying some graphs algorithm (minumum spanning tree, breath search first topological sort etc etc...) and to understand better the theory I'm implementing them with python... I made my own graph class, the constructor is simply this: class graph: "in forma di matrice e' una matrice normale, in forma di lista uso un dizionario" def __init__(self,nodes,edges,dir=False,weight=[]): # inizializzatore dell'oggetto, di default in forma di lista di adiacenza e undirected # il grafo puo' essere anche pesato "di default uso la lista di adiacenza per rappresentare il grafo, usare set" self.adj_list = {} self.nodes = nodes self.edges = edges # in modo da avere comodi questi dati, se bidirezionale non ci sono tutti self.weight = weight self.dir = dir # anche questo deve essere raggiungibile for n in nodes: self.adj_list[n] = [] for n in nodes: for e in edges: if dir: # se ho la direzione guardo l'ordine dei vertici nel lato if n == e[0]: self.adj_list[n].append(e[1]) elif n in e: other = e[((e.index(n))+1) % 2] self.adj_list[n].append(other) if weight: self.w = {} for idx in range(len(edges)): self.w[edges[idx]] = weight[idx] # assegno in corrispondenza Well then I wanted to draw graphs and I found that pydot is working really nicely. BUT I'd like to do this, an interactive program to see ho the algorithms works... For example in the breath search first, every time the algorithm colors a node, the program should redraw the graphs. Which modules should I use for graphics (I use macosX and I'd like something cross platforms). Now I'm doing something like this def draw_graph(self): """disegna un grafo con pydot""" import os output = 'graph.png' self.dot_graph.write_png(output) com = 'open '+output os.popen(com) which I think is very ugly and not fitting very well for my purpose. I also created a class to represent matrix (for the matrix view of the graph) but I found that numpy has a very complete implementation, I think I'll go with it. Thank you very much, if you have any kind of suggestions/links please write it :) -- http://mail.python.org/mailman/listinfo/python-list