2
$\begingroup$

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 ?

$\endgroup$
  • 3
    $\begingroup$ A "walk" may have repeated vertices and edges. A "path" may not repeat any vertices (or edges). $\endgroup$ – Szabolcs May 25 '18 at 13:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Szabolcs May 25 '18 at 13:44
  • $\begingroup$ Szabolcs your completely true. 11 is for k= 4. But is there a way to find the walks ? $\endgroup$ – cyrille.piatecki May 25 '18 at 16:43
  • $\begingroup$ Szabolcs I have corrected the graph to correspond to the matrix and modified the nomber of closed walks. $\endgroup$ – cyrille.piatecki May 25 '18 at 18:51
1
$\begingroup$

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] :=
 AssociationThread[
  VertexList[g],
  VertexList[g][[#]] & /@ AdjacencyMatrix[g]["AdjacencyLists"]
 ]

adjList[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[
 Catenate[extend[adjList[g]] /@ #] &,
 {{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}} *)
|improve this answer|||||
$\endgroup$
  • $\begingroup$ Szabolcs, I thank you very much for your contribution. But what could I do if there are loops ? Your solution doesn't work $\endgroup$ – cyrille.piatecki May 28 '18 at 11:52
  • $\begingroup$ @cyrille.piatecki Can you give an example where it does not work? $\endgroup$ – Szabolcs May 28 '18 at 11:54
  • $\begingroup$ g = Graph[{1 -> 2, 2 -> 3, 3 -> 2, 3 -> 1, 3 <-> 3}, VertexLabels -> Automatic] $\endgroup$ – cyrille.piatecki May 28 '18 at 11:55
  • $\begingroup$ Sorry I am really tired my exemple is a mess. $\endgroup$ – cyrille.piatecki May 28 '18 at 11:56
  • $\begingroup$ @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. $\endgroup$ – Szabolcs May 28 '18 at 12:57

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.