Version 4 of Display a graph in a BWidget Tree

Updated 2003-04-20 19:41:02

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