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

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

Another update available - Fully Working K-Center. A little description.

KCenter procedure uses such subprocedures: sortEdges, extendTwoSquaredGraph
and GreedyMaxIndependentSet.

Generally, it goes like this:
- it searches for solution by extending two-squared graph G(i)**2 with
another edge during each iteration
- the edges are in sorted sequence
- for each found G(i)**2, it finds Mi - maximal independent set with greedy
algorithm
- if |Mi| <= k, the search is ended and solution can be returned

When reviewing code, please go straightly to revision 31 - it's well
commented,  I think it will be fast to go through the code.

About GreedyMaxIndependentSet: there are some tests provided, e.g. test
concerning graph from wiki reference (so there is a graph picture at the
same time:) ).

I've also corrected bug that, I found in extendTwoSquaredGraph procedure.
I'm going to add some test cases to cover that case.



Best Regards,
Michal Antoniewski