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

Question

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

Answer 1

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

Answer 2

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