1
$\begingroup$

Following up on the discussion in Problem with EdgeWeight and FindCycle?, consider the simple directed graph:

graph = Graph[{1 \[DirectedEdge] 2,
               2 \[DirectedEdge] 3,
               3 \[DirectedEdge] 1,     
               3 \[DirectedEdge] 2 }, 
               EdgeWeight -> {1 \[DirectedEdge] 2 -> 0,
                              2 \[DirectedEdge] 3 -> -1,
                              3 \[DirectedEdge] 1 -> 1,    
                              3 \[DirectedEdge] 2 -> 1 },
                EdgeLabels -> "EdgeWeight", VertexLabels -> "Name"]

A simple directed graph

Note this graph has two circuits of length 0: 1 -> 2 -> 3 -> 1 and 2 -> 3 -> 2

FindCycle[graph,0]

returns:

{{1 \[DirectedEdge] 2, 2 \[DirectedEdge] 3, 3 \[DirectedEdge] 1}}

It only finds one of the two cycles. Is the "all" in

For weighted graphs, FindCycle[g,k] gives all cycles with total weights less than k.

incorrect as well?

$\endgroup$

1 Answer 1

1
$\begingroup$

It's the documentation, not the implementation that has the issues.

FindCycle[graph,0,All]

returns both cycles.

Changing the graph so that 1 -> 2 -> 3 -> 1 has total weight -1:

graph = Graph[{1 \[DirectedEdge] 2,
               2 \[DirectedEdge] 3, 
               3 \[DirectedEdge] 1, 
               3 \[DirectedEdge] 2}, 
              EdgeWeight -> {1 \[DirectedEdge] 2 -> -1, 
                             2 \[DirectedEdge] 3 -> -1,
                             3 \[DirectedEdge] 1 -> 1, 
                             3 \[DirectedEdge] 2 -> 1}, 
               EdgeLabels -> "EdgeWeight", VertexLabels -> "Name"]

graph with a negative weight circuit

and invoking FindCycle:

FindCycle[graph,0]

again returns

{{1 \[DirectedEdge] 2, 2 \[DirectedEdge] 3, 3 \[DirectedEdge] 1}}

a circuit of total weight -1

FindCycle[graph,0,All]

returns both circuits.

It appears the documentation should read

For weighted (directed) graphs, FindCycle[g,k] gives some cycle(s) with total weight less than or equal to k. FindCycle[g,k,All] gives all cycles with total weight less than or equal to k.

$\endgroup$

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.