COIN-OR::LEMON - Graph Library

Opened 13 years ago

Last modified 5 years ago

#421 new enhancement

Better DAG test and topological ordering implementation

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

Description (last modified by Alpar Juttner)

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 q. 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 Andras Kucsma 9 years ago.
Implementation of the proposed TopologicalSort?

Download all attachments as: .zip

Change History (3)

comment:1 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

Changed 9 years ago by Andras Kucsma

Attachment: 421.diff added

Implementation of the proposed TopologicalSort?

comment:2 Changed 5 years ago by Alpar Juttner

Description: modified (diff)
Note: See TracTickets for help on using tickets.