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

1 Answer 1

2
$\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}} *)
$\endgroup$
5
  • $\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$ May 28, 2018 at 11:52
  • $\begingroup$ @cyrille.piatecki Can you give an example where it does not work? $\endgroup$
    – Szabolcs
    May 28, 2018 at 11:54
  • $\begingroup$ g = Graph[{1 -> 2, 2 -> 3, 3 -> 2, 3 -> 1, 3 <-> 3}, VertexLabels -> Automatic] $\endgroup$ May 28, 2018 at 11:55
  • $\begingroup$ Sorry I am really tired my exemple is a mess. $\endgroup$ May 28, 2018 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, 2018 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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