Topological sort: Difference between revisions

=={{header|Bracmat}}==

<lang>( ("des_system_lib".std synopsys "std_cell_lib" "des_system_lib" dw02 dw01 ramlib ieee)

(dw01.ieee dw01 dware gtech)

(dw02.ieee dw02 dware)

(dw03.std synopsys dware dw03 dw02 dw01 ieee gtech)

(dw04.dw04 ieee dw01 dware gtech)

(dw05.dw05 ieee dware)

(dw06.dw06 ieee dware)

(dw07.ieee dware)

(dware.ieee dware)

(gtech.ieee gtech)

(ramlib.std ieee)

("std_cell_lib".ieee "std_cell_lib")

(synopsys.)

(cycle-11.cycle-12)

(cycle-12.cycle-11)

(cycle-21.dw01 cycle-22 dw02 dw03)

(cycle-22.cycle-21 dw01 dw04)

: ?libdeps

& :?indeps

& ( toposort

= A Z res module dependants todo done

. !arg:(?todo.?done)

& ( areDone

=

. !arg:

| !arg

: ( %@

: [%( !module+!done+!indeps:?+(? !sjt ?)+?

| ~(!libdeps:? (!sjt.?) ?)

& !sjt !indeps:?indeps

)

)

?arg

& areDone$!arg

)

& ( !todo

: ?A

(?module.?dependants&areDone$!dependants)

( ?Z

& toposort$(!A !Z.!done !module):?res

)

& !res

| (!todo.!done)

)

)

& toposort$(!libdeps.):(?cycles.?res)

& out$("

compile order:" !indeps !res "\ncycles:" !cycles)

);

</lang>

Output:

<lang>compile order:

ieee

std

dware

dw02

dw05

dw06

dw07

gtech

dw01

dw04

ramlib

std_cell_lib

synopsys

des_system_lib

dw03

cycles:

(cycle-11.cycle-12)

(cycle-12.cycle-11)

(cycle-21.dw01 cycle-22 dw02 dw03)

(cycle-22.cycle-21 dw01 dw04)</lang>