Re: [Tcllib-devel] ping gsoc graph work ...

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

Hello.

I updated some tests for Max-Cut ( testing subprocedures seperately ).

And now TSP.

After some rethinking I came up with such solution to handle those
uncomplete graphs:
- first step filling graph with edges to have a complete graph. At the same
time saving set of original Edges. Weights on new edges are set to Inf. [ In
practise algorithm is avoiding them anyway, so maybe it's even not needed to
take that step ].

- further, algorithm goes the same, until creating Hamilton Cycle (
procedure findHamiltonCycle ).

- what we were given was the set of nodes ( Hamilton cycle ) given based on
found Eulerian tour. But when graph is not complete edges based on tour
might not exist. So, at each step of adding next node to the result (
Hamilton cycle ), algorithm checks, if edge between given nodes exists. If
it exists, it's allright - we don't need to change nothing. If not - we have
to search for the shortest path between current two nodes and add this path
to solution.

- what I described assumes that we accept doubled occurances of nodes in
solution. Going back to definition of the problem - it says that there
shouldn't be such situations ( TSP problem is finding shortest Hamilton
Cycle, with only one occurance of each vertex ). So, now it's time to
decide, what to do: give that solution I describe above, or in such case
return error that it's not Hamilton's graph ( don't know if I wrote it well,
but I mean graph without proper Hamilton cycle ).

Implementation is at SVN now. I debugged it step by step and it worked for
examples I was testing it, but still there can be some cases needed
consideration - I am on it. When I ran Christofides for it's Tight Example
it gave me the solution that reaches maximum approximation factor ( for
graph with 7 nodes, where OPT* was 6, it found solution with cost 9 ).
It still needs some upgrades ( like probably variable originalEdges will be
erased, as we need at that step whole original graph anyway...and other), so
you don't have to check implementation very strictly now, I just wanted to
show the main idea and next step in work.



[*] By OPT and ALG, I used to name OPTimal solution and solution given by
ALGorithm.

Best Regards,
Michał Antoniewski