# Finding Non-Simple Paths of a Given Length on a Graph

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

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}.

• 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. Jul 2, 2019 at 18:14
• @Szabolcs what do you mean by a 'partial walk' and how would you program this? Jul 2, 2019 at 19:24

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

(* <|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}, ...
}
*)

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):

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