Algoritmo molto veloce per tutti i percorsi tra due nodi

Question

Sono molto nuovo alla codifica di Python e sto cercando un algoritmo che trovi rapidamente tutti i percorsi tra un nodo iniziale e un nodo finale per un grafico molto grande - ad esempio un grafico che ha circa 1000 nodi e 10.000 bordi. Il numero di percorsi effettivamente esistenti dal nodo iniziale al nodo finale è di dimensioni inferiori o inferiori a dieci. Per aiutare a contestualizzare la domanda un po 'di più, considera un social network - Se avessi 1000 amici e volevo sapere in quanti modi il mio migliore amico della scuola si connette al mio compagno di stanza del college, non mi interessa il fatto che il mio il migliore amico della scuola superiore è collegato a tutti e 200 i miei amici del liceo perché questi percorsi non portano mai al mio compagno di stanza. Quello che voglio fare con questo codice Python è quello di suddividere rapidamente i percorsi che esistono tra i miei due amici e sostanzialmente di eliminare tutto il "rumore" che esiste attorno a questi due nodi.

Ho provato a implementare un numero di esempi di codice, che funzionano bene su grafici piccoli e semplici. Tuttavia, quando provo a incorporarli nella mia analisi a grandi grafici, richiedono troppo tempo per essere utili.

Avete qualche suggerimento sui metodi da investigare (ad esempio, qualcosa già creato in networkx o anche informazioni sull'utilizzo di uno stack rispetto alla ricorsione, ecc ...), esempi di codice da implementare, o anche altri percorsi al di fuori di pitone da perseguire? Tieni presente che sono un principiante pitone.

Answer 1

Personalmente raccomanderei l'utilizzo di un database grafico per questo. Neo4j o Rexter vengono in mente.

Quando si accede a questi da Python ci sono un paio di librerie disponibili:

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

Anche se non sarebbe impossibile scrivere una versione di Python veloce/scalabile di questi, non ce n'è uno in questo momento per quanto ne so.

Answer 2

Forse vuoi tutti i percorsi semplici (nessun nodo ripetuto) tra due nodi? NetworkX ha una funzione per ciò che si basa sulla ricerca in profondità. Vedere http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html

L'esempio da lì mostra che il numero di percorsi semplici può essere grande:

>>> 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]