\Start{Flows}{17 November}{Kopeliovich Sergey}

\Section{Flows}

\Subsection{Definitions}

Let we have oriented graph $G$ of $n$ vertices and $m$ edges.
Between each two vertices $v$ and $u$ of $G$ there is edge with capacity
$c_{v,u} \ge 0$. If we want to say "there is no edge", let $c_{v,u} = 0$.

\begin{Def}{Flow from $s$ to $t$} --
  function $f_{v,u} \in \R$, which satisfies three propetries

  \begin{MyList}[0pt]
    \item $\forall v, u \quad f_{v,u} \le c_{v,u}$ (flow is not greater than capacity)
    \item $\forall v, u \quad f_{v,u} = {-}f_{u,v}$ (antisymmetry)
    \item $\forall v \not= s, t \quad \sum_u f_{v,u} = 0$ (conservation of flow)
  \end{MyList}
\end{Def}

The $s$ is called {\it source}, and the $t$ is called {\it sink}.

Let denote $f_e$ and $c_e$ -- flow and capacity for edge $e$.

\begin{Def}{Cut between $s$ and $t$} --
  partition of vertices of the graph $V \colon V = S \sqcup T, s \in S, t \in T$.\\
  ($S \cap T = \varnothing$, source is in $S$, sink is in $T$)
\end{Def}

Let denote cut as $(S, T)$.

\begin{Def}{Value of flow $|f| = \sum_v f_{s,v}$ (sum of flow from source $s$).}\end{Def}

Value of flow may be negative. It does not contradict the definition.

\begin{Def}{Value of cut $C(S, T) = \sum\limits_{v \in S, u \in T} c_{v, u}$} (sum of capacities of edges throw the cut).\end{Def}

\begin{Def}{Denote $F(A, B) = \sum\limits_{v \in A, u \in B} f_{v, u}$}\end{Def}

This is just a notation. $A$ and $B$ may intersect or even coincide.

\begin{Def}{Max flow} -- $f \colon |f| = \max$\end{Def}

\begin{Def}{Min cut} -- $(S,T) \colon C(S, T) = \min$\end{Def}

\begin{Def}{Edge $e$ is saturated $\EQ f_e = c_e$}\end{Def}

\begin{Def}{Residual network $G_f$ -- graph of edges $c_e - f_e > 0$}.\\
Capacities of edges in residual network are $c_e - f_e$.
\end{Def}

\begin{Def}{Augumenting path} -- path from $s$ to $t$ throw edges $e \colon f_{e} < c_{e}$.\\
In other words ``path in residual network''\end{Def}

\begin{Def}{Circulation -- flow of zero value.}\end{Def}

For example, any cycle is a circulation.

\pagebreak

\vspace*{-2em}
\Subsection{Theorem and algorithm of Ford-Fulkerson}

\begin{Lm}{Value of flow equals to value of the flow, flowing throw the cut:}\\
$\forall \text{ cut } (S, T), \forall \text{ flow } f \quad |f| = F(S, T)$
\begin{proof}{\small $|f| = F(\{s\}, V) = F(S, V) = F(S, S) + F(S, T) = 0 + F(S, T) = F(S, T)$}\end{proof}
\end{Lm}

\begin{Lm}{Any flow is no more than any cut:}
\label{Lm:FlowCut}
$\forall \text{ cut } (S, T), \text{ flow } f \quad |f| \le C(S, T)$
\begin{proof}{\small $|f| = F(S, T) \le C(S, T)$}\end{proof}
\end{Lm}

\begin{Lm}{\it About augumenting path.} If there is an augumenting path, flow is not max flow.\end{Lm}
\begin{proof}
Let there is an augumenting path. Let increase flow along the path, and decrease flow in opposite direction.
All 3 propetries are satisfied, value of the flow is increased.
\end{proof}

\THEE{Algorithm of Ford-Fulkerson.} \\
The algorithm searches for max flow in graph with integer capacities.

\begin{MyTabbing}
$f \leftarrow 0$ \\
\t{while} augumenting path exists: \\
\> find it using \t{dfs}, which uses only not saturated edges \\
\> let path is: $s = v_1, v_2, \dots, v_k = t$\\
\> $x = \min_{i=1..k{-}1}\bigl[c_{v_{i{+}1},v_i} - f_{v_{i{+}1},v_i}\bigr]$ ($x > 0$; $x = $ how much flow we may push along the path)\\
\> increase the flow along the path by $x$\\
\t{return} $f$ 
\end{MyTabbing}

If $c_{v,u}$ are integer then $x \ge 1$, so the algorithm somewhen finishes.

Maximality of resulting flow follows from the theorem:

\begin{Thm}{\bf Ford-Fulkerson's.} \quad $\max |f| = \min C(S, T)$.\end{Thm}
\begin{proof}
  Let show cut, whose value is same as value of the flow.
  It follows (use Lm \autoref{Lm:FlowCut}) that flow is max flow and cut is min cut.
  Let take flow obtained by Ford-Fulkerson's algorithm. Let launch \t{dfs} from $s$ using only not saturated edges ($f_{u,v} < c_{u,v}$).
  Such \t{dfs} finishes in $\O(n + m)$. It does not reach $t$, because there is no augumenting path.
  Vertices of the graph are splitted into two sets -- marked by \t{dfs} ($S$), and not marked ($T$).
  All edges from $a \in S$ to $b \in T$ satisfy $f_{a,b} = c_{a,b}$,
  in other case \t{dfs} would go throw the edge and visit $b$.
  So $F(S, T) = C(S, T) \SO |f| = C(S, T)$.
\end{proof}

\begin{Rem} Algorithm to find min cut.\\ 
If we already have max flow then we may build min cut in $\O(n + m)$ time.\end{Rem}

Working time of Ford-Fulkerson's algorithm is $\O(|f| \cdot m)$, but in practice it is smaller.
Any way there are tests such that even Ford-Fulkerson with randomizatin in \t{dfs} (iterate edges in random order)
works in exponential of $n$ time.

\vspace*{0.5em}

Algorithm of Ford-Fulkerson is applicable for integer capacities.

For ratio capacities it can work infinitely long.

\pagebreak

\vspace*{-2.5em}
\Subsection{Problems}

\THEE{Problem about maximum  matching in bipartite graph} \\
It may be solved in $\O(nm)$, using max flow. 
Add source to the first part of vertices, add sink to the second part, find max flow. $|f| \le n$.
Edges of bipartite graph (edges between parts), wich are saturated by the max flow are edges of the maximum matching.

\THEE{Problem about matrix recovery} \\
You are given sums in rows and columns of square matrix. All numbers in the matrix are from $0$ to $100$.
The problem: recovery the matrix. 
The solution: let consider bipartite graph with source and sink. The first part -- rows, the second part -- columns. 
Let add edges from source to rows witch capacity "sum in the row". Also let add same edges from columns to sink.
Cell of the matrix -- edges between row and column with capacity 100.
Let find max flow in this graph.
If all edges from source and all edges to sink are saturated then matrix exists and flow between rows and columns describes the matrix.

\THEE{Problem about people and flights} \\
There is an airport. Some flights are going the same direction, each can transfer $k_i$ and will flight out at $t_i$. 
There are some people, each human has range of acceptable times $[l_i..r_i]$, when he wants to flight out.
The problem is to distribute humans to flights.
Let build graph: from source edges to humans with capacity 1, from humans edges to flights, 
from flights to sink edges with capacity $k_i$.

\Subsection{Implementation}

\begin{example}\label{exm:flowcode}
To make \t{dfs} work in $\O(n + m)$ time,
let store lists of adjacent edges for each vertex.
To maintain antisymmetry of flow, each edge has paired backward edge.
\end{example}
\begin{code}
struct Edge {
  int from, to; 
  int next; // number of the next edge from vertex "from"
  int f; // flow
  int c; // capacity
};
int n, m;
vector<Edge> edges;
vector<int> head; // number of the first edge for each vertex

void add_edge( int a, int b, int capacity ) {
  edges.push_back(Edge {a, b, head[a], 0, capacity});
  head[a] = edges.size() - 1;
}
void read() {
  cin >> n >> m; // number of vertices and edges
  edges.reserve(2 * m); // each edge has paired backward edge
  head = vector<int>(n, -1); // -1 means empty list
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c, a--, b--; // in input vertices usually are numbered 1..n
    add_edge(a, b, c); // forward edge
    add_edge(b, a, 0); // backward edge
  }
}
\end{code}

Now that edge number \t{i} has paired backward edge number \t{i\XOR 1}.
To iterate all edges from vertex \t{i} you should start from edge \t{head[i]}:
\lstinline`for (int e = head[i]; e != -1; e = edges[e].next)`.
In Ford-Fulkerson algorithm we should find path and increase flow throw the path.
We will increase the flow while backtracking.

\begin{code}
int cc;
vector<int> u; // Iff u[i] = cc then vertice is marked

int dfs( int v, int flow ) {
  if (v == t)
    return flow;
  u[v] = cc; // do not visit any vertice twice
  for (int x, i = head[v]; i != -1; i = edges[e].next) {
    Edge &e = edges[i];
    if (e.f < e.c && u[e.to] != cc && (x = dfs(e.to, min(flow, e.c-e.f))) > 0) {
      e.f += x, edges[i ^ 1].f -= x; // incerease forward edge, decrease backward
      return x;
    }
  }
  return 0;
}
int maxFlow() {
  read();
  cc = 1, u = vector<int>(n, 0);
  int f = 0, add;
  while ((add = dfs(s, INT_MAX)) > 0)
    f += add, cc++; // command "cc++" unmarks all vertices
  return f;
}
\end{code}

\vspace*{0.3em}
Optimizations:
\begin{MyList}[0pt]
  \item You may store \t{c-f} instead of storing both \t{f} and \t{c}.
  \item Almost always you should not store \t{from}.
\end{MyList}
\vspace*{-0.8em}

\THEE{Remark:} without backward edges algorithm fails:

\begin{center}\includegraphics[width=5cm]{pics/1.png}\end{center}

If the first \t{dfs} finds the red path, the second \t{dfs} can not find a path without backward edges.
Using backward edges it can find the blue path.

\begin{center}\includegraphics[width=5cm]{pics/2.png}\end{center}

\pagebreak

\vspace*{-2em}
\Subsection{Flow decomposition}

\THEE{Decompose flow into paths}.\\
Path from $s$ to $t$, through which flows $x$ items is
a flow of value $x$.
Ford-Fulkerson algorithm works as
Алгоритм Форда-Фалкерсона works as "let add small paths-flows and obtain big flow".
Now that we should solve opposite problem:

\begin{Def}{Decomposition: you have to describe flow as sum of some pathes and a circulation.
Additional restricton: in the decomposition there are no opposite edges. }
\end{Def}

Red and blue paths on the picture above are not correct decomposition,
because one edge is used in both directions.

Algorithm to build decomposition: cleave another path by \t{dfs} using edges with non zero flow.

\begin{code}
int getPath( int v, int flow ) {
  if (v == t)
    return flow;
  u[v] = cc; 
  for (int x, i = head[v]; i != -1; i = edges[e].next) {
    Edge &e = edges[i];
    if (e.f > 0 && u[e.to] != cc && (x = getPath(e.to, min(flow, e.f))) > 0) {
      e.f -= x, edges[i ^ 1].f += x; // cleave the path
      return x;
    }
  }
  return 0;
}
\end{code}

Working time is $\O(m^2)$, because \t{getPath} works in $\O(m)$ time

and after each launch of \t{getPath} number of edges with zero flow incereases. 

{\it Exercise:} improve working time up to $\O(nm)$.

\Subsection{Problem about $k$ paths}

Now that using decomposition of flow into paths we can solve following problems:
\begin{MyList}[0pt]
  \item Find $k$ disjoint by edges paths from $s$ to $t$ in oriented graph.
  \item Find $k$ disjoint by edges paths from $s$ to $t$ in not oriented graph.
  \item Find $k$ disjoint by vertices paths from $s$ to $t$ in oriented graph.
  \item Find $k$ disjoint by vertices paths from $s$ to $t$ in not oriented graph.
\end{MyList}
We can solve all these problems in $\O(km)$: 
launch Ford-Fulkerson's algorithm, then decompose the flow.
In not oriented graph a not oriented edge can be described as two oriented edges.
To make pathes disjoint by vertices, let make a copy for each vertex:

\vspace*{-1em}
\newlength{\mywidth}
\setlength{\mywidth}{100pt}
\begin{center}
\begin{tabular}{p{\mywidth}p{\mywidth}p{\mywidth}}
    \vspace{-0.3em}
    \includegraphics[width=\mywidth]{pics/5.png}
    \vspace{-1em}
  &
  \begin{center}
    {\Huge $\longrightarrow$}
  \end{center}
  &
    \vspace{-0.3em}
    \includegraphics[width=\mywidth]{pics/6.png}

    \vspace{-1em}
  \\
\end{tabular} 
\end{center}
\vspace*{-1em}

Disjoint by edges path in new graph are disjoint by vertices path in initial graph.

\pagebreak

\vspace*{-2em}
\Subsection{Several sources and sinks}

We have to find several disjoint paths. Each path should begin in a vertex from set $A$.
Each path should end in a vertex from set $B$. In other words we have to find flow in 
graph with several sources and sinks.
Let add global source -- vertex $s$ with edges from $s$ to all $A$. 
Add global sink -- vertex $t$ with edges from $B$ to $t$.
Find flow from $s$ to $t$.

\Subsection{Algorithms for max flow problem}

\begin{example}\label{exm:edmonds}
\THEE{Edmonds–Karp algorithm} -- let use \t{bfs} instead of \t{dfs}.
It turns out, number of augumenting paths do not exceed $\mfrac{nm}{2}$, so algorithm works in time $\O(nm^2)$ and also works
for graphs with ratio capacities.
\end{example}

\vspace*{0.5em}
We won't prove asymptotic of working time, you may read it \href{http://www.cs.cornell.edu/courses/cs4820/2011sp/handouts/edmondskarp.pdf}{here}.

\THEE{Scaling flow algorithm} -- let look for augumenting path, along which we can push $k = 2^t$ extra flow.
Main condition in \t{dfs} is transformed:\\
\lstinline|if (e.f + k <= e.c && u[e.to] != cc && (x = dfs(e.to, min(flow, e.c - e.f))) > 0) {|\\
Main loop of algorithm is transformed:
\begin{code}
int maxFlow() {
  read();
  cc = 1, u = vector<int>(n, 0);
  // MAX_CAPACITY <= 2^t <= 2*MAX_CAPACITY
  for (int k = (1 << t); k > 0; k = k / 2, cc++) 
    while ((add = dfs(s, k, INT_MAX)) > 0)
      f += add, cc++;
  return f;
}
\end{code}

\begin{Thm}
On graphs with integer capacities Scaling algorithm works in time $\O(m^2 \log U)$, where $U$ -- maximal capacity.
\end{Thm}
\begin{proof}
We iterate $\log U$ different $k$, \t{dfs} works in $\O(m)$, 
now we have to show that for each $k$ we'll get only $\O(m)$ paths. 
Denote flow before looking for paths of value $k$ as $f_1$.
Denote flow after looking for all paths of size $k$ as $f_2$.
For $f_1$ there is no "augumenting paths of size $2k$", so there is such cut that all edges $e$, going throw the cut, satisfy $c_e - f_e < 2k$.
Consider decomposition of flow $f_2 - f_1$. Each path in decomposition has size at least $k$ and goes throw the cut.
So there are no more than $\mfrac{m \cdot 2k}{k} = 2m = \O(m)$ paths.
\end{proof}

\THEE{Remark.} In practice Scaling algorithm works in $\O(m^2)$. ;)

\pagebreak

\vspace*{-2em}
\Subsection{Advertisement}

There are some cool and quiet easy algorithms:
\begin{MyList}[0pt]
  \item \href{https://en.wikipedia.org/wiki/Dinic%27s_algorithm}{Dinic's algorithm}
    \begin{InnerMyList}
      \item Finds max flow in $\O(n^2m)$, with Scaling idea works in $\O(nm \log U)$.
      \item Gives \href{https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm}{Hopcroft–Karp algorithm}
        to find matching in bipartite graph in time $\O(m\sqrt{n})$.
      \item Finds max flow in networks with unit capacities in $\O(\min(m^{1/2},n^{2/3})m)$ time.
    \end{InnerMyList}
  \item Family of algorithms based on "preflow" idea and using "global relabeling" optimization.\\
    In practice these algorithms are good. Not worse than $nm$.
  \item Ahuja-Orlin's algorithm based on ideas of "preflow" and "scaling of excess". \\
    It works in $\O(nm + n^2\log U)$ time.
\end{MyList}

\Section{Mincost Flows}

\Subsection{Definitions}

You are given weighted oriented graph. $w_e$ -- weight of edge $e$. 
Each edge $e$ has backward pair $e'$.
We already now, $f_e = {-}f_{e'}$.
Let define weight of backward edge equal to ${-}w_e$.
Let define weight of flow $f$ equal to $W(f) = \mfrac{1}{2}\sum_e f_ew_e$. 
Note, $W(f) = \sum_{e \in E} f_ew_e$, where $E$ -- set of forward edges.\\
Notation $W(x)$ we also will use for path $p$ ($W(p)$ -- weight of the path), circulation $z$ ($W(z)$ -- weight of the circulation).
Let define common problems:

\THE{Min cost flow:} to find flow $f \colon W(f) = \min$

\vspace*{-0.3em}
\THE{Min cost max flow:} to find flow $f \colon |f| = \max, W(f) = \min$

\vspace*{-0.3em}
\THE{Min cost k-flow:} to find flow $f \colon |f| = k, W(f) = \min$

\Subsection{Algorithm for "min cost k-flow" problem}

\vspace*{-0.3em}
\begin{Lm}
\label{lm:NoCycles}
If there is negative cycle in residual network then flow is not mincost.
\end{Lm}
\begin{proof}Let $C$ -- negative cycle in $G_f$, consider flow $f + C$ (increase flow along the cycle). \\
Value was not changed. Weight was decreased.\end{proof}

\begin{Lm}
If there are no negative cycles in residual network then flow is mincost.
\label{lm:MinCost}
\end{Lm}
\begin{proof}
Let there is flow $f_1$ and flow $f_2 \colon |f_1| = |f_2|, W(f_1) > W(f_2)$,
Consider flow $h = f_2 - f_1$ in network $G_{f_1}$. It's correct flow because of $(f_2-f_1)_e \le (c - f_1)_e$.
Note $|h| = 0$, $W(h) < 0$, it's negative circulation. Circulation can be decomposed into cycles.
One of these cycles has negative weight.
\end{proof}

\begin{Lm}Denote mincost k-flow as $f_k$. Then $f_{k{+}1} = f_k + \t{shortestPath} + \t{zeroCirculation}$.\end{Lm}
\begin{proof}
Consider flow $h = f_{k{+}1} - f_k$ in $G_{f_k}$. $|h| = 1$, decomposition of $h$ is path $p$ and circulation~$z$.
$f_{k{+}1}$ is mincost, so $W(z) \le 0$ and $W(p) = W(\t{shortestPath})$. \\
Using lemma \autoref{lm:NoCycles} we have $W(z) \ge 0 \SO W(z) = 0$.
\end{proof}

\vspace*{-0.3em}
\THEE{Algorithm for "mincost k-flow" problem} (works only for graphs without negative cycles).
\begin{MyTabbing}
$f \leftarrow 0$ (there are no negative cycles) \\
for i=1..k: \\
\> find shortest path using Bellman-Ford algorithm \\
\> increase flow along the path by $1$\\
\t{return} $f$ 
\end{MyTabbing}

Algorithm works in $\O(knm)$ time.

\vspace*{0.5em}
Denote $d_k = W(f_{k{+}1}) - W(f_k)$ (weight of $k$-th augumenting path).
From proof of Edmonds-Karp algorithm [\ref{exm:edmonds}] we have $d_{k{+}1} \ge d_k$.
So we may optimize the algorithm described above, let push not one unit of flow, but $\min_{e \in path} (c_e - f_e)$ units.

\pagebreak

\vspace*{-2em}
\Subsection{Algorithm for "min cost flow" problem}

We already know $d_{k{+}1} \ge d_k$.
Weight of the flow decreases while $d_k < 0$.

Algorithm: let start with $f_0$ and while $d_k < 0$ add the path to the flow.

Working time is $\O(nm|f|)$, where $|f|$ -- value of the seeking flow.  

\Subsection{Implementation of mincost flow algorithm}

Let modificate the code [\ref{exm:flowcode}], we'll get:
\begin{code}
void add_edge( int a, int b, int capacity, int weight ) {
  edges.push_back(Edge {a, b, head[0], 0, capacity, weight});
  head[a] = edges.size() - 1;
}

queue<int> q;
void relax( int v, int d ) {
  if (dist[v] > d)
    return;
  dist[v] = d;
  if (!in_queue[v])
    q.push(v), in_queue[v] = 1;
}
bool ford_bellman() {
  const int infty = 1e9; 
  for (int i = 0; i < n; i++)
    dist[i] = infty, in_queue[i] = 0;
  relax(s, 0);
  while (q.size()) {
    int v = q.front(); q.pop();
    in_queue[v] = 0;
    for (int i = head[v]; i != -1; i = edges[e].next) {
      Edge &e = edges[i];
      if (e.f < e.c)
        relax(e.to, d[v] + e.weight);
    }
  }
  return dist[t] < infty;
}
...
add_edge(a, b, c, w); // forward edge
add_edge(a, b, 0, -w); // backward edge
\end{code}

This implementation of Bellman-Ford algorithm uses $\O(n)$ of memory and $\O(nm)$ of time in the worst case. In average case it works in $\O(m)$.
This implementation is known as "\href{http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm}{Shortest Path Faster Algorithm}" (SPFA).
Please, do not confuse this implementation with "Levit's algorithm". Levit pushes some vertices to front of queue.

\pagebreak

\vspace*{-2em}
\Subsection{Negative cycles}

If there are negative cycles in the graph then $f_0 \not= 0$.
To find $f_0$, let use lemmas \autoref{lm:NoCycles} and \autoref{lm:MinCost}. 
Start with empty flow. Then while there is negative cycle in residual network, let increase the flow along the cycle.
We can use Bellman-Ford algorithm to find negative cycle in $\O(nm)$ time.

\vspace*{0.5em}
This approach gives us another algorithm to find $f_k$.

\THEE{Algorithm for "mincost k-flow" problem}
\begin{InnerMyList}
  \item Find any flow of value $k$.
  \item While there is negative cycle in residual network, let increase the flow along the cycle.
  \item If there are no negative cycles the flow is mincost \autoref{lm:MinCost}.
\end{InnerMyList}
\vspace*{-0.5em}
This algorithm works especially good, if we look for "\href{http://webcourse.cs.technion.ac.il/236359/Spring2013/ho/WCFiles/MMC.ps}{cycle of minimal mean weight}''

\Subsection{Advertisement}

Idea of \href{https://en.wikipedia.org/wiki/Johnson%27s_algorithm}{Johnson's potentials}
allows us to use Dijkstra instead of Bellman-Frd.
Now that algorithm for mincost k-flow problem works in $\O(km\log n)$ time and even in $\O(k(m + n\log n))$ time.

\vspace*{0.5em}
Note, we do not know yet how to find mincode in polynomial of $n$, $m$ and $\log U$ time.
Such algorithms exist. The most simple is based on idea of "capacity scaling" and works in time $\O(\t{Dijkstra } m \log U)$ ($m \log U$ times launches Dijkstra's algorithm).

