You can subscribe to this list here.
2001 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(15) 
_{Nov}
(37) 
_{Dec}
(15) 

2002 
_{Jan}
(13) 
_{Feb}
(58) 
_{Mar}
(61) 
_{Apr}
(8) 
_{May}

_{Jun}
(18) 
_{Jul}
(51) 
_{Aug}
(11) 
_{Sep}
(41) 
_{Oct}
(19) 
_{Nov}
(39) 
_{Dec}
(14) 
2003 
_{Jan}
(46) 
_{Feb}
(28) 
_{Mar}
(3) 
_{Apr}
(132) 
_{May}
(93) 
_{Jun}
(46) 
_{Jul}
(22) 
_{Aug}
(55) 
_{Sep}
(13) 
_{Oct}
(6) 
_{Nov}
(8) 
_{Dec}
(6) 
2004 
_{Jan}
(28) 
_{Feb}
(60) 
_{Mar}
(9) 
_{Apr}
(28) 
_{May}
(39) 
_{Jun}
(40) 
_{Jul}
(36) 
_{Aug}
(13) 
_{Sep}
(21) 
_{Oct}
(38) 
_{Nov}
(25) 
_{Dec}
(8) 
2005 
_{Jan}
(6) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(2) 
_{May}
(17) 
_{Jun}
(9) 
_{Jul}
(7) 
_{Aug}
(90) 
_{Sep}
(44) 
_{Oct}
(40) 
_{Nov}
(22) 
_{Dec}
(1) 
2006 
_{Jan}
(31) 
_{Feb}
(10) 
_{Mar}
(1) 
_{Apr}
(3) 
_{May}
(8) 
_{Jun}
(28) 
_{Jul}
(5) 
_{Aug}
(42) 
_{Sep}
(40) 
_{Oct}
(40) 
_{Nov}
(27) 
_{Dec}
(26) 
2007 
_{Jan}
(14) 
_{Feb}
(13) 
_{Mar}
(3) 
_{Apr}
(3) 
_{May}
(22) 
_{Jun}

_{Jul}

_{Aug}
(17) 
_{Sep}
(10) 
_{Oct}

_{Nov}
(24) 
_{Dec}
(5) 
2008 
_{Jan}

_{Feb}
(2) 
_{Mar}
(3) 
_{Apr}
(4) 
_{May}
(18) 
_{Jun}
(10) 
_{Jul}
(1) 
_{Aug}
(10) 
_{Sep}
(5) 
_{Oct}
(3) 
_{Nov}
(5) 
_{Dec}
(3) 
2009 
_{Jan}
(17) 
_{Feb}
(31) 
_{Mar}
(5) 
_{Apr}
(6) 
_{May}
(15) 
_{Jun}
(52) 
_{Jul}
(48) 
_{Aug}
(39) 
_{Sep}
(6) 
_{Oct}
(11) 
_{Nov}
(8) 
_{Dec}
(6) 
2010 
_{Jan}
(2) 
_{Feb}
(3) 
_{Mar}
(1) 
_{Apr}

_{May}
(3) 
_{Jun}
(12) 
_{Jul}
(1) 
_{Aug}

_{Sep}
(4) 
_{Oct}

_{Nov}
(4) 
_{Dec}
(1) 
2011 
_{Jan}
(3) 
_{Feb}
(21) 
_{Mar}
(17) 
_{Apr}
(8) 
_{May}
(10) 
_{Jun}
(7) 
_{Jul}

_{Aug}
(1) 
_{Sep}
(1) 
_{Oct}

_{Nov}
(5) 
_{Dec}
(3) 
2012 
_{Jan}
(1) 
_{Feb}
(1) 
_{Mar}
(3) 
_{Apr}
(1) 
_{May}
(6) 
_{Jun}

_{Jul}
(1) 
_{Aug}
(1) 
_{Sep}
(1) 
_{Oct}
(1) 
_{Nov}

_{Dec}
(8) 
2013 
_{Jan}
(3) 
_{Feb}
(7) 
_{Mar}
(3) 
_{Apr}
(1) 
_{May}
(2) 
_{Jun}
(1) 
_{Jul}
(1) 
_{Aug}
(3) 
_{Sep}
(1) 
_{Oct}
(1) 
_{Nov}

_{Dec}

2014 
_{Jan}
(1) 
_{Feb}
(12) 
_{Mar}
(4) 
_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 




1
(2) 
2
(2) 
3
(1) 
4

5

6
(9) 
7
(2) 
8
(1) 
9
(2) 
10
(2) 
11
(2) 
12

13
(11) 
14

15
(1) 
16

17

18
(1) 
19

20
(3) 
21
(1) 
22

23
(3) 
24
(3) 
25

26

27
(1) 
28

29
(1) 
30

31


From: Andreas Kupries <akupries@sh...>  20090729 01:46:12

Not much to say > 2062: #Dinic algorithm for finding maximum flow in flow network > 2063: # > 2064: # > 2065: #Reference: http://en.wikipedia.org/wiki/Dinic's_algorithm > 2066: # > 2067: proc ::struct::graph::op::MaximumFlowByDinic {G s t blockingFlowAlg} { > 2068: > 2069: if { !($blockingFlowAlg eq "dinic"  $blockingFlowAlg eq "mkm") } { > 2070: return code error "Uncorrect name of blocking flow algorithm. Choose \"mkm\" for Malhotra, Kumar and Maheshwari algorithm and \"dinic\" for Dinic algorithm." > 2071: } > 2072: > 2073: foreach arc [$G arcs] { > 2074: set u [$G arc source $arc] > 2075: set v [$G arc target $arc] > 2076: > 2077: dict set f [list $u $v] 0 > 2078: dict set f [list $v $u] 0 > 2079: } > 2080: > 2081: while {1} { > 2082: set residualG [createResidualGraph $G $f] One new graph is currently created per loop, and never released. Memory leak. > 2134: set paths [ShortestsPathsByBFS $LevelGraph $s paths] > 2135: > 2136: if { $paths == 0 } break > 2137: if { ![dict exists $paths $t] } break > 2346: #deleting arcs with 0 throughputs for proper pathfinding > 2347: foreach arc [$Gf arcs] { > 2348: if { [$Gf arc get $arc throughput] == 0 } { > 2349: $Gf arc delete $arc > 2350: } > 2351: } The loop can be written as $Gf arc delete {*}[$Gf arcs key throughput value 0] Per http://docs.activestate.com/activetcl/8.5/tcllib/struct/graph.html#37 (arcs) and http://docs.activestate.com/activetcl/8.5/tcllib/struct/graph.html#13 (arc delete) key key Limit the list of arcs that are returned to those arcs that have an associated key key. value value This restriction can only be used in combination with key. It limits the list of arcs that are returned to those arcs whose associated key key has the value value. The {*} syntax expands the result of the [...] to make each word a separate argument in the command it was used in, here 'arc delete'. This type of reduction may apply in other places as well, although this is the first time I noticed it. We can fix this up when integrating the project results into Tcllib proper.  So long, Andreas Kupries <akupries@...> <http://www.purl.org/NET/akupries/>; Developer @ <http://www.activestate.com/>;  
From: Andreas Kupries <andreask@ac...>  20090727 23:27:19

XOpsSetup > 1999: proc WrongAttributes {args} { > 2000: set message "The input network doesn't have all attributes set correctly... Please, check again attributes: " > 2001: foreach a $args { > 2002: if { !([lindex $args end] == $a) } { > 2003: set message "$message\"$a\" and " > 2004: } else { > 2005: set message "$message\"$a\"" This form should be written as append message "\"$a\"" See also line 2003. > 2006: } > 2007: } The whole loop can be written as append message\"[join $args "\" and \""]\" Assuming that [llength $args] > 0, always. If not we just have to make this 'append' command conditional. join {a b c} , => "a,b,c" > 2008: > 2009: return "$message for input graph." > 2010: } > 2011: andreask@...:~/workbench/gsoc> graphops.tcl > 2070: #Dinic algorithm for finding blocking flow > 2071: # > 2072: # > 2073: #Algorithm for given network G with source s and sink t, finds a blocking > 2074: #flow, which can be used to obtain a maximum flow for that network G. > 2075: # > 2076: #Some steps that algorithm takes: > 2077: #1. constructing the level graph from network G > 2078: #2. until there are edges in level graph: I guess 'no edges', that would match code. > 2079: # 3. find the path between s and t nodes in level graph > 2080: # 4. for each edge in path update current throughputs at those edges and... > 2081: # 5. ...deleting nodes from which there are no residual edges > 2082: #6. return the dictionary containing the blocking flow > 2083: > 2084: proc ::struct::graph::op::BlockingFlowByDinic {G s t} { > 2085: set iteration 1 > 2094: #1. > 2095: set LevelGraph [createLevelGraph $G s] Leak. The graph is not deleted when we are done. > 2096: > 2097: #2. the main loop > 2098: while { [llength [$LevelGraph arcs]] > 0 } { > 2099: > 2102: #3. > 2103: set paths [ShortestsPathsByBFS $LevelGraph $s paths] > 2104: > 2105: if { ![dict exists $paths $t] } break > 2106: set path [dict get $paths $t] > 2107: lappend path $t > 2108: > 2109: if { $path == 0 } break This is never true, because of line 2107. If the check is about 'no paths', that should have been handled by line 2105, so this condition is possibly superfluous. > 2139: #deleting the node, if it hasn't any outgoing arcs > 2140: if { ![llength [$LevelGraph nodes out $u]]  ![llength [$LevelGraph nodes in $u]] } { > 2141: if { $u != $s } { Check u != s first, avoids the more expensive 'nodes out/in' commands when it can. > 2155: #Malhotra, Kumar and Maheshwari Algorithm for finding blocking flow > 2156: # > 2157: # > 2158: #Algorithm for given network G with source s and sink t, finds a blocking > 2159: #flow, which can be used to obtain a maximum flow for that network G. > 2160: # > 2161: #For given node v, Let c(v) be the min{ a, b }, where a is the sum of all incoming > 2162: #throughputs and b is the sum of all outcoming throughputs from the node v. > 2163: # > 2164: #Some steps that algorithm takes: > 2165: #1. constructing the level graph from network G > 2166: #2. until there are edges in level graph: edges ? no edges ? > 2167: # 3. finding the node with the minimum c(v) > 2168: # 4. sending c(v) units of throughput by incoming arcs of v > 2169: # 5. sending c(v) units of throughput by outcoming arcs of v > 2170: # 6. 4 and 5 steps can cause exceed or deficiency of throughputs at nodes, so we exceed => excess > 2171: # send exceeds forward choosing arcs greedily and... > 2172: # 7. ...the same with deficiencies but we send those behind. behind => backward. > 2173: # 8. delete the v node from level graph > 2174: # 9. upgrade the c values for all nodes > 2175: # > 2176: #10. if no other edges left in level graph, return b  found blocking flow > 2177: # > 2178: proc ::struct::graph::op::BlockingFlowByMKM {G s t} { > 2179: > 2200: foreach node [dict keys $c] { > 2201: set cv [dict get $c $node] Can also be written as dict for $c {node cv} { per http://docs.activestate.com/activetcl/8.5/tcl/TclCmd/dict.htm#M12 > 2264: #7. > 2265: for { set i [ expr { [dict get $distances $minCv_node]  1} ] } { $i > 0 } { decr i } { Why not 'incr i 1' ? > 2279: #9. correctingg the in/out throughputs for each node after > 2280: #deleting one of the nodes in network > 2281: set c [countThroughputsAtNodes $LevelGraph $s $t] We might be able to avoid this if we can correct the pernode throughputs immediately, as part of the loops above. That is for the future however, as it would also make the code above more complex as well. > 2282: > 2283: #if node has no availiable outcoming or incoming throughput > 2284: #delete that node from the graph > 2285: foreach key [dict keys $c] { > 2286: if { [dict get $c $key] == 0 } { dict for $c {key val} { if { $val == 0 } { > 2293: set b [dict filter $b script {flow flowvalue} {expr {$flowvalue != 0}}] > 2294: #10. LevelGraph is not destroyed, memory leak > 2295: return $b > 2296: } > 2297: > 2325: > 2326: #Subprocedure for blocking flow finding by MKM algorithm > 2327: # > 2328: #It computes for graph G and each of his nodes the throughput value  > 2329: #for node v: from the sum of availiable throughputs from incoming arcs and > 2330: #the sum of availiable throughputs from outcoming arcs chooses lesser and sets > 2331: #as the throughput of the node. > 2332: # > 2333: #Throughputs of nodes are returned in the dictionary. > 2334: # > 2335: proc ::struct::graph::op::countThroughputsAtNodes {G s t} { > 2336: > 2337: foreach v [$G nodes] { > 2338: > 2339: set outcoming [$G arcs out $v] > 2340: set incoming [$G arcs in $v] > 2341: > 2342: set outsum 0 > 2343: set insum 0 > 2344: > 2345: foreach o $outcoming i $incoming { > 2346: > 2347: if { !([llength $o] == 0) } { [llength $o] > 0 > 2348: set outsum [ expr { $outsum + [$G arc get $o throughput] } ] > 2349: } > 2350: > 2351: if { !([llength $i] == 0) } { > 2352: set insum [ expr { $insum + [$G arc get $i throughput] } ] > 2353: } > 2354: > 2355: set value [Min $outsum $insum] > 2356: } > 2357: > 2358: if { ($v ne $t) && ($v ne $s) } { This condition means that the whole computation above was wasted. Better to move this to line 2338 and invert, i.e. let the loop 'continue' for v either s or t. > 2359: dict set c $v $value > 2360: } > 2361: } > 2362: > 2363: return $c > 2364: } > 2365: > 2417: > 2418: #Subprocedure for blockingflow finding algorithm by MKM > 2419: # > 2420: #It checks for graph G if node given at input has a exceed > 2421: #or deficiency of throughput. > 2422: # > 2423: #For exceed the positive value of exceed is returned, for deficiency > 2424: #procedure returns negative value. If the incoming throughput > 2425: #is the same as outcoming, procedure returns 0. > 2426: # > 2427: proc ::struct::graph::op::findExcess {G node b} { > 2428: > 2429: set incoming 0 > 2430: set outcoming 0 > 2431: > 2432: foreach key [dict keys $b] { lassign $key u v ? > 2433: if { [lindex $key 0] eq $node } { > 2434: set outcoming [ expr { $outcoming + [dict get $b $key] } ] > 2435: } > 2436: if { [lindex $key 1] eq $node } { > 2437: set incoming [ expr { $incoming + [dict get $b $key] } ] > 2438: } > 2439: } > 2440: > 2441: if { $incoming == $outcoming } { > 2442: return 0 > 2443: } > 2444: > 2445: if { $incoming > $outcoming } { > 2446: return [ expr { $incoming  $outcoming } ] > 2447: } else { > 2448: return [ expr { (1) * ($outcoming  $incoming) } ] Or return [ expr { $outcoming  $incoming } ] > 2449: } > 2450: > 2451: } > 3458: > 3459: proc ::struct::graph::op::decr { int { n 1 } } { Might be easier to write incr i 1 at the call site. > 3460: if { [ catch { > 3461: uplevel incr $int $n > 3462: } err ] } { > 3463: return code error "decr: $err" > 3464: } > 3465: return [ uplevel set $int ] > 3466: } Andreas. 
From: Harald Oehlmann <Harald.Oehlmann@Elmicron.de>  20090724 19:07:45

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 highlevel 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. 
From: Jeff Hobbs <jeffh@ac...>  20090724 15:29:55

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] \ > 
From: Koen Danckaert <koen@re...>  20090724 13:43:45

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] \ 
From: Jeff Hobbs <jeffh@ac...>  20090723 18:09:30

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 subnodes >> (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/komododocguibuilder.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 
From: Koen Danckaert <koen@re...>  20090723 13:28:12

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 > ASCIIArts: > + < Tree Widget border >   < this line is the issue >  +Node 1 >   >  +Node 2 > > Current behaviour: >  this line is not present > > Login entry to current behaviour: > > 20040421 Jeff Hobbs <jeffh@...> > * 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 subnodes > (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 
From: Harald Oehlmann <Harald.Oehlmann@Elmicron.de>  20090723 08:33:03

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 ASCIIArts: + < Tree Widget border   < this line is the issue  +Node 1    +Node 2 Current behaviour:  this line is not present Login entry to current behaviour: 20040421 Jeff Hobbs <jeffh@...> * 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 subnodes (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 
From: Andreas Kupries <akupries@sh...>  20090721 05:27:48

> 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 <akupries@...> <http://www.purl.org/NET/akupries/>; Developer @ <http://www.activestate.com/>;  
From: Andreas Kupries <andreask@ac...>  20090720 18:24:01

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 readindex 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: #"d1". > 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 (19411953, 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 ifblock handling the even diameter., and the fact that this big ifblock 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 ifblock, 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. 
From: Andreas Kupries <andreask@ac...>  20090720 17:00:18

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 "d1" >  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 "musthave" 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. 
From: Harald Oehlmann <Harald.Oehlmann@Elmicron.de>  20090720 13:11:16

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 tradeoffs 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 
From: Michał Antoniewski <antoniewski.m@gm...>  20090718 22:32:48

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 "d1"  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 "musthave" 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 
From: Andreas Kupries <andreask@ac...>  20090715 16:38:20

graphmanipulations@... wrote: > > New versions of FordFulkerson's and BusackerGowen'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 graphopg${impl}s${setimpl}st${stkimpl}q${queimpl}BusackerGowen3.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 BusackerGowen (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 0weighted > 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 end1] 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 subexpressions 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 subexpressions / 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 
From: Andreas Kupries <andreask@ac...>  20090713 20:27:58

> I will review revision 35 sometime today. The testsuite for BusackerGowen 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 nonzero 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 end1] 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 nonnegative 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 end1] 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 end1] 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. 
From: Andreas Kupries <andreask@ac...>  20090713 20:17:16

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 listlike 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. 
From: Michał Antoniewski <antoniewski.m@gm...>  20090713 19:49:37

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 
From: Andreas Kupries <andreask@ac...>  20090713 17:47:04

Michał Antoniewski wrote: > ( BellmanFord'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 maxflow algorithms > rather focuses on doing something other than augmenting paths, e.g. > blocking flows (Dinic) or push&relabel (GoldbergTarjan). > 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'sBellman'sd'EsopoPapego 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 cutdown 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 BusackerGowen (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. 
From: Andreas Kupries <andreask@ac...>  20090713 17:47:02

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. 
From: Andreas Kupries <andreask@ac...>  20090713 17:47:01

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: BusackerGowen ( already implemented,just have to do some more tests ) Looking forward to that. Andreas 
From: Andreas Kupries <andreask@ac...>  20090713 17:46:56

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. 
From: Andreas Kupries <andreask@ac...>  20090713 17:46:53

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 premade 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 standalone application or > also applet? I see it as standalone app which we can put into either the examples/struct/ or the apps/ subtree of Tcllib. I will review revision 35 sometime today. Andreas. 
From: Michał Antoniewski <antoniewski.m@gm...>  20090713 17:13:50

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 premade 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 standalone application or also applet? Best Regards, Michał Antoniewski 
From: Michał Antoniewski <antoniewski.m@gm...>  20090713 16:56:38

2009/7/12 Lars Hellström <Lars.Hellstrom@...> > 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 breadthfirstsearch 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 EdmondsKarp 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. > > > ( BellmanFord'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 maxflow algorithms rather focuses on > doing something other than augmenting paths, e.g. blocking flows (Dinic) or > push&relabel (GoldbergTarjan). > 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'sBellman'sd'EsopoPapego 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 FordFulkerson into Edmond's Karp ( >> actually, it's already done ). >> >>  min cost flow problems  actually, we've got one algorithm in timeline >> for >> that: BusackerGowen ( 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 FordFulkerson (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. BusackerGowen and FordFulkerson 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 MalhotraKumarMaheshwari >> 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 MalhotraKumarMaheshwari) are now in timeline, but >> > > Both Dinic and MalhotraKumarMaheshwari appear to be maxflow > algorithms, AFAICT. > > For mincostflow, 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 mincostflow problem. > Mincostflow with capacities can be reduced to mincostflow 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 (BusackerGowen) Algorithm, CS = Capacity Scaling > Algorithm, and MMCC = Minimum Mean CycleCancelling 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 BusackerGowen (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 
From: Michał Antoniewski <antoniewski.m@gm...>  20090713 14:25:50

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 