73 lines
2.1 KiB
Text
73 lines
2.1 KiB
Text
import Algorithms as algo;
|
|
import Text as text;
|
|
|
|
class DirectedGraph {
|
|
_adjecentVertices = {};
|
|
add_vertex( vertex_ ) {
|
|
_adjecentVertices[vertex_] = [];
|
|
}
|
|
add_edge( from_, to_ ) {
|
|
_adjecentVertices[from_].push( to_ );
|
|
}
|
|
adjecent_vertices( vertex_ ) {
|
|
return ( vertex_ ∈ _adjecentVertices ? _adjecentVertices.get( vertex_ ) : [] );
|
|
}
|
|
}
|
|
|
|
class DepthFirstSearch {
|
|
_visited = set();
|
|
_postOrder = [];
|
|
_cycleDetector = set();
|
|
run( graph_, start_ ) {
|
|
_cycleDetector.insert( start_ );
|
|
_visited.insert( start_ );
|
|
for ( vertex : graph_.adjecent_vertices( start_ ) ) {
|
|
if ( vertex == start_ ) {
|
|
continue;
|
|
}
|
|
if ( vertex ∈ _cycleDetector ) {
|
|
throw Exception( "A cycle involving vertices {} found!".format( _cycleDetector ) );
|
|
}
|
|
if ( vertex ∉ _visited ) {
|
|
run( graph_, vertex );
|
|
}
|
|
}
|
|
_postOrder.push( start_ );
|
|
_cycleDetector.erase( start_ );
|
|
}
|
|
topological_sort( graph_ ) {
|
|
for ( vertex : graph_._adjecentVertices ) {
|
|
if ( vertex ∉ _visited ) {
|
|
run( graph_, vertex );
|
|
}
|
|
}
|
|
return ( _postOrder );
|
|
}
|
|
}
|
|
|
|
main() {
|
|
rawdata =
|
|
"des_system_lib | std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n"
|
|
"dw01 | ieee dw01 dware gtech\n"
|
|
"dw02 | ieee dw02 dware\n"
|
|
"dw03 | std synopsys dware dw03 dw02 dw01 ieee gtech\n"
|
|
"dw04 | dw04 ieee dw01 dware gtech\n"
|
|
"dw05 | dw05 ieee dware\n"
|
|
"dw06 | dw06 ieee dware\n"
|
|
"dw07 | ieee dware\n"
|
|
"dware | ieee dware\n"
|
|
"gtech | ieee gtech\n"
|
|
"ramlib | std ieee\n"
|
|
"std_cell_lib | ieee std_cell_lib\n"
|
|
"synopsys |\n";
|
|
dg = DirectedGraph();
|
|
for ( l : algo.filter( text.split( rawdata, "\n" ), @( x ) { size( x ) > 0; } ) ) {
|
|
def = algo.materialize( algo.map( text.split( l, "|" ), string.strip ), list );
|
|
dg.add_vertex( def[0] );
|
|
for ( n : algo.filter( algo.map( text.split( def[1], " " ), string.strip ), @( x ) { size( x ) > 0; } ) ) {
|
|
dg.add_edge( def[0], n );
|
|
}
|
|
}
|
|
dfs = DepthFirstSearch();
|
|
print( "{}\n".format( dfs.topological_sort( dg ) ) );
|
|
}
|