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.