Finden Sie alle möglichen Pfade einer bestimmten Länge zwischen zwei Knoten in einem Diagramm

Question

Für mittelgroße (~ 50 Knoten, Durchschnitt Grad: ~ 4), ungerichtete, ungewichtete Graphen Ich möchte alle möglichen Pfade einer angegebenen Länge zwischen zwei Knoten i und j mit R.

Das Paket igraph bietet , die ich verwenden konnte und dann einfach das Ergebnis auf Pfade der Länge, die ich wünsche. Das Problem ist jedoch, dass standardmäßig auch alle möglichen längeren Pfade aufzählt, was Stunden dauert, selbst für kleinere Netzwerke.

Ich weiß, es gibt mehrere sehr ähnliche Fragen rund um SO, noch nicht spezifisch für R, und wichtiger nicht neuer als igraph 's .

Answer 1

Wenn ich Ihre Frage richtig verstehe, wollen Sie nicht alle möglichen Wege zwischen i und j, sondern nur die kürzesten - ist das richtig?

Das erreichen Sie mit der Funktion all_shortest_paths von igraph.

Gegeben:

require(igraph) 
edges= graph.formula(A - B, 
        A - C, 
        B - C, 
        B - C, 
        C - D, 
        B - D, 
        D - E) 

wenn i = A und j = D (nur sagen):

>all_shortest_paths(edges,from="A", to="D") 
$res 
$res[[1]] 
+ 3/5 vertices, named: 
[1] A C D 

$res[[2]] 
+ 3/5 vertices, named: 
[1] A B D 


$nrgeo 
[1] 1 1 1 2 0 

Im Gegenteil, all_simple_paths würden Sie längere Pfade (l = 4), das Ich möchte nicht:

> all_simple_paths(edges,from="A", to="D") 
[[1]] 
+ 4/5 vertices, named: 
[1] A B C D 

[[2]] 
+ 3/5 vertices, named: 
[1] A B D 

[[3]] 
+ 4/5 vertices, named: 
[1] A C B D 

[[4]] 
+ 3/5 vertices, named: 
[1] A C D 

Ich hoffe, das hilft.