Flow network

In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a road system, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

Definition

A network is a graph $G = (V, E)$ , where V are a set of vertices and E are a set of edges, together with a non-negative function $c : V \times V \to ℝ \infty$ , called the capacity function. Without loss of generality, it is assumed that if $(u, v) \in E$ then $(v, u)$ is also a member of $E$ , since if $(v, u) \notin E$ then $(v, u)$ may be added to E and then setting $c (v, u) = 0$ .

If two nodes in $G$ are distinguished, a source $s$ and a sink $t$ , then $(G, c, s, t)$ is called a flow network.^[1]

Flows

There are various notions of a flow function that can be defined in a flow graph. Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such as what is the maximum number of units that can be transferred from the source node s to the sink node t? The simplest example of a flow function is known as a pseudo-flow.

A pseudo-flow is a function

f : V \times V \to ℝ

that satisfies the following two constraints for all nodes

u

and

v

Skew symmetry: Only encode the net flow of units between a pair of nodes $u$ and $v$ (see intuition below), that is: $f (u, v) = - f (v, u)$ .
Capacity constraint: An arc's flow cannot exceed its capacity, that is: $f (u, v) \leq c (u, v)$ .

Given a pseudo-flow $f$ in a flow network, it is often useful to consider the net flow entering a given node $v$ , that is, the sum of the flows entering $v$ . The excess function $x f : V \to ℝ$ is defined by $x f (u) = \sum v \in V f (v, u)$ . A node $u$ is said to be active if $x f (u) > 0$ , deficient if $x f (u) < 0$ or conserving if $x f (u) = 0$ .

These final definitions lead to two strengthenings of the definition of a pseudo-flow:

A pre-flow is a pseudo-flow that, for all

v ∈ V \{s

}, satisfies the additional constraint:

Non-deficient flows: The net flow entering the node $v$ is non-negative, except for the source, which "produces" flow. That is: $x f (v) \geq 0$ for all $v ∈ V \{s$ }.

A feasible flow, or just a flow, is a pseudo-flow that, for all

v ∈ V \{s, t

}, satisfies the additional constraint:

Flow conservation: The net flow entering the node $v$ is 0, except for the source, which "produces" flow, and the sink, which "consumes" flow. That is: $x f (v) = 0$ for all $v ∈ V \{s, t$ }.

The value of a feasible flow $f$ , denoted $| f |$ , is the net flow into the sink $t$ of the flow network. That is, $| f | = x f (t)$ .

Intuition

In the context of flow analysis, there is only an interest in considering how units are transferred between nodes in a holistic sense. Put another way, it is not necessary to distinguish multiple arcs between a pair of nodes:

Given any two nodes $u$ and $v$ , if there are two arcs from $u$ to $v$ with capacities $5$ and $3$ respectively, this is equivalent to considering only a single arc between $u$ and $v$ with capacity $8$ — it is only useful to know that $8$ units can be transferred from $u$ to $v$ , not how they can be transferred.
Again, given two nodes $u$ and $v$ , if there is a flow of $5$ units from $u$ to $v$ , and another flow of $3$ units from $v$ to $u$ , this is equivalent to a net flow of $2$ units from $u$ to $v$ , or a net flow of $-2$ units from $v$ to $u$ (so sign indicates direction) — it is only useful to know that a net flow of $2$ units will flow between $u$ and $v$ , and the direction that they will flow, not how that net flow is achieved.

For this reason, the capacity function $c : V \times V \to ℝ \infty$ , which does not allow for multiple arcs starting and ending at the same nodes, is sufficient for flow analysis. Similarly, it is enough to impose the skew symmetry constraint on flow functions to ensure that flow between two vertices is encoded by a single number (to indicate magnitude), and a sign (to indicate direction) — by knowing the flow between $u$ and $v$ you implicitly, via skew symmetry, know the flow between $v$ and $u$ . These simplifications of the model aren't always immediately intuitive, but they are convenient when it comes time to analysing flows.

The capacity constraint simply ensures that a flow on any one arc within the network cannot exceed the capacity of that arc.

Concepts useful to flow problems

Residuals

The residual capacity of an arc with respect to a pseudo-flow $f$ , denoted $c f$ , is the difference between the arc's capacity and its flow. That is, $c f (e) = c (e) - f (e)$ . From this we can construct a residual network, denoted $G f (V, E f)$ , which models the amount of available capacity on the set of arcs in $G = (V, E)$ . More formally, given a flow network $G$ , the residual network $G f$ has the node set $V$ , arc set $E f = {e \in V \times V : c f (e) > 0}$ and capacity function $c f$ .

This concept is used in Ford–Fulkerson algorithm which computes the maximum flow in a flow network.

Note that there can be a path from $u$ to $v$ in the residual network, even though there is no path from $u$ to $v$ in the original network. Since flows in opposite directions cancel out, decreasing the flow from $v$ to $u$ is the same as increasing the flow from $u$ to $v$ .

Augmenting paths

An augmenting path is a path $(u 1, u 2, ..., u k)$ in the residual network, where $u 1 = s$ , $u k = t$ , and $c f (u i, u i + 1) > 0$ . A network is at maximum flow if and only if there is no augmenting path in the residual network $G f$ .

Multiple sources and/or sinks

Sometimes one needs to model a network with more than one source, a supersource is introduced to the graph.^[2] This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink.^[3]

Example

A flow network showing flow and capacity

To the left you see a flow network with source labeled $s$ , sink $t$ , and four additional nodes. The flow and capacity is denoted $f/c$ . Notice how the network upholds skew symmetry, capacity constraints and flow conservation. The total amount of flow from $s$ to $t$ is 5, which can be easily seen from the fact that the total outgoing flow from $s$ is 5, which is also the incoming flow to $t$ . We know that no flow appears or disappears in any of the other nodes.

Residual network for the above flow network, showing residual capacities.

Below you see the residual network for the given flow. Notice how there is positive residual capacity on some edges where the original capacity is zero, for example for the edge $(d,c)$ . This flow is not a maximum flow. There is available capacity along the paths $(s,a,c,t)$ , $(s,a,b,d,t)$ and $(s,a,b,d,c,t)$ , which are then the augmenting paths. The residual capacity of the first path is $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))$ $=\min(5-3,3-2,2-1)=\min(2,1,1)=1$ . Notice that as long as there exists some path with a positive residual capacity, the flow will not be maximum. The residual capacity for some path is the minimum residual capacity of all edges in that path.

Well known algorithms for Max-Flow
Inventor(s)	Year	Time complexity
Edmonds–Karp algorithm	1972	$O (m 2 n)$
MPM (Malhotra, Pramodh-Kumar and Maheshwari) algorithm^[4]	1978	$O (n 3)$
J. Orlin	2013	$O (mn)$

Applications

Picture a series of water pipes, fitting into a network. Each pipe is of a certain diameter, so it can only maintain a flow of a certain amount of water. Anywhere that pipes meet, the total amount of water coming into that junction must be equal to the amount going out, otherwise we would quickly run out of water, or we would have a buildup of water. We have a water inlet, which is the source, and an outlet, the sink. A flow would then be one possible way for water to get from source to sink so that the total amount of water coming out of the outlet is consistent. Intuitively, the total flow of a network is the rate at which water comes out of the outlet.

Flows can pertain to people or material over transportation networks, or to electricity over electrical distribution systems. For any such physical network, the flow coming into any intermediate node needs to equal the flow going out of that node. This conservation constraint is equivalent to Kirchhoff's current law.

Flow networks also find applications in ecology: flow networks arise naturally when considering the flow of nutrients and energy between different organizations in a food web. The mathematical problems associated with such networks are quite different from those that arise in networks of fluid or traffic flow. The field of ecosystem network analysis, developed by Robert Ulanowicz and others, involves using concepts from information theory and thermodynamics to study the evolution of these networks over time.

The simplest and most common problem using flow networks is to find what is called the maximum flow, which provides the largest possible total flow from the source to the sink in a given graph. There are many other problems which can be solved using max flow algorithms, if they are appropriately modeled as flow networks, such as bipartite matching, the assignment problem and the transportation problem. Maximum flow problems can be solved efficiently with the relabel-to-front algorithm. The max-flow min-cut theorem states that finding a maximal network flow is equivalent to finding a cut of minimum capacity that separates the source and the sink. Where a cut is the division of vertices such that the source is in one division and the sink is in another.

In a multi-commodity flow problem, you have multiple sources and sinks, and various "commodities" which are to flow from a given source to a given sink. This could be for example various goods that are produced at various factories, and are to be delivered to various given customers through the same transportation network.

In a minimum cost flow problem, each edge $u,v$ has a given cost $k(u,v)$ , and the cost of sending the flow $f(u,v)$ across the edge is $f(u,v)\cdot k(u,v)$ . The objective is to send a given amount of flow from the source to the sink, at the lowest possible price.

In a circulation problem, you have a lower bound $l(u,v)$ on the edges, in addition to the upper bound $c(u,v)$ . Each edge also has a cost. Often, flow conservation holds for all nodes in a circulation problem, and there is a connection from the sink back to the source. In this way, you can dictate the total flow with $l(t,s)$ and $c(t,s)$ . The flow circulates through the network, hence the name of the problem.

In a network with gains or generalized network each edge has a gain, a real number (not zero) such that, if the edge has gain g, and an amount x flows into the edge at its tail, then an amount gx flows out at the head.

In a source localization problem, an algorithm tries to identify the most likely source node of information diffusion through a partially observed network. This can be done in linear time for trees and cubic time for arbitrary networks and has applications ranging from tracking mobile phone users to identifying the originating village of disease outbreaks.^[5]

References

↑ A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989
↑ This article incorporates public domain material from the NIST document: Black, Paul E. "Supersource". Dictionary of Algorithms and Data Structures.
↑ This article incorporates public domain material from the NIST document: Black, Paul E. "Supersink". Dictionary of Algorithms and Data Structures.
↑ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). "An $O(|V|^{3})$ algorithm for finding maximum flows in networks". Information Processing Letters. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.
↑ http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf

External links

Maximum Flow Problem
Real graph instances
Lemon C++ library with several maximum flow and minimum cost circulation algorithms
QuickGraph, graph data structures and algorithms for .Net

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.