Maximum Flow

Supported Graph Characteristics

Weighted edges

Homogeneous vertex types

Heterogeneous vertex types

Flow is the concept of something moving from one vertex to another in a graph, such as money (in a financial graph), data (in a computer network), or even water (in a utility network).

A graph must have weighted edges to represent flow.

The maximum flow problem is to find the maximum possible flow from a source vertex to the target vertex.

Assuming a weighted graph 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,
   SET<STRING> e_type_set, SET<STRING> reverse_e_type_set, STRING cap_attr,
  STRING cap_type, FLOAT min_flow_threshhold = 0.001, BOOL print_results = TRUE, BOOL display_edges = TRUE, BOOL spit_to_file = FALSE, STRING file_path = "/home/tigergraph/tg_query_output.csv")

Parameters

Parameter Description

Parameter	Description
`VERTEX source`	Source vertex where the flow starts. Provide the vertex ID and type as a tuple: `("id","type")`
`VERTEX sink`	Target vertex where the flow is to be sent to. Provide the vertex ID and type as a tuple: `("id","type")`
`SET<STRING> v_type_set`	Vertex types to consider in the path.
`SET<STRING> e_type_set`	Edge types to traverse.
`SET<STRING> reverse_e_type_set`	Reverse edge types to traverse.
`STRING cap_attr`	Name of the attribute that contains the capacity of the edge.
`STRING cap_type`	Data type of the `cap_attr` attribute.
`FLOAT min_flow_threshold`	Minimum flow for an edge to carry if it is to carry any flow.
`BOOL print_results`	If true, output JSON to standard output.
`BOOL display_edges`	If true, the resulting path includes edges in addition to vertices.
`BOOL split_to_file`	If true, the file output will contain every edge and how much flow they would carry to achieve the maximum flow.
`STRING file_path`	If not empty, write output to this file.

VERTEX source

Source vertex where the flow starts. Provide the vertex ID and type as a tuple: ("id","type")

VERTEX sink

Target vertex where the flow is to be sent to. Provide the vertex ID and type as a tuple: ("id","type")

SET<STRING> v_type_set

Vertex types to consider in the path.

SET<STRING> e_type_set

Edge types to traverse.

SET<STRING> reverse_e_type_set

Reverse edge types to traverse.

STRING cap_attr

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

STRING cap_type

Data type of the cap_attr attribute.

FLOAT min_flow_threshold

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

BOOL print_results

If true, output JSON to standard output.

BOOL display_edges

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

BOOL split_to_file

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

STRING file_path

If not empty, write output to this file.

Output

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.

Time complexity

The time complexity of the Edmond-Karp algorithm is independent of maximum flow in the graph. Here, the time complexity is \(O(VE^2)\) where \(V\) is the number of vertices and \(E\) is the number of edges in the graph.

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.

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