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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.