Trova tutti i percorsi tra due vertici (nodi)

Question

Sono nuovo alla programmazione R e sono coinvolto nella rappresentazione di grafici usando R. Vorrei chiedere come implementare un codice in grado di trovare tutti i percorsi tra due vertici o nodi basati su una matrice di adiacenza. Ho visto molte implementazioni in altri linguaggi di programmazione, ma la maggior parte di esse utilizzava code come in (BFS) per farle funzionare. Ad esempio questo è l'elenco dei bordi del mio grafico.

  [,1] [,2] 
    [1,] 0 1 
    [2,] 1 2 
    [3,] 1 3 
    [4,] 1 4 
    [5,] 2 5 
    [6,] 2 6 
    [7,] 5 7 
    [8,] 5 8 
    [9,] 6 9 
    [10,] 6 10 
    [11,] 8 11 
    [12,] 10 12 
    [13,] 11 13 
    [14,] 11 14 
    [15,] 11 15 
    [16,] 12 16 
    [17,] 12 17 
    [18,] 12 18 
    [19,] 13 19 
    [20,] 16 20 
    [21,] 19 21 
    [22,] 19 22 
    [23,] 20 22 
    [24,] 20 23  

Se volevo tutti i percorsi tra il nodo 0 e il nodo 22, dovrebbero essere due percorsi:

[[1]] 
    [1] 0 1 2 6 10 12 16 20 22 

    [[2]] 
    [1] 0 1 2 5 8 11 13 19 22 

Grazie

Answer 1

Si desidera avere una buona lettura dei modelli grafici vista attività :

http://ftp.heanet.ie/mirrors/cran.r-project.org/web/views/gR.html

Anche se io non cosa ciò che si sta facendo è la modellazione grafica in senso statistico, questa vista attività delinea i pacchetti per la gestione del grafico e gli algoritmi.

Ho usato l'igraph per varie cose di graphy.

Answer 2

Supponendo che si dispone di un semplice directed acyclic graph (DAG), il seguente approccio funziona per il conteggio:

(A^n)_ij ti dà il numero di percorsi di lunghezza n tra i nodi i e j. Pertanto è necessario calcolare A + A^2 + ... + A^n + ... per ottenere il numero totale di percorsi tra due nodi qualsiasi. È essenziale lavorare con un DAG, in quanto ciò garantisce che per un numero sufficiente di n, A^n = 0. Quindi il risultato può essere scritto come A . (I - A)^(-1) dove I è la matrice di identità.

---

EDIT:

io non so davvero R quindi posso solo darvi qualche pseudocodice o chiarimenti.

Innanzitutto, troviamo il set di nodi raggiungibile dal nodo i. Definiamo il vettore v per contenere solo zeri tranne che nella posizione i dove contiene 1. E.g. per il 1 ° nodo avrete

v = (1,0,0, ..., 0) 

Ora lascia v_(n+1) = sign(v_n + A . v_n), in cui lo scopo della funzione sign() è quello di sostituire gli elementi non nulli di 1 e mantenere zeri 0. Fate questa iterazione fino a raggiungere il punto fisso, e si Avremo un vettore v con elementi diversi da zero nelle posizioni corrispondenti ai nodi raggiungibili dal nodo i.

Se al posto del vettore v si inizia con la matrice identità (della stessa dimensione di A), si ottengono i nodi raggiungibili per ciascun nodo in un colpo solo.

Ora si dispone della serie di nodi raggiungibili per qualsiasi nodo iniziale. Allo stesso modo è possibile ottenere l'elenco di nodi da cui è possibile raggiungere qualsiasi nodo di destinazione (è sufficiente invertire i bordi diretti, ad es.trasporre A)

Successivamente, percorriamo il grafico e troviamo tutti i percorsi necessari.

Questa funzione ricorsiva dovrebbe farlo (pseudocodice):

traverse(path-so-far, target): 
    let S = the last element of path-so-far 
    if S == target: 
     output path-so-far 
     return 
    let N = the set of nodes reachable from S in one step 
    remove all nodes from N from which the target is not reachable 
    for each K in N: 
     traverse(append(path-so-far, K), target) 

path-so-far è la lista dei nodi già visitati; target è il nodo di destinazione.

Per una determinata coppia di nodi di avvio e di destinazione, è sufficiente eseguire traverse({start}, target).

Nota che il passo in cui togliamo tutti i nodi da cui l'obiettivo non è raggiungibile sia lì solo per accelerare l'attraversamento, e non entrate "vicoli ciechi"

Answer 3

Basta fare una ricerca in profondità senza controllare i nodi visitati - questo può dare il numero di percorsi tra due punti di una lunghezza specifica

void dfs(int start, int hops) 
{ 
    if(hops == k && start == t) 
    { 
     path++; 
     return; 
    } 
    else if(hops >= k) 
    return; 
    for(int w = 1; w <= n; w++) 
    if(routes[start][w]) 
     dfs(w, hops + 1); 
} 

E nel principale, chiamare

dfs(start_node, length); 

Come fare Y fai se ci sono più percorsi che collegano due punti e ognuno è considerato diverso?

Answer 4

Ho usato il seguente codice per creare una matrice (vertici x vertici) che contiene il numero di tutti i percorsi tra ogni due vertici.

library(igraph) 
setwd("C:/Workspace") 
graph <- read.graph("graph.txt", format="edgelist") 
direct <- get.adjacency(graph) 
indirect <- direct 
max <- vcount(graph)-1 
for(i in 0:max) 
for(j in 0:max) 
    indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out")) 

Propongo di utilizzare la libreria igraph per questo scopo.

library(igraph) 

ho messo la vostra lista bordo in un file chiamato "graph.txt", che ho messo in "C: \ spazio di lavoro". Allora io uso il seguente codice per leggere in quel file in R:

setwd("C:/Workspace") 
graph <- read.graph("graph.txt", format="edgelist") 

si potrebbe desiderare di tracciare il grafico solo per essere sicuri che s' va bene tutto (tuttavia, questo passo può essere lasciato via):

plot(graph, layout=layout.fruchterman.reingold.grid) 

genero una matrice di adiacenza per vedere tutti i collegamenti diretti tra i vertici:

direct <- get.adjacency(graph) 

Poi ho creare una matrice fittizio denominato "indiretto" che è una copia della matrice adjancency. Ho solo bisogno di questa matrice di riempire in seguito con i valori indiretti:

indirect <- direct 

Infine, iterare su tutto il grafico per trovare il numero di tutti i collegamenti indiretti tra ogni due vertici. Ho inserito questo numero nella matrice indiretta che ho appena creato (inoltre ho creato una clausola mettendo tutti i valori sullo zero diagonale). La modalità "out" garantisce che vengano conteggiati solo i percorsi in uscita.Questo può anche essere impostato su "in" o "totale":

max <- vcount(graph)-1 
for(i in 0:max) 
for(j in 0:max) 
    indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out")) 

Answer 5

Controllare la seguente funzione IGRAPH out:

http://igraph.org/r/doc/all_simple_paths.html

Si elencano tutti i percorsi semplici da un'unica fonte.

Descrizione Questa funzione elenca semplici percorsi da un vertice di origine a un altro vertice o vertice. Un percorso è semplice se i vertici che visita non vengono visitati più di una volta.

Uso all_simple_paths (grafico, da, a = V (grafico), MODE = c ("fuori", "a", "all", "totale"))

Argomenti

grafico
Il grafico di input.

da
Il vertice di origine.

a
Il vertice di destinazione dei vertici. Predefinito a tutti i vertici.

modalità
Costante di carattere, indica se i tracciati più brevi verso o dai vertici indicati devono essere calcolati per i grafici diretti. Se fuori i percorsi più brevi dal vertice, se in poi sarà considerato. Se tutto, il valore predefinito, verrà utilizzato il grafico indiretto corrispondente, vale a dire. i percorsi non diretti vengono cercati. Questo argomento è ignorato per i grafi non orientati.

dettagli

Nota che potenzialmente ci sono esponenzialmente molti percorsi tra due vertici di un grafo, e si può esaurire la memoria quando si utilizza questa funzione, se il grafico è reticolare.

Questa funzione attualmente ignora i bordi multipli e di loop.