DGA usage examples

Author Jackson McCann.

If the .dot file is saved as test1.dot and the following script is run:

 tclsh test1.tcl test1.dot a0 b3

Then the colored.dot file will display the shortest path between a0 and b3 in red.

The example dosn't specify any weights for the edges, a default weight of 1 will be assigned to each edge. In order to assign other weights to an edge add an attribute of weight to the edge like this:

 n1 -> n2[weight="5"]

Sample test1.dot file ----------------------------

digraph G {

        a0 -> a1 -> a2 -> a3;
        b0 -> b1 -> b2 -> b3;
        x -> a0;
        x -> b0;
        a1 -> b3;
        b1 -> a3;

}

test1.tcl code start ---------------------------

 # Test script 1 for the DGA package.  Test the shortest path implementation
 # in the DGA package.

 package require ASDOT
 package require DGA

 # This script takes three input parameters.
 #    graphName -  The .dot file that is to be loaded
 #    startNode -  The node to be used for the start of the shortest
 #                 path calculation.  The algorithm finds the shortest
 #                 path to all other reachable nodes from this starting node
 #    endNode   -  The node to display the shortest path to.
 set graphName [lindex $argv 0]
 set startNode [lindex $argv 1]
 set endNode [lindex $argv 2]

 # Read the .dot file in and build the TCL graph from it
 set graph [ASDOT::read_dot $graphName]

 # Calculate the shortest path to all reachanble nodes from the
 # startNode
 DGA::shortest_path $graph $startNode

 # Get back the predecesor list.  For each node n this defines
 # it's predecessor (if any) that will route back to the startNode
 set pl [DGA::predecessor_list $graph]
 puts $pl

 # Now colour the graph to show the route from the endNode to the 
 # startNode
 set cn $endNode
 while {1} {
     $graph node set $cn -key color red
     set arc [$graph node get $cn -key predecessor]
     if { $arc == {} } {break} 
     $graph arc set $arc -key color red

     set cn [$graph arc source $arc]

     if { $cn == $startNode } {
         $graph node set $startNode -key color red
         break ;
     }
 }

 # Write out the graph to colored.dot, when displayed using dotty this
 # should show the shortest path from startNode to endNode in red
 ASDOT::write_dot colored.dot $graph

 # Display the shortest path nodes and arcs using the pl_ helper
 # functions
 set pNode [DGA::pl_node $pl $endNode]
 set pArc  [DGA::pl_arc $pl $endNode]
 set pDist [DGA::pl_dist $pl $endNode]
 puts "$endNode $pDist $pArc"
 while {1} {
     set pDist [DGA::pl_dist $pl $pNode]
     set pArc  [DGA::pl_arc $pl $pNode]
     puts "$pNode $pDist $pArc"
     set pNode [DGA::pl_node $pl $pNode]
     if { $pNode == {} } { break }
 }

 # Tidy up the graph
 $graph destroy