Bardzo szybki algorytm dla wszystkich ścieżek między dwoma węzłami

Question

Jestem bardzo nowy w kodowaniu Pythona i szukam algorytmu, który szybko znajdzie wszystkie ścieżki między węzłem początkowym a węzłem końcowym dla bardzo dużego wykresu - powiedzmy wykres ma około 1000 węzłów i 10 000 krawędzi. Liczba ścieżek, które faktycznie istnieją od węzła początkowego do węzła końcowego, jest mała - dziesięć lub mniej. Aby nieco uszczegółowić to pytanie, zastanów się nad siecią społecznościową - jeśli miałbym 1000 przyjaciół i chciałem wiedzieć, ile sposobów mój najlepszy przyjaciel z liceum łączy się z moim współlokatorem ze studiów, nie obchodzi mnie to, że mój najlepszy przyjaciel z liceum jest podłączony do wszystkich 200 moich przyjaciół ze szkoły średniej, ponieważ te ścieżki nigdy nie prowadzą do mojego współlokatora. Co chcę zrobić z tym kodem Pythona, szybko podzielę ścieżki, które istnieją między moimi dwoma przyjaciółmi i zasadniczo pozbywam się całego "szumu", który istnieje wokół tych dwóch węzłów.

Próbowałem wprowadzić wiele przykładów kodu, z których wszystkie działają dobrze na małych, prostych wykresach. Jednak, gdy próbuję włączyć je do mojej dużej analizy wykresów, wszystkie one trwają zbyt długo, aby były przydatne.

Czy wszyscy mają jakieś sugestie dotyczące metod badania (np. Coś, co zostało już stworzone w siecix, a nawet informacje na temat używania stosu vs. rekursji, itp.), Przykłady kodu do zaimplementowania lub nawet inne trasy poza pyton do ścigania? Pamiętaj, jestem początkującym pytonem.

Answer 1

Osobiście polecam używanie do tego bazy danych wykresów. Neo4j lub Rexter przychodzą na myśl.

Podczas uzyskiwania dostępu do nich z poziomu Pythona istnieje kilka bibliotek dostępne:

• http://bulbflow.com/overview/
• http://py2neo.org/

Chociaż nie byłoby możliwe, aby napisać szybko/skalowalną wersję Pythona z nich, teraz nie ma nikogo, o ile mi wiadomo.

Answer 2

Może chcesz wszystkie proste (bez powtarzających się węzłów) ścieżki między dwoma węzłami? NetworkX ma funkcję, która opiera się na pierwszym wyszukiwaniu. Zobacz http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html

przykładzie stamtąd pokazuje, że liczba prostych ścieżek mogą być duże:

>>> import networkx as nx 
>>> G = nx.complete_graph(4) 
>>> for path in nx.all_simple_paths(G, source=0, target=3): 
...  print(path) 
... 
[0, 1, 2, 3] 
[0, 1, 3] 
[0, 2, 1, 3] 
[0, 2, 3] 
[0, 3]