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}
(1) 
_{Jun}

_{Jul}

_{Aug}
(1) 
_{Sep}
(3) 
_{Oct}
(9) 
_{Nov}
(4) 
_{Dec}
(1) 
2015 
_{Jan}

_{Feb}

_{Mar}
(2) 
_{Apr}
(3) 
_{May}
(17) 
_{Jun}
(4) 
_{Jul}
(2) 
_{Aug}
(2) 
_{Sep}

_{Oct}
(1) 
_{Nov}
(1) 
_{Dec}
(1) 
2016 
_{Jan}
(9) 
_{Feb}
(4) 
_{Mar}

_{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: Michał Antoniewski <antoniewski.m@gm...>  20090710 21:54:26

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 ( 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 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. 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 )  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 regarding situation with doubling algorithms that solve the same problems, I proposed something other ( Set Cover, SSS ). Another option, if you don't like to have another maxflow algorithm, can be just doing blocking flow algorithm ( on the other hand, doing the max flow when we've got blocking flows won't take long...). Or doing all of flow problems, and maybe replacing something else with Set Cover and SSS. So anyway there can be a lot of combinations:) Tomorrow, I'm going to send the code containing all corrections mentioned in previous mails , Busacker Gowen Implementaion , extension to Edmond's Karp and also some more test cases. Best Regards, Michal Antoniewski 
From: Andreas Kupries <andreask@ac...>  20090710 15:53:20

Lars Hellström wrote: > Andreas Kupries skrev: >> Micha? Antoniewski wrote: >>> We are given graph (weighted, directed) G, and nodes s and t, which are >>> source and sink for that graph. >> Give the suggestive naming of these two nodes, do they have special >> requirements / constraints ? >> >> Like, for example: >> "source must not have incoming arcs". >> "sink must not have outgoing arcs". >> ? > > No, the source is just where the flow comes from, and the sink is where > it must go. Ok. Thanks for the clarification. I guess I was misguided by the examples I have seen, or remember to have seen, which all had source only outgoing and sink only incoming. >> Regarding the weights the wikipedia reference tells us that the >> algorithm may not converge for irrational weights ... Oh, ok, is not a >> problem for an implementation on a computer. Our 'float/double' values >> are always rational, due to finite precision. > > Yes, but note that this is one of the cases where complexity estimates > must take into account the size of the numbers given as input... But on > second though, this probably doesn't apply here, because what has been > implemented may well be the EdmondsKarp algorithm rather than the > FordFulkerson algorithm! (See below.) Heh. > >> > 1311: #s  the node that is a source for graph G >> > 1312: #t  the node that is a sink for graph G >> > 1313: # >> > 1314: #Output: >> > 1315: #Procedure returns the dictionary contaning throughputs for all edges. For >> > 1316: #each key ( the edge between nodes u and v in the for of list u v ) >> there is >> > 1317: #a value that is a throughput for that key. Edges where throughput values >> > 1318: #are equal to 0 are not returned ( it is like there was no link in the >> flow network >> > 1319: #between nodes connected by such edge). >> > 1320: # >> > 1321: #Reference: http://en.wikipedia.org/wiki/FordFulkerson_algorithm >> > 1322: >> > 1323: proc ::struct::graph::op::FordFulkerson {G s t} { >> >> Missing checks: Are s and t nodes of G ? >> Also, should the source s have incoming arcs ? >> Further, should sink t have outgoing arcs ? > > There is no reason to limit the arcs around source or sink. Right, per your clarification. This leaves only Are s and t nodes of G ? as check. >> > 1345: >> > 1346: #setting the path from source to sink >> > 1347: set path [lreverse [dict get [struct::graph::op::dijkstra $residualG >> $s arcmode directed] $t]] > > 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 ? > and the simple choice of always using a shortest path > is all that is needed to turn FordFulkerson into EdmondsKarp! It > also has the effect of making the algorithm polynomial, regardless of > the capacity sizes. Interesting. > There's really no reason for tcllib to house a FordFulkerson > implementation that is not an EdmondsKarp; were it not for historical > factors (e.g. that Ford and Fulkerson also proved the maxflowmincut > theorem), the former algorithm would just be regarded as a broken form > of the latter, which terminates more by luck than by merit. Heh. > > Lars Hellström > > PS: On the matter of picking a new problem to implement an algorithm > for, I would like to suggest Mincostflow > (http://en.wikipedia.org/wiki/Minimum_cost_flow_problem). Will take a look. Andreas. 