# Ford-Fulkerson algorithm with asymmetric adjacency matrix

Suppose that I have a bipartite graph $G=(A \cup B, E)$ and $A = \{1, 2, \dots, n\}$, $B = \{1, 2, \dots, m\}$. After a virtual sink $s = 0$ and a source $t = n+1$ is included into the graph, I want to implement Ford-Fulkersen max flow algorithm.

To the algorithm, we need a symmetric adjacency matrix, therefore $O((n + m)^2)$ space.

However, in a bipartite graph, it is enough to use an adjacency matrix with $O(nm)$ space. But I could not figure out how to modify the algorithm so that it works with an asymmetric adjacency matrix.

Is there any way that Ford-Fulkersen max flow algorithm works in above scenario?

The algorithm doesn't need a symmetric adjacency matrix. It needs to keep track of a flow and a residual network. Both are supported on the edges of $G$ and their inverses. You can store them in roughly the same way you store your graph $G$, using the same amount of space (up to a multiplicative constant).
• How do I differentiate $adj_{ij}$ in the original graph with $res_{ij}$ in residual graph? For instance $adj_{22} = 4$ means there exists an edge from $2 \in A$ to $2 \in B$ with capacity 4 but $res_{22} = -1$ means there exists a backwards edge from $2 \in B$ to $2 \in A$. Is this correct? – padawan May 11 '16 at 8:16