Given a flow network with a source $$$s$$$ and sink $$$t$$$ (each edge has a capacity $$$c_i$$$ and flow $$$f_i$$$). You need to find decomposition into $$$s-t$$$ paths, where each path has a flow value $$$f_p$$$, such that it results in this flow network. Also, not all paths are correct, and we only need consider "correct" paths (we can understand is path correct or not while traversing the network). It is guarantee what this decomposition exists.
First of all, how I found a flow network? I used linear programming to solve this task. I have some inequalities for flows and for paths, and now I want to restore the answer as a decompisition of $$$s-t$$$ paths.
Is there exists a polynomial algorithm to solve this? The number of paths doesn't matter.
https://github.com/the-tourist/algo/blob/master/flows/flow_decomposition.cpp
Why do you need capacities if you know flows?
You find the flow network with any standard maxflow algorithm. If the flow is $$$F$$$, there are $$$F$$$ paths each with flow value $$$1$$$. Any path is found by simply bruteforce extending, $$$O((N+M)F)$$$ total. It might be impossible to get $$$O(N+M)$$$ paths in the general case.
UPD: I'm an idiot, this sample is incorrect.
In general case, why can't there be situation when we choose some bad path and block some paths which should be in our answer?
Oh yea, that means we have $$$O(M)$$$ paths. I just said might because $$$O(F)$$$ isn't considered polynomial and didn't think about it further. That means the solution you're looking for is very simple: always find an arbitrary $$$s-t$$$ path along edges that have flow \gt 0$, take the minimum of flows along its edges, subtract this flow from this path and repeat. (In fact, that's how I implement simple maxflow, without regard for time complexity.)
I think we misunderstood each other a litlte bit, but it doesn't matter because now I got it.
This procedure works because if we subtrstract minimum flow from some path we still get correct flow in this network. If we have a situation in which we can't find a non-zero path, but the total flow is not zero, then it means that inital flow was incorrect.
Yes.
A proof of this fact that I really like (I have not found a real "application" of this fact, other than it being a nice mathematical construction):
Say you have a valid flow. Construct from it a directed multigraph, where edges will have no weight. For each edge $$$a \rightarrow b$$$ with flow $$$f$$$ originally, you now put $$$f$$$ edges from $$$a$$$ to $$$b$$$. The total in-flow at each node now becomes the in-degree of the node. The same for out-flow and out-degree. That means that the original flow is valid (satisfies flow conservation) if and only if the multigraph has indegree = outdegree for every node (except s and t).
If the total flow was $$$f$$$, then $$$s$$$ will have $$$+f$$$ net degree, and $$$t$$$ will have $$$-f$$$ net degree. So by adding exactly $$$f$$$ "fake" edges from $$$t$$$ to $$$s$$$, we will get the net degree to be $$$0$$$ at every vertex. But that is the condition for directed euler cycle. So, the multigraph (actually the connected component of s and t in the underlying graph) has an euler cycle. But if you pick that cycle and remove the $$$f$$$ fake edges from it, the remaining edges naturally form $$$f$$$ edge-disjoint paths form $$$s$$$ to $$$t$$$, completing the construction.