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.

Sign up for GitHub

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

Jump to bottom

Topological sort may not return a node in a cycle when it fails #264

Closed
flavioakira opened this issue Mar 4, 2023 · 1 comment
Closed

Topological sort may not return a node in a cycle when it fails #264

flavioakira opened this issue Mar 4, 2023 · 1 comment

Comments

@flavioakira
Copy link

flavioakira commented Mar 4, 2023 •
edited
Loading

A reproducible example:

Graph(1~>2, 2~>1, 2~>3, 3~>4, 4~>5, 5~>6, 6~>7, 7~>8, 8~>9, 9~>10).topologicalSort
// res: graph.CycleNodeOrTopologicalOrder = Left(9)

Graph(1~>2, 2~>1, 2~>3, 3~>4, 4~>5, 5~>6, 6~>7, 7~>8, 8~>9, 9~>10).topologicalSortByComponent.toList
// res: List[graph.CycleNodeOrTopologicalOrder] = List(Left(9))

val graph = Graph(1~>2, 2~>1, 2~>3, 3~>4, 4~>5, 5~>6, 6~>7, 7~>8, 8~>9, 9~>10)
graph.topologicalSort match {
  case Left(nodeInCycle) => graph.findCycleContaining(nodeInCycle)
}
// res: Option[graph.Cycle] = None
@flavioakira flavioakira changed the title Topological sort does not return a node in a cycle Topological sort does not return a node in a cycle when it fails Mar 4, 2023
@peter-empen peter-empen changed the title Topological sort does not return a node in a cycle when it fails Topological sort may not return a node in a cycle when it fails Mar 24, 2023
peter-empen added a commit that referenced this issue Mar 29, 2023
@peter-empen
back-port "inproper cycle node for failed topo sort fixes #264" from 2.x
141956d
peter-empen added a commit that referenced this issue Mar 29, 2023
@peter-empen
back-port "inproper cycle node for failed topo sort fixes #264" from 2.x
0cbff5a
@peter-empen
Copy link
Contributor

this has now been published in 1.13.6 😃

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@peter-empen @flavioakira