Théorie des graphes en python

Question

Je me demandais comment les gens traitent la théorie des graphes en python ? Comment un graphe est-il stocké ? Existe-t-il des bibliothèques pour cela ?

Par exemple, comment puis-je entrer un graphique et ensuite trouver son polynôme chromatique ? Ou sa circonférence ? Ou le nombre d'arbres uniques ? Qu'en est-il des problèmes qui impliquent le poids des bords comme les problèmes de vendeur ?

Je n'ai pas besoin de réponses à toutes ces questions, je cherche simplement une méthode ou un ensemble d'outils qui pourront m'aider à résoudre des problèmes de ce type.

Merci, Dan

Answer 1

Ceci pourrait aider - http://wiki.python.org/moin/PythonGraphApi . De la page et un rapide tour d'horizon, python-graph semble assez mature.

• Prise en charge des graphes dirigés, non dirigés, pondérés et non pondérés.
• Prise en charge des hypergraphes
• Opérations canoniques
• Importation et exportation XML
• Importation et exportation du langage DOT (pour utilisation avec Graphviz)
• Génération aléatoire de graphes
• Accessibilité (fermeture transitive)
• Recherche en largeur d'abord
• Algorithme du chemin critique
• Identification des sommets et des arêtes coupés
• Détection des cycles
• Recherche en profondeur
• Recherche heuristique (algorithme A*)
• Identification des composants connectés
• Flux maximal / Coupe minimale (algorithme d'Edmonds-Karp)
• Arbre de portée minimale (algorithme de Prim)
• Accessibilité mutuelle (composants fortement connectés)
• Recherche du plus court chemin (algorithme de Dijkstra)
• Recherche du plus court chemin (algorithme de Bellman-Ford)
• Tri topologique
• Identification des bords transitifs

Answer 2

networkx

Caractéristiques

Fonctions standard de la théorie des graphes et de la physique statistique
Échange facile d'algorithmes de réseau entre les applications, les disciplines et les plateformes.
De nombreux graphes classiques et réseaux synthétiques
Les nœuds et les arêtes peuvent être "n'importe quoi" (par exemple, des séries chronologiques, du texte, des images, des enregistrements XML).
Exploitation du code existant de logiciels hérités de haute qualité en C, C++, Fortran, etc.
Source ouverte (encourage la contribution de la communauté)
Testé à l'unité

Avantages supplémentaires de Python

Prototypage rapide de nouveaux algorithmes
Facile à enseigner
Multi-plateforme
Permet d'accéder facilement à presque toutes les bases de données

Answer 3

Il y a un article merveilleux http://www.python.org/doc/essays/graphs/

Answer 4

Vous pouvez également jeter un coup d'œil à NetworkX qui possède des algorithmes assez avancés et des capacités de dessin pour les graphiques !

Sur le site web :

Caractéristiques

* 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

Answer 5

Je voudrais faire la promotion sans vergogne de ma propre bibliothèque de graphes en Python : outil graphique .

Il est très rapide, car il est implémenté en C++ avec la bibliothèque graphique Boost, et il contient de nombreux algorithmes et une documentation complète.