Re: [Tcllib-devel] Graph Manip

[Andreas K. <and...@ac...>]

Michał Antoniewski wrote:
> Hello.

I had a look at the BellmanFord{Johnson}.tcl per revision 7 and would like to 
offer the following critiques ...


(1)	Running tclchecker (*) over the code I get lots of warning about

		BellmanFord.tcl:29 (warnExpr) use curly braces to avoid double
		substitution and/or performance degradation
		expr  [dict size $distances]-1

	etc. The solution to this is add braces { ... } around the expression.
	In the example above write

			expr  { [dict size $distances]-1 }
	instead of	expr  [dict size $distances]-1

	without the braces you can get unexpected substitutions, and the
	performance degradation referenced in the warning means that the
	unbrached cannot be byte-compiled. It works, but much slower as it is
	run by the text-interpreter part.

	For additional information and discussion please see
		http://wiki.tcl.tk/10225


(2)	I see that you are using Tcl 8.5 dictionaries.

	This should be indicated by a 'package require Tcl 8.5' command in the
	code. Otherwise someone may try to run it with 8.4 and then ask why it
	isn't working when the first dict error is thrown.

	Note that for the final integration we should do something
	like you can see at the top of json/json.tcl, or even better,
	doctools2toc/import_json.tcl.

	In the case of json.tcl it tries to use the dict compatibility package		if the 
code is not run under 8.5 or better.

	And the import_json.tcl goes one step further and provides a mini
	emulation of the needed dict commands in place if even the dict
	compatibility package is not available.


(3)	Your use of 'graphTransformation' looks to be a bug.

	You say 'set newG [graphTransformation $G]'. That is a OK. If we have
	to change the graph for the algorithm working on a copy is a good
	thing.

	The problem I see is, that implementation of 'graphTransformation'
	doesn't create a copy at all, but modifies the input graph in place.

	A related problem, which is be present even if the proc would make a
	copy is that the special node you are adding has a fixed name 's'.

	This is bad, because the moment the input graph already has a node with 	that 
name you have lost.

	For things like that it is better to use

		set s [$G node insert]

	i.e. create a node without specifying a name. The graph G will then
	itself choose a name which doesn't clash with any existing node names.

	This however also means that the name of the special node may have to
	be remembered somewhere so that	you can address the node where needed
	by the algorithm.


(4)	A bit of confusion. Both BellmanFord.tcl and BellmanFordJohnson.tcl
	seem to have both BellmanFord and Johnson implementations, and it is
	not fully clear to me which is the more current code, if any.


(*)	Regarding tclchecker I have talked to Jeff Hobbs and he has no problem
	with us (ActiveState) giving you a free TclDevKit license. This would
	allow you to run Tcl Dev Kit's tclchecker on your own, and see the
	problems it points out.

	Would you be interested in that ?

	(I strongly recommend the use of static syntax checkers as one more
	arrow in your quiver helping you in the hunting of bugs).


Andreas.