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
withdeg[n]==0
into a queue (or a stack)q
. - While
q
is not empty:- Get a node
n
fromg
. This is the next node in the topological order. - For each out-arc
a
ofn
:- Decrease
deg[target(a)]
by 1 - If
deg[target(a)]==0
then puttarget(a)
intoq
- Decrease
- Get a node
Note: See
TracTickets for help on using
tickets.