Maximum Flow

Algorithm link: Maximum Flow

The maximum flow problem is to find the maximum possible flow from a source vertex to the target vertex given a graph which represents a flow network where every edge has a capacity under the following constraints :

  • Flow on an edge doesn’t exceed the capacity of the edge.

  • Incoming flow is equal to outgoing flow for every vertex except s and t.

TigerGraph’s implementation of the Maximum Flow algorithm is based on a modified version of the Edmond-Karp algorithm.

Use cases

The Maximum Flow algorithm has real world applications such as airline scheduling, and in solving circulation-demand problems.

Specifications

CREATE QUERY tg_maxflow(VERTEX source, VERTEX sink, Set<STRING> v_type,
  SET<STRING> e_type, SET<STRING> reverse_e_type, STRING cap_attr,
  STRING cap_type, FLOAT min_flow_threshhold = 0.001, BOOL print_accum = TRUE, BOOL display_edges = TRUE, BOOL spit_to_file = FALSE, STRING file_path = "/home/tigergraph/tg_query_output.csv")

Time complexity

\(O(F + E)\)

Parameters

Parameter Data type Description

source

VERTEX

Source vertex where the flow starts.

sink

VERTEX

Target vertex where the flow is to be sent to.

v_type

SET<STRING>

Vertex types to consider in the path.

e_type

SET<STRING>

Edge types to traverse.

reverse_e_type

SET<STRING>

Reverse edge types to traverse.

cap_attr

STRING

Name of the attribute that contains the capacity of the edge.

cap_type

STRING

Data type of the cap_attr attribute.

min_flow_threshold

FLOAT

Minimum flow for an edge to carry if it is to carry any flow.

print_accum

BOOL

If true, output JSON to standard output.

display_edges

BOOL

If true, the resulting path includes edges in addition to vertices.

split_to_file

BOOL

If true, the file output will contain every edge and how much flow they would carry to achieve the maximum flow.

file_path

STRING

If not empty, write output to this file.

Result

JSON result

The return value is the maximum flow that can be carried from the source to the sink. If you set display_edges to true, the result will contain all edges that carry flow. However, it does not output how much flow each edge carries to achieve the maximum flow.

CSV result

The first line is the maximum flow that can be carried from the source to the sink. If you set split_to_file to true, the result will contain all edges that carry flow as well as how much flow they carry to achieve maximum flow.

Example

Suppose we have the following four areas a, b, c and d in a city. Between each area is a pipeline that can be used to deliver water.

max flow

If a is the source and d is the target (the sink), the maximum flow from a to d in this network is 51. With the edge from a to d carrying 35, and the remaining edges each carrying 8.

If we run the max flow algorithm on this network, we will get the result that the maximum flow is from a to d is 51:

Query
RUN QUERY tg_maxflow (("a", "area"), ("d", "area"), ["area"], ["pipeline"], ["reverse_pipeline"], "capacity", "FLOAT", _, _, _, TRUE, _)
  • JSON

  • CSV

{
  "error": false,
  "message": "",
  "version": {
    "schema": 1,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [
    {"@@sum_max_flow": 51},
    {"@@edges_set": [
      {
        "from_type": "area",
        "to_type": "area",
        "directed": true,
        "from_id": "b",
        "to_id": "d",
        "attributes": {"capacity": 8},
        "e_type": "pipeline"
      },
      {
        "from_type": "area",
        "to_type": "area",
        "directed": true,
        "from_id": "c",
        "to_id": "d",
        "attributes": {"capacity": 8},
        "e_type": "pipeline"
      },
      {
        "from_type": "area",
        "to_type": "area",
        "directed": true,
        "from_id": "a",
        "to_id": "c",
        "attributes": {"capacity": 20},
        "e_type": "pipeline"
      },
      {
        "from_type": "area",
        "to_type": "area",
        "directed": true,
        "from_id": "a",
        "to_id": "d",
        "attributes": {"capacity": 35},
        "e_type": "pipeline"
      },
      {
        "from_type": "area",
        "to_type": "area",
        "directed": true,
        "from_id": "a",
        "to_id": "b",
        "attributes": {"capacity": 34},
        "e_type": "pipeline"
      }
    ]}
  ]
}
Maxflow: 51
From,To,Flow
a,c,8
c,d,8
a,b,8
b,d,8
a,d,35