Re: [Tcllib-devel] ping gsoc graph work ...

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

Andreas Kupries wrote:
> Now, I noticed that you changed the tests for adjlist a bit. It seems that the 
> results did not change in their essence, but only in the order nodes were 
> sorted in the various (sub)lists, right ?
> 
> In other words the changed results are in the same equivalence class as the 
> previous ones. There is no significant difference between
> 
> 	{n1 {n2 n3} n2 n1 n3 n1}
> and	{n2 n1 n1 {n3 n2} n3 n1},
> 
> just order, which is irrelevant for our dictionaries.
> 
> This is another issue often seen with test suites. That we check results for 
> exact identity, causing the rejection of perfectly correct results because they 
> are not exactly identical to whatever the previous algorithm created as its result.
> 
> 
> This was particular seen in test suites, here in Tcllib, when the Tcl core went 
> from 8.4 to 8.5. The hash table implementation of the core changed in that 
> transition, causing the results of 'array get' and 'array names' to change, 
> i.e. elements were returned in a different order. This tripped all the 
> testsuites which were not prepared to handle the equivalence class of correct 
> results and tested exactly instead.
> 
> The solution we implemented was to 'lsort' and 'dictsort' (*) the results of 
> the tested commands, projecting all results in an equivalence class to a 
> canonical form for that class. This canonical form can then be tested for exactly.
> 
> For the two adjlist algorithms you implemented it was simply details in the 
> implementation which changed the order.
> 
> I do not believe that we have to update the testsuite right now to take this 
> possibility into account, however please be aware this in the future.

And as a very concrete example I ran the testsuite of modules/struct, with the 
critcl implementation of struct::graph active (*), here is an excerpt:

==== graphop-gcritcl-scritcl-stcritcl-qcritcl-BellmanFord-1.9 BellmanFord, some 
weights set to 0 FAILED
==== Contents of test case:

         SETUP_PARTIALLYZEROWEIGHTED
         set result [struct::graph::op::BellmanFord mygraph node1]
         mygraph destroy
         set result

---- Result was:
node4 1 node3 0 node2 0 node1 0
---- Result should have been (exact matching):
node2 0 node3 0 node4 1 node1 0
==== graphop-gcritcl-scritcl-stcritcl-qcritcl-BellmanFord-1.9 FAILED

The result is correct, it simply presents the nodes in a different order.
For this simple data structure (dictionary) our projection to canonical
can be done by the helper 'dictsort', i.e. by changing

	set result [struct::graph::op::BellmanFord mygraph node1]
to
	set result [dictsort [struct::graph::op::BellmanFord mygraph node1]]

and changing the expected result to
	{node1 0 node2 0 node3 0 node4 1}
i.e. sorting it.

==========================================================
NOTE:
	This is _not_ a request to fix the testsuite now.
	I rather prefer to catch up on our timeline a bit
	This is polish, and can be done at/near the end.
==========================================================

~~~
(*) It is an implementation of struct::graph in C, and part of the differences
     to the Tcl implementation is a the changed order of nodes/arcs returned by
    [G nodes], [G arcs], etc.

Andreas