Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Cycles are reported incorrectly #2198

Closed
byorgey opened this issue Oct 21, 2024 · 0 comments · Fixed by #2199
Closed

Cycles are reported incorrectly #2198

byorgey opened this issue Oct 21, 2024 · 0 comments · Fixed by #2199
Labels
Bug The observed behaviour is incorrect or unexpected. S-Nice to have The bug fix or feature would be nice but doesn't currently have much negative impact.

Comments

@byorgey
Copy link
Member

byorgey commented Oct 21, 2024

Describe the bug
I just noticed that Swarm.Util.Graph.getGraphCycles does not actually find directed cycles, and thus failOnCyclicGraph could output an error message indicating a cycle that does not exist. Note that whether an error is generated is correct --- failOnCyclicGraph indeed fails precisely when the graph has directed cycles. However, when there are directed cycles, it may print something which is not a directed cycle.

To Reproduce
The smallest example I could come up with is the following scenario description:

version: 1
name: "bad-cycles"
author: Brent Yorgey
description: An example for 2198
robots:
  - name: base
objectives:
  - id: a
    condition: 'true'
    prerequisite:
      logic:
        and:
          - b
          - c
          - d
  - id: b
    condition: 'true'
    prerequisite: a
  - id: c
    condition: 'true'
    prerequisite:
      logic:
        and:
          - a
          - d
  - id: d
    condition: 'true'
    prerequisite:
      logic:
        and:
          - a
          - c
world:
  dsl: '{stone}'

Trying to load this with e.g. scripts/play.sh -i data/scenarios/bad.yaml results in an error message:

Failed to acquire scenarios from path 'data/scenarios/bad.yaml':
  Parse failure:
    Aeson exception:
    Error in $: Prerequisites graph contains cycles: [a -> b -> c -> d]

It is correct to reject this scenario, but the reported cycle a -> b -> c -> d is bogus: b does not depend on c. In fact, there are two cycles, a -> b and a -> c -> d.

Expected behavior
The error message should report a true cycle, i.e. a sequence of nodes where each depends on the next, and the last depends on the first.

Additional context
stronglyConnComp computes a topologically sorted list of strongly connected components (SCCs). It is true that every component will be a singleton vertex (AcyclicSCC) if and only if the graph has no directed cycles. However, in the case that there are nontrivial SCCs, the list of vertices reported in a (confusingly named) CyclicSCC (or NECyclicSCC) is in no particular order and need not represent a cycle. The above example constructs a graph with four vertices, where a and b are mutually reachable and there is a directed cycle a -> c -> d -> a. In this case all four vertices are part of the same SCC (since any vertex can be reached from any other) but they obviously do not form a cycle. Even in the case where an SCC does actually consist of a cycle and nothing else, I am not even sure it is guaranteed that the vertices will be returned in order around the cycle. It seems a reasonable assumption, but the documentation does not specify.

I plan to fix this shortly but wanted to file an issue for discussion/posterity.

@byorgey byorgey added Bug The observed behaviour is incorrect or unexpected. S-Nice to have The bug fix or feature would be nice but doesn't currently have much negative impact. labels Oct 21, 2024
@mergify mergify bot closed this as completed in #2199 Oct 27, 2024
@mergify mergify bot closed this as completed in 39adce6 Oct 27, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Bug The observed behaviour is incorrect or unexpected. S-Nice to have The bug fix or feature would be nice but doesn't currently have much negative impact.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant