Designing a graph study program

[andrea]

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

 

[Diez B. Roggisch]

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

 

[andrea]

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

 

[Marc 'BlackJack' Rintsch]

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

 

[Diez B. Roggisch]

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

 

[andrea]

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

 

[Marc 'BlackJack' Rintsch]

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

 

[Alexander Schliep]

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

 

[andrea]

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?

 

[Alexander Schliep]

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

 

[andrea]

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.


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