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

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

New update available. A little description, what's new.

1. I found out, what was wrong with Fleury procedure.

struct::set subtract arcs $arc - that line (1630) doesn't delete any edges
from current set of edges, when edge looks like this
 [list $u $v], so it was causing trouble.

set arcs [$copy arcs] -  I replaced it with that line, which straightly sets
current set of edges used by algorithm from the copy of graph algorithm is
working on. Actually, IMHO that variable "arcs" can be erased from that
implementation.

Now, all tests are passed and "ab c/a bc" problem is corrected in TSP
implementations.


2.  Christofides is using Greedy Max Matching implementation now. For graph
which is a Tight Example, Max Matching finds right solution, and
Christofides goes well too, reaching max approximation factor.

I've created sorting set of edges for a graph as a subprocedure, as it can
be useful. It is used in Max Matching to choose edges with lowest cost at
first. It will be also useful for K-Center problems.

Tests for both TSP problems are updated. I will quickly add some more for
Christofides in next update.

I'm placing tests for subprocedures in files, where tests for procedures
which use them are....should I change it and create separate test files for
them? And should they be tested treating like separate procedures? What I
mean, is for example: is the assumption that weights on arcs in graph given
at input properly set proper ( because previous procedure, which uses that
subprocedure, checks that before ), or there should be at the beginning:

$VerifyWeightsAreOk $G and appropriate tests for it.

I've added also condition for checking, if given graph is connected.


3. Changes in implementation, considering remarks from previous mails for
Max-Cut and TSP problems.

Next coming, Vertices Cover and further implementations and corrections for
Metric K-Center.


Best Regards,
Michal Antoniewski