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

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

Michał Antoniewski wrote:
> Vertices Cover algorithm is availiable - implementation + tests.

Looking forward to the commit ... I.e. this doesn't seem to be available in the 
repository yet.

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

Reading up on the definition ... Yes, that sounds sensible.

> 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....:)

Hm.

> 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... ).

Hm. Could be convenient. On the other hand, this is also

	[$G node degrees $N] <=> [llength [$G node degree $N]]

so the method would be mostly syntactical sugar ... Lets decide at the end.

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

Andreas.