COIN-OR::LEMON - Graph Library

Opened 7 years ago

Last modified 5 years ago

#421 new enhancement

Better DAG test and topological ordering implementation

Reported by: alpar Owned by: alpar
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

Currently all these functions use Dfs with a custom visitor. I have a feeling that a direct algorithm might be faster and/or more memory efficient. The algorithm I propose is the following:

  • Compute the in-degree of all nodes and store them in a NodeMap deg.
  • Put all node n with deg[n]==0 into a queue (or a stack) q.
  • While q is not empty:
    • Get a node n from g. This is the next node in the topological order.
    • For each out-arc a of n:
      • Decrease deg[target(a)] by 1
      • If deg[target(a)]==0 then put target(a) into q

Attachments (1)

421.diff (3.3 KB) - added by r0mai 3 years ago.
Implementation of the proposed TopologicalSort?

Download all attachments as: .zip

Change History (2)

comment:1 Changed 5 years ago by alpar

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release

Changed 3 years ago by r0mai

Implementation of the proposed TopologicalSort?

Note: See TracTickets for help on using tickets.