COIN-OR::LEMON - Graph Library

Opened 14 years ago

Last modified 6 years ago

#421 new enhancement

Better DAG test and topological ordering implementation — at Initial Version

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

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

Change History (0)

Note: See TracTickets for help on using tickets.