2003-04-20, Svenn Are 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.

Here's the resultant screenshot: http://www.bjerkem.de/svenn/images/wiki/graph2tree2.gif

CMcC Just a thought, but walk not revisiting nodes might be a design goal, to permit the walk to terminate in the presence of cycles? Perhaps a better mod to graph.tcl would be to ensure that the setting of visited() occurs before the command call, so you could selectively unset visited per node within the command, and achieve the goal you want? I'm guessing your data is a DAG, so you wouldn't have any cycles. I've submitted a feature request to tcllib for just this change: http://sourceforge.net/tracker/index.php?func=detail&aid=724822&group_id=12883&atid=362883

I see that someone (presumably the author) has also submitted a feature request: http://sourceforge.net/tracker/index.php?func=detail&aid=724730&group_id=12883&atid=362883 which seems more complete :)

---

2003-04-21, Svenn Are Bjerkem

That's right, it was me with the feature request. It all started with the need to show some example, but I didn't register for a sourceforge user.

The way ::struct::graph::walk in struct::graph is working with dfs is correct if it had been called ::struct::graph::path. On the other hand, I don't want to critisize the choice of name for the procedure, but rather argue for augmenting walk with more features. Problem is that I argue from the application view rather from the theoretical side. Currently I solve the problem by overloading ::struct::graph::_walk locally in my application (which at this point is not yet finished) in order to allow a node to be visited more than once.

---