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

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

 This block of lines, 461-477, looks to me as something which should be put
> into its own command. I see that Christofides uses a variant of this (lines
> 503-517, without 505), just putting in the arcs instead of duplicating them.
> That can be folded into a single helper, and the duplication of arcs
> controlled by a single boolean argument.


Done.

> 478:
> 479:          set tourvar 0

>Why is the variable initialized to a number, when it becomes a list after
the call ?

When I tested this implementation, sometimes occured that graph wasn't
Eulerian, so this was my way to prevent it from crushing when variable
tourvar is not assigned. As I mentioned before this code needed still some
refactoring, now line 479 isn't needed, forgot to delete it.

> 480:          isEulerian? $TGraph tourvar
> 481:          lappend result [$TGraph arc source [lindex $tourvar 0]]
> 482:
> 483:          foreach i $tourvar {
> 484:                  set u [$TGraph arc target $i]
> 485:
> 486:                  if { [lsearch $result $u] < 0 } {
> 487:                          lappend result $u
> 488:                          set hh [$TGraph arc getweight $i]

 >>      Where is the value 'hh' used ? I do not see anything. If it is not
used
 >>      we can eliminate this I would say. On the other hand, if it should
have
 >>      been used, then something else is missing.

The same as previous one :) Corrected.


> 489:                  }
> 490:          }
> 491:          lappend result [$TGraph arc source [lindex $tourvar 0]]
> 492:          return $result
> 493:
> 494:  }

>>My understanding of this algorithm is that a min-spanning tree is made,
its arcs are then duplicated, and the euler tour >>through that graph is
then reduced into a hamilton cycle by ignoring every node already put into
the result.

>>And the approximation comes from the use of the minimal spanning tree.

Correct. Duplicating arcs gives us confidence that graph is Eulerian.
Finding Eulerian tour gives us sequence of visiting nodes in Hamilton cycle.


>>Missing: Deletion of the temporary graph TGraph. This is a memory leak.

Corrected.

> 496:  proc ::struct::graph::op::Christofides { G } {

>>See my comments above regarding lines 461-477.

Corrected. Other code problems that were noted, corrected as well.


> 523:                          $oddTGraph node insert $v
> 524:                  }
> 525:          }
> 526:
> 527:          #create complete graph
> 528:          foreach v [$oddTGraph nodes] {
> 529:                  foreach u [$oddTGraph nodes] {
> 530:                          if { ![$oddTGraph arc exists $u$v] & ![expr
{$u eq $v}] } {

>>nother problem, maybe: This queries oddTGraph for the existence of arcs,
but at this point oddTGraph contains only nodes >>(added by lines 521-524).
This means that the first part of the condition is always true and
superfluous, right ? Or should this >>condition have queried the TGraph ?

This procedure adds only edges, and when there is an edge between pair of
nodes we don't want another - that's why line 530 looks like this. So,
before adding (e.g. for node X and Y) we are checking if this edge were
added before ( for Y and X ). Loops are also unwelcome.


>>And Christofides becomes a bit clearer to me. Start with minimal spanning
tree, then create a max matching over the nodes >>of odd degree for
side-ways connections, instead of duplicating each arc in the tree. From
this we then construct euler tour >>and hamilton cycle like in the
'MetricTravelingSalesMan'.

Right.

So summarizing:
- added new commands for both TSP algorithms: findHamiltonCycle and
createTGraph.
- correcting code regardning remarks that were mentioned

Now I'm going to add adding edges to handle uncomplete graphs. As a
consequence those graphs can have repeated nodes in the return value ( the
same nodes can occur more than once ).

Best Regards,
Michał Antoniewski