Menu
▾
▴
Re: [Tcllib-devel] Graph Manipulations
|
From: Andreas K. <and...@ac...> - 2009-05-28 18:05:05
|
Michał Antoniewski wrote:
> Update at Assembla is done.
>
> Check : "Tcllib/ver2" folder for updates I enumarated last time.
>
> Some tests are done for smaller graphs just to check some single cases,
> some of them base on more complex graphs and offer more complex tests as
> well ( all those graphs were checked by me, algorithms were firstly done
> on paper step by step, then I debugged my implementations step by step
> to see if they make each operation properly ).
Lets go through the code.
> 106: #Bellman's Ford Algorithm
> 107: #
> 108: #Input:
> 109: #Graph - G
> 110: #Edge weights - w
> 111: #Start node - s
> 112: #
> 113: #Output:
> 114: #Array d[u] of distances of each node from start node
> 115: #Returns 0 if there is a cycle with negative sum of weights
Do you have web references about the algorithm, at wikipedia or other website ?
If yes, adding them to the documentation would be appreciated, as it makes
looking it up much easier.
> 116:
> 117: proc ::struct::graph::op::BellmanFord { G startnode } {
> 118:
> 119: #checking if all edges have their weights set
> 120: VerifyWeightsAreOk $G
> 121:
> 122: #checking if the startnode exists in given graph G
> 123: if {![$G node exists $startnode]} {
> 124: return -code error "node \"$startnode\" does not exist in graph \"$G\""
> 125: }
The indentation doesn't look too nice, this however is a nit, i.e. this can be
fixed later. Even so, it looks nicer if it properly indented from the beginning.
May I ask what editor you use ? If it is emacs your buffer mode should be Tcl,
and the command ESC C-\, aka 'indent-region', can be used to indent a whole
block (marker to cursor) nicely.
Other editors may have similar commands.
> 126:
> 127: # nodes of graph G
> 128: set V [$G nodes]
> 129: set E [$G arcs]
> 130:
> 131: #initialization
> 132: foreach i $V {
> 133: dict set distances $i Inf
> 134: }
> 135:
> 136: dict set distances $startnode 0
> 137:
> 138: #main loop
> 139: for { set i 1 } { $i <= [ expr { [dict size $distances]-1 } ] } { incr i } {
The second argument of 'for' is an expression already, making nested 'expr'
command superfluous and just the code less readable.
I.e. the
{ $i <= [ expr { [dict size $distances]-1 } ] }
should be written as
{ $i <= ([dict size $distances]-1) }
> 140:
> 141: foreach j $E {
> 142: set u [$G arc source $j] ;# start node of edge j
> 143: set v [$G arc target $j] ;# end node of edge j
> 144:
> 145: if { [dict get $distances $v] > [expr [ dict get $distances $u ] + [$G arc getweight $j]] } {
Ditto here, the first argument of 'if' is an expression, and nested expr
commands are superfluous.
> 146: dict set distances $v [expr [dict get $distances $u] + [$G arc getweight $j]]
Brace your expressions.
> 147: }
> 148: }
> 149: }
> 150:
> 151: #checking if there exists cycle with negative sum of weights
> 152: foreach i $E {
> 153: set u [$G arc source $i] ;# start node of edge i
> 154: set v [$G arc target $i] ;# end node of edge i
> 155:
> 156: if { [dict get $distances $v] > [expr [ dict get $distances $u ] + [$G arc getweight $i]] } {
> 157: return 0
Uh. Compare to line 161. Your command has a varying return type. 0 for this
case, versus a dictionary. Looking back I see it documented in lines 114 and 115.
Even so, this is not a good API design. The caller will have to go through
contortions to handle this type of thing ... I.e. check for length of result,
if 1 then it is likely this case, so we check for the 0. Otherwise it is a dict.
Now, is this case of a 'cycle with negative sum of weights' an error case of
the algorithm ? Then it is likely better to actually throw an error, i.e.
'return -code error ...'
Even returning an empty dictionary, i.e. {} is better as we can then be sure
that the return-type is always a dictionary.
> 158: }
> 159: }
> 160:
> 161: return $distances
> 162:
> 163: }
> 166: #Johnsons Algorithm
> 167: #-------------------------------------------------------------------------
> 168: #Input:
> 169: # graph G, possible options:
> 170: # -cutdisplay ( returns only existing distances, cuts all Inf values )
> 171: #
> 172: #Output:
> 173: # dictionary containing distances from each pair of vertices
> 174: # returns 0 if cycle with negative sum of weights at edges is found
Same thing I as mentioned for BellmanFord, either throw an error or at least
use the empty dictionary {} as result for the exceptional case, to have a
single return-type, not a mix
> 175:
> 176: proc ::struct::graph::op::Johnsons { G args} {
> 177:
> 178: #options for procedure
The procedure argument 'args' is always a list, and should be processed with
list commands.
> 179: if { $args eq "-cutdisplay" } {
> 180: set param 1
> 181: } elseif { $args eq "" } {
> 182: set param 0
> 183: } else {
> 184: return -code error "Bad option given. Available options: -cutdisplay"
> 185: }
More canonical would be
set param 0 ; # default
foreach option args {
switch -exact -- $option {
-cutdisplay {
set param 1
}
default {
return -code error "Bad option \"$option\". Expected -cutdisplay"
}
}
}
Other notes
* The name of the variable for an option should reflect a connection to
the option. When I read 'param' later I will not think of
'-cutdisplay'.
* The name -cutdisplay does not evoke (for me) a connection to the
removal of infinities either.
> 186:
> 187: #checking if all edges have their weights set
> 188: VerifyWeightsAreOk $G
> 189:
> 190: #Transformation of graph G - adding one more node connected with
> 191: #each existing node with an edge, which weight is 0
> 192: set V [$G nodes]
> 193: set s [$G node insert]
> 194:
> 195: foreach i $V {
> 196: if { $i ne $s } {
> 197: $G arc insert $s $i
> 198: }
> 199: }
> 200:
> 201: $G arc setunweighted
> 202:
> 203: #potential values
> 204: set h [BellmanFord $G $s]
> 205:
> 206: #are there any negative cycles?
> 207: if { $h eq 0 } {
> 208: return 0
> 209: } else {
Remember my note regarding throwing an error for the 'cycle with negative
weight'. Using the empty dict the check changes to
if { ![llength $h] } {
When an error is thrown this error has to be caught and re-thrown, to allow us
to undo the addition of the special start node $s (see my note below about that)
> 210:
> 211: $G node delete $s
Should this not happen for the error case above as well ?
I.e. right now the graph is left modified if the input had a negative cycle.
> 212:
> 213: #setting new weights for edges in graph G
> 214: foreach i [$G arcs] {
> 215: set u [$G arc source $i]
> 216: set v [$G arc target $i]
> 217:
> 218: $G arc setweight $i [ expr [$G arc getweight $i] + [dict get $h $u] - [dict get $h $v] ]
Brace your expressions.
We should document that the weights on the graph are changed ... Hm, reading
further I see that you undo the re-weighting in the distances you are pulling
out of dijkstra.
Does that mean we should undo this change to the graph as well ?
If this re-weighting is like the special node we added, then yes.
> 219: }
> 220:
> 221: #finding distances between all pair of nodes
> 222: foreach i [$G nodes] {
> 223: set dijkstra [::struct::graph::op::dijkstra $G $i -arcmode directed -outputformat distances]
As Johnson is defined in the same namespace as dijkstra we can use just
'dijkstra' as the command name. See also line 204 where this is done.
> 224:
> 225: foreach j [$G nodes] {
> 226: if { $i ne $j } {
> 227: if { $param eq 1 } {
As 'param' is a boolean (values 0, 1) a comparison is not required.
Writing
if { $param } { ...
is sufficient and more readable as well. Having the variable now named to evoke
a connection to -cutdisplay and the code is a bit more self-documenting as
well, no need to remember what it stood for.
> 228: if { [dict get $dijkstra $j] ne "Inf" } {
> 229: dict set values [list $i $j] [ expr [ dict get $dijkstra $j] - [dict get $h $i] + [dict get $h $j] ]
Brace your expressions.
> 230: }
> 231: } else {
> 232: dict set values [list $i $j] [ expr [ dict get $dijkstra $j] - [dict get $h $i] + [dict get $h $j] ]
Brace your expressions.
> 233: }
> 234: }
> 235: }
> 236:
> 237: }
> 238: }
> 239:
> 240: return $values
> 241: }
> 242:
Next up, the test cases ...
|
