Re: [Tcllib-devel] Busacker-Gowen

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

> I will review revision 35 sometime today.

The testsuite for Busacker-Gowen is currently very sparse.

 > 1491:	#Subprocedure for Busacker Gowen algorithm
 > 1492:	#
 > 1493:	#Input:
 > 1494:	#graph G - network, whose edge weights represent costs of using those 
edges
 > 1495:	#dictionary f - some flow for network G. Keys represent edges and values
 > 1496:	#are flows at those edges
 > 1497:	#dictionary c - max possible flows at edges in network G
 > 1498:	#path - set of nodes for which we transform the network
 > 1499:	#newC - max possible flows at edges in network G after updating
 > 1500:	#the network G
 > 1501:	#
 > 1502:	#Subprocedure checks 6 vital conditions and for them updates the network
 > 1503:	#(let values with * be updates values for network). So, let edge (u,v) be
 > 1504:	#the non-zero flow for network G:
 > 1505:	#1. c*(v,u) = f(u,v)  --- adding apparent arc
 > 1506:	#2. d*(v,u) = -d(u,v)

What is 'd' here ? I saw no explanation of its meaning.

 > 1507:	#3. c*(u,v) = c(u,v) - f(u,v)    --- if f(v,u) = 0 and c(u,v) > f(u,v)
 > 1508:	#4. d*(u,v) = d(u,v)             --- if f(v,u) = 0 and c(u,v) > f(u,v)
 > 1509:	#5. c*(u,v) = 0                  --- if f(v,u) = 0 and c(u,v) = f(u,v)
 > 1510:	#6. d*(u,v) = Inf                --- if f(v,u) = 0 and c(u,v) = f(u,v)
 > 1511:	
 > 1512:	proc ::struct::graph::op::createAugmentingNetwork {G f _c path newC} {
 > 1513:	
 > 1530:		
 > 1531:		#we set new values for each edge contained in the path from input
 > 1532:		foreach u [lrange $path 0 end-1] v [lrange $path 1 end] {
 > 1533:		

			set uv [list $u $v]
			set vu [list $v $u]
			... Replace the list calls with variables

 > 1534:			set f_uv [dict get $f [list $u $v]]
 > 1535:			set f_vu [dict get $f [list $v $u]]
 > 1536:			set c_uv [dict get $c [list $u $v]]
 > 1537:			set d_uv [$Gf arc getweight [list $u $v]]
 > 1538:			
 > 1571:	}

 > 1573:	#Busacker Gowen's algorithm - computing minimum cost maximum flow in a 
flow network
 > 1574: 
#-------------------------------------------------------------------------------------
 > 1575:	#
 > 1576:	#The goal is to find a flow, whose max value can be d, from source 
node to
 > 1577:	#sink node in given flow network. That network except throughputs at 
edges has
 > 1578:	#also defined a non-negative cost on each edge - cost of using that 
edge when
 > 1579:	#directing flow with that edge ( it can illustrate e.g. fuel usage, 
time or
 > 1580:	#any other measure dependent on usages ).
 > 1581:	#
 > 1582:	#Input:
 > 1583:	#graph G - flow network, weights at edges are costs of using 
particular edge
 > 1584:	#desiredFlow - max value of the flow for that network
 > 1585:	#dictionary c - throughputs for all edges
 > 1586:	#node s - the source node for graph G
 > 1587:	#node t - the sink node for graph G
 > 1588:	#
 > 1589:	#Output:
 > 1590:	#f - dictionary containing values of used throughputs for each edge ( 
key )
 > 1591:	#found by algorithm.
 > 1592:	#
 > 1593:	#Reference: http://en.wikipedia.org/wiki/Minimum_cost_flow_problem
 > 1594:	#
 > 1595:	
 > 1596:	proc ::struct::graph::op::BusackerGowen {G desiredFlow c s t} {

Is a negative desiredFlow allowd ? Zero flow ?
s, t not in G ?

 > 1597:	
 > 1598:		set Gf [struct::graph]
 > 1599:		
 > 1620:		set currentFlow 0
 > 1621:		set stPath 1
 > 1622:		
 > 1623:		#main loop - it ends when we reach desired flow value or there is no 
path in Gf
 > 1624:		#leading from source node s to sink t
 > 1625:		
 > 1626:		while { ($currentFlow < $desiredFlow) && $stPath } {
 > 1627:		
 > 1628:			#setting the path 'p' from 's' to 't'
 > 1629:			
 > 1630:			set path [lreverse [dict get [struct::graph::op::dijkstra $Gf $s 
-arcmode directed] $t]]
 > 1631:			lappend path $t
 > 1632:			
 > 1633:			#if there is no path - break
 > 1634:			if { $path == $t } {

Left side ($path) is list, right side ($) is node. Better conditions, which do 
not mix types

(a)	$path eq [list $t]
(b)	[llength $path] == 1

I prefer (b). This can also be moved before line 1631, but then it has to be 
changed to

	[llength $path] == 0
<=>	![llength $path]

 > 1635:				set stPath 0
 > 1636:				break
 > 1637:			}

Given the 'break' in line 1636 aborting the loop, I do not believe
that we can come here with $stPath == 0. Making the condition below
(line 1639) likely irrelevant, always true.

 > 1639:			if { $stPath } {
 > 1640:				#counting max throughput that is availiable to send
 > 1641:				#using path 'p'
 > 1642:				set maxThroughput Inf
 > 1643:			
 > 1644:				for {set i 0} {$i < [llength $path]-1 } { incr i } {
 > 1645:					set u [lindex $path $i]
 > 1646:					set v [lindex $path [expr { $i+1 }]]

Same pattern as in FordFulkerson (foreach u [lrange 0 end-1] v [lrange 1 end] ...)

 > 1647:					
 > 1648:					if { $maxThroughput > [dict get $c [list $u $v]] } {
 > 1649:						set maxThroughput [dict get $c [list $u $v]]
 > 1650:					}
 > 1651:				}

The whole max operation could possible be moved into a separate
command, it seems to occur in at least two places.

 > 1652:				
 > 1653:				#if max throughput that was found will cause exceeding the desired
 > 1654:				#flow, send as much as it's possible
 > 1655:				if { [expr { $currentFlow + $maxThroughput }] <= $desiredFlow } {

Nested 'expr' is superflous. Can be written as one parenthesized expression.

 > 1656:					set fAdd $maxThroughput
 > 1657:					set currentFlow [ expr { $currentFlow + $fAdd } ]
 > 1658:				} else {
 > 1659:					set fAdd [ expr { $desiredFlow - $currentFlow } ]
 > 1660:					set currentFlow [ expr { $currentFlow + $fAdd } ]
 > 1661:				}
 > 1662:				
 > 1663:				#update the throuputs on edges
 > 1664:				for {set i 0} {$i < [llength $path]-1 } { incr i } {
 > 1665:				
 > 1666:					set v [lindex $path $i]
 > 1667:					set u [lindex $path [expr { $i+1 }]]

See above (foreach u [lrange 0 end-1] v [lrange 1 end] ...).

 > 1668:		

Need variables for clarity. (f_uv, c_uv, etc.).
			
 > 1669:					if { [dict get $f [list $u $v]] >= $fAdd } {
 > 1670:						dict set f [list $u $v] [ expr { [dict get $f [list $u $v]] - 
$fAdd } ]
 > 1671:					}
 > 1672:					
 > 1673:					if { ( [dict get $f [list $u $v]] < $fAdd ) && ( [dict get $f 
[list $u $v]] > 0 ) } {
 > 1674:						dict set f [list $v $u] [ expr { $fAdd - [dict get $f [list $u 
$v]] } ]
 > 1675:						dict set f [list $u $v] 0
 > 1676:					}
 > 1677:					
 > 1678:					if { [dict get $f [list $u $v]] == 0 } {
 > 1679:						dict set f [list $v $u] [ expr { [dict get $f [list $v $u]] + 
$fAdd } ]
 > 1680:					}
 > 1681:				}
 > 1682:				#create new Augemnting Network
 > 1683:				set Gf [createAugmentingNetwork $Gf $f $c $path c]
 > 1684:			}		
 > 1685:		}
 > 1686:		
 > 1687:		#erasing the edges from solution, where throuputs are equal to 0
 > 1688:		foreach flow [dict keys $f] {
 > 1689:			if { [dict get $f $flow] == 0 } {
 > 1690:				set f [dict remove $f $flow]
 > 1691:			}
 > 1692:		}
 > 1693:		

Gf resource leak. Not destroyed.

 > 1694:		return $f
 > 1695:	}



Andreas.