estructura de datos: grafo dirigido

[Martín Gaitán]

hola gente:

tengo que implementar un programita 'simulador de trafico de redes'
(ejercicio teorico) que basicamente trabaja con grafos dirigidos que
representan un red de routers con el 'costo' de transferencias de
paquetes entre ellos.

luego usa el algoritmo de dijkstra para encontrar el camino menos
costoso para enviar los paquetes de un punto a otro.

la cuestion es: cual es la forma mas conveniente de implementar una
estructura de grafos con aristas con peso no simétrico ? incluye
python algo ya implementado ?

en este ejemplo
http://www.ece.uci.edu/~chou/py02/python.html#Fig-3

proponen una estructura de diccionarios que contienen diccionarios

por ejemplo
L = {'A': {'C':2, 'D':6}, 'B': {'D':8, 'A':3},
'C': {'D':7, 'E':5}, 'D': {'E':-2}, 'E': {}}
que representa que el nodo A esta conectado al C con costo 2 y al D con 6, etc.

les parece optima?

en wikipedia hay un ejemplo de implementacion de dijkstra que usa otra
estructura en la que intervienen tuplas para definir la arista (nodo,
peso).

[1] http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#Python


saludos.
tin

[Juanjo Conti]

Pegale una mirada a esto: http://www.python.org/doc/essays/graphs.html

Un saludo

Juanjo

[Guillermo Garcia]

Otra opción es la clase Graph en los fuentes del libro AIMA:

http://aima-python.googlecode.com/svn/trunk/search.py

*
*

Post by Juanjo Conti
Pegale una mirada a esto: http://www.python.org/doc/essays/graphs.html
Un saludo
Juanjo

[Alejandro J. Cura]

Post by Martín Gaitán
tengo que implementar un programita 'simulador de trafico de redes'
(ejercicio teorico) que basicamente trabaja con grafos dirigidos que
representan un red de routers con el 'costo' de transferencias de
paquetes entre ellos.
luego usa el algoritmo de dijkstra para encontrar el camino menos
costoso para enviar los paquetes de un punto a otro.
la cuestion es: cual es la forma mas conveniente de implementar una
estructura de grafos con aristas con peso no simétrico ? incluye
python algo ya implementado ?
en este ejemplo
http://www.ece.uci.edu/~chou/py02/python.html#Fig-3
proponen una estructura de diccionarios que contienen diccionarios
por ejemplo
L = {'A': {'C':2, 'D':6}, 'B': {'D':8, 'A':3},
'C': {'D':7, 'E':5}, 'D': {'E':-2}, 'E': {}}
que representa que el nodo A esta conectado al C con costo 2 y al D con 6, etc.
les parece optima?
en wikipedia hay un ejemplo de implementacion de dijkstra que usa otra
estructura en la que intervienen tuplas para definir la arista (nodo,
peso).
[1] http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#Python

La otra opcion es usar NetworkX, una biblioteca que ya tiene todo eso
implementado: https://networkx.lanl.gov/wiki/Tutorial
Fijate que hasta tenes dijkstra:
https://networkx.lanl.gov/wiki/QuickReference#nodal-properties

Saludos,

[Martín Gaitán]

Post by Alejandro J. Cura
La otra opcion es usar NetworkX, una biblioteca que ya tiene todo eso
implementado: https://networkx.lanl.gov/wiki/Tutorial
https://networkx.lanl.gov/wiki/QuickReference#nodal-properties
Saludos,
--
alecu

Perfecto!
Estaba usando pydot para graficar los grafos pero esto no solo grafica
(mediante matplotlib), sino que tiene incorporados todos los metodos
que necesito. genial!

gracias.
tin

[Martín Gaitán]

Post by Alejandro J. Cura
La otra opcion es usar NetworkX, una biblioteca que ya tiene todo eso
implementado: https://networkx.lanl.gov/wiki/Tutorial

como dije, la libreria está genial... pero necesito hacer algo simple
y no encuetro la aguja en el pajar: cuando dibujo el grafo quiero que
los edges tengan su valor (entero) como label.

se puede?

uso un objeto XGraph por lo que las aristas tienen su valor. como lo
muestro en el dibujito cuando hago

networkx.draw(grafo)
pylab.show()


?
acá la docu del metodo draw y sus derivados.

https://networkx.lanl.gov/reference/networkx/networkx.drawing.nx_pylab-module.html#draw

[Alejandro J. Cura]

Post by Martín Gaitán
como dije, la libreria está genial... pero necesito hacer algo simple
y no encuetro la aguja en el pajar: cuando dibujo el grafo quiero que
los edges tengan su valor (entero) como label.

Por lo que veo, necesitas hacerlo (mas o menos) a mano.
Te paso un ejemplo de como. Tal vez tendría que ir al cookbook :-)

Saludos,