[Tcllib-devel] Review rev 41 - Re: Graphops - Documentation

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

 > 1360:			if { ($paths == {}) || (![dict exists $paths $t]) } break

In case of '$paths == {}' being true the ![dict exists $paths $t] should be 
true as well. And conversely, if [dict exists $paths $t], then paths != {} too.

Meaning that the '![dict exists $paths $t]' condition should be all that is needed.


 > 1649:			if { ($paths == {}) || (![dict exists $paths $t]) } break

Ditto.

 > 2141:			if { $paths == {} } break
 > 2142:			if { ![dict exists $paths $t] } break

Ditto.


 > 2480:	proc ::struct::graph::op::findExcess {G node b} {
 > 2481:	
 > 2482:		set incoming 0
 > 2483:		set outcoming 0
 > 2484:		
 > 2485:		foreach key [dict keys $b] {
 > 2486:			
 > 2487:			lassign $key u v
 > 2488:			if { $u eq $node } {
 > 2489:				set outcoming [ expr { $outcoming + [dict get $b $key] } ]
 > 2490:			}
 > 2491:			if { $v eq $node } {
 > 2492:				set incoming [ expr { $incoming + [dict get $b $key] } ]
 > 2493:			}		
 > 2494:		}

Just noted
	http://docs.activestate.com/activetcl/8.5/tcl/TclCmd/dict.htm#M16

dict keys allows a glob pattern to select specific keys. Using that ability a 
slightly different set of loops is possible. Two loops, and the conditional is 
hidden in the 'dict keys' commands, and done at C-level.

		foreach key [dict keys $b [list $node *]] {
			set outcoming [ expr { $outcoming + [dict get $b $key] } ]
		}

		foreach key [dict keys $b [list * $node]] {
			set incoming [ expr { $incoming + [dict get $b $key] } ]
		}

My apologies, I did not notice that before. We might have other loops which can 
benefit from this.

 > 2498:	
 > 2499:	#Travelling Salesman Problem - Heuristic of local searching
 > 2500:	#2 - approximation Algorithm
 > 2501: 
#-------------------------------------------------------------------------------------
 > 2502:	#
 > 2503:	
 > 2504:	proc ::struct::graph::op::TSPLocalSearching {G C} {
 > 2505:		
 > 2506:		foreach arc $C {
 > 2507:			if { ![$G arc exists $arc] } {
 > 2508:				return -code error "Given cycle has arcs not included in graph G."
 > 2509:			}
 > 2510:		}


C = cycle in G ? Should possibly also check that adjacent arcs share a node, 
and the destination node of the last arc matches the sourcen ode of the first 
(== ensure that it is a cycle). Is it also required to be a cycle through all 
nodes ?

G is complete graph I guess?

 > 2567:						#we consider only arcs that are not adjacent
 > 2568:						if { !($iu eq $ju) && !($iu eq $jv) && !($iv eq $ju) && !($iv eq 
$jv) } {

	!($x eq $y) <==> ($x ne $y)


 > 2569:					
 > 2570:							#set the current cycle
 > 2571:							set CPrim [copyGraph $CGraph]
 > 2572:						
 > 2573:							#transform the current cycle:
 > 2574:							#1.
 > 2575:							$CPrim arc delete $i
 > 2576:							$CPrim arc delete $j
 > 2577:						
 > 2578:						
 > 2579:							set param 0

	param means 'no new edges' ?

 > 2601:						
 > 2602:							$CPrim arc setunweighted 1
 > 2603:						
 > 2604:							#check if it's still a cycle or if any arcs were added instead 
those erased
 > 2605:							if { !([struct::graph::op::distance $CPrim $iu $ju] > 0 ) || 
$param } {

Move param check to front, allow skipping of expensive 'distance' op.

 > 2606:						
 > 2607:								#deleting new edges if they were added before in current iteration
 > 2608:								if { !$param } {
 > 2609:									$CPrim arc delete [list $iu $ju]
 > 2610:								}						
 > 2611:							
 > 2612:								if { !$param } {
 > 2613:									$CPrim arc delete [list $iv $jv]
 > 2614:								}

These two blocks can be merged into one I would say, based on the fact that 
they have the same condition. Or should they have different conditions ?


 > 2632:						
 > 2633:							#count current value of cycle
 > 2634:							set cycleWeight [countCycleWeight $CPrim]


This we might be able to perform incrementally in the future, by keeping track 
of the erase/add operations and the changes they cause to the total weight.

 > 2676:	proc ::struct::graph::op::copyGraph {G} {

This procedure might be applicable to other algorithms. I haven't
checked backed however. There were so many graph copy ops I lost track
of which had been identical, all the slight differences.


Andreas.