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

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

Andreas Kupries wrote:
> Michał Antoniewski wrote:
>> Hello.

Comments between the lines of code


 > 433:	#Metric Travelling Salesman Problem (TSP) - 2 approximation algorithm
 > 434: 
#-------------------------------------------------------------------------------------
 > 435:	#Travelling salesman problem is a very popular problem in graph theory, 
where
 > 436:	#we are trying to find minimal Hamilton cycle in weighted complete 
graph. In other words:
 > 437:	#given a list of cities (nodes) and their pairwise distances (edges), 
the task is to find
 > 438:	#a shortest possible tour that visits each city exactly once.
 > 439:	#TSP problem is NP-Complete, so there is no efficient algorithm to 
solve it. Greedy methods
 > 440:	#are getting extremely slow, with the increase in the set of nodes.
 > 441:	#
 > 442:	#For this algorithm we consider a case when for given graph G, the 
triangle inequality is
 > 443:	#satisfied. So for example, for any three nodes A, B and C the distance 
between A and C must
 > 444:	#be at most the distance from A to B plus the distance from B to C. 
What's important
 > 445:	#most of the considered cases in TSP problem will satisfy this condition.
 > 446:	#
 > 447:	#Input: weighted and complete graph G
 > 448:	#Output: approximated solution of minimum Hamilton Cycle - closed path 
visiting all nodes,
 > 449:	#each exactly one time.
 > 450:	#
 > 451:	#Reference: http://en.wikipedia.org/wiki/Travelling_salesman_problem
 > 452:	#
 > 453:	
 > 454:	proc ::struct::graph::op::MetricTravellingSalesman { G } {
 > 455:		
 > 456:		#checking if all weights are set
 > 457:		VerifyWeightsAreOk $G
 > 458:		
 > 459:		#create minimum spanning tree for graph G
 > 460:		set T [struct::graph::op::prim $G]


 > 461:		#graph algorithm is working on - spanning tree of graph G
 > 462:		set TGraph [struct::graph]
 > 463:		
 > 464:		#fill TGgraph with nodes
 > 465:		foreach n [$G nodes] {
 > 466:			$TGraph node insert
 > 467:		}
 > 468:		
 > 469:		#fill TGraph with arcs
 > 470:		foreach e $T {
 > 471:			set v [$G arc source $e]
 > 472:			set u [$G arc target $e]
 > 473:			$TGraph arc insert $u $v $u$v
 > 474:			$TGraph arc insert $v $u $v$u
 > 475:			$TGraph arc setweight $u$v [$G arc getweight $e]
 > 476:			$TGraph arc setweight $v$u [$G arc getweight $e]
 > 477:		}

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.




 > 478:		
 > 479:		set tourvar 0

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

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

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

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




 > 496:	proc ::struct::graph::op::Christofides { G } {
 > 497:		#checking if all weights are set
 > 498:		VerifyWeightsAreOk $G
 > 499:		
 > 500:		#create minimum spanning tree for graph G
 > 501:		set T [prim $G]
 > 502:		

 > 503:		#graph algorithm is working on - spanning tree of graph G
 > 504:		set TGraph [struct::graph]

 > 506:		#fill TGgraph with nodes
 > 507:		foreach n [$G nodes] {
 > 508:			$TGraph node insert
 > 509:		}
 > 510:		#fill TGraph with arcs
 > 511:		foreach e $T {
 > 512:			set v [$G arc source $e]
 > 513:			set u [$G arc target $e]
 > 514:			$TGraph arc insert $u $v $u$v
 > 515:			$TGraph arc setweight $u$v [$G arc getweight $e]
 > 516:		}
 > 517:				

See my comments above regarding lines 461-477.



 > 505:		set oddTGraph [struct::graph]

I moved this out of the block setting up TGraph to make the separation of the 
two graphs clearer and also that the block can be factored into a helper for 
clarity.

 > 518:		#################
 > 519:	
 > 520:		set oddNodes {}
 > 521:		foreach v [$TGraph nodes] {
 > 522:			if { [ expr {[$TGraph node degree $v] % 2} ] eq 1 } {

Superfluous nested use of expr, and bogus use of string equality operator 'eq' 
over regular (numeric) equality operator '=='.

Strings => 'eq'
Numbers => '=='

 > 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}] } {

Superfluous nested 'expr' command. Just use (...).

Another 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 ?

 > 531:					$oddTGraph arc insert $v $u $v$u
 > 532:				}
 > 533:			}
 > 534:		}
 > 535:		####
 > 536:		#		MAX MATCHING HERE!!!
 > 537:		####
 > 538:		set M {}		
 > 539:				
 > 540:		foreach e [$oddTGraph arcs] {
 > 541:			if { [lsearch $M $e] < 0 } {

Possible alternative:	![struct::set contains $M $e]

(The struct::set commands may have hashtable underneath, making the check faster).


 > 542:				$oddTGraph arc delete $e
 > 543:			}
 > 544:		}
 > 545:		
 > 546:		#operation: M + T
 > 547:		foreach e [$oddTGraph arcs] {
 > 548:			set v [$oddTGraph arc source $e]
 > 549:			set u [$oddTGraph arc target $e]
 > 550:			$TGraph arc insert $u $v $u$v
 > 551:		}
 > 552:		
 > 553:		#################
 > 554:		


 > 555:		set tourvar 0
 > 556:		isEulerian? $TGraph tourvar
 > 557:		
 > 558:		lappend result [$TGraph arc source [lindex $tourvar 0]]
 > 559:		
 > 560:		foreach i $tourvar {
 > 561:			set u [$TGraph arc target $i]
 > 562:			
 > 563:			if { [lsearch $result $u] < 0 } {
 > 564:				lappend result $u
 > 565:			}
 > 566:		}
 > 567:		
 > 568:		return $result
 > 569:		
 > 570:	}

Missing: Deletion of the temporary graph TGraph. This is a memory leak.
	Ditto missing deletion of oddTGraph.

Also, identical to the end of MetricTravelingSalesMan (MTS), worthy of putting 
into a common helper command for both.

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

(Yes, you mentioned this in your mail, however that was a bit low-level a 
description and I had not seen the code yet).



>> I'm writing to clear some matters about Christofides Algorithm:
> 
> Ok. Note, please update the algorithm status info in the timeline at 
> http://wiki.tcl.tk/23203
> 
>> I implemented it with a empty space for MaxMatching use. It still needs 
>> some refactoring but I want to clear some things first.

I agree that the last part of MTS and Christofides, i.e. construction of euler 
tour and hamilton cycle can be put into a helper command common to both.



>>  
>> Both 2-approximation algorithm and Christofides uses some similar steps 
>> but I thought it's not worth to divide them into procedures - this way 
>> it looks more clear and intuitive IMHO.
> 
> I see. Can't comment on that yet, will do after I had my look through the new code.

After seeing the code I believe the opposite to be true.


And some of the operations, like M+T, look like they could be of very general 
use, and maybe something fro th graph structure itself. We can postpone that 
however. This also ties a bit in Lars's message about possible functional 
groups, which I still haven't answered.



>>  
>> Next update - MAX-CUT. I want to catch up with timeline, but I'm still 
>> working on those TSP too.

Andreas.