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

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

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

>>Ok. Although I am a bit behind on my mail here. Looking at the time this
mail missed me by a few minutes on Friday. And I >>am not reading office
mail from the home system (*). Can I entice you to send your mails not only
to me, but
>>      Tcllib Developers <tcl...@li...>
>>as well ? That will reach me at home too, as I subscribed both office and
personal email adresses to the list.

No problem:) I didn't write at your home address, cause I didn't want to
bother you during weekend too...:)

>>A bit of chiding here. A reason that the mentors ask the students for the
timeline of their project is to have them think about >>and become aware of
such dependencies.

I know it's not a good sequence that TSP using MaxMatching is before
MaxMatching itself, but I strongly wanted to have MaxMatching at the end,
cause as far as I know it's implementation can be troublesome, so when I
have everything other done and there is only Max Matching it would easier to
focus and it won't cause any delays in timeline, as I estimated it could
when done earlier. Maybe, it will turn out that implementation will go
smoothly, without any problems and those "safety measures" were not required
( I hope:) ).

About TSP:

>>One thing this would depend on is whether the route found is required to
be a cycle, or can visit vertices more than once.

I would stick to definition of the problem, which says that we are looking
for path (with minimal cost) which visits each node exactly once, and ends
in the starting node.


One more way to handle MaxMatching case can be implementing greedy
MaxMatching, for graphs with even number of nodes.
Then, it's possible to write test cases, forcing test graphs to have even
number of nodes in their minimal spanning tree found in the first step of
the algorithm. That way, we can test the TSP procedure and only add some
tests when proper MaxMatching is done ( tight examples for Christofides also
have even number of nodes in min spanning tree).

Regarding your notes about both TSP algorithms, I'm going to divide them
into some auxiliary procedures.

Best Regards,
Michał Antoniewski