Description

Network flow algorithms apply to directed networks in which edges have certain capacities and a flow moves from source nodes (i.e., nodes with in-degree 0) to sink nodes (i.e., nodes with out-degree 0).

In our everyday life, flow algorithms can be applied to all problem domains that involve networks (e.g., water supply, electricity/power, internet, shipment) in which the goal is to move some flow (e.g., water, electricity/power, products, internet traffic, message) from one position to another within the network as efficient as possible.

The demo presents three flow algorithms that will be applied on a network with water pipes. The thickness of each edge indicates the edge capacity while the blue-colored part the flow load. The label of each edge is in form "flow / capacity".

The blue part in the interior of each node indicates the flow that comes across the node through the incoming edges. Source nodes are bounded by a green rectangle, while sink nodes by a red rectangle. For "Minimum Cost" algorithm, source nodes are also the ones that can "supply" flow to the network, while sink nodes are those that "demand" flow from the network.

The user can select one of the provided algorithms using the combo-box in the toolbar. The result of each algorithm is also visualized in the toolbar. In the case where for some reason, no feasible solution is found, the result will be -1. Possible changes to the flow due to another algorithm selection or user interaction are highlighted temporary with orange color.

Legal Disclosure | Privacy Policy | View on GitHub

Algorithms

Maximum Flow

The maximum flow problem seeks to determine the maximum load that a network can handle considering a capacity constraint. Applications of the maximum flow algorithm include the following:
  • Determine the maximum amount of data that can be sent through a computer network.
  • Find the maximum amount of fluids (e.g. water or oil) that a network of pipelines can supply.
  • Calculate the amount of goods that a company can transport from warehouses to stores depending on the number of available trucks and the state of the roads.

Things to Try

  • Modify the network's structure by adding or removing nodes and edges.
  • Drag an edge to increase or decrease its capacity.
  • Press button of the toolbar to load the initial graph.
  • Press button of the toolbar to layout the existing graph.

Minimum Cost Flow

The minimum cost flow describes the flow through a network that produces the lowest cost. The solution depends on the edges' capacity and cost. Some nodes can supply flow to the network while others can demand flow from the network. Applications of the minimum cost algorithm include the following:
  • Find the parts in pipelines or data networks that handle the most flow and would affect the flow the most when they fail.
  • Find the most efficient flight passenger lift in which passengers can leave/board the plane at every stop to prevent empty flights.
  • Find the optimal location for facilities based on their connection with the surrounding neighborhood (e.g. hospitals, fire stations).
  • Solve the transportation problem where a certain demand of goods must by satisfied by a number of warehouses such that the transportation costs are minimized.

Things to Try

  • Modify the network's structure by adding or removing nodes and edges.
  • Drag an edge to increase/decrease its capacity.
  • Drag the blue-part of a node to increase its supply or demand. The label in the interior of the node indicates the flow that comes across after the algorithm has been applied plus/minus the corresponding supply/demand respectively. Nodes bounded by a green rectangle represent "supply" nodes, while nodes bounded by a red rectangle represent "demand" nodes.
  • Click on a "cost" label and use and of the popup menu to increase or decrease the edge's cost. Press to apply the algorithm.
  • Press button of the toolbar to load the initial graph.
  • Press button of the toolbar to layout the existing graph.

Maximum Flow Minimum Cut

The maximum flow minimum cut problem determines the maximum amount of flow that can be sent through the network and calculates the minimum cut. A cut separates the network such that source and sink nodes are disconnected and no flow from the source can reach the sink. The minimum cut is the cut with the minimum capacity and its value equals to the maximum flow. Applications of the maximum flow minimum cut algorithm include the following:
  • Determine a maximum bipartite matching in a general graph.
  • Calculate the maximum flow of a network.
  • Find a parking spot for each car that minimizes the total time required for all cars to find a spot.

Things to Try

  • Modify the network's structure by adding or removing nodes and edges.
  • Drag an edge to increase or decrease its capacity.
  • Take a look at the min-cult line to determine the edges that belong to the cut.
  • Press button of the toolbar to load the initial graph.
  • Press button of the toolbar to layout the existing graph.