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

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

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.