tcllib-devel — Discussion of development for tcllib

[Tcllib-devel] Anouncement: BWidget 1.9 Bugfix release

[Harald O. <Har...@El...>]

Dear community,

BWidget 1.9.0 is out.
Thanks to all active people sending bug reports, patches and using BWidget.

Enjoy,
Harald
--------------------------------------------------------------------------
URL: https://sourceforge.net/projects/tcllib

All open bugs and patches were checked and many led to modified code.

Highlights:
- MainFrame: getmenustate method
- ScrollFrame: follows much better when contents size changes
- ComboBox: Posting, Keyboard, not unique contents return,
  Mac X11 and aqua, text selection handling.
- Listbox: item deletion error
- PasswdDlg: disabled password handling
- Balloon Help: Placement on borders and on multiple screens (as far as
possible)

Modifications which may rise incompatibilities:

- Option data base entry for "MessageDlg -text" changed
  from "*MessageDlg.frame.msg.message"
  to "*MessageDlg.frame.msg.text"
--------------------------------------------------------------------------

WHAT IS BWIDGET ?

The BWidget Toolkit is a high-level Widget Set for Tcl/Tk built using
native Tcl/Tk 8.x namespaces.

The BWidgets have a professional look&feel as in other well known
Toolkits (Tix or Incr Widgets), but the concept is radically different
because everything is pure Tcl/Tk.  No platform dependencies, and no
compiling required.  The code is 100% Pure Tcl/Tk.

The BWidget library was originally developed by UNIFIX Online, and
released under both the GNU Public License and the Tcl license.
BWidget is now maintained as a community project, hosted by
Sourceforge.  Scores of fixes and enhancements have been added by
community developers. See the ChangeLog file for details.

Re: [Tcllib-devel] BWidget patch 2825354 - fork or L in tree widget - please discuss

[Jeff H. <je...@ac...>]

Agreed.

On 24/07/2009 6:30 AM, Koen Danckaert wrote:
> Jeff Hobbs wrote:
>> In there, you will see that the node to the top is actually drawn, and 
>> in the one in sources (with newer BWidget), it isn't.  I actually 
>> prefer the newer lack of top anchor look, and it does have the single 
>> node case to start.  I think this also applies to how the tree is 
>> used.  When it has the classic single root node, it is better without 
>> the top anchor line displayed, but I could see it as ok with multiple 
>> root nodes.
>>
>> In the end, this can simply be made an option, like -showrootanchor or 
>> something.
> 
> Ok, I already thought that the Windows style you were referring to 
> always had exactly one top node, which is not the case for BWidget 
> (where the real "root" node is actually invisible).
> 
> I propose to make the line dependent on whether there are multiple top 
> nodes. (Harald, the patch for that is below.) It seems we could agree on 
> that, and I prefer it to an extra option (= extra documentation, which 
> will probably difficult to understand without trying out.)
> 
> --Koen
> 
> 
> Index: tree.tcl
> ===================================================================
> RCS file: /cvsroot/tcllib/bwidget/tree.tcl,v
> retrieving revision 1.59
> diff -b -u -r1.59 tree.tcl
> --- tree.tcl    30 Jun 2009 16:17:37 -0000    1.59
> +++ tree.tcl    24 Jul 2009 13:26:22 -0000
> @@ -1369,12 +1369,9 @@
>         set yp $y1
>         set y1 [_draw_node $path $node $x0 [expr {$y1+$deltay}] $deltax 
> $deltay $padx $showlines]
>     }
> -    if { $showlines && [llength $nodes] } {
> -    if {$y0 < 0} {
> -        # Adjust the drawing of the line to the first root node
> -        # to start at the vertical point (not go up).
> -        incr y0 $deltay
> -    }
> +    # Only draw a line to the virtual root node when there are multiple 
> top nodes.
> +    set len [llength $nodes]
> +    if { $showlines && $len && !($y0 < 0 && $len < 2) } {
>         set id [$path.c create line $x0 $y0 $x0 [expr {$yp+$deltay}] \
>                     -fill    [Widget::getoption $path -linesfill]   \
>                     -stipple [Widget::getoption $path -linestipple] \
> 

Re: [Tcllib-devel] BWidget patch 2825354 - fork or L in tree widget - please discuss

[Koen D. <ko...@re...>]

Jeff Hobbs wrote:
> In there, you will see that the node to the top is actually drawn, and 
> in the one in sources (with newer BWidget), it isn't.  I actually prefer 
> the newer lack of top anchor look, and it does have the single node case 
> to start.  I think this also applies to how the tree is used.  When it 
> has the classic single root node, it is better without the top anchor 
> line displayed, but I could see it as ok with multiple root nodes.
> 
> In the end, this can simply be made an option, like -showrootanchor or 
> something.

Ok, I already thought that the Windows style you were referring to always had exactly one top node, which is not the case for BWidget (where the real "root" node is actually invisible).

I propose to make the line dependent on whether there are multiple top nodes. (Harald, the patch for that is below.) It seems we could agree on that, and I prefer it to an extra option (= extra documentation, which will probably difficult to understand without trying out.)

--Koen


Index: tree.tcl
===================================================================
RCS file: /cvsroot/tcllib/bwidget/tree.tcl,v
retrieving revision 1.59
diff -b -u -r1.59 tree.tcl
--- tree.tcl	30 Jun 2009 16:17:37 -0000	1.59
+++ tree.tcl	24 Jul 2009 13:26:22 -0000
@@ -1369,12 +1369,9 @@
         set yp $y1
         set y1 [_draw_node $path $node $x0 [expr {$y1+$deltay}] $deltax $deltay $padx $showlines]
     }
-    if { $showlines && [llength $nodes] } {
-	if {$y0 < 0} {
-	    # Adjust the drawing of the line to the first root node
-	    # to start at the vertical point (not go up).
-	    incr y0 $deltay
-	}
+    # Only draw a line to the virtual root node when there are multiple top nodes.
+    set len [llength $nodes]
+    if { $showlines && $len && !($y0 < 0 && $len < 2) } {
         set id [$path.c create line $x0 $y0 $x0 [expr {$yp+$deltay}] \
                     -fill    [Widget::getoption $path -linesfill]   \
                     -stipple [Widget::getoption $path -linestipple] \

Re: [Tcllib-devel] BWidget patch 2825354 - fork or L in tree widget - please discuss

[Jeff H. <je...@ac...>]

On 23/07/2009 6:10 AM, Koen Danckaert wrote:
>> Issue:
>> - there is a vertical line from the top of the widget to the first node

>> Addiditional explanation by Jeff:
>>
>> The reason I made that change was to be visually compatible with Windows
>> (older style, as new style is no lines) when you actually have sub-nodes
>> (the [+] and [-] indicators). The line to the top is then inconsistent
>> with the way others draw.
>> You could try and make that check contingent on whether subnodes exist,
>> but I think that may seem odd.
> 
> My opinion is:
> 
> - When the first node has subnodes, it does not really matter. Both
> styles look good visually. It may be inconsistent with some older
> Windows style, but as Jeff points out, the new Windows style is to
> draw no lines at all. So why would we still try to match the older
> style?

I actually disagree on this point.  With subnodes it actually does look 
odd to anchor right to the top.

> - When the first node has no subnodes, it looks strange to have no line.
> - When there are only 1 or 2 nodes in the tree, it looks even more strange:
> 
> pack [Tree .t -padx 2]
> .t insert end root node1 -text "Node 1"
> .t insert end root node2 -text "Node 2"  ;# try with and without this line
> 
> Of course, you could say that you never want a tree with only 1 node,
> but in one of our applications we let the user interactively create a
> tree, and in that case a tree with 1 node may be a necessary
> intermediate state.
> 
> Making the line dependent on whether subnodes exist would also be
> strange: then the line will suddenly (dis)appear when subnodes are
> created/deleted in such an interactive application.

At first I was ambivalent, but I dug up an app where BWidget was still 
used that I wrote (GUI Builder, at http://spectcl.sourceforge.net).  In 
it you will find a few use cases that in review I prefer the current (no 
top anchor line) behavior.  You can find pictures of the various tabs at:

http://docs.activestate.com/komodo/3.5/komodo-doc-guibuilder.html#guibuilder_top

In there, you will see that the node to the top is actually drawn, and 
in the one in sources (with newer BWidget), it isn't.  I actually prefer 
the newer lack of top anchor look, and it does have the single node case 
to start.  I think this also applies to how the tree is used.  When it 
has the classic single root node, it is better without the top anchor 
line displayed, but I could see it as ok with multiple root nodes.

In the end, this can simply be made an option, like -showrootanchor or 
something.

Jeff

Re: [Tcllib-devel] BWidget patch 2825354 - fork or L in tree widget - please discuss

[Koen D. <ko...@re...>]

Harald Oehlmann wrote:
> Hello BWidget community,
> 
> Koen Danckaert proposes in BWidget patch 2825354 to revert a
> modification on the tree widget (tree.tcl).
> 
> Issue:
> 
> Old (and proposed behaviour) :
> - there is a vertical line from the top of the widget to the first node
> ASCII-Arts:
> +----        <- Tree Widget border
> |  |         <- this line is the issue
> |  +--Node 1
> |  |
> |  +--Node 2
> 
> Current behaviour:
> - this line is not present
> 
> Login entry to current behaviour:
> 
> 2004-04-21 Jeff Hobbs <je...@Ac...>
> * tree.tcl (_draw_subnodes): Adjust the drawing of the line to the
> first root node to start at the vertical point (not go up).
> 
> Addiditional explanation by Jeff:
> 
> The reason I made that change was to be visually compatible with Windows
> (older style, as new style is no lines) when you actually have sub-nodes
> (the [+] and [-] indicators). The line to the top is then inconsistent
> with the way others draw.
> You could try and make that check contingent on whether subnodes exist,
> but I think that may seem odd.

My opinion is:

- When the first node has subnodes, it does not really matter. Both styles look good visually. It may be inconsistent with some older Windows style, but as Jeff points out, the new Windows style is to draw no lines at all. So why would we still try to match the older style?
- When the first node has no subnodes, it looks strange to have no line.
- When there are only 1 or 2 nodes in the tree, it looks even more strange:

pack [Tree .t -padx 2]
.t insert end root node1 -text "Node 1"
.t insert end root node2 -text "Node 2"  ;# try with and without this line

Of course, you could say that you never want a tree with only 1 node, but in one of our applications we let the user interactively create a tree, and in that case a tree with 1 node may be a necessary intermediate state.

Making the line dependent on whether subnodes exist would also be strange: then the line will suddenly (dis)appear when subnodes are created/deleted in such an interactive application.

--Koen

[Tcllib-devel] BWidget patch 2825354 - fork or L in tree widget - please discuss

[Harald O. <Har...@El...>]

Hello BWidget community,

Koen Danckaert proposes in BWidget patch 2825354 to revert a
modification on the tree widget (tree.tcl).

Issue:

Old (and proposed behaviour) :
- there is a vertical line from the top of the widget to the first node
ASCII-Arts:
+----        <- Tree Widget border
|  |         <- this line is the issue
|  +--Node 1
|  |
|  +--Node 2

Current behaviour:
- this line is not present

Login entry to current behaviour:

2004-04-21 Jeff Hobbs <je...@Ac...>
* tree.tcl (_draw_subnodes): Adjust the drawing of the line to the
first root node to start at the vertical point (not go up).

Addiditional explanation by Jeff:

The reason I made that change was to be visually compatible with Windows
(older style, as new style is no lines) when you actually have sub-nodes
(the [+] and [-] indicators). The line to the top is then inconsistent
with the way others draw.
You could try and make that check contingent on whether subnodes exist,
but I think that may seem odd.

---
Please write your opinion.

Thank you,
Harald

Re: [Tcllib-devel] Revision 37 (fwd)

[Andreas K. <aku...@sh...>]

 
> now -
>  > 1761:					#we set u at the beginning of the queue
>  > 1762:						if { [lsearch $queue $u] < 0 } {
>  > 1763:							set queue [linsert $queue 0 $u]
>  > 1764:						}
> 
> Ok, this makes the index method (1) more complex, because now the
> 'linsert' happens at $at, not 0.
> 
> For 'struct::queue' the method to insert at the front is
> 'unget'. Unfortunately there is no 'seach' method however, so using
> struct::queue is not possible, contrary to what I thought before/above.
> 
> 
> I have the feeling I should step the algorithm with an example to see
> how this optimization works.
> 
> (The other branch is clear: Node not visited before, mark as visited
> and put on queue for processing).
> 
> Your 'lsearch' <=3D>  '$u ni $queue'

Ok, should you choose to go for a rewrite using $at etc. to iterate
over the queue then 'in' is not applicable anymore, because then the
option -start is needed to start your search at 'at' instead of the
beginning of the queue.

Realized that a bit late, while walking through the park.

-- 
So long,
	Andreas Kupries <aku...@sh...>
			<http://www.purl.org/NET/akupries/>
	Developer @	<http://www.activestate.com/>
-------------------------------------------------------------------------------

Re: [Tcllib-devel] Revision 37

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

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

And the promised review.

 > 1362:			
 > 1363:			set paths [ShortestsPathsByBFS $residualG $s paths]
 > 1364:			
 > 1365:			if { ($paths == 0) || (![dict exists $paths $t]) } break

I infer that ShortestsPathsByBFS can return either a number or a
dictionary. Not a good thing. The result type should be stable, only
one thing.
	

 > 1646:			
 > 1647:			#setting the path 'p' from 's' to 't'
 > 1648:			set paths [ShortestsPathsByBFS $Gf $s paths]
 > 1649:			
 > 1650:			#if there are no more paths, the search has ended
 > 1651:			if { ($paths == 0) || (![dict exists $paths $t]) } break

Ditto.

Now lets see why this happens.

 > 1707:	proc ::struct::graph::op::ShortestsPathsByBFS {G s outputFormat} {
 > 1708:		
 > 1709:		switch -exact -- $outputFormat {
 > 1710:			distances {
 > 1711:				set outputMode distances
 > 1712:			}
 > 1713:			paths {
 > 1714:				set outputMode paths
 > 1715:			}
 > 1716:			default {
 > 1717:				return -code error "Unknown output format \"$outputFormat\", 
expected graph, or tree"

graph, or tree ? Not distances, or paths ?

 > 1718:			}
 > 1719:		}
 > 1720:		
 > 1721:		set queue [list $s]
 > 1722:		set result {}
 > 1723:		
 > 1724:		#initialization of marked nodes, distances and predecessors
 > 1725:		foreach v [$G nodes] {
 > 1726:			$G node set $v marked 0

The marking can also be stored in a dict or array. As temporary data
it maybe should. Right now the 'marked' attribute is apparently
persistent, i.e. added to G by the operation, but not removed before
returning.

 > 1727:			dict set distances $v Inf
 > 1728:			dict set pred $v -1
 > 1729:		}
 > 1730:		
 > 1731:		#the s node is initially marked and has 0 distance to itself
 > 1732:		$G node set $s marked 1
 > 1733:		dict set distances $s 0
 > 1734:			
 > 1735:		#the main loop
 > 1736:		while { [llength $queue] != 0 } {
 > 1737:		
 > 1738:			#removing top element from the queue
 > 1739:			set v [lindex $queue 0]
 > 1740:			lremove queue $v

lremove is based on value, yet we know the element to remove is at
index 0. lrange and lreplace are applicable, no search required (as
done by lremove).

Note: The way lists are implemented in Tcl this type of operation
(removing an element at the beginning of the list) involves copying
the whole remainder of the list. This easily makes an algorithm O(n^2)
in the length of the list (queue).


A way to avoid that is to never remove elements, but use an index to
keep track how far we have processed the elements.

(1)	set queue {}
	set at 0 ;# next element to process
	while {$at < [llength $queue]} {
		set element [lindex $queue $at]
		incr at

		... process element, possibly extend the queue ...
	}

The memory used fby the 'queue' variable is larger, as nothing is
removed until the loops ends. It is finite however. Here it would be
bound by the number of nodes in the graph.


Another possibility is to use struct::queue (already required by some
other operations in the package).

	set q [struct::queue]
	while {[$q size]} {
		set element [$q get]
		... process element, possibly extend queue
	}
	$q delete

The implementation of struct::queue is similar to (1), with a bit more
code complexity to keep memory usage down without giving up the
performance (lappend is done into a second buffer, and buffers are
switched when the read buffer is exhausted per the read-index vs it
length).


 > 1741:			
 > 1742:			#for each arc that begins in v
 > 1743:			foreach arc [$G arcs -out $v] {
 > 1744:				
 > 1745:				set u [$G arc target $arc]
 > 1746:				set newlabel [ expr { [dict get $distances $v] + [$G arc getweight 
$arc] } ]
 > 1747:				
 > 1748:				if { $newlabel < [dict get $distances $u] } {
 > 1749:					
 > 1750:					dict set distances $u $newlabel
 > 1751:					dict set pred $u $v
 > 1752:					
 > 1753:					#case when current node wasn't placed in a queue yet -
 > 1754:					#we set u at the end of the queue
 > 1755:					if { [$G node set $u marked] == 0 } {
 > 1756:						lappend queue $u
 > 1757:						$G node set $u marked 1
 > 1758:					} else {
 > 1759:					
 > 1760:					#case when current node u was in queue before but it is not in it 
now -
 > 1761:					#we set u at the beginning of the queue
 > 1762:						if { [lsearch $queue $u] < 0 } {
 > 1763:							set queue [linsert $queue 0 $u]
 > 1764:						}

Ok, this makes the index method (1) more complex, because now the
'linsert' happens at $at, not 0.

For 'struct::queue' the method to insert at the front is
'unget'. Unfortunately there is no 'seach' method however, so using
struct::queue is not possible, contrary to what I thought before/above.


I have the feeling I should step the algorithm with an example to see
how this optimization works.

(The other branch is clear: Node not visited before, mark as visited
and put on queue for processing).

Your 'lsearch' <=>  '$u ni $queue'

 > 1765:					}
 > 1766:				}
 > 1767:			}
 > 1768:		}
 > 1769:		
 > 1770:		#if the outputformat is paths, we travel back to find shorests paths
 > 1771:		#to return sets of nodes for each node, which are their paths between
 > 1772:		#s and particular node
 > 1773:		dict set paths nopaths 1
 > 1774:		if { $outputMode eq "paths" } {
 > 1775:			foreach node [$G nodes] {	
 > 1776:				
 > 1777:				set path {}
 > 1778:				set lastNode $node
 > 1779:			
 > 1780:				while { $lastNode != -1 } {
 > 1781:					set currentNode [dict get $pred $lastNode]
 > 1782:					if { $currentNode != -1 } {
 > 1783:						lappend path $currentNode
 > 1784:					}
 > 1785:					set lastNode $currentNode
 > 1786:				}
 > 1787:				
 > 1788:				set path [lreverse $path]

Ah, this is different from dijkstra, this is why the caller did not
have to lreverse on their own.

	Any specific reason why this is better ?
	Or is dijkstra's form for the result better ?

	Or should we modify 'disjktra' to return the same as this
	procedure ?

 > 1789:				
 > 1790:				if { [llength $path] != 0 } {
 > 1791:					dict set paths $node $path
 > 1792:					dict unset paths nopaths
 > 1793:				}
 > 1794:			}
 > 1795:			
 > 1796:			if { ![dict exists $paths nopaths] } {
 > 1797:				return $paths
 > 1798:			} else {
 > 1799:				return 0

Better to return '{}' <=> an empty dictionary

That makes the return type always a dictionary, and the checks in
lines 1365 and 1651 become simpler (The ![dict exists] becomes
sufficient).

 > 1810:	proc ::struct::graph::op::BFS {G s outputFormat} {
 > 1811:		
 > 1812:		set queue [list $s]
 > 1813:			
 > 1826:		if { $outputMode eq "graph" } {
 > 1827:		#graph initializing
 > 1828:			set BFSGraph [struct::graph]
 > 1829:			foreach v [$G nodes] {
 > 1830:				$BFSGraph node insert $v
 > 1831:			}
 > 1832:		} else {
 > 1833:		#tree initializing
 > 1834:			set BFSTree [struct::tree]
 > 1835:			$BFSTree set root name $s
 > 1836:			$BFSTree rename root $s
 > 1837:		}
 > 1838:		
 > 1839:		#initilization of marked nodes
 > 1840:		foreach v [$G nodes] {
 > 1841:			$G node set $v marked 0

Note discussion of marking for 'ShortestPathByBFS'.

 > 1842:		}
 > 1843:		
 > 1844:		#start node is marked from the beginning
 > 1845:		$G node set $s marked 1
 > 1846:		
 > 1847:		#the main loop
 > 1848:		while { [llength $queue] != 0 } {
 > 1849:			#removing top element from the queue
 > 1850:			
 > 1851:			set v [lindex $queue 0]
 > 1852:			lremove queue $v

Note discussion of the queue handling above for 'ShortestPathByBFS'.


 > 1853:			
 > 1854:			foreach x [$G nodes -adj $v] {
 > 1855:				if { ![$G node set $x marked] } {
 > 1856:					$G node set $x marked 1
 > 1857:					lappend queue $x
 > 1858:					
 > 1859:					if { $outputMode eq "graph" } {				
 > 1860:						$BFSGraph arc insert $v $x [list $v $x]
 > 1861:					} else {
 > 1862:						$BFSTree insert $v end $x
 > 1863:						lappend result [list $v $x]

The variable 'result' seems to be superfluous. Not used by the loop,
not returned either. Leftover bits ?

 > 1864:					}				
 > 1865:				}
 > 1866:			}
 > 1867:		}
 > 1868:		
 > 1869:		
 > 1870:		if { $outputMode eq "graph" } {
 > 1871:			return $BFSGraph
 > 1872:		} else {
 > 1873:			return $BFSTree
 > 1874:		}
 > 1875:	}

 > 1877:	#Minimum Diameter Spanning Tree - MDST
 > 1878:	#
 > 1879:	#
 > 1880:	#The goal is to find for input graph G, the spanning tree that
 > 1881:	#has the minimum diameter worth.
 > 1882:	#
 > 1883:	#General idea of algorithm is to run BFS over all vertices in graph
 > 1884:	#G. If the diameter "d" of the tree is odd, then we are sure that tree
 > 1885:	#given by BFS is minimum (considering diameter value). When, diameter "d"
 > 1886:	#is even, then optimal tree can have minimum diameter equal to "d" or
 > 1887:	#"d-1".
 > 1888:	#
 > 1889:	#In that case, what algorithm does is rebuilding the tree given by BFS, by
 > 1890:	#adding a vertice between root node and root's child node (nodes), 
such that
 > 1891:	#subtree created with child node as root node is the greatest one (has the
 > 1892:	#greatests height). In the next step for such rebuilded tree, we run 
again BFS
 > 1893:	#with new node as root node. If the height of the tree didn't changed, 
we have found
 > 1894:	#a better solution.
 > 1895:	
 > 1896:	proc ::struct::graph::op::MinimumDiameterSpanningTree {G} {
 > 1897:	
 > 1898:		set min_diameter Inf
 > 1899:		set best_Tree [struct::graph]
 > 1900:		
 > 1901:		foreach v [$G nodes] {
 > 1902:		
 > 1903:			#BFS Tree
 > 1904:			set T [BFS $G $v tree]		
 > 1905:			#BFS Graph
 > 1906:			set TGraph [BFS $G $v graph]
 > 1907:				
 > 1908:			#Setting all arcs to 1 for diameter procedure
 > 1909:			$TGraph arc setunweighted 1
 > 1910:			
 > 1911:			#setting values for current Tree
 > 1912:			set diam [diameter $TGraph]
 > 1913:			set subtreeHeight [ expr { $diam / 2 - 1} ]
 > 1914:				
 > 1915:			##############################################
 > 1916:			#case when diameter found for tree found by BFS is even:
 > 1917:			#it's possible to decrease the diameter by one.
 > 1918:			if { [expr { $diam % 2 } ] == 0 } {

Nested expression superfluous

		if { ($diam % 2) == 0 } {

 > 1919:				
 > 1920:				#for each child u that current root node v has, we search

	Each child u of v ... Are you talking only about the direct children ?
	Or also about the child of children of v, etc. ?

 > 1921:				#for the greatest subtree(subtrees) with the root in child u.
 > 1922:				#
 > 1923:				foreach u [$TGraph nodes -adj $v] {
 > 1924:					set u_depth [$T depth $u]

	As u is a child of v the depth should be '1', always.

 > 1925:					set d_depth 0
 > 1926:					

 > 1927:					set descendants [$T descendants $u]
 > 1928:					
 > 1929:					foreach d $descendants {
 > 1930:						if { $d_depth < [$T depth $d] } {
 > 1931:							set d_depth [$T depth $d]
 > 1932:						}
 > 1933:					}

If I read this correctly, you are computing for each node d under u
the depth, i.e. distance to the root, and take the maximum. IIRC this
is the height of the tree under u, relative to root, is that correct ?

If yes, then this should be

		1 + [$T height $u]

I believe (struct::tree has a 'height' method).

 > 1934:					
 > 1935:					#depth of the current subtree
 > 1936:					set depth [ expr { $d_depth - $u_depth } ]

Now, with u_depth == 1, always, and d_depth = 1 + [$T height $u] we get

	depth == 1 + [$T height $u] - 1 == [$T height $u]

If my assumptions are correct then lines 1924 - 1936 can be collapsed into one 
command.

	set depth [$T height $u]


 > 1937:								
 > 1938:					#proceed if found subtree is the greatest one
 > 1939:					if { $depth >= $subtreeHeight } {
 > 1940:						
 > 1941:						#temporary Graph for holding potential better values
 > 1942:						set tempGraph [struct::graph]
 > 1943:						
 > 1944:						foreach node [$TGraph nodes] {
 > 1945:							$tempGraph node insert $node
 > 1946:						}
 > 1947:						
 > 1948:						#zmienic nazwy zmiennych zeby sie nie mylily
 > 1949:						foreach arc [$TGraph arcs] {
 > 1950:							set _u [$TGraph arc source $arc]
 > 1951:							set _v [$TGraph arc target $arc]
 > 1952:							$tempGraph arc insert $_u $_v [list $_u $_v]
 > 1953:						}

I believe I have seen this graph initialization (1941-1953, copy of
nodes, copy of structure with u/v arc naming convention) often enough
that we can puts this into a separate procedure we can call at all the
relevant places. It seems hat we need it for basically every operation


 > 1954:			
 > 1955:						if { [$tempGraph arc exists [list $u $v]] } {
 > 1956:							$tempGraph arc delete [list $u $v]
 > 1957:						} else {
 > 1958:							$tempGraph arc delete [list $v $u]
 > 1959:						}

 > 1960:						
 > 1961:						#for nodes u and v, we add a node between them
 > 1962:						#to again start BFS with root in new node to check
 > 1963:						#if it's possible to decrease the diameter in solution
 > 1964:						set node [$tempGraph node insert]
 > 1965:						$tempGraph arc insert $node $v [list $node $v]
 > 1966:						$tempGraph arc insert $node $u [list $node $u]
 > 1967:					
 > 1968:						set tempGraph [BFS $tempGraph $node graph]
 > 1969:								
 > 1970:						$tempGraph node delete $node
 > 1971:						$tempGraph arc insert $u $v [list $u $v]
 > 1972:						$tempGraph arc setunweighted 1
 > 1973:						
 > 1974:						set tempDiam [diameter $tempGraph ]
 > 1975:						
 > 1976:						#if better tree is found (that any that were already found)
 > 1977:						#replace it
 > 1978:						if { $min_diameter > $tempDiam } {
 > 1979:							set $min_diameter [diameter $tempGraph ]
 > 1980:							set best_Tree $tempGraph
 > 1981:						}

Hm. Here are some leaks ... If tempGraph does not become best_Tree it
should be released, correct ?  Further, if tempGraph does become
best_Tree then the old best_Tree (if defined) should be released too.

 > 1982:					}
 > 1983:					
 > 1984:				}
 > 1985:			}
 > 1986:			################################################################
 > 1987:			
 > 1988:			set currentTreeDiameter [ diameter $TGraph ]

set currentTreeDiameter $diam

See line 1912, before the humunguous if-block handling the even diameter.,
and the fact that this big if-block is not changing TGraph at all.


 > 1989:			
 > 1990:			if { $min_diameter > $currentTreeDiameter } {
 > 1991:				set min_diameter $currentTreeDiameter
 > 1992:				set best_Tree $TGraph

See leak discussion above (1981).


 > 1993:			}
 > 1994:		

The tree $T (line 1904) seems to leak as well.
	
 > 1995:		}
 > 1996:		
 > 1997:		return $best_Tree
 > 1998:	}
 > 1999:	
 > 2000:	#
 > 2001:	proc ::struct::graph::op::MinimumDegreeSpanningTree {G} {

 > 2022:		#main loop	
 > 2023:		foreach e [$G arcs] {
 > 2024:			
 > 2025:			set u [$G arc source $e]
 > 2026:			set v [$G arc target $e]
 > 2027:			

 > 2028:			$MST arc setunweighted 1

This command is indendent of 'e', should be run before the
loop. Around line 2021, after MST has gotten its arcs.

 > 2029:			
 > 2030:			#setting the path between nodes u and v in Spanning Tree MST
 > 2031:			set path [dict get [dijkstra $MST $u] $v]
 > 2032:			lappend path $v
 > 2033:			
 > 2034:			#if nodes u and v are neighbours, proceed to next iteration

This condition is quicker checked with 'arc exists' for the two
possible directions, see below. Doing so means that we can move the
expensive dijkstra into the if-block, hopefully using it less.

 > 2035:			if { [llength $path] > 2 } {

	if { !arc exists (u -> v) && !(arc exists v ->) }

 > 2036:				
 > 2037:				#search for the node in the path, such that its degree is greater 
than degree of any of nodes
 > 2038:				#u or v increased by one
 > 2039:				foreach node $path {
 > 2040:					if { [$MST node degree $node] > [ expr { [Max [$MST node degree 
$u] [$MST node degree $v]] + 1 } ] } {

Nested 'expr' superfluous, see also line 1918.


Andreas.

Re: [Tcllib-devel] Revision 37

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

Michał Antoniewski wrote:
> Hello.
>  
> Regarding previous ping mail, promised description.
>  
>  
> 1. BFS.
>  
> After some attempts and different organisations of code I decided to 
> divide that BFS procedure into 2 procedures - one for shortests paths 
> finding (ShortestPathsByBFS) and standard BFS (BFS).
>  
> Why and some notes about them:
> - creating one procedure for both, makes code quite complex
> - as both procedures can return dictionaries, trees and graphs, there 
> would be a lot of repeated code or a lot of statements like if which 
> make code doesn't look good ( I just wasn't satisfied at all when I 
> looked at it )
> - dividing into 2 procedures, lets us give easily some improvement to 
> path finding : e.g. if node wasn't in queue yet, it's added at the end 
> of the queue, but when it was added before and erased also from the 
> queue, we add it at the beginning of the queue - it helps a lot cause a 
> lot of not needed computation is omitted.
> - I just see it like 1000 times clearer, when there is such division - 
> both, more intuitive and also considering implementation.

I'll have a closer look at this then.


> Shortests path finding by BFS vs Dijkstra:
> - BFS can work with negative weights ( but negative cycles are of course 
> unwelcome )
> - it's quicker for not sparse graphs, with big amount of nodes
> - it also finds (like Dijkstra) paths from one node to others, so we 
> don't have to use e.g Bellman's Ford, when negative weights are there.

> Path finding by BFS returns us:
> - dictionary containing distances between start node s and each other 
> vertice
> - or dictionary containing paths between start node and each other vertice

Like dijkstra then.

> Notes to BFS path finding:
> - it's weighted, so to get unweighted version we just give at input 
> graph with all weights set to 1.... it's allright or should there be 
> considered unweighted option?

No need for the unweighted option, IMHO.

> - it works with graph using edge weights - should I change it to 
> attributes

Does it make sense for upcoming algorithms ?

 > and assume for further work that all code should be using
> only attributes?

Yes, IMHO.

> Standards BFS returns:
> - BFS tree found by algorithm (struct::tree)
> - BFS graph found by algorithm


> 2. MDST - Minimum diameter spanning tree
>  
> Firstly, how algorithm works:
> - it searches for each node it's BFS tree - so, for each node there is 
> found a tree, with root in that node

> - if, that tree has odd diameter, it's optimal solution

(*)

> - if not.... there can be better solution. For diameter d (diameter of 
> the tree found by BFS), OPT can be "d" or "d-1"

> - now to find, if there is better solution, we do a little trick:
>         a) we search for the deepest subtree of current BFS tree, 
> considering only children of root node as roots of that subtree [*]
>         b) for each subtree found, we do such operation: we add a node 
> between root node of subtree and root node of BFS tree and run BFS again 
> with the start node in a new node we have just added. If the depth of 
> the tree won't change the better solution is found.

> - from all the trees that BFS found, we choose the one with the smallest 
> diameter.

> [*] I've got one concern about that step. My resources say two things: 
> one that we find as I wrote above - the deepest subtree, but also I 
> found that we search for subtree, which height ( the greatest level in a 
> tree -> depth + 1 ) is equal to diameter ( BFS Tree )/2 - 1 (lets call 
> it X for further investigation). So, know I have an issue, if I can just 
> put that equality with X or not, cause I found an example of tree that 
> have even diameter and has bigger value of height than X. On the other 
> hand, that example didn't force the improvement of solution....so, it's 
> possible that this X value can bound the set of proper trees well....but 
> as I'm not completely sure I've put in the code "height >= X" and will 
> investigate it further.
>  
> Implementation:
> - it uses both : graph found with BFS and tree found by BFS.
> - graph is used for diameter counting and other issues, tree is better 
> for handling descendants and finding the greatest tree.
> - it forces adding struct::tree package require to graph ops....is that ok?

Yes.

> - when diameter is odd, it just checks, if found solution is better than 
> previous one

Ah, so what you say at (*) above means 'optimal solution for that specific 
node', not 'optimal solution for the entire graph'.

> - when diameter is even, it does those operations I described above. It 
> creates additional graph for it - tempGraph. If tempGraph has better 
> diameter after providing those changes - the better solution is set.
>  
>  
> 3. Flow problems
>  
> Now both Flow Problems use BFS pathfinding procedure.
>  
> I wrote a little about it in previous mails but to remind:
> - negative arcs - BFS can handle them
> - for not sparse networks BFS is better than Dijkstra - like I noted above.
> - Dijkstra after adding those "must-have" improvements, does a lot more 
> computations. So generally, for typical flow problems BFS will get 
> shorter times of computations -
> even for complete networks ( it's proven ).

> - as BFS has some pathological cases, when reaches exponential increase 
> of amount of operations, but those networks won't occur in practise.

Can you describe the pathological cases ?
This would make a good thing to note in the docs.

> I hope I remebered to write about everything. Just tell me what you 
> think about such organisation.

Review of rev 37+38 will be done sometime today.

> Tests are not full yet, so I will supplement the lacking ones.

Andreas.

[Tcllib-devel] BWidget verification, tagging and TBWidget

[Harald O. <Har...@El...>]

Hi Damon, Hi Jeff, Hi community,

1) Tag BWidget 1.9

IMHO BWidget made a good step in direction bug fixing.
I plan to release the 1.9 bugfix release friday this week.

Are there any objections about that ?

2) Themed BWidget:

I propose to move BWidget direction themed widgets (e.g. ttk).

The last fix which was included (Scrollable Frame) showed, that it
requires quite a couple of trade-offs to support tk and ttk in the same
packages. The number of "if {[Widget::themed]}" are increasing and hit
the parameter level now.

I suggest to branch BWidget here into two loadable packages:
-	BWidget - tk version (requires tk 8.1 (afaik))
-	TBWidget - ttk version (requires tk 8.5)

They should be compatible if senseful (as tk and ttk).
The difference is to issue a different "package require".
If you don't use any themed parameters, they should be identical on the
script level. In future, both may move forward and new widgets may only
be implemented in one of them.

All current themed code will be removed from BWidget and will only be
present in TBWidget (here, someone may complain. The current
Implementation is IMHO only half functional as for example the -bg
parameter mostly runs into an error).

If both packages would be loadable together ?
Propably not.

Please discuss the issue on this list.

Looking forward to your comments,
Harald

[Tcllib-devel] Revision 37

[Michał A. <ant...@gm...>]

Hello.

Regarding previous ping mail, promised description.


1. BFS.

After some attempts and different organisations of code I decided to divide
that BFS procedure into 2 procedures - one for shortests paths finding
(ShortestPathsByBFS) and standard BFS (BFS).

Why and some notes about them:
- creating one procedure for both, makes code quite complex
- as both procedures can return dictionaries, trees and graphs, there would
be a lot of repeated code or a lot of statements like if which make code
doesn't look good ( I just wasn't satisfied at all when I looked at it )
- dividing into 2 procedures, lets us give easily some improvement to path
finding : e.g. if node wasn't in queue yet, it's added at the end of the
queue, but when it was added before and erased also from the queue, we add
it at the beginning of the queue - it helps a lot cause a lot of not needed
computation is omitted.
- I just see it like 1000 times clearer, when there is such division - both,
more intuitive and also considering implementation.


Shortests path finding by BFS vs Dijkstra:
- BFS can work with negative weights ( but negative cycles are of course
unwelcome )
- it's quicker for not sparse graphs, with big amount of nodes
- it also finds (like Dijkstra) paths from one node to others, so we don't
have to use e.g Bellman's Ford, when negative weights are there.

Path finding by BFS returns us:
- dictionary containing distances between start node s and each other
vertice
- or dictionary containing paths between start node and each other vertice

 Notes to BFS path finding:
- it's weighted, so to get unweighted version we just give at input graph
with all weights set to 1.... it's allright or should there be considered
unweighted option?
- it works with graph using edge weights - should I change it to attributes
and assume for further work that all code should be using only attributes?

Standards BFS returns:
- BFS tree found by algorithm (struct::tree)
- BFS graph found by algorithm


2. MDST - Minimum diameter spanning tree

Firstly, how algorithm works:
- it searches for each node it's BFS tree - so, for each node there is found
a tree, with root in that node
- if, that tree has odd diameter, it's optimal solution
- if not.... there can be better solution. For diameter d (diameter of the
tree found by BFS), OPT can be "d" or "d-1"
- now to find, if there is better solution, we do a little trick:
        a) we search for the deepest subtree of current BFS tree,
considering only children of root node as roots of that subtree [*]
        b) for each subtree found, we do such operation: we add a node
between root node of subtree and root node of BFS tree and run BFS again
with the start node in a new node we have just added. If the depth of the
tree won't change the better solution is found.
- from all the trees that BFS found, we choose the one with the smallest
diameter.

[*] I've got one concern about that step. My resources say two things: one
that we find as I wrote above - the deepest subtree, but also I found that
we search for subtree, which height ( the greatest level in a tree -> depth
+ 1 ) is equal to diameter ( BFS Tree )/2 - 1 (lets call it X for further
investigation). So, know I have an issue, if I can just put that equality
with X or not, cause I found an example of tree that have even diameter and
has bigger value of height than X. On the other hand, that example didn't
force the improvement of solution....so, it's possible that this X value can
bound the set of proper trees well....but as I'm not completely sure I've
put in the code "height >= X" and will investigate it further.

Implementation:
- it uses both : graph found with BFS and tree found by BFS.
- graph is used for diameter counting and other issues, tree is better for
handling descendants and finding the greatest tree.
- it forces adding struct::tree package require to graph ops....is that ok?
- when diameter is odd, it just checks, if found solution is better than
previous one
- when diameter is even, it does those operations I described above. It
creates additional graph for it - tempGraph. If tempGraph has better
diameter after providing those changes - the better solution is set.


3. Flow problems

Now both Flow Problems use BFS pathfinding procedure.

I wrote a little about it in previous mails but to remind:
- negative arcs - BFS can handle them
- for not sparse networks BFS is better than Dijkstra - like I noted above.
- Dijkstra after adding those "must-have" improvements, does a lot more
computations. So generally, for typical flow problems BFS will get shorter
times of computations -
even for complete networks ( it's proven ).
- as BFS has some pathological cases, when reaches exponential increase of
amount of operations, but those networks won't occur in practise.


I hope I remebered to write about everything. Just tell me what you think
about such organisation.

Tests are not full yet, so I will supplement the lacking ones.

Best Regards,
Michał Antoniewski

[Tcllib-devel] Review -- Re: Michael Antoniewski committed [36]: New versions of Ford-Fulkerson's and Busacker-Gowen's - using attributes instead of auxiliary dictionaries/edge weigh...

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

gra...@al... wrote:
> 
> New versions of Ford-Fulkerson's and Busacker-Gowen's - using attributes 
> instead of auxiliary dictionaries/edge weights
> New Tests - TODO: some tests when BFS will replace Dijkstra, to show it 
> is handling right cases which Dijkstra couldn't
> Some other little corrections
> Commit from user: Michael Antoniewski
> 
> More details 
> <http://code.assembla.com/graphmanipulations/subversion/changesets/36>

fordfulkerson.test

 >   86:	#Test 3.1 - case when input network has lacking attributes
 >   87:	test 
graphop-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-3.1 
{BusackerGowen, missing attributes } {

Typo, or this testcase is in the wrong test file (fordfulkerson.test <=> 
BusackerGowen)

 >   88:	    SETUP_BUSACKERGOWEN_2
 >   89:	    catch {struct::graph::op::BusackerGowen mygraph 25 s t } result
 >   90:	    mygraph destroy
 >   91:	    set result
 >   92:	} [WrongAttributes throughput cost]

graphops.tcl

 > 1328:		#checking if all attributes for input network are set well ( costs 
and throughputs )
 > 1329:		foreach e [$G arcs] {
 > 1330:			if { ![$G arc keyexists $e throughput] } {
 > 1331:				return -code error "The input network doesn't have all attributes 
set correctly...Some throughputs/costs missing. Please, check again attributes 
\"throughput\" and \"cost\" for input graph."
 > 1332:			}
 > 1333:		}

The comment in line 1328 and error message in line 1333 seem to be
copied from Busacker-Gowen (BG) without modification for FordFulkerson
(FF). FF doesn't have/need/use cost information as far as I can see.

I wonder if I can kill the loop ...

	if {![struct::set empty \
		[struct::set difference \
			[$G arcs] \
			[dict keys [$G arc attr throughput]]]]} {
	    error ...
	}

If not all arcs have a 'throughput' attribute then 'arcs - keys' not
empty. Of course, internally the 'arc attr' will run a loop, and the
'difference' loops internally as well, and we are not stopping early
when something without the attr is found. So, let us keep the checking
via loop. It is clear enough.


 > 1346:		#deleting the arcs that are 0-weighted
 > 1347:		foreach e [$residualG arcs] {
 > 1348:			if { [$residualG arc set $e throughput] == 0 } {

		set ? Ok, it works because 'set' returns the value as well.
		Still, using 'get' is easier to understand.

 > 1349:				$residualG arc delete $e
 > 1350:			}
 > 1351:		}
 > 1352:		
 > 1353:		#the main loop - works till the path between source and the sink can 
be found
 > 1354:		while {1} {
 > 1355:			


 > 1356:			#setting the edge weights to find the shortests path between source 
and sink
 > 1357:			#considering number of edges
 > 1358:			foreach e [$residualG arcs] {
 > 1359:				$residualG arc setweight $e 1
 > 1360:			}

Am I correct that you are not setting the arc weights in 'createResidualGraph' ?
If yes, then

	$residualG arc setunweighted 1

should do the same thing as this loop (It sets the weight of all arcs
without weights to the specified value). Could also be moved to
'createResidualGraph' to make it part of the setup for the residual.


 > 1397:				#if maxThroughput is not greater than current throughput at the 
edge not contained in path p (here - v->u),
 > 1398:				#we add a difference between those values to edge contained in the 
path p (here u->v) and substract that
 > 1399:				#difference from edge not contained in the path p.
 > 1400:					set difference [ expr { $f_vu - $maxThroughput } ]
 > 1401:					dict set f [list $u $v] [ expr { $f_uv + $difference } ]
 > 1402:					dict set f [list $v $u] [ expr { $f_vu - $difference } ]

				$f_vu - $difference
			==	$f_vu - ($f_vu - $maxThroughput)
			==	$maxThroughput


 > 1447:			set u [lindex $e 0]
 > 1448:			set v [lindex $e 1]

		lassign $e u v

 > 1531:			set c_uv [$G arc set [list $u $v] throughput]
 > 1532:			set d_uv [$G arc set [list $u $v] cost]

			arc set
		=>	arc get

 > 1534:			#adding apparent arcs
 > 1535:			if { ![$Gf arc exists [list $v $u]] } {
 > 1536:				$Gf arc insert $v $u [list $v $u]

 > 1537:				#1.

	References to the equations are good.

 > 1637:		
 > 1638:		while { $currentFlow < $desiredFlow } {
 > 1639:		
 > 1640:			#preparing correct values for dijkstra
 > 1641:			foreach edge [$Gf arcs] {
 > 1642:				$Gf arc setweight $edge [$Gf arc set $edge cost]

				'arc get' presumably when reading the cost ?

 > 1643:			}

 > 1659:			foreach u [lrange $path 0 end-1] v [lrange $path 1 end] {
 > 1660:				if { $maxThroughput >     [$Gf arc set [list $u $v] throughput] } {
 > 1661:					set maxThroughput [$Gf arc set [list $u $v] throughput]
 > 1662:				}

One thing I note generally is that you tend to repeat common
expressions/commands. In a compiled language that tends to be fixed by
the compiler's optimization passes, i.e detecting common
sub-expressions and pulling them out and run only once.

In Tcl no such detection and optimization takes place.

Sometimes this means that more variables are used, to save unchanging
results (of common sub-expressions / commands). Sometimes this means
less variables are used, because expression inlining and then
simplification creates a less complex expression/command (see below
1671+).

 > 1663:			}
 > 1664:			
 > 1665:			#if max throughput that was found will cause exceeding the desired
 > 1666:			#flow, send as much as it's possible
 > 1667:			if { ( $currentFlow + $maxThroughput ) <= $desiredFlow } {
 > 1668:				set fAdd $maxThroughput
 > 1669:				set currentFlow [ expr { $currentFlow + $fAdd } ]
 > 1670:			} else {
 > 1671:				set fAdd [ expr { $desiredFlow - $currentFlow } ]
 > 1672:				set currentFlow [ expr { $currentFlow + $fAdd } ]

			current
			= current + add
			= current + (desired - current)
			= desired

 > 1690:			
 > 1691:			#create new Augemnting Network
 > 1692:			set Gf [createAugmentingNetwork $Gf $f $path]

The Gf argument to 'createAugmentingNetwork' still leaks, because the
command creates a new graph. I a making sense ? To not leak

			set Gfnew [createAugmentingNetwork $Gf $f $path]
			$Gf destroy
			set Gf $Gfnew

 > 1693:		}
 > 1694:		
 > 1695:		#erasing the edges from solution, where throuputs are equal to 0
 > 1696:		foreach flow [dict keys $f] {
 > 1697:			if { [dict get $f $flow] == 0 } {
 > 1698:				set f [dict remove $f $flow]
 > 1699:			}
 > 1700:		}

Per http://docs.activestate.com/activetcl/8.5/tcl/TclCmd/dict.htm#M10
this explicit loop can be replaced with

	set f [dict filter $f {flow flowvalue} {expr {$flowvalue != 0}}]

	# <=> Keep           all flows with value != 0.
	# <=> Discard/remove all flows with value == 0.

Note further
	http://docs.activestate.com/activetcl/8.5/tcl/TclCmd/dict.htm#M14
and	http://docs.activestate.com/activetcl/8.5/tcl/TclCmd/dict.htm#M17

I haven't gone back and checked if these are applicable, they may.

Andreas

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.

Re: [Tcllib-devel] Flow problems - attributes question

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

Michał Antoniewski wrote:
> Oh, I think I missed somehow note to use attributes for arcs/nodes.

Let me check my mail archives ... Ok, found it, review rev 32, mail of July 7 
... I am inlining

Michał Antoniewski wrote:
 > >
 > >
 > >
 > >     Should document structure of nodeWeights as list of (list (node,
 > >     weight)). This I inferred from the commands using the data, otherwise
 > >     it could have been a dictionary.
 > >
 > >
 > > Oh, sorry, I forgot to describe it...Yes, it's a list like you said. I
 > > thought also adding maintenance of weights at nodes for struct::graph
 > > could be a good new functionality, so that nodeWeights could be found by
 > > "$G node weights" for example. In that case, it could be useful to
 > > change that list (nodeWeights) to work as a dictionary ( regarding "$G
 > > arc weights returns dict ).
 > > Weights at nodes could be widely used in graph coloring algorithms.

We already have general node attributes, i.e. each node in a graph can have an
arbitrary set of named values. The relevant methods are

	node set    $u $name $value	- Set named attribute to a value
	node append $u $name		- Append data to attribute
	node append $u $name		- Ditto, but list-like
	node get    $u $name		- Retrieve attribute value for node
	node getall $u			- Retrieve all attributes for node
	node unset  $u $name		- Delete attribute
	node keyexists $u $name		- Check if attribute is known to node.

And also, especially interesting for us:

	node attr $name			- Return attribute value for all nodes
					  as dictionary (node -> value).

http://docs.activestate.com/activetcl/8.5/tcllib/struct/graph.html

May I propose to use this facility ? In the first iteration we can use a fixed
attribute name, like 'weight', and later on the attribute name could be made
configurable.

I know that this is different from what we did last year for the arc weights.
This is actually intentional. Seeing them both I am hoping to get a feel for
the differences and similarities in the both approaches and which would be
better in general.


> I was writing test cases and now it appeared even more useful...e.g., 
> when testing, if input is proper...So, I will change that and then 
> update, so there will disappear that dictionary from input which 
> contains throughputs (in Busacker Gowen).

I see. Ok.


> But I've got a question...I need to use dijkstra ( or later other path 
> finding procedure ), but it finds the path using weights on edges ...

Yes.

> And I need it to search for costs....It forces me to place costs on edge 
> weights in graph G and throughputs as edge attributes...

Right.

> Or maybe I missed something and it's possible somehow to run dijkstra 
> with set of attributes as weights?

Unfortunately not. This is why I am driving a bit towards the arc/node 
attribute, to prevent problem like that in the future. For example, I see in 
the latest FordFulkerson who you are using a 'copyWeights' variable to 
temporarily save the capacities so that you can use dijkstra with weight 1 
everywhere, then reload the old weights. Right now we have to do it this way 
with a full graph copy, because of the distinct arc weights.

(I am not asking you to rewrite dijkstra yet. After the summer maybe).

>  
> Another option could be just setting those weights (from attribute 
> values) just before running Dijkstra....is that a good way?

Yes, that is a possibility. The 'arc attr' method will be of help. It provides 
a dictionary of the arc -> value mapping for a named attribute A.

 > Then I
> could use only attributes in implementation, both for costs and 
> throughputs ( arc weights would be set only for Dijkstra ).
>  
> Please, tell me which version you consider better? So, I will correct it 
> to get a final version.

I would say, try to use arc attributes (see the short doc above for node 
attributes, then replace node -> arc for the equivalent methods). Document the 
name of the arc attributes.


> About Dijkstra....I created test cases where Dijkstra easily 
> fails....so, BFS will be needed surely :) Regarding other mail....if we 
> would want to use Dijkstra anyway, it would need creating separate 
> version of it, or if we don't want any optimizations, just making sure 
> it won't get any negative weights should do the trick ...but still BFS 
> looks better....

I will leave that decision in your hands, you are nearer to the code and the 
possible effort required for either solution.

Andreas.

[Tcllib-devel] Flow problems - attributes question

[Michał A. <ant...@gm...>]

Oh, I think I missed somehow note to use attributes for arcs/nodes.

I was writing test cases and now it appeared even more useful...e.g., when
testing, if input is proper...So, I will change that and then update, so
there will disappear that dictionary from input which contains throughputs
(in Busacker Gowen).

But I've got a question...I need to use dijkstra ( or later other path
finding procedure ), but it finds the path using weights on edges ...

And I need it to search for costs....It forces me to place costs on edge
weights in graph G and throughputs as edge attributes...
Or maybe I missed something and it's possible somehow to run dijkstra with
set of attributes as weights?

Another option could be just setting those weights (from attribute
values) just before running Dijkstra....is that a good way?  Then I could
use only attributes in implementation, both for costs and throughputs ( arc
weights would be set only for Dijkstra ).

Please, tell me which version you consider better? So, I will correct it to
get a final version.


About Dijkstra....I created test cases where Dijkstra easily fails....so,
BFS will be needed surely :) Regarding other mail....if we would want to use
Dijkstra anyway, it would need creating separate version of it, or if we
don't want any optimizations, just making sure it won't get any negative
weights should do the trick ...but still BFS looks better....

Best Regards,
Michał Antoniewski

Re: [Tcllib-devel] FordFulkerson

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

Michał Antoniewski wrote:
>         ( Bellman-Ford's is worser to use in that case than Dijkstra ).
>         However,
>         I've found some info saying that there is algorithm (path
>         finding), which
>         suits best for flow problems - it's faster than Dijkstra for
>         rare networks
> 
> 
>     Do you mean _sparse_ networks?
> Yes, sorry. Sometimes translating literally is dangerous :) 

Quite.


>     No, the literature I have just discusses BFS vs. DFS for finding
>     augmenting paths. I believe most work on faster max-flow algorithms
>     rather focuses on doing something other than augmenting paths, e.g.
>     blocking flows (Dinic) or push&relabel (Goldberg--Tarjan).

> I found some more info on that. Firstly, about Dijkstra, it can be used 
> in flow problems, but it's needed to do some changes, like when weights 
> are negative, adding the same value to all weights, just to get all 
> positive weights in network (so, the differences between them are 
> constant ). Also, I found out that this PDM algorithm I mentioned is 
> Moore's-Bellman's-d'Esopo-Papego algorithm for finding paths between two 
> nodes, but negative weights are possible. When, I looked at pseudocode 
> it turned out to be....BFS (weighted) :) :)  This weird name PDM made 
> some confusion... So generally, BFS is better than Dijkstra ( however, 
> it can't be stopped like Dijkstra, when found certain path and must go 

Note that our dijkstra implementation cannot stop either. Maybe a cut-down 
implementation is needed to just find a single path A -> B, which stops as 
early as possible ?

> through all paths ), so I guess it should be placed in implementation 

I guess you meant	"in _its own_ implementation"

> instead of Dijkstra's.


> Oh, that's interesting. I didn't know before those CS and Orlin's 
> algorithms. I've decided to choose Busacker-Gowen (or SSP) to add in my 
> application's timeline, as it was AFAIK the most popular algorithm for 
> that problem and also well known to me.

Andreas.

Re: [Tcllib-devel] Busacker-Gowen

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

Michał Antoniewski wrote:
> So, Busacker and Gowen, a little description:
>  
> Generally, the problem concerns finding the max possible flow (but not 
> greater than 'd', which we give at input ) but now input network not 
> only has throughputs but also each edge has it's cost. So, we are 
> seaching for max flow with a minimum cost from source to sink.

And here is another example to fuel Lars's objection against distinct arc 
weights. We have arc capacaties and costs, both of which are some sort of 
weight, for the different parts of the algorithm

> Algorithm goes like this:
> - we search for shortest path between s and t ( considering edge costs )
> - we compute maximum value of throughput that can be send by the path
> - if adding such througput exceeds 'd' (input value of flow we desired) 
> we add as much as possible (so the desired flow value 'd' is reached)
> - transform network into Augmenting Network
> - repeat from the top.
> - procedure ends when there is no path, or 'd' is reached.
>  
> Everything is described in the code.

Ok.

Andreas.

Re: [Tcllib-devel] FordFulkerson

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

Lars Hellström wrote:
> Michał Antoniewski skrev:
>>  Hello.
>>
>> About flow problems:
>> - Edmond's Karp algorithm, like Lars has written, is indeed extension of
>> Ford's Fulkerson. The difference is as it was said, in Edmond's Karp we
>> search for shortest paths between s and t. Just to mention, those shortest
>> paths are chosen considering the smallest amount of edges between s and t,
>> not throughputs. So, it's like running Dijkstra on residual graph, with all
>> weights at edges set to 1, just for that one operation. After some thinking,
>> I don't see any way to omit using Dijkstra or any other path finding method

That is ok, Michal. My objection to the code I saw was that the exact same 
dijkstra was run twice, I was not against its general use.

>> - min cost flow problems - actually, we've got one algorithm in timeline for
>> that: Busacker-Gowen ( already implemented,just have to do some more tests )

Looking forward to that.

Andreas

Re: [Tcllib-devel] FordFulkerson

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

Lars Hellström wrote:
> Andreas Kupries skrev:
>> Lars Hellström wrote:
>>> Using [dijkstra] for computing the augmenting path /probably/ means it 
>>> will be a shortest path (though it depends on how weights are assigned 
>>> in $residualG),
>> Can you explain how the weights have to be assigned in the residualG to 
>> not make this a shortest path ?
> 
> If the weights are taken to be the residual capacities, then in a 
> $residualG of
> 
>        1        2
>    u -----> v -----> w
>    |                 A
>    |        8        |
>    +-----------------+,
> 
> [dijkstra] will pick u->v->w as shortest path from u to w, even though 
> the shortest path in the sense relevant here (fewest number of edges) 
> is u->w. All weights equal to 1 makes the two concepts equal.

Thanks for the explanation. Looking at the rev 33 code it seems that it uses 
dijktra with the capacity weights, so not shortest path by hop, but by 
remaining capacity.

Might make sense to modify dijkstra to be able to ignore any weights

> 
> BTW, this is why I'm skeptical against the distiguished weight property 
> of [struct::graph]s: sometimes weight means cost, other times it means 
> capacity, so mixing algorithms that apply one interpretation with 
> algorithms that apply the other is going to be awkward.

Yes. See also my comments then Michal asked me about node weights. I asked him 
to try to use the standard node attributes for that, instead of distinct node 
weights. For comparison, and later (aater GSoC) to possibly change the existing 
code over to regular arc attributes for weights etc.

Andreas.

Re: [Tcllib-devel] Busacker-Gowen

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

Michał Antoniewski wrote:
> Forgot to add that all corrections you noted in previous mails are also 
> done in last revision.
>  
> And also:
>  
>  >>That is an interesting applet. May I propose that we do something 
> like this after the project, as an example ?
>  
> I can do something like that applet, no problem:) Maybe it could be nice 
> idea placing there pre-made graphs, which were used in tests ( I mean 

Yes.

> those most vital. I believe each set of tests for each algorithm has 
> that leading one or two, which consider most cases and can show well how 
> algorithm works ).

 > And also you see it as stand-alone application or
> also applet?

I see it as stand-alone app which we can put into either the examples/struct/ 
or the apps/ subtree of Tcllib.

I will review revision 35 sometime today.

Andreas.

Re: [Tcllib-devel] Busacker-Gowen

[Michał A. <ant...@gm...>]

Forgot to add that all corrections you noted in previous mails are also done
in last revision.

And also:

>>That is an interesting applet. May I propose that we do something like
this after the project, as an example ?

I can do something like that applet, no problem:) Maybe it could be nice
idea placing there pre-made graphs, which were used in tests ( I mean those
most vital. I believe each set of tests for each algorithm has that leading
one or two, which consider most cases and can show well how algorithm
works ). And also you see it as stand-alone application or also applet?



Best Regards,
Michał Antoniewski

Re: [Tcllib-devel] FordFulkerson

[Michał A. <ant...@gm...>]

2009/7/12 Lars Hellström <Lar...@re...>

> Michał Antoniewski skrev:
>
>>  Hello.
>>
>> About flow problems:
>> - Edmond's Karp algorithm, like Lars has written, is indeed extension of
>> Ford's Fulkerson. The difference is as it was said, in Edmond's Karp we
>> search for shortest paths between s and t. Just to mention, those shortest
>> paths are chosen considering the smallest amount of edges between s and t,
>> not throughputs. So, it's like running Dijkstra on residual graph, with
>> all
>> weights at edges set to 1, just for that one operation. After some
>> thinking,
>> I don't see any way to omit using Dijkstra or any other path finding
>> method
>>
>
> Note that a basic breadth-first-search would be sufficient here (a tragedy
> of the 60's is that DFS was easier to implement than BFS; had it been the
> other way round, it's probable that Ford and Fulkerson would have ended up
> with Edmonds--Karp from the start).
>


Actually, next step in timeline will be spanning tree algorithms, like
spanning tree with minimum diameter which uses BFS, so BFS is in timeline
anyway.



>
>
> ( Bellman-Ford's is worser to use in that case than Dijkstra ). However,
>> I've found some info saying that there is algorithm (path finding), which
>> suits best for flow problems - it's faster than Dijkstra for rare networks
>>
>
> Do you mean _sparse_ networks?
>


Yes, sorry. Sometimes translating literally is dangerous :)


>
>
> and for typical flow problems even for complete networks. It was called
>> PDM,
>> so I have to review it and find some more info about it to say more about
>> is
>> it worth implementing it....
>>
>> Maybe Lars knows anything about it? I would guess, it can be some improved
>> version of e.g. Dijkstra, adapted for flow problems.
>>
>
> No, the literature I have just discusses BFS vs. DFS for finding augmenting
> paths. I believe most work on faster max-flow algorithms rather focuses on
> doing something other than augmenting paths, e.g. blocking flows (Dinic) or
> push&relabel (Goldberg--Tarjan).
>


I found some more info on that. Firstly, about Dijkstra, it can be used in
flow problems, but it's needed to do some changes, like when weights are
negative, adding the same value to all weights, just to get all positive
weights in network (so, the differences between them are constant ). Also, I
found out that this PDM algorithm I mentioned is
Moore's-Bellman's-d'Esopo-Papego algorithm for finding paths between two
nodes, but negative weights are possible. When, I looked at pseudocode it
turned out to be....BFS (weighted) :) :)  This weird name PDM made some
confusion... So generally, BFS is better than Dijkstra ( however, it can't
be stopped like Dijkstra, when found certain path and must go through all
paths ), so I guess it should be placed in implementation instead of
Dijkstra's.

Next algorithm in timeline considering flow problems is Dinic and 3 Hindu
algorithm, with blocking flows etc. Actually, we were talking with Andreas
about replacing it with some new problems ( Set Cover, Shortest Super String
), but in that case maybe, it's worth not to erase it from timeline and
maybe replacing with Set Cover another problem (if any)?




>  So, I think I'm going to extend Ford-Fulkerson into Edmond's Karp (
>> actually, it's already done ).
>>
>> - min cost flow problems - actually, we've got one algorithm in timeline
>> for
>> that: Busacker-Gowen ( already implemented,just have to do some more tests
>> )
>>
>
> Also known as "successive shortest path algorithm", it seems (the
> underlying theorem appears independently in at least three papers, only one
> of which is by Busacker and Gowen). If so, then I'm not surprised, as this
> algorithm appears to be very similar to Ford--Fulkerson (including the
> unfortunate dependence on capacities in the running time). Should indeed be
> a rather minor modification of what you've already presented.
>
> There appears to be a catch, however: I see a mention that one cannot at
> all steps use Dijkstra to find the shortest paths, as there may be negative
> weights (costs) on edges.
>


Yes, Dijkstra can't be used, if we don't modify it a bit ( like I said above
), what makes it also more costly. Busacker-Gowen and Ford-Fulkerson are
based on the same concept, so there indeed are similarities, but still
needed to be examined in new problem definition.

 - another extension is Dinic method combined with Malhotra-Kumar-Maheshwari
>> algorithm ( which finds blocking flow ). It's another way for finding max
>> flow in flow networks. As far as I know, there is also Dinic's algorithm
>> for
>> finding blocking flows, so actually, that also can be chosen... Both
>> algorithms (Dinic and Malhotra-Kumar-Maheshwari) are now in timeline, but
>>
>
> Both Dinic and Malhotra--Kumar--Maheshwari appear to be max-flow
> algorithms, AFAICT.
>
> For min-cost-flow, the literature I have at hand rather suggests the
> capacity scaling algorithm (by Edmonds and Karp) or Orlin's algorithm, both
> of which are polynomial. A catch is however that at least the descriptions I
> have for these are for the uncapacitated min-cost-flow problem.
> Min-cost-flow with capacities can be reduced to min-cost-flow without
> capacities, but there is an overhead for doing so. The complexities appear
> to be
>
>         Uncapacitated       Capacitated
> SSP      O(mn+B(n^2+m))      O(mn+B(n^2+m))
> CS       O(n(n^2+m)\log B)   O(m(n^2+m)\log B)?
> Orlin    O(n(n^2+m)\log m)   O(m(n^2+m)\log m)
> MMCC     O(m^3 n^2 \log n)   O(m^3 n^2 \log n)
>
> Here, n=number of vertics, m=number of edges, and B is the sum over all
> vertices of the absolute value of the net flow at that vertex. SSP =
> Successive Shortest Path (Busacker--Gowen) Algorithm, CS = Capacity Scaling
> Algorithm, and MMCC = Minimum Mean Cycle-Cancelling Algorithm.
>
> Unfortunately, there is no clear winner.
>
>
> Lars Hellström
>
>

Oh, that's interesting. I didn't know before those CS and Orlin's
algorithms. I've decided to choose Busacker-Gowen (or SSP) to add in my
application's timeline, as it was AFAIK the most popular algorithm for that
problem and also well known to me.



Best Regards,
Michał Antoniewski

Re: [Tcllib-devel] Busacker-Gowen

[Michał A. <ant...@gm...>]

So, Busacker and Gowen, a little description:

Generally, the problem concerns finding the max possible flow (but not
greater than 'd', which we give at input ) but now input network not only
has throughputs but also each edge has it's cost. So, we are seaching for
max flow with a minimum cost from source to sink.

Algorithm goes like this:
- we search for shortest path between s and t ( considering edge costs )
- we compute maximum value of throughput that can be send by the path
- if adding such througput exceeds 'd' (input value of flow we desired) we
add as much as possible (so the desired flow value 'd' is reached)
- transform network into Augmenting Network
- repeat from the top.
- procedure ends when there is no path, or 'd' is reached.

Everything is described in the code.

Best Regards,
Michał Antoniewski

Re: [Tcllib-devel] FordFulkerson

[Lars H. <Lar...@re...>]

Michał Antoniewski skrev:
>  Hello.
> 
> About flow problems:
> - Edmond's Karp algorithm, like Lars has written, is indeed extension of
> Ford's Fulkerson. The difference is as it was said, in Edmond's Karp we
> search for shortest paths between s and t. Just to mention, those shortest
> paths are chosen considering the smallest amount of edges between s and t,
> not throughputs. So, it's like running Dijkstra on residual graph, with all
> weights at edges set to 1, just for that one operation. After some thinking,
> I don't see any way to omit using Dijkstra or any other path finding method

Note that a basic breadth-first-search would be sufficient here (a 
tragedy of the 60's is that DFS was easier to implement than BFS; had 
it been the other way round, it's probable that Ford and Fulkerson 
would have ended up with Edmonds--Karp from the start).

> ( Bellman-Ford's is worser to use in that case than Dijkstra ). However,
> I've found some info saying that there is algorithm (path finding), which
> suits best for flow problems - it's faster than Dijkstra for rare networks

Do you mean _sparse_ networks?

> and for typical flow problems even for complete networks. It was called PDM,
> so I have to review it and find some more info about it to say more about is
> it worth implementing it....
> 
> Maybe Lars knows anything about it? I would guess, it can be some improved
> version of e.g. Dijkstra, adapted for flow problems.

No, the literature I have just discusses BFS vs. DFS for finding 
augmenting paths. I believe most work on faster max-flow algorithms 
rather focuses on doing something other than augmenting paths, e.g. 
blocking flows (Dinic) or push&relabel (Goldberg--Tarjan).

> So, I think I'm going to extend Ford-Fulkerson into Edmond's Karp (
> actually, it's already done ).
> 
> - min cost flow problems - actually, we've got one algorithm in timeline for
> that: Busacker-Gowen ( already implemented,just have to do some more tests )

Also known as "successive shortest path algorithm", it seems (the 
underlying theorem appears independently in at least three papers, only 
one of which is by Busacker and Gowen). If so, then I'm not surprised, 
as this algorithm appears to be very similar to Ford--Fulkerson 
(including the unfortunate dependence on capacities in the running 
time). Should indeed be a rather minor modification of what you've 
already presented.

There appears to be a catch, however: I see a mention that one cannot 
at all steps use Dijkstra to find the shortest paths, as there may be 
negative weights (costs) on edges.

> - another extension is Dinic method combined with Malhotra-Kumar-Maheshwari
> algorithm ( which finds blocking flow ). It's another way for finding max
> flow in flow networks. As far as I know, there is also Dinic's algorithm for
> finding blocking flows, so actually, that also can be chosen... Both
> algorithms (Dinic and Malhotra-Kumar-Maheshwari) are now in timeline, but

Both Dinic and Malhotra--Kumar--Maheshwari appear to be max-flow 
algorithms, AFAICT.

For min-cost-flow, the literature I have at hand rather suggests the 
capacity scaling algorithm (by Edmonds and Karp) or Orlin's algorithm, 
both of which are polynomial. A catch is however that at least the 
descriptions I have for these are for the uncapacitated min-cost-flow 
problem. Min-cost-flow with capacities can be reduced to min-cost-flow 
without capacities, but there is an overhead for doing so. The 
complexities appear to be

          Uncapacitated       Capacitated
SSP      O(mn+B(n^2+m))      O(mn+B(n^2+m))
CS       O(n(n^2+m)\log B)   O(m(n^2+m)\log B)?
Orlin    O(n(n^2+m)\log m)   O(m(n^2+m)\log m)
MMCC     O(m^3 n^2 \log n)   O(m^3 n^2 \log n)

Here, n=number of vertics, m=number of edges, and B is the sum over all 
vertices of the absolute value of the net flow at that vertex. SSP = 
Successive Shortest Path (Busacker--Gowen) Algorithm, CS = Capacity 
Scaling Algorithm, and MMCC = Minimum Mean Cycle-Cancelling Algorithm.

Unfortunately, there is no clear winner.


Lars Hellström

Re: [Tcllib-devel] FordFulkerson

[Lars H. <Lar...@re...>]

Andreas Kupries skrev:
> Lars Hellström wrote:
>> Using [dijkstra] for computing the augmenting path /probably/ means it 
>> will be a shortest path (though it depends on how weights are assigned 
>> in $residualG),
> 
> Can you explain how the weights have to be assigned in the residualG to 
> not make this a shortest path ?

If the weights are taken to be the residual capacities, then in a 
$residualG of

       1        2
   u -----> v -----> w
   |                 A
   |        8        |
   +-----------------+,

[dijkstra] will pick u->v->w as shortest path from u to w, even though 
the shortest path in the sense relevant here (fewest number of edges) 
is u->w. All weights equal to 1 makes the two concepts equal.

BTW, this is why I'm skeptical against the distiguished weight property 
of [struct::graph]s: sometimes weight means cost, other times it means 
capacity, so mixing algorithms that apply one interpretation with 
algorithms that apply the other is going to be awkward.

Lars Hellström