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

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

Andreas Kupries wrote:
> Michał Antoniewski wrote:
> 
>> Update 1 (Revision 12):    New version of Adjacency List.
>>  
>> What's new:
>> - changed the implementation considering your regards - now undirected 
>> case is simpler
>> - lsearch isn't used now  --> lsort
>> - and other lesser changes.
>>  
>> You were of course right about implementation, now it looks much 
>> simpler.

Sometimes you have to just look at things from a slightly different angle.

Ok, yes, that looks much nicer. And it should be easier to understand as well.

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.

Maybe not as easy to write a specialized sorting routine which collapses 
equivalence classes of results into a canonical form, but after such is done 
algorithm changes may not require testsuite changes because of leaked 
implementation details.


(*) And custom sorting commands for more complex data structures.

Andreas.