  `Let's take Robert's example:   c0 c1 c2 e0 x     x e1    x  x e2 x  xThe nodes in the graph:- S (starting point)- T (the ending point)- e0, e1, e2 (the events)- c0, c1, c2 (the counters)There is an edge from the source to all the events.There is an edge from all the counters to the sync.There is an edge between an event and a counter, ifit can count the event.The capacity of any edge is 1.The max flow algorithm returns the maximum number ofevents that can be measured together. If max_flow ==number of events, we maxed out.To find the assignment, we simply need to inspect theoutgoing edges from events and use the only edge whichhas a flow == 1.If we list all the edges for the example above, we have:S -> e0S -> e1S -> e2e0 -> c0e0 -> c2e1 -> c1e1 -> c2e2 -> c0e2 -> c1c0 -> Tc1 -> Tc2 -> Tthen we do max_flow(S, T), Here we find 3.Given the capacity is either 0 or 1, I think we could usebitmasks to describe the edges.On Mon, Nov 14, 2011 at 3:12 PM, Peter Zijlstra <peterz@infradead.org> wrote:> On Mon, 2011-11-14 at 13:55 +0100, Stephane Eranian wrote:>> I have been talking with co-workers experts in operational research>> about our problem. They all pointed to me to the max flow algorithm from>> Ford-Fulkerson (search for it on Wikipedia). I think it solves the complexity>> and recursion problems. My understanding is that the complexity is also>> more under control.>> How would you apply this algorithm to the problem at hand? I'm probably> missing the obvious thing here, but if we want the flow to be the number> of assigned counter then we end up with nodes being the various> permutations of assignments or so, which isn't helpful since that'd be> n! nodes.>>>`   