rustworkx icon indicating copy to clipboard operation
rustworkx copied to clipboard

Added general form of transitive closure

Open Procatv opened this issue 1 year ago • 1 comments

Resolves #704

Bulids on PR #707 (Not pushed yet) to implement the general form of the transitive closure of a graph. Implemented function by following structure from @IvanIsCoding:

  • Condense the graph into strongly connect components (which we already implement)
  • Apply the DAG algorithm and get the transitive closure for the intermediate graph
  • Map the answer from the intermediate graph to the original graph

On my testing branch containing the #707 PR as well, all tests pass.

Procatv avatar Jul 29 '24 13:07 Procatv

CI should be unblocked now that #1258 is merged

IvanIsCoding avatar Jul 29 '24 21:07 IvanIsCoding