tcllib-devel — Discussion of development for tcllib

Re: [Tcllib-devel] Graph Manipulations

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

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 ...

Re: [Tcllib-devel] Graph Manipulations

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

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 ).
>  
> So, this is how it looks for now:)

Ok and thank you. I will look through this over the day and then come back to 
you. In the mean time I also send out my treatise on writing test cases, a 
minute ago, I guess it crossed paths with your mail.

Andreas.

Re: [Tcllib-devel] gsoc'09 - Re: Graph Manipulations

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

Andreas Kupries wrote:
>> 4. Tests ( with tcltest package ). I'm going to construct some special 
>> cases and build some graphs, where especially algorithm could fail. For 
>> approximation algorithms, surely will be needed Tight Examples ( cases 
>> where algorithm gets it's maximum approximation factor ). If you can 
>> give me some remarks about tests I would appreciate.
> 
> I will definitely try. This one is also a point where I have to think a bit 
> more before writing, thus not an immediate answer in this mail.

The promised treatise on writing test cases ...


Thinking about past tests and testsuites I am currently seeing three levels of 
tests ...

First, "drudgery" tests. Written to check absolutely basic assumptions which 
should never fail.

Example: For a command FOO taking two arguments, three tests calling it with 
zero, one, and three arguments. The basic checks that the command fails if it 
has not enough arguments, or too many.

After that come the tests checking things based on our knowledge of the 
command, about its properties and assumptions. Some examples:

**	The BellmanFord takes a _startnode_ as argument, and this node should
	be a node of the graph. equals one test case checking the behavior
	when the specified node is not a node a graph.

	This often gives rise to code in the implementation which explicitly
	checks the assumption and throws a nice error. Instead of letting the
	algorithm fails later in some weird non-deterministic way.

	Such checks cannot be done always. The graph argument for example is
	just a command in itself, and while we expect it to exhibit a certain
	interface, i.e. set of sub-commands aka methods, we cannot check that
	it has them, except by actually trying to use them. That is done by the
	algorithm anyway, so an explicit check is just overhead we can get by
	without.

**	IIRC one of the distinguishing characteristic of either BellmanFord
	and/or Johnson is that they are able to handle negative weights.
	Whereas Dijkstra requires positive weights.

	This makes three testcases ... Graph with all positive weights, all
	negative, and a mix of positive and negative weights.

	Thinking about it, do the algorithm handle weight '0' as well ? Another
	test case, or several, if we mix zero with positive and negative
	weights.

**	The two algorithms we are currently thinking about are about distances
	between nodes, and distance can be 'Inf'inity, i.e. nodes may not be
	connected. This means that good test cases are

	(1)	Strongly connected graph
	(2)	Connected graph
	(3)	Disconnected graph.

	At the extremes of (1) and (3) we have the fully connected graphs and
	graphs without edges, only nodes, i.e. completely disconnected.

**	IIRC both of the algorithms take weighted arcs, and fill in a default
	if arcs are left unweighted in the input graph.

	This also induces three test cases:

	(1)	Graph will all arcs with explicit weights.
	(2)	Graph without weights at all.
	(3)	Graph with mixture of weighted and unweighted graphs.


What I have described above via examples is called 'black-box' testing. Test 
cases are designed and written based on our knowledge of the properties of the 
algorithm and its inputs, without referencing a particular implementation.

Your query about tests for 'maximum approximation factor' falls into this 
category. Your algorithm has extrema, so we should have tests which forces the 
algorithm to these extrema. If we know (how to construct) inputs which do so.


Going further, a complement to 'black-box' testing is 'white-box'. For this we 
know the implementation of the algorithm, we look at it and design our tests 
cases so that they force the code through all possible paths in the 
implementation. Wherever a decision is made we have a test cases forcing a 
specific direction of the decision, for all possible directions.

In practice I often hope that the black-box tests I have made are enough to 
cover all the paths, obviating the need for white-box tests.


So, if you now believe that writing tests for an algorithm takes at least as 
much time as coding the algorithm, and often more time, then you are completely 
right. It does.


An interesting connection is to documentation. In one direction, the properties 
you are checking with black-box testing are properties which should be 
documented in the algorithm man page. And conversely, if you have documentation 
of properties of an algorithm then this is a good reference to base black-box 
tests on.

In practice test cases and documentation often get written together, 
cross-influencing each other. And the actual writing of test cases is a mix of 
black and white box, possibly influencing the implementation while writing the 
tests. Like writing test for 'startnode not in input graph' serving as reminder 
to put in a check for this into the code.

Andreas.

Re: [Tcllib-devel] Graph Manipulations

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

Michał Antoniewski wrote:
> Hello.
>  
> At first, I would like to thank you for your responses. They helped me a 
> lot and made a lot of things clear.

> I will send new files at SVN tomorrow (28 May), containing updated 
> Tcllib version and some test cases.

Ok.

> (0) Main Plan of the work
>  
> You understood it correctly. And of course you're right. I've also 
> wanted to go with implementing code directly to graphops.tcl file and 
> test files but for first week I decided to go with that plan.
>  
> In fact, I'm now working like you said - straight on tcllib files. 
> Bellman-Ford and Johnson's implementations are now in graphops.tcl ( and 
> they work ).
>  
> Thanks a lot for README.developer - it was very helpful.

This file is actually in Tcllib, in the toplevel directory, although the CVS 
head is still a bit older than what I gave you.

> More about that matter in (5).


> (1) Johnson's - return value.
>  
> Like you said, setting [list $node1 $node2] was solution to this 
> problem. I've already corrected it.
>  
> I've got one more concern about returning values in both : Johnson's and 
> Bellman-Ford's. Thanks for info about Infinity value, I changed it. But 
> what about situation when there is no connection between two nodes? 

> There are two options:
> A) return Inf value for each pair of nodes between which path doesn't exist.
> B) return only pairs of nodes (or in case of Bellman-Ford nodes) between 
> which path does exist
>  
> Latter rule (B) cuts the return value only to connections in graph that 
> we are interested in (only existing ones). On the other hand 
> ::struct::graph::op::dijkstra is made according to A rule. What solution 
> do you prefer?

Hm ... I would prefer to stay consistent with 'dijkstra', that way the three 
commands are (roughly) interchangeable from the API point of view. So, (A).
The other form, i.e. (B), can be generated from that, by dropping all pairs 
with distance 'Inf'. Should we run into scaling trouble (i.e. large graphs), we 
can still switch to (B).


> (2)  Bug with GraphTransformation proc
>  
>      It is now corrected. Procedure now returns node that was added, so 
> it can be deleted from the graph when it is needed ( without a risk that 
> node names will overlap ).

Ok, so you are going for modification of the input in-place, with reversal of 
the changes at the end, so the input looks to be unchanged by the algorithm. 
That works too.

> I arranged it as auxiliary-procedure in graph::op ( it is not contained 
> in namespace ).

Hm. That I will have to see, I believe, before I comment.

> As I've noticed that in graph::op, there aren't many procedures like 
> this, and it shouldn't be useful also for other algorithms, maybe 
> dividing Johnsons procedure isn't good idea. I think I'm going to place 
> GraphTransformation into Johnson's proc - this will be more intuitive 
> and algorithm will be in one proc, which we can analyze step by step.

It depends on the complexity of the actions a bit. Even if the code is not used 
by anything but Johnson's it can make sense to place the commands into (a) 
procedure(s), to make/keep the main function (more) readable/short. Otherwise 
complex setup commands may distract from the main algorithm.

This is a bit of a judgment call, and may depend on personal aesthetics.

> (3) TclChecker
>  
> Thanks for that remark - it is now corrected. Moreover, 
> http://wiki.tcl.tk/10225 was very interesting.

Our Wiki is a wonderful and invaluable resource in general, IMHO.

> About TclDevKit license - of course I'm interested in it. Thank you very 
> much for that - I'm sure it will be very helpful.

Ok. The Tcl Dev Kit can be retrieved at
	http://www.activestate.com/tcl_dev_kit/
	(Use the 'Try It' link).

and I will start the process for the license here.

> (4) Tcl 8.5 - integration
>  
> Yes, it's very important case. As in first week, there is a lot to 
> discuss, I would like to get back to it, straight after I will be sure 
> about some other things.

Sure.

>  
> (5) Tests

> Some remarks:
>  
> As I see in other implementations, each algorithm implementation should 
> firstly check if graph given at input is valid.
> So, surely it should be added to algorithm code and there should be 
> created tests for it - e.g. checking if graph has weights set on all edges.

IIRC you handled that case by forcing weights on the edges without them (set 
allunweighted ...).

I have some thoughts about tests circulating in my mind ever since your Monday 
mail, which I really should write up. They should be mostly coherent by now, I 
believe (I usually try to not think consciously about it, but let my 
subconscious work things out before starting to write).


> As I said before tests I created will be availible tomorrow at SVN - I 
> will try to comment them well to set clearly, what each of them is for.

Ok. Looking forward to it.

Andreas.

Re: [Tcllib-devel] To disable teapot libraries

[KATO K. <k.k...@gm...>]

Andreas Kupries wrote:
> To avoid all this and make sure that we are testing the code in the Tcllib
> we are working with, instead of something installed, Tcllib provides a
> number of helper commands in the devtools/testutilities.tcl file

OK... Thank you.

I decided not to use 'package require' on the tests.
Since it develops also except the predetermined directory in tcllib,
'source' will be used simply.

Re: [Tcllib-devel] gsoc'09 - Re: Graph Manipulations

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

Kevin Kenny wrote:
> Andreas Kupries wrote:
>> Yes. The standard strings are "Inf" and "-Inf".
>>
>> Kevin, do you have anything to add here, as one of the guys knowing the math 
>> stuff in the Tcl core better than most ?
> 
> Nothing you didn't already say. Inf and -Inf are parsed as floating
> point numbers.

Ok. Thank you for your time.

Andreas.

Re: [Tcllib-devel] gsoc'09 - Re: Graph Manipulations

[Kevin K. <ke...@ac...>]

Andreas Kupries wrote:
> 1. What about infinity values... In my implementation of Bellman Fords I 
>> just added string "inf", as a value of infinity ( in initialization we 
>> assign value of infinity on each distance we are searching for). Is it 
>> okay, or you've got other way to assign those values?
> 
> Let me check something ... I believe that in Tcl 8.5 we have standard strings 
> for the infinities already. Matching these would be a good thing, even if we 
> are working with Tcl 8.4 ...
> 
> 	% tclsh
> 	% info patchlevel
> 	8.5.7
> 	% expr log(0)
> 	-Inf
> 
> Yes. The standard strings are "Inf" and "-Inf".
> 
> Kevin, do you have anything to add here, as one of the guys knowing the math 
> stuff in the Tcl core better than most ?

Nothing you didn't already say. Inf and -Inf are parsed as floating
point numbers.

-- 
73 de ke9tv/2, Kevin

Re: [Tcllib-devel] Graph Manipulations

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

Michał Antoniewski wrote:
> Hello.

> 3. Generally, I'm implementing algorithms as normal procedures. Then 
> after writing tests and checking if those procedures work well, they 
> should be placed in tcllib ( just like hierarchy at SVN says). Do you 
> accept this approach?

Having seen the code now I believe I begin to understand what you are doing and 
asking here.

	In essence you are writing each algorithm X as a set of global
	procedures in a file X.tcl, including basic test cases at the bottom of
	file.

	Then, when you are satisfied with the implementation you plan to
	transfer the set of procedures to the struct/graphops.tcl file, and
	rename them so that they are in the proper namespace. The test code you
	further plan to transform into a set of regular test cases which are
	then put into a .test file under struct/graph/tests directory.

Is this understanding of your planning correct ?

The question you should ask yourself here is

	What are the advantages, if any, of this approach over the alternative,
	i.e. of working directly within the struct/graphops.tcl file, and the
	tests files under struct/graph/tests ?

	Conversely, what are the disadvantages of this approach ?

One disadvantage, in my opinion, is that you are doing something in two steps 
(code, and transfer) where one step would be sufficient (code). This is a 
disadvantage in my eyes because the transfer step is simply one more place 
where bugs can be introduced. Does that make sense to you ?

Andreas.

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.

Re: [Tcllib-devel] Graph Manip

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

Michał Antoniewski wrote:
> Hello.
>  
> Some new questions:
>  
> Johnson's and BellmanFord's implementations are done and I think they 
> work well ( I tested them for some example graphs and checked single 
> steps of algorithms).

The example graphs should be made into test cases ...

 > Now I'm going to create proper tcltest test cases
> to be 100% sure. But tell me :
>  
> I made Johnson's procedure to return dictionary containing distances for 
> all pair of vertices in format e.g. node1node2 distance12, where node1 
> connected with node2 is key (for a dict) and distance12 is value for 
> distance between node1 and node2. You can check it in file at assembla - 
> just start it for example graph I made there.

Ok, the form node1node2 as is is not very good as key to your result dictionary.

I can readily envision four node names A, B, C, D where AB = CD, thus clashing 
in the result dictionary.

Trivial example
	A = ab
	B = c
	C = a
	D = bc

Now	AB = abc = CD

The solution to this problem is to use [list $node $node2] as key. This form 
puts the two node names into the key without letting them loose their identity. 
For the example above we now readily distinguish

	{ab c}
from	{a bc}

where before we could not.

Often people use a simple separator like ',' to separate the parts of the key 
for a multi-dimensional array (which we have here, albeit as a value, i.e. 
dict). I.e.

	node1   = A
	node2   = B
	key	= A,B

This works best in situations where the programmer has control over the sub 
keys, for otherwise an analogous situation can be constructed where keys clash. 
This is what makes this solution unsuitable here.

	A = a,b
	B = c
	C = a
	D = b,c

	A,B = a,b,c = C,D

The list quoting I proposed however will work correctly even if the node names 
contain spaces (our nominal separator), because then these spaces will get 
quoted for the list element, preserving identity of the parts.

	A = 'a b'
	B = c
	C = a
	D = 'b c'

list $A $B = {{a b} c}
list $C $D = {a {b c}}


> Do you have any remarks about format of values Johnson's procedure 
> returns? Maybe you've got any better idea - I'm just connecting node 
> names for each pair.

Andreas.

Re: [Tcllib-devel] To disable teapot libraries

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

KATO Kanryu wrote:
> When I single-tested tcllib/yaml.test,
> I found "package require yaml" put teapot/yaml-0.3.3.tm before "./yaml.tcl".
> 
> So I had to rename yaml-0.3.3.tm to yaml-0.3.3.tm.nouse.
> 
> How to escape this problem?

Hi.

This is a problem which has been solved for the tcllib testsuite. By not using 
the 'package' command. The problem with 'package' is that you cannot specify 
explicitly which code to use, except by listing a version number.

And if multiple implementations of the package with the same version exist the 
package system is free to choose randomly which to take. And in the case of Tcl 
Modules being being present things become even more quirkier.

To avoid all this and make sure that we are testing the code in the Tcllib we 
are working with, instead of something installed, Tcllib provides a number of 
helper commands in the devtools/testutilities.tcl file

Here is an example of their use taken from report/report.test

	# ------------------------------------------------------------------

[1]	source [file join \
	        [file dirname [file dirname [file join [pwd] [info script]]]] \
	        devtools testutilities.tcl]

	testsNeedTcl     8.2
	testsNeedTcltest 1.0

[2]	support {
[3]	    use struct/matrix.tcl struct::matrix
	}
[2]	testing {
[3]	    useLocal report.tcl report
	}

	# -------------------------------------------------------------------

(Ad 1)	First we are loading the test utilities, using a path relative to the
	location of the .test file.

(Ad 2)	The support and testing commands simply define a bit of context for the
	useXXX commands inside. Here we basically declare which package is
	under test (testing), and which other packages we load to just support
	the testing and the package test (support).

(Ad 3)	The 'use' command takes a path relative to the modules/ directory, and
	the name of the package provided by the referenced file, and loads it.

	The 'useLocal' command is similar, except that the path is relative to
	the directory the .test is in.


> I implement for single test for yaml.test beginning.
> 
> --------------------------------------------------------
> # lappend auto_path [pwd]
> set auto_path [linsert $auto_path 0 [pwd]]
> package require tcltest
> namespace import ::tcltest::*
> puts [package require yaml]
> --------------------------------------------------------


For yaml the equivalent code would look similar to

	# ------------------------------------------------------------------

	source [file join \
	        [file dirname [file dirname [file join [pwd] [info script]]]] \
	        devtools testutilities.tcl]

	testsNeedTcl     8.x ; ## Which version of Tcl is needed by yaml ?
	testsNeedTcltest 1.0 ; ## Which version of tclltest ?

	testing {
	    useLocal yaml.tcl yaml
	}

	# -------------------------------------------------------------------


Hope that helps.

Andreas

[Tcllib-devel] gsoc'09 - Re: Graph Manipulations

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

Michał Antoniewski wrote:
> Hello.
> 
> Today, I started my work and I've got some questions.

Ok. I will answer to the best of my abilities. I may explicitly draw in other 
people and their expertise, depending on the context. As of now I will copy our 
conversation to tcllib-devel, allowing the community to chime in as well.

 > As it is in
> timeline I started with Bellman-Ford and Johnson's.
> 
> 1. What about infinity values... In my implementation of Bellman Fords I 
> just added string "inf", as a value of infinity ( in initialization we 
> assign value of infinity on each distance we are searching for). Is it 
> okay, or you've got other way to assign those values?

Let me check something ... I believe that in Tcl 8.5 we have standard strings 
for the infinities already. Matching these would be a good thing, even if we 
are working with Tcl 8.4 ...

	% tclsh
	% info patchlevel
	8.5.7
	% expr log(0)
	-Inf

Yes. The standard strings are "Inf" and "-Inf".

Kevin, do you have anything to add here, as one of the guys knowing the math 
stuff in the Tcl core better than most ?


> 
> 2. Documentation. Should I just extend those html files in tcllib ( 
> graphops.html ) or write my documantation? As we talked it over before - 
> documentation will be made at the end.

Looking over the Tcllib sources I have here I do not see any file named 
"graphops.html". Can you tell me where you found it ?

The documentation format for Tcllib modules and packages is 'doctools'. The 
packages needed to handle this format are in Tcllib itself. All the files 
ending in '.man' in Tcllib are in this format. The 'sak' tool has some commands 
to validate this format, and to convert from doctools to HTML, nroff, etc.

> 3. Generally, I'm implementing algorithms as normal procedures. Then 
> after writing tests and checking if those procedures work well, they 
> should be placed in tcllib ( just like hierarchy at SVN says). Do you 
> accept this approach?

Let me have a look at what you committed so far and then I will come back to 
you on that. In other words, I would like to defer an answer on this one until 
I had a look at the code and have a seen a more concrete example of what you 
are talking about here.


> 4. Tests ( with tcltest package ). I'm going to construct some special 
> cases and build some graphs, where especially algorithm could fail. For 
> approximation algorithms, surely will be needed Tight Examples ( cases 
> where algorithm gets it's maximum approximation factor ). If you can 
> give me some remarks about tests I would appreciate.

I will definitely try. This one is also a point where I have to think a bit 
more before writing, thus not an immediate answer in this mail.

Andreas.

[Tcllib-devel] To disable teapot libraries

[KATO K. <k.k...@gm...>]

When I single-tested tcllib/yaml.test,
I found "package require yaml" put teapot/yaml-0.3.3.tm before "./yaml.tcl".

So I had to rename yaml-0.3.3.tm to yaml-0.3.3.tm.nouse.

How to escape this problem?

I implement for single test for yaml.test beginning.

--------------------------------------------------------
# lappend auto_path [pwd]
set auto_path [linsert $auto_path 0 [pwd]]
package require tcltest
namespace import ::tcltest::*
puts [package require yaml]
--------------------------------------------------------

[Tcllib-devel] To compare dicts recursively

[KATO K. <k.k...@gm...>]

On making tests, we often have to compare dict data recursively.
So I have used dictsort in yaml.test .

slebetman implies a way to analyze POT values recursively.
(To see, proc compile_json)
http://wiki.tcl.tk/13419

So I make new dictsort in json.test as dictsort3.
http://tcllib.cvs.sourceforge.net/viewvc/tcllib/tcllib/modules/json/json.test?revision=1.6&view=markup

I think the way makes us to compare POT values easier.

Regards,
Kanryu

Re: [Tcllib-devel] ISO: status of tcllib modules

[Andreas K. <aku...@sh...>]

Kevin wrote 
> 'calendar' was sort of a rough draft of the 8.5 [clock] functionality
> and is no longer relevant (a fully-8.5-compatible [clock] that loads
> into 8.4 is available at SourceForge). I've just never figured out how
> to get rid of it cleanly.

You believe 'calendar' should be removed completely ?

Well, first step would be to remove the references from the installer ...

	% grep calendar support/installation/modules.tcl 
	Exclude calendar
	Module  calendar     _tci _man  _null

second step then to 'cvs remove' the files in the modules/calendar
directory.

-- 
So long,
	Andreas Kupries <aku...@sh...>
			<http://www.purl.org/NET/akupries/>
	Developer @	<http://www.activestate.com/>
-------------------------------------------------------------------------------

Re: [Tcllib-devel] ISO: status of tcllib modules

[Kevin K. <ke...@ac...>]

Larry W. Virden wrote:
> It appears that currently the following modules are not installed
> by the tcllib install makefile target:
> 
> calendar
> devtools
> doctools2base
> doctools2idx
> imap4
> rest
> 
> I am guessing that 3 of these - devtools, doctools2base and doctools2idx -
> are there to support tcllib doc generation.
> 
> What about the other 3 modules? Are they no longer supported modules?
> Are modules that are in development but not yet ready for distribution?
> I do notice that the 3 have no .man files - is that what is holding
> them back?
> 
> I'm just curious about the state of the code.

'rest' is brand new and (I presume) Aaron is still working on it.

'calendar' was sort of a rough draft of the 8.5 [clock] functionality
and is no longer relevant (a fully-8.5-compatible [clock] that loads
into 8.4 is available at SourceForge). I've just never figured out how
to get rid of it cleanly.

I don't know about 'imap4'.

-- 
73 de ke9tv/2, Kevin

Re: [Tcllib-devel] ISO: status of tcllib modules

[Aaron F <ro...@fe...>]

rest is new and as such has not been added to the installer yet. I will 
defer to Andreas as to whether that is appropriate. the documentation is 
there but is in need of some formatting.

--Aaron

Andreas Kupries wrote:
> Larry W. Virden wrote:
>> It appears that currently the following modules are not installed
>> by the tcllib install makefile target:
>>
>> calendar
> 
> Explicitly excluded, out of date, deprecated, functional.
> Can be installed, by giving the +exclude option to the installer.
> 
>> devtools
> 
> Internal. Testsuite support and such. Was never installed IIRC, and is not 
> intended to.
> 
>> doctools2base
>> doctools2idx
> 
> Just committed yesterday. doctools v2.
> Still have to redo the 'toc' and 'doc' parts.
> 
>> imap4
> 
> Not included because the code is not in a state fit for use. Was never 
> installed. Nobody ever took this code up to make it usable.
> 
>> rest
> 
> Defering to Aaron Faupell aka RockShox on the state of this.
> 
> 
>> I am guessing that 3 of these - devtools, doctools2base and doctools2idx -
>> are there to support tcllib doc generation.
>>
>> What about the other 3 modules? Are they no longer supported modules?
>> Are modules that are in development but not yet ready for distribution?
>> I do notice that the 3 have no .man files - is that what is holding
>> them back?
> 
> Andreas.
> 

Re: [Tcllib-devel] ISO: status of tcllib modules

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

Larry W. Virden wrote:
> It appears that currently the following modules are not installed
> by the tcllib install makefile target:
> 
> calendar

Explicitly excluded, out of date, deprecated, functional.
Can be installed, by giving the +exclude option to the installer.

> devtools

Internal. Testsuite support and such. Was never installed IIRC, and is not 
intended to.

> doctools2base
> doctools2idx

Just committed yesterday. doctools v2.
Still have to redo the 'toc' and 'doc' parts.

> imap4

Not included because the code is not in a state fit for use. Was never 
installed. Nobody ever took this code up to make it usable.

> rest

Defering to Aaron Faupell aka RockShox on the state of this.


> I am guessing that 3 of these - devtools, doctools2base and doctools2idx -
> are there to support tcllib doc generation.
> 
> What about the other 3 modules? Are they no longer supported modules?
> Are modules that are in development but not yet ready for distribution?
> I do notice that the 3 have no .man files - is that what is holding
> them back?

Andreas.

[Tcllib-devel] ISO: status of tcllib modules

[Larry W. V. <lv...@gm...>]

It appears that currently the following modules are not installed
by the tcllib install makefile target:

calendar
devtools
doctools2base
doctools2idx
imap4
rest

I am guessing that 3 of these - devtools, doctools2base and doctools2idx -
are there to support tcllib doc generation.

What about the other 3 modules? Are they no longer supported modules?
Are modules that are in development but not yet ready for distribution?
I do notice that the 3 have no .man files - is that what is holding
them back?

I'm just curious about the state of the code.

Thank you.


-- 
Tcl - The glue of a new generation.   http://wiki.tcl.tk/
Larry W. Virden
http://www.xanga.com/lvirden/
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.

Re: [Tcllib-devel] [Fwd: [TCLCORE] [Tcl/Tk Community] We need *urgent* advertisement among CS students about Tcl in GSoC 2009]

[Colin M. <co...@ch...>]

> Hi! I'm Tomasz Kosiak.
>
> See Tcl/Tk GSoC 2009 in a pill at http://tinyurl.com/tcl-gsoc2009 and
> this is the only URL students shall write down to get started.
>   

Suggest the project ideas are linked to from the pill.  Suggest it be 
only one slide, if it's only one slide.

> Official news about Tcl/Tk GSoC 2009 is at http://www.tcl.tk/gsoc/ and
> http://wiki.tcl.tk/22182.
>   

Yeah, that ... should be linked to.

Colin

[Tcllib-devel] AsciiDoc

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

http://www.methods.co.nz/asciidoc/

	looks interesting. Have to see what I can steal for doctools.
	Especially the input pieces for formulae, tables, and graphviz.

Andreas.

Re: [Tcllib-devel] tklib and tcllib examples directories

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

Larry W. Virden wrote:
> The README file in tcllib and tklib both say:
> 
>   There is currently one true action for examples, _exa. It copies all
>   files in the source directory for examples into the directory chosen
>   by the user as destination for examples.
> 
> Is that making a reference to actions taken by the release
> coordinator? Because I don't see a Makefile target or configure option
> that would allow a user to choose a destination for examples...

It refers to the installer.tcl script and the code it uses.

It is possible that this option is not made accessible when performing 
installation via 'make install'. I.e. that 'make install' restricts itself to 
applications, the packages, and manpages.

However a direct invokation of installer.tcl from the command line should allow 
you to specify the necessary option (or let you do it from the GUI, if that is 
invoked).

Andreas

[Tcllib-devel] tklib and tcllib examples directories

[Larry W. V. <lv...@gm...>]

The README file in tcllib and tklib both say:

  There is currently one true action for examples, _exa. It copies all
  files in the source directory for examples into the directory chosen
  by the user as destination for examples.

Is that making a reference to actions taken by the release
coordinator? Because I don't see a Makefile target or configure option
that would allow a user to choose a destination for examples...

-- 
Tcl - The glue of a new generation.   http://wiki.tcl.tk/
Larry W. Virden
http://www.xanga.com/lvirden/
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.

[Tcllib-devel] note about tcllib modules/rest/rest.man

[Larry W. V. <lv...@gm...>]

 The meta data at the beginning of modules/rest/rest.man appears to have
 been copied from the tar.man file - the module and title description is
 Tar file handling, but the contents do not correspond to that.

-- 
Tcl - The glue of a new generation.   http://wiki.tcl.tk/
Larry W. Virden
http://www.xanga.com/lvirden/
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.

[Tcllib-devel] note about tcllib modules/rest/rest.man

[Virden, L. W. <lv...@ca...>]

The meta data at the beginning of modules/rest/rest.man appears to have
been copied from the tar.man file - the module and title description is
Tar file handling, but the contents do not correspond to that.
-- 
Tcl - The glue of a new generation.  <URL: http://wiki.tcl.tk/ >
Larry W. Virden <mailto:lv...@ca...><URL: http://www.purl.org/NET/lvirden/ >
Even if explicitly stated to the contrary, nothing in this posting should 
be construed as representing my employer's opinions.
-><-