# Policy-Compliant Maximum Network Flows
## 4 Policy-Compliant Paths and Algorithms
### Brute Force Approach  
A basic, inefficient way of solving the policy-compliant maximum flow problem is by way of brute force. In its essence, we first calculate all policy-compliant paths from source to sink, and afterward try out all different orders in which these paths can be filled up. The maximum flow will be reached by at least one of these orderings. As such, this approach will result in the exact solution, however, at the expense of large computational complexity and memory requirements. Indeed, as we employ our search via e.g., a depth-first-search, it might be the case that we need to visit a certain vertex \(u\in E\) more than once, because the internal state of the FSA might be different. Effectively, we need to build a new graph \(G_{BF}\) that contains tuples of vertices and states. After appropriately defining the edges between these tuples, a typical depth-first-search might be used to enumerate successively all policy-compliant paths. More formally, we perform the following steps.  
1. Define \(G_{BF}\) as the graph with \(V_{BF}=\{(u,q):u\in V\wedge q\in Q\}\) and \(E_{BF}=\{((u_{1},q_{1}),(u_{2},q_{2})):u_{1},u_{2}\in V\wedge q_{1},q_{2}\in Q \wedge(u_{1},u_{2})\in E\wedge\delta(q_{1},l((u_{1},u_{2})))=q_{2}\}\). That is, the vertices of \(G_{BF}\) are all possible tuples of vertices in \(V\) and states in \(Q\), and the vertices in \(G_{BF}\) are connected if and only if the corresponding vertices \(u_{1}\) and \(u_{2}\) in \(V\) were connected by an edge \(e\in E\), such that the FSA changes its state from \(q_{1}\) to \(q_{2}\) when reading the symbol \(l(e)\) associated with the original edge. Thus, we are defining \(G_{BF}\) as the Cartesian product of \(V\) and \(Q\).
2. Start a depth-first-search from \((s,q_{0})\) to all \((t,q)\) such that \(q\in F\). This will produce all paths of the form \(p=[e_{1},\ldots,e_{n}]\) with \(\forall e_{i}:e_{i}\in E_{BF}\) while \(\exists v\in V_{BF}:e_{1}=((s,q_{0}),v)\) and \(\exists v\in V_{BF}:\exists q\in F:e_{n}=(v,(t,q))\). Every such path corresponds to a policy-compliant path in \(G\), and every policy-compliant path in \(G\) will be found this way. Collect all paths found by this depth-first-search in the set \(BF=\{p_{1},\ldots,p_{n}\}\).
3. Generate all permutations of the elements in this set \(BF\); this results in \(n!\) sequences of the \(n\) paths. Each of these sequences will correspond to an ordering in which we fill the paths to their residual capacity at that time. Note that it is not necessary to generate all permutations at once. It is sufficient to do this iteratively via e.g., the Steinhaus-Johnson-Trotter algorithm.
4. Each such sequence \(s=[p_{1}^{s},\ldots,p_{n}^{s}]\) contains exactly the same items as \(BF\) itself. We define an empty flow \(f_{s}(u,v)=0\) and iterate through this sequence: for each path \(p_{i}^{s}=[e_{i,1}^{s},\ldots,e_{i,m}^{s}]\) we calculate \(min_{i}^{s}=min\{c(e_{i,j}^{s})-f_{s}(e_{i,j}^{s}):1\leq j\leq m\}\) which represents the largest amount of flow that can be accommodated along the path \(p_{i}^{s}\) at that moment. The flow \(f_{s}\) can now be increased to a new flow \(f_{s}^{\prime}\) as follows: \[f_{s}^{\prime}(u,v)=\begin{cases}f_{s}(u,v)+min_{i}^{s}&\text{if }(u,v)\in p_{i}^{s},\\ f_{s}(u,v)&\text{otherwise}.\end{cases}\] (15)
5. After all paths \(p_{i}^{s}\) are processed, the final flow \(f_{s}\) will be a lower bound for the policy-compliant maximum flow for the network \(G\). Thus, \(max\{|f_{s}|\}\) will be the value of the policy-compliant maximum flow.  
It is clear that this approach results in the exact value of the solution to the policy-compliant maximum flow problem. However, except for small networks and automata it will quickly take too much space and time to execute.