Hola,
Quería saber si alguien conocía alguna implementacion del TAD Grafos, en python. Obviamente, con clases. O a lo sumo, alguna ayuda de cómo hacerlo.
Desde ya, muchas gracias por su ayuda, un saludo!
Pablo.
21/11/2009, 12:36
| |||
| |||
| Implementacion grafos en python Hola, Quería saber si alguien conocía alguna implementacion del TAD Grafos, en python. Obviamente, con clases. O a lo sumo, alguna ayuda de cómo hacerlo. Desde ya, muchas gracias por su ayuda, un saludo! Pablo. |
|
23/11/2009, 09:04
| |||
| |||
| Respuesta: Implementacion grafos en python No conozco una implementación completa de un grafo, pero se me ocurre cómo implementarlo de forma relativamente sencilla. Creo que deberías crear una clase 'vertice' y representar las aristas como una lista de otros vértices. La lista es necesaria en tanto que no sabes cuántas aristas pueden salir de un vértice. Así, si la lista de vértices del vértice "a" contiene a "b", significa que existe una arista (a,b) Si luego la lista de "b" contiene a "a", quiere decir que existe (b,a) y por lo tanto existe {a,b} Si se tratase de un árbol binario podrías tener una clase "nodo" tal que cada objeto de esa clase tenga dos atributos (también de tipo "nodo") que sean los subnodos izquierdo y derecho. Sin más detalles es difícil ayudar más. Saludos. |
|
23/11/2009, 19:40
| |||
| |||
| Respuesta: Implementacion grafos en python Bueno, viendo que has respondido (desde ya, gracias por eso), te comento un poco más lo que ando ncesitando. Según lo que entendí, existen varias formas de implementar una GRAFO, y la mas conocidas son mediante una matriz de adyacencia, y una lista de adyacencia. En mi caso particular, me interesa la implementación que utiliza la lista de adyacencia, ya que ocupa menos espacio en memoria. Este tipo de implementacion se basa en una lista de todos los vertices, donde cada uno tenga a su vez otra lista con los vertices a los que está relacionado (digamos, el vertice A se relaciona con los vertices B,G y H, entonce en esa segunda lista, apareceria B,G y H). Ahora, lo que no se me ocurre, es como modelar el TDA en si. Me conviene crear una clase 'vertice', otra 'arista' y otra 'grafo', y dentro de la clase grafo crear metodos que representen las primitivas del TDA? O de que otra forma se te ocurre que sería factible realizarlo? Con respecto a lo del arbol binario, en principio, tendría que ser un grafo genérico. Luego, más adelante y mediante el algortimo de ¿Prim?, la idea sería convertirla en un arbol minimo. Pero por el momento, solo necesito el Grafo en sí. Es más, si se te ocurre cualquier otra cosa a la hora de implementarlo, completamente distinta a lo que he planteado, desde ya, que es más que bienvenido tu aporte/ayuda! Un saludo, y nuevamente, gracias! Pablo |
|
23/11/2009, 20:32
| |||
| |||
| Respuesta: Implementacion grafos en python Recientemente tuve que modelar árboles y listas en Modula-2, así que tengo el tema de los TDA bastante fresco  Yo lo haría simplemente con una clase vértice que contenga una lista (llámala "aristas" si quieres) de otros vértices. De esta forma un grafo sería un conjunto de vértices, creo que haciendo una clase Grafo cuyos objetos contengan una lista de vértices sería suficiente Saludos. |
|
24/11/2009, 09:28
| |||
| |||
| Respuesta: Implementacion grafos en python Claro, la clase arista está de más. Y las primitivas (digamos, insertar_vertice, obtener_vertice, etc), sería métodos de la clase Grafo, no es cierto? Creo que con esto termino de cerrar mi idea. Desde ya, muchas gracias! Pablo |
|
09/12/2009, 21:37
| |||
| |||
| Respuesta: Implementacion grafos en python Bueno, vuelvo aca y me doy cuenta que.. me había olvidado de agradecer tu post, Alvaro! Desde ya, comento que lo he hecho asi, asique.. muchas gracias! Un saludo, Pablo |
