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.