# How to find the closed path in a digraph

The graph

g = Graph[{1 \[DirectedEdge] 2, 2 \[DirectedEdge] 3,  3 \[DirectedEdge] 2, 3 \[DirectedEdge] 1, 3 <-> 3}]


is associated to the matrix

m = ( {{0, 0, 1}, {1, 0, 1}, {0, 1, 1}  } )


The trace of m^k gives the number of closed walks of length k. So for k=2, Tr[MatrixPower[m, 2]] gives 3 closed walks. I want to list those 3 closed walks so I have tried cw=Table[FindPath[g, i, i, {3}], {i, 3}]. The computational result is {{},{},{}}. I certainly have made a mistake but I do not see which. Due to comments I have understud my mistake but the question stay open : how to list the closed walks of length k ?

• A "walk" may have repeated vertices and edges. A "path" may not repeat any vertices (or edges). May 25 '18 at 13:39
• Also, the adjacency matrix and the graph you show do not correspond to each other. For the graph the result is 1, specifically the walk 3 -> 3 -> 3. For the matrix, the result is 3 (not 11), and the walks are 3 -> 2 -> 3, 2 -> 3 -> 2 and 3 -> 3 ->3. May 25 '18 at 13:44
• Szabolcs your completely true. 11 is for k= 4. But is there a way to find the walks ? May 25 '18 at 16:43
• Szabolcs I have corrected the graph to correspond to the matrix and modified the nomber of closed walks. May 25 '18 at 18:51

Let us work with a proper directed graph, not a mixed graph, as mixed graphs can get us into a mess.

g = Graph[{1 -> 2, 2 -> 3, 3 -> 2, 3 -> 1, 3 -> 3},
VertexLabels -> Automatic]


First we define a more useful AdjacencyList which follows only out-edges in directed graphs and returns a full association.

adjList[g_?DirectedGraphQ] :=
VertexList[g],
]

(* <|1 -> {2}, 2 -> {3}, 3 -> {1, 2, 3}|> *)


This function extends an existing walk in all possible ways based on an adjacency list.

extend[al_][walk_] := Append[walk, #] & /@ al@Last[walk]


For example, if we are currently in node 3, we can end up in nodes 1, 2 or 3.

extend[adjList[g]][{2, 3}]
(* {{2, 3, 1}, {2, 3, 2}, {2, 3, 3}} *)


Generate all walks of length 3:

Nest[
{{1}, {2}, {3}},
3
]
(* {{1, 2, 3, 1}, {1, 2, 3, 2}, {1, 2, 3, 3}, {2, 3, 1, 2}, {2,
3, 2, 3}, {2, 3, 3, 1}, {2, 3, 3, 2}, {2, 3, 3, 3}, {3, 1, 2,
3}, {3, 2, 3, 1}, {3, 2, 3, 2}, {3, 2, 3, 3}, {3, 3, 1, 2}, {3, 3,
2, 3}, {3, 3, 3, 1}, {3, 3, 3, 2}, {3, 3, 3, 3}} *)


Which are cyclic?

Cases[%, {s_, ___, s_}]
(* {{1, 2, 3, 1}, {2, 3, 1, 2}, {2, 3, 3, 2}, {3, 1, 2, 3}, {3,
2, 3, 3}, {3, 3, 2, 3}, {3, 3, 3, 3}} *)

• Szabolcs, I thank you very much for your contribution. But what could I do if there are loops ? Your solution doesn't work May 28 '18 at 11:52
• @cyrille.piatecki Can you give an example where it does not work? May 28 '18 at 11:54
• g = Graph[{1 -> 2, 2 -> 3, 3 -> 2, 3 -> 1, 3 <-> 3}, VertexLabels -> Automatic] May 28 '18 at 11:55
• Sorry I am really tired my exemple is a mess. May 28 '18 at 11:56
• @cyrille.piatecki Don't use a mixed graph. The input must be a directed graph. All edges must be directed. Don't use <-> in the input. May 28 '18 at 12:57