# Policy-Compliant Maximum Network Flows
## 3 Graph Model and Basic Algorithms
### Realization of a Flow  
Apart from calculating the value of the maximum flow in a flow network, we are also interested in the actual paths followed by the flow; this set of paths is called the \"realization\" of the flow. Augmenting paths are a device to calculate the maximum flow, however, augmenting paths are not real paths in the flow network as they might comprise edges from \(E_{f}\) that are not in \(E\). Define a path from \(s\) to \(t\) in \(G\) in exactly the same way as an augmenting path, except that edges in the path should be contained in \(E\) instead of \(E_{f}\). Thus, in addition to (5)-(7), we replace (4) with \[\forall e_{i}:e_{i}\in E.\] (10) Given a flow network \(G\) and accompanying maximum flow \(f\), it is possible to determine a set \[S=\{(p_{1},c_{1}),(p_{2},c_{2}),\ldots,(p_{n},c_{n})\}\] (11) that realizes that flow. Intuitively, we start with no flow in the network at all. Then, for each of the paths \(p_{i}\) we fill all edges of that path with an additional amount \(c_{i}\). After all paths are processed, we obtain the maximum flow \(f\). Construction of this set \(S\) can be done simultaneously with the calculation of the maximum flow. During execution of the maximum flow algorithm, we perform the following steps every time a new augmenting path \(p\) with additional flow amount \(c\) has been found, starting with an empty set \(S=\{\}\). 1. We split the augmenting path in forward sections and backward sections. That is, if \(p=[e_{1},e_{2},\ldots,e_{n}]\), we cut it down and obtain \([[e_{1},\ldots,e_{i}],[e_{j},\ldots,e_{k}],\ldots,[e_{l},\ldots,e_{n}]]\) such that every section \([e_{x},\ldots,e_{y}]\) contains only edges from \(E\) or only edges from \(E_{f}-E\). Without losing generality, we only discuss the case where the augmenting path \(p\) consists of two forward sections with one backward section in between, thus \(p=[[e_{1},\ldots,e_{i}],[e_{j},\ldots,e_{k}],[e_{l},\ldots,e_{n}]]\) such that \(\{e_{1},\ldots,e_{i},e_{l},\ldots,e_{n}\}\subseteq E\) and \(\{e_{j},\ldots,e_{k}\}\subseteq E_{f}-E\). 2. For this backward section \([e_{j},\ldots,e_{k}]\) there must exist a path \(p^{\prime}\) carrying some flow in the opposite direction, which the augmenting path \(p\) is canceling out. Indeed, as \([e_{j},\ldots,e_{k}]\) are edges in \(E_{f}\), they have been introduced in the residual graph \(G_{f}\) thanks to the fact that the corresponding forward edges in \(E\) have already been used in a previously found path. Thus, if \(e_{j}=(u_{j},v_{j})\) and \(e_{k}=(u_{k},v_{k})\), then \(S\) will already contain an item \((p^{\prime},c^{\prime})\) where the path \(p^{\prime}=[\ldots,(v_{x},v_{k}),(v_{k},u_{k}),\ldots,(v_{j},u_{j}),(u_{j},u_ {y}),\ldots]\), as the augmenting path \(p\) is crossing that section in the reverse direction, see Figure 2.
3. Remove this item \((p^{\prime},c^{\prime})\) from \(S\), and add two new paths \([e_{1},\ldots,e_{i},(u_{j},u_{y}),\ldots]\) and \([\ldots,(v_{x},v_{k}),e_{l},\ldots,e_{n}]\), each with amount \(c\). As such, the augmenting path has been cut and glued together with a previously found path, resulting in two new paths. 4. Now, it might be that \(c<c^{\prime}\). In that case, path \(p^{\prime}\) is not to be removed from \(S\) entirely, as it still carries some flow that was not canceled by \(p\). Add \((p^{\prime},c^{\prime}-c)\) to \(S\). Thus, each iteration of the maximum flow algorithm results in an augmenting path that is possibly cut in sections to remove reversed edges from the residual graph. Forward sections are glued together with sections from previously found paths. When no augmenting paths can be found, the set \(S\) will contain paths and associated flow amounts, that together sum up to the maximum flow. That is, if upon termination \(S=\{(p_{1},c_{1}),\ldots,(p_{n},c_{n})\}\), we have  
\[f(u,v)=\sum_{\{(p_{i},c_{i}):(u,v)\in p_{i}\}}c_{i} \tag{12}\]  
Figure 2: Three sections: forward, backward and forward.