Ich bin sehr neu in der Python-Programmierung und suche nach einem Algorithmus, der schnell alle Pfade zwischen einem Startknoten und einem Endknoten für einen sehr großen Graphen findet - etwa einen Graphen mit ungefähr 1000 Knoten und 10.000 Kanten. Die Anzahl der tatsächlich existierenden Pfade vom Startknoten zum Endknoten ist klein - zehn oder weniger. Um die Frage ein wenig zu kontextualisieren, ziehe ein soziales Netzwerk in Betracht - Wenn ich 1000 Freunde hätte und wissen möchte, wie viele Möglichkeiten mein bester Freund von der High School mit meinem Mitbewohner verbindet, ist mir egal, dass mein Der beste Freund von der High School ist mit allen 200 meiner Schulfreunde verbunden, weil diese Wege nie zu meinem Mitbewohner führen. Was ich mit diesem Python-Code machen möchte, ist, dass ich die Pfade, die zwischen meinen beiden Freunden existieren, schnell aufteilen und im Wesentlichen das ganze "Rauschen" beseitigen, das um diese beiden Knoten herum existiert.
Ich habe versucht, einige Code-Beispiele zu implementieren, die alle gut in kleinen, einfachen Graphen funktionieren. Wenn ich jedoch versuche, sie in meine große Graphanalyse zu integrieren, brauchen sie alle zu lange, um nützlich zu sein.
Haben Sie irgendwelche Vorschläge für Methoden, die untersucht werden sollen (z. B. etwas, das bereits in networkx erstellt wurde oder sogar Informationen zur Verwendung eines Stapels oder einer Rekursion usw.), zu implementierende Codebeispiele oder sogar andere Routen außerhalb von Python verfolgen? Denken Sie daran, ich bin ein Python-Neuling.
Persönlich würde ich empfehlen, dafür eine Graphdatenbank zu verwenden. Neo4j oder Rexter fallen mir in den Sinn.
Beim Zugriff auf diese von Python stehen ein paar Bibliotheken zur Verfügung:
Obwohl es nicht unmöglich wäre, eine schnelle / skalierbare Python-Version von diesen zu schreiben, gibt es momentan keinen, soweit ich weiß.