38 votos

Teoría de grafos en python

¿Me preguntaba cómo tratan personas con teoría de grafos en python? ¿Cómo se guarda un gráfico? ¿Hay bibliotecas para esto?

¿Por ejemplo como sería un gráfico de la entrada y luego encontrar su cromática polinomios? ¿O su circunferencia? ¿O el número de árboles de expansión únicos? ¿Qué problemas que involucran el peso del borde como vendedor los problemas?

No necesito todos estos respondió, justo estoy buscando un conjunto de método o herramienta que será capaz de ayudarme a enfoque de resolver problemas como este.

Gracias, Dan

25voto

Chris Dennett Puntos 12396

esto podría ayudar - http://wiki.python.org/moin/PythonGraphApi. A partir de la página y rápida lookaround, python-gráfico parece bastante madura.

  • Apoyo dirigido, grafo, ponderado y no ponderado de los gráficos
  • Apoyo para hypergraphs
  • Canónica de operaciones
  • Importación y exportación XML
  • DOT-Lenguaje de importación y de exportación (para el uso con Graphviz)
  • Aleatorio de generación de gráficos
  • Accesibilidad (cierre transitivo)
  • Búsqueda en anchura
  • Ruta crítica algoritmo
  • Corte de vértice y del corte-borde de identificación
  • Ciclo de detección de
  • Búsqueda en profundidad
  • Búsqueda heurística (A* algoritmo)
  • Identificación de los componentes conectados
  • Máximo flujo / Mínimo de corte (Edmonds-Karp algoritmo)
  • Mínimo árbol de expansión (el algoritmo de Prim)
  • Mutuo-accesibilidad (fuertemente los componentes conectados)
  • La ruta más corta de búsqueda (Dijkstra algorithm)
  • La ruta más corta de búsqueda (Bellman-Ford algoritmo)
  • Topológico de la clasificación
  • Transitiva borde de identificación

18voto

gnibbler Puntos 103484

networkx

Características

Estándar de teoría de grafos y la física estadística funciones
Fácil intercambio de la red de algoritmos entre aplicaciones, las disciplinas y las plataformas
Muchos clásicos gráficos y redes sintéticas
Los nodos y las aristas pueden ser "cualquier cosa" (por ejemplo, series de tiempo, texto, imágenes, XML registros)
Explota código existente de alta calidad de legado de software en C, C++, Fortran, etc.
De código abierto (invita a la comunidad a la entrada)
La unidad probada

Beneficios adicionales de Python

Rápida creación de prototipos de nuevos algoritmos
Fácil de enseñar
Multi-plataforma
Permite un fácil acceso a casi cualquier base de datos

10voto

Haoran Wang Puntos 153

Hay un magnífico artículo http://www.python.org/doc/essays/graphs/

7voto

Tiago Peixoto Puntos 875

Me gustaría conectar descaradamente mi propia biblioteca gráfica de python: herramientas-gráfico.

Es muy rápido, ya que está implementado en C++ con la biblioteca gráfica de Boost, y contiene muchos algoritmos y extensa documentación.

7voto

makapuf Puntos 744

También puede echar un vistazo a NetworkX que ha avanzado bastante en algoritmos y capacidad de dibujo para los gráficos!

Desde el sitio web:

Características

* Standard graph-theoretic and statistical physics functions
* Easy exchange of network algorithms between applications, disciplines, and platforms
* Many classic graphs and synthetic networks
* Nodes and edges can be "anything" (e.g. time-series, text, images, XML records)
* Exploits existing code from high-quality legacy software in C, C++, Fortran, etc.
* Open source (encourages community input)
* Unit-tested

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X