search

dominikbraun / graph

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
https://graph.dominikbraun.io
Apache License 2.0
1.82k stars 96 forks source link

Change `TopologicalSort` and `TransitiveReduction` to fail at runtime for acyclic graphs #49

Closed dominikbraun closed 2 years ago

dominikbraun commented 2 years ago

With release 0.12.0, TopologicalSort and TransitiveReduction check whether the graph actively prevents the creation of cycles with the PreventCycles option being set.

In the future, those functions should not rely on the graph not having any cycles, but should just run and fail if a cycle is detected. The preceding isDag() check should be removed.

Hrily commented 2 years ago

@dominikbraun

Was easily able to do this for TopologicalSort, but wasn't able to for TransitiveReduction mostly because the DFS function makes it hard to detect cycles. Need your help for it.

Also a question: Since TransitiveReduction mutates the graph, what should be the failure strategy here? Should we roll-back the changes made or leave the graph in inconsistent state?

dominikbraun commented 2 years ago

@Hrily Thanks for your thoughts on this.

Also a question: Since TransitiveReduction mutates the graph, what should be the failure strategy here? Should we roll-back the changes made or leave the graph in inconsistent state?

We have no choice but to return the transitive reduction as a new graph instead of mutating the original one.

Some versions ago, a graph was guaranteed to be acyclic if you created a graph using Acyclic(), because Acyclic() proactively prevented the creation of cycles when adding an edge. This behavior has changed (see #45). Now, Acyclic() just declares a graph to be acyclic, but this doesn't automatically prevent the creation of cycles.

TransitiveReduction and TopologicalSort just checked whether Acyclic has been set, and if so, they would be safe to run since they have a guarantee that the graph is acyclic. Because this guarantee doesn't exist anymore, both functions need to check this themselves at runtime now.

TransitiveReduction potentially leaving the graph in an inconsistent state is a scenario I didn't have in mind back then. We'll have to break the behavior of TransitiveReduction and return a new graph.

Hrily commented 2 years ago

@dominikbraun

We have no choice but to return the transitive reduction as a new graph instead of mutating the original one.

Makes sense. Will raise another PR for this since it will involve significant changes to TransitiveReduction.

dominikbraun commented 2 years ago

@dominikbraun

We have no choice but to return the transitive reduction as a new graph instead of mutating the original one.

Makes sense. Will raise another PR for this since it will involve significant changes to TransitiveReduction.

Alright. For now, you may just use the Clone method for cloning the graph if you want to.

Hrily commented 2 years ago

@dominikbraun

Raise #57 for changes related to TransitiveReduction.

Also, fixed review comments on #56. Please re-review.