62 lines
1.5 KiB
Plaintext
62 lines
1.5 KiB
Plaintext
def topsort( graph ) =
|
|
val L = seq()
|
|
val S = seq()
|
|
val g = dict( graph )
|
|
|
|
for (v, es) <- g
|
|
g(v) = seq( es )
|
|
|
|
for (v, es) <- g if es.isEmpty()
|
|
S.append( v )
|
|
|
|
while not S.isEmpty()
|
|
val n = S.remove( 0 )
|
|
L.append( n )
|
|
|
|
for (m, es) <- g if n in es
|
|
if (es -= n).isEmpty()
|
|
S.append( m )
|
|
|
|
for (v, es) <- g
|
|
if not es.isEmpty()
|
|
return None
|
|
|
|
Some( L.toList() )
|
|
|
|
dependencies = '''
|
|
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
|
|
'''
|
|
|
|
// convert dependencies data into a directed graph
|
|
graph = dict()
|
|
deps = set()
|
|
|
|
for l <- WrappedString( dependencies ).lines() if l.trim() != ''
|
|
case list(l.trim().split('\\s+')) of
|
|
[a] -> graph(a) = []
|
|
h:t ->
|
|
d = set( t )
|
|
d -= h // remove self dependencies
|
|
graph(h) = d
|
|
deps ++= t
|
|
|
|
// add graph vertices for dependencies not appearing in left column
|
|
for e <- deps if e not in graph
|
|
graph(e) = []
|
|
|
|
case topsort( graph ) of
|
|
None -> println( 'un-orderable' )
|
|
Some( ordering ) -> println( ordering )
|