473,324 Members | 2,535 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

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 :)

May 8 '07 #1
10 1877
>
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
May 8 '07 #2
On 8 Mag, 13:02, "Diez B. Roggisch" <d...@nospam.web.dewrote:
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

May 8 '07 #3
In <11**********************@n59g2000hsh.googlegroups .com>, 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
May 8 '07 #4
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
May 8 '07 #5
On 8 Mag, 13:55, "Diez B. Roggisch" <d...@nospam.web.dewrote:
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

May 8 '07 #6
In <11**********************@l77g2000hsb.googlegroups .com>, 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
May 8 '07 #7
andrea <ke******@gmail.comwrites:
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

May 9 '07 #8
On 9 Mag, 09:10, Alexander Schliep <schl...@molgen.mpg.dewrote:
andrea <kerny...@gmail.comwrites:
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?

May 10 '07 #9
andrea <ke******@gmail.comwrites:
On 9 Mag, 09:10, Alexander Schliep <schl...@molgen.mpg.dewrote:
>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/pr...ATBox-MTCM.pdf
describing the ideas.

Best,
Alexander
May 10 '07 #10
On 10 Mag, 16:52, Alexander Schliep <schl...@molgen.mpg.dewrote:
andrea <kerny...@gmail.comwrites:
On 9 Mag, 09:10, Alexander Schliep <schl...@molgen.mpg.dewrote:
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

Jun 7 '07 #11

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: KevinGPO | last post by:
I am making a monitor program for the PC. My monitor program will grab statistics about CPU and memory every 1 or 5 seconds. Then I want to store this data so I have a history and hence be able to...
1
by: Randy Powell | last post by:
HI folks, I'm a neophyte Access administrator and user. I've got a database working pretty well that I received a lot of help on here. Thanks! I supervise a small children's crisis program and...
1
by: entropy123 | last post by:
Hey all, In an effort to solve a sticky - for me - problem I've picked up Sedgewick's 'Algorithm's in C'. I've tried working through the first few problems but am a little stumped when he refers...
11
by: Chapman | last post by:
Is it possible to plot the graph as an output of my program in C? It can be a simple graph as quadratic curves for example or a correlation between 2 variables only. Thanks
11
by: Andreas.Burman | last post by:
Hi What is the best way to implement a undirected weighted graph ADT in javascript?
4
by: John Henry | last post by:
I am looking for a ready made simple graph package. I found an extensive one in the piana package but when I try to use just the graph portion, it fails to load because of the line: class...
1
by: mpalazzo | last post by:
I'm doing some graph manipulation in VBA, and have made a reference (and am using successfully) the Graph.exe for MS Office. My problem is that I can't be sure exactly what version of Access my end...
4
by: Man4ish | last post by:
namespace ve/////////////////ve.h { struct VertexProperties { std::size_t index; boost::default_color_type color; }; }...
2
by: khacthuy | last post by:
I need to write a program with content: Colored plane graphs. Tell people what I know. I always code for the study. Thanks please send me mail: khacthuy.3k@gmail.com I come from VietNamese...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.