Re: [Tcllib-devel] GSoC Graph. Review revision 25

[Michał A. <ant...@gm...>]

Vertices Cover algorithm is availiable - implementation + tests.

After implementing standard version, I tested it and it reached max
approximation factor unlikely often. So, I came up with a bit of improvement
and now it finds far better solutions.

Generally, algorithm works by picking an edge, adding source and target
nodes to solution and erasing those two nodes ( so, all edges adjecent to
them also disappear ). My idea, was to sort at the beginning pairs of nodes
(only those between which there is an edge ) with degrees and then do the
algorithm steps. This gives nice boost because, at first we add those nodes
to solution, that when erased the most of the edges will disappear.

I extended also procedure sortEdges into sortGraph, which now takes graph
and sort option at input, and returns sorted dictionary ( edges and weights
or nodes and degrees, I think can be useful ). Maybe, it will be good idea
to put the switch there, and more option parameters can appear to make this
general sorting procedure... Just wondering....:)

Now I remembered that you've written your implementation for sorting too, in
one of previous mails..... I'm gonna review it tomorrow and do the possible
change.

Moreover, I think it could also be useful to implement procedure "graphName
node degrees" (in the same fashion the "graphName arc weights" is
constructed). If you're interested in it, we can add it e.g. at the end of
timeline ( when it turns out that at the end, there will be other tasks to
do, I can do it later, if you like... ).

Going back to Vertices Cover, there is also other way to implement it (with
the same approximation factor) using Greedy Max Matching (which is
implemented already). But I think that version will be less suitable for
other improvements that can be possibly done ( like that degree improvement
).

Tomorrow, I hope full K-Center and starting with flow algorithms.


Best Regards,
Michal Antoniewski