[http://www.bjerkem.de/svenn/images/wiki/graph2tree1.gif] 2003-04-20, [Svenn Bjerkem] An application idea needed the possibility to display a design hierarcy as a tree, but the nature of the data fitted best as a directed graph. This is the case with electronic circuits represented in the SPICE netlist format. In the application each node (vertex) represent a subcircuit and each arc (edge) indicate the hierarchy. The SPICE netlist format define all module names in the global namespace and the module hierarchy is depending on the level of the module instantiation. An example of a module is a two input NAND circuit (called NAND2) which may be a building block of many different higher level blocks. In pseudo SPICE this would be something like: SUBCKT NAND2 O A B ... Module definition ... .ENDS The instantiation of NAND2 in higher level modules: SUBCKT ALU ... pin interface ... X_N1 O1 A1 B1 NAND2 X_N2 O2 A2 B2 NAND2 ... rest of alu definition ... .ENDS ALU At an even higher level of our design, the ALU is instantiated, but also one of our primitive NAND2 is needed, maybe for an ALU select signal, who knows, in electronic design primitives are used at any level. .SUBCKT CPU ... pin interface ... X_N1 ... pin interface ... ALU X_N2 O1 A1 B1 NAND2 ... rest of CPU definition ... .ENDS CPU If you look at at the finished design, the hierarchy of an electronic chip is best looked at as a tree structure, but the cells actually used are defined once and then replicated. I found that the struct::graph could be used very efficiently during parsing of SPICE netlists as I only had to check for definitions and instantiations. Each SUBCKT definition cause the insertion of a node (vertex) if it doesn't already exist, and each instantiation insert an arc (edge) between the instantiating node and the definition node. This way each definition exist once and only once. A graph may be a good thing, but for some reason I like to look at the design as a tree, so I used the walk function of struct::graph to explore my graph. During this exploring I discovered a weakness in the implementation of walk: If a node is visited once, it is not visited anymore, causing my NAND2 to appear once, the first time hit, and then no more. I Illustrate the problem by the following code: package require struct package require BWidget Tree .tree -xscrollcommand {.xsb set} -yscrollcommand {.ysb set} scrollbar .ysb -command {.tree yview} scrollbar .xsb -command {.tree xview} -orient horizontal grid .tree .ysb -sticky nsew grid .xsb -sticky ew grid rowconfig . 0 -weight 1 grid columnconfig . 0 -weight 1 set circuit [struct::graph] foreach node [list i ii iii iv v vi vii viii ix] { $circuit node insert $node } foreach {edge} [list {i ii} {i ix} {ix ix} {vii vi} {i vii} \ {ii iii} {iii iv} {iv v} {v vi} \ {vi viii} {viii i}] { $circuit arc insert [lindex $edge 0] [lindex $edge end] } set path {} proc walk-graph-callback {mode graph node} { global path puts "$mode: $node $path" switch -glob -- $mode { "enter" { if {[string equal $path ""]} { puts " path is: root, insert: $node" .tree insert end root $node -text $node } { puts " path is: $path, insert: $node" set localroot [join $path .] .tree insert end $localroot $localroot.$node -text $node } lappend path $node } "leave" { set path [lreplace $path end end]} default {} } } $circuit walk i -order both -type dfs -dir forward \ -command walk-graph-callback .tree opentree i This is actually the implementation of the struct::graph test As you can see from the introducing gif, the path i -> vii -> vi -> viii is not shown completely because node vi has already been visited by the walk i -> ii -> iii -> iv -> v -> vi -> vii If I modified the tcllib implementation and added array unset visited $node on line 1834 in graph.tcl I got the wanted result. [http://www.bjerkem.de/svenn/images/wiki/graph2tree2.gif]