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

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

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

> Updated.

Thank you.

>  >>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... 
> <mailto: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...:)

That is no trouble. Either I am outside walking some park, without net 
connection (= not bothered at all), or I am inside reading, and then I can 
reading about graphs as well.


>  >>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:) ).

I see. Sort of what I often do ... Get the small stuff/fry out of the way 
first, working up to the more complex pieces.

So it was intentional, not an oversight. For future projects to note, I believe 
that it is a good idea to explicitly document such decisions to avoid questions 
later.

> 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.

Looking forward to it.

Andreas.