|
From: Andreas K. <and...@ac...> - 2009-06-23 19:30:15
|
Review of changes to the TSP code in revision 19 ...
> 462: set TGraph [struct::graph]
> 463:
> 464: #filling graph TGraph with edges and nodes
> 465: set TGraph [createTGraph $G $T 0]
We seem to create TGraph twice here. ... Yes, createTGraph also
creates the graph. So we still have a leaked graph object, created on
line 462. I guess that line 462 can be deleted, was forgotten.
> 488: #graph algorithm is working on - spanning tree of graph G
> 489: set TGraph [struct::graph]
> 490: set TGraph [createTGraph $G $T 1]
See above, about lines 462, 465. TGraph created twice, object of line 489 leaked.
> 501: #create complete graph
> 502: foreach v [$oddTGraph nodes] {
> 503: foreach u [$oddTGraph nodes] {
> 504: if { ![$oddTGraph arc exists $u$v] & !($u eq $v) } {
Ah, I missed something in my first review. I didn't see the !
operator, I guess due to the nested expr nearby. The complement to
the eq'ual operator is 'ne' for 'not equal.
if { ![$oddTGraph arc exists $u$v] & ($u ne $v) } {
Also a reminder about the $u$v problem, nodes a/bc vs ab/c giving us identical
arc names.
> 534: #Finds Hamilton cycle in given graph G
> 535: #Procedure used by Metric TSP Algorithms:
> 536: #Christofides and Metric TSP 2-approximation algorithm
> 537:
> 538: proc ::struct::graph::op::findHamiltonCycle {G} {
> 539: isEulerian? $G tourvar
> 540:
> 541: lappend result [$G arc source [lindex $tourvar 0]]
> 542:
> 543: foreach i $tourvar {
> 544: set u [$G arc target $i]
> 545:
> 546: if { [lsearch $result $u] < 0 } {
'ni' operator.
> 547: lappend result $u
> 548: }
> 549: }
> 550: lappend result [$G arc source [lindex $tourvar 0]]
> 551: return $result
> 552: }
> 553:
> 554: #Creating graph from sets of given nodes and edges
> 555: #In option param we decide if we want edges to be
> 556: #duplicated or not
> 557: #0 - duplicated (Metric TSP 2-approximation algorithm)
> 558: #1 - single (Christofides Alogrithm)
> 559:
> 560: proc ::struct::graph::op::createTGraph {G Edges param} {
Naming. param => 'doublearcs' or similar.
> 561: set TGraph [graph]
Does that (graph) work? Shouldn't it be 'struct::graph' ? Because we
are in the struct::graph::op namespace, which doesn't have a
struct::graph::op::graph command. Nor do we have a ::graph
command. Well, we should not. We might have one in the testsuite,
masking the problem.
Andreas.
|