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

[Lars H. <Lar...@re...>]

Andreas Kupries skrev:
> 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.

Chiming in (perhaps a bit late), then...

Is there a reason this is titled graph /manipulations/, when most of it 
  is about implementing algorithms that take a graph as input but don't 
aim to change it in any way? Not that I mind (I'm more comfortable 
modelling graphs as immutable data than as mutable objects), but often 
one wants higher level operations that modify graphs than just 
adding/removing one edge/vertex.

As an example, one kind of manipulation that seems useful (especially 
when you get to the flow algorithms, in a couple of weeks) would be an 
operation that splits every vertex in two, where one part receives the 
incoming edges and the other gets the outbound edges, with a new edge 
from in-part to out-part. (This is a classical trick for reducing flow 
problems with capacities on vertices to flow problems with capacities 
only on the edges.)


>  > As it is in
>> timeline I started with Bellman-Ford and Johnson's.

In general, I think time is better spent implementing one algorith each 
for doing A, B, and C, than three different algorithms for doing A, but 
YMMV.

Also, I find the rule applied in struct::graph::op about naming 
commands after algorithms that is a bit curious. There's certainly a 
point in doing so when you've got many algorithms for doing the same 
thing, but on the other hand it renders code employing these commands 
more obscure.

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

Perhaps http://tcllib.sourceforge.net/doc/graphops.html? That one does 
not seem to be listed in http://tcllib.sourceforge.net/doc/index.html, 
though... ;-)

Regarding that previously existing manpage, I notice it documents both 
[struct::graph:op::kruskal] and [struct::graph:op::prim] as computing a 
minimum spanning tree (I presume that should be a minimum /weight/ 
spanning tree) for a graph, but fails to give any distinguishing trait, 
other than the names of the algorithms. While this may be sufficient, 
for a reader with access to the literature, I think the average tcllib 
user would appreciate a bit more information; in particular, I think 
the respective complexities of the commands should be given the 
manpage, especially since the results varies depending on how cleverly 
an algorithm has been implemented. (E.g., looking in a textbook I see a 
naive O(mn) implementation of Kruskal, but also a more efficient O(m 
\log n) implementation, and a note that O(m \alpha(m,n)) is possible.)

IOW, when documenting this kind of command, please give (a good 
estimate of) its complexity as well.


Also, regarding the API provided by struct::graph, I find it a bit 
curious that "weight" is singled out as a special property of arcs, 
with its own methods for setting, getting, and so on. I suspect a more 
practical approach for a higher level package like struct::graph::op 
would be that the weight was some attribute given to the arcs, and that 
a command for computing e.g. a shortest path would take as an argument 
(or option value) the name of the attribute to use as "weight" in this 
particular calculation.

Lars Hellström