2
$\begingroup$

For the following graph:

g = Graph[{0 -> 1, 1 -> 2, 2 -> 3, 3 -> 0, 0 -> 0, 1 -> 1, 2 -> 2, 
   3 -> 3}, VertexLabels -> Automatic, 
  VertexLabelStyle -> Directive[Black, Bold, 16]]

enter image description here

I want to calculate all paths of length 6 that exist between node 0 and every other node in the graph. The FindPath[] function only allows me to calculate simple paths, but here there are no simple paths of length 6.

For example, one of the paths of length 6 between 0 and 2 is {0,0,0,0,1,1,2}.

$\endgroup$
  • $\begingroup$ This is easy; just take a partial walk, take the last vertex: you can extend the walk with any of its neighbours. The number of walks grows exponentially with their length. $\endgroup$ – Szabolcs Jul 2 at 18:14
  • $\begingroup$ @Szabolcs what do you mean by a 'partial walk' and how would you program this? $\endgroup$ – smallscot Jul 2 at 19:24
4
$\begingroup$

This generates all walks of length 6, starting at vertex 0, for the graph g. I use a function from IGraph/M for convenience.

Needs["IGraphM`"]

adj = IGAdjacencyList[g]
(* <|0 -> {0, 1}, 1 -> {1, 2}, 2 -> {2, 3}, 3 -> {0, 3}|> *)

step[{most___, last_}] := {most, last, #} & /@ adj[last]

Nest[Join @@ step /@ # &, {{0}}, 6 (* length of walks *) ]
(*
 {
  {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 1, 1},
  {0, 0, 0, 0, 0, 1, 2}, {0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 1, 1, 2},
  {0, 0, 0, 0, 1, 2, 2}, {0, 0, 0, 0, 1, 2, 3}, ...
 }
*)
$\endgroup$
0
$\begingroup$

For the case of source-target pairs (as opposed to source to all other vertices), using a modification of Szabolcs's step to avoid vertices that, if taken, will take us too far from the target vertex (too far to reach the target within remaining number of steps) gives us all walks from source to target vertex with specified length directly (without the need to filter all walks to get the ones that end in the target vertex):

ClearAll[steps, walks, adjl, dist]
adjl[g_] := GroupBy[EdgeList[g], First -> Last]

dist[g_, t_]:= Association[# -> GraphDistance[g, #, t]& /@ VertexList[g]]

steps[g_, l_, t_][{most___, last_}] := {most, last, #} & /@ 
    Select[dist[g, t][#] <= l - Length[{most, last}] &] @ adjl[g][last]

walks[g_, s_, t_, l_] := Nest[Join @@ steps[g, l, t] /@ # &, {{s}}, l ]

walks[g, 0, 2, 6]

{{0, 1, 2, 3, 0, 1, 2}, {0, 1, 2, 2, 2, 2, 2}, {0, 1, 1, 2, 2, 2,   2}, {0, 1, 1, 1, 2, 2, 2}, {0, 1, 1, 1, 1, 2, 2}, {0, 1, 1, 1, 1, 1, 2}, {0, 0, 1, 2, 2, 2, 2}, {0, 0, 1, 1, 2, 2, 2}, {0, 0, 1, 1, 1, 2, 2}, {0, 0, 1, 1, 1, 1, 2}, {0, 0, 0, 1, 2, 2, 2}, {0, 0, 0, 1, 1, 2, 2}, {0, 0, 0, 1, 1, 1, 2}, {0, 0, 0, 0, 1, 2, 2}, {0, 0, 0, 0, 1, 1, 2}, {0, 0, 0, 0, 0, 1, 2}}

This matches the list obtained by filtering all walks computed using Szabolcs's step:

Sort @ walks[g, 0, 2, 6] == Sort @ Cases[{__, 2}] @ Nest[Join @@ step /@ # &, {{0}}, 6] 

True

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.