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

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

Michał Antoniewski wrote:
> Hello.
>  
> I'm writing to clear some matters about Christofides Algorithm:

Ok. Note, please update the algorithm status info in the timeline at 
http://wiki.tcl.tk/23203

> I implemented it with a empty space for MaxMatching use. It still needs 
> some refactoring but I want to clear some things first.

Ok, I will have a look.

> Generally, TSP is problem concerning complete graphs, but there is a way 
> of handling other graphs by adding edges with very big weights

Can these big weights be 'Inf'inity ? Or do they have to be tailired to the 
existing weights in some way ?

 > and then
> working on complete graph - those high costing added edges won't be 
> taken under consideration in finding optimal tour. Would you like to 
> handle those graphs at the beginning of procedure or just assume we get 
> complete graph at input?

> Now it is working, assuming that graph is complete but I can add this 
> feature - I think it is good idea.

Having the code handling non-complete graphs automatically is likely a major 
convenience for users of the command.


> Christofides implementation:
> It uses some graphs: firstly it creates minimum spanning tree graph 
> (TGraph), next is graph for MAx MAtching created by nodes with odd 
> degree from TGraph (oddTGraph). Then oddTGraph is changed to have only 
> edges we need to add to TGraph, and in next step we do M + T, so TGraph 
> gets new edges created by MaxMatching to assure its eulerian. The rest 
> goes like before.
>  
> As max matching is not availible yet I'm testing it by placing correct 
> values returned by max-matching, and checking if all code paths work 
> good. I think for now good idea would be to implement some greedy 
> max-matching, which can be helpful to place some test code (Graphs for 
> tests are ready).

How complicated is the max-matching ? Which is an indirect way of asking, how 
much effort would have to be put into implementing it ?


>  
> Both 2-approximation algorithm and Christofides uses some similar steps 
> but I thought it's not worth to divide them into procedures - this way 
> it looks more clear and intuitive IMHO.

I see. Can't comment on that yet, will do after I had my look through the new code.

>  
> Next update - MAX-CUT. I want to catch up with timeline, but I'm still 
> working on those TSP too.

Andreas.