Options
All
  • Public
  • Public/Protected
  • All
Menu

Network flow algorithms

TypeScript implementation of some network flow algorithms.

Github license David GitHub Workflow test GitHub Workflow build Coveralls Code style prettier Repository top language

Implemented algorithms

Where:

  • n: n° of nodes,
  • m: n° of arcs,
  • C: largest magnitude of any arc cost,
  • U: largest magnitude of any supply/demand or finite arc capacity.

The algorithms use the concepts, definitions and notations expressed in the book Network Flows: Theory, Algorithms, and Applications, Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.


Table of Contents

Install

npm or yarn

You can install utils package with npm:

npm i @cedoor/nfa --save

or with yarn:

yarn add @cedoor/nfa

CDN

You can also load it using a script tap using unpkg:

<script src="https://unpkg.com/@cedoor/nfa/"></script>

or JSDelivr:

<script src="https://cdn.jsdelivr.net/npm/@cedoor/nfa/"></script>

Usage

The library documentation is automatically generated with TypeDoc and published on nfa.cedoor.dev and can be used on Node.js and browsers with different types of modules (AMD, CommonJS, ES modules). Here some examples:

// Imports the module with ES modules.
import { Graph, Node, Arc, dfs, bellmanFord, edmondsKarp, cycleCanceling } from "@cedoor/nfa"
// Or with commonJS modules.
// const { Graph, Node, Arc, dfs, bellmanFord, edmondsKarp, cycleCanceling } = require("@cedoor/nfa")
// Or with the global variable 'nfo' on the browser side.

const graph = new Graph()

// Creates the nodes with the outgoing arcs.
const node1 = new Node(1, 10, [new Arc(2, 3, 10), new Arc(3, 5, 18)])
const node2 = new Node(2, 0, [new Arc(3, 8, 12)])
const node3 = new Node(3, 0, [new Arc(4, 4, 20)])
const node4 = new Node(4, -10, [])

graph.addNode(node1)
graph.addNode(node2)
graph.addNode(node3)
graph.addNode(node4)

const tree = dfs(graph, 1)
const tree2 = bellmanFord(graph, 1)
const [, maximumFlow] = edmondsKarp(graph)
const [, , minimumCost] = cycleCanceling(graph)

// 'tree' is a JS Map containing node/previous-node pairs.
// The source node always has -1 as its previous node.
console.log(tree) // Map { 1 => -1, 2 => 1, 3 => 1, 4 => 3 }

// 'tree2' is a JS Map containing node/[previous-node, distance] pairs.
console.log(tree2) // Map { 2 => [ 1, 3 ], 3 => [ 1, 5 ], 4 => [ 3, 9 ] }
console.log(maximumFlow) // 10
console.log(minimumCost) // 9

Algorithms can also take the graph parameter as JSON:

[
    {
        "id": 1,
        "balance": 10,
        "arcs": [
            {
                "head": 2,
                "cost": 3,
                "capacity": 10,
                "flow": 0
            },
            {
                "head": 3,
                "cost": 5,
                "capacity": 18,
                "flow": 0
            }
        ]
    },
    {
        "id": 2,
        "balance": 0,
        "arcs": [
            {
                "head": 3,
                "cost": 8,
                "capacity": 12,
                "flow": 0
            }
        ]
    },
    {
        "id": 3,
        "balance": 0,
        "arcs": [
            {
                "head": 4,
                "cost": 4,
                "capacity": 20,
                "flow": 0
            }
        ]
    },
    {
        "id": 4,
        "balance": -10,
        "arcs": []
    }
]

Contacts

Developers

Index

Type aliases

GraphData

GraphData: { arcs: { capacity: number; cost: number; flow?: undefined | number; head: number }[]; balance: number; id: number }[]

Type used to define the structure of the graph data which can be passed into the graph class constructor to create a graph using external data (i.e. JSON data).

Functions

bellmanFord

  • bellmanFord(graph: Graph | GraphData, sourceNodeId: number): Map<number, [number, number]> | number[]
  • The Bellman–Ford algorithm finds the shortest paths of a directed graph. The algorithm returns a map with the nodes and their predecessors and a map with the nodes and their distances from the source node. If there are negative cycles the algorithm returns the path of the cycle. Time complexity: O(n * m).

    Parameters

    Returns Map<number, [number, number]> | number[]

    A map with distances and predecessors or the path of the negative cycle.

bfs

  • bfs(graph: Graph | GraphData, sourceNodeId: number, sinkNodeId?: undefined | number): Map<number, number> | number[]
  • The Breadth-First Search algorithm finds the tree of the shortest directed paths from the source node to the other nodes of the graph and returns it as map of the <node, previous node> pairs. If a sink node is specified the algorithm return the specific directed path from the source node to the sink node as an array. This algorithm use a queue data structure to visit the nodes. Time complexity: O(n + m) = O(m).

    Parameters

    • graph: Graph | GraphData
    • sourceNodeId: number
    • Optional sinkNodeId: undefined | number

    Returns Map<number, number> | number[]

    The tree of the shortest paths or the path between the source node and the sink node.

cycleCanceling

  • The Cycle-Canceling algorithm solves the minimum-cost flow problem starting from a feasible graph obtained with a maximum flow algorithm and, as long as negative cost cycles exist, augment the flow along this cycles. This implementation uses the Edmonds-Karp algorithm to solve the maximum flow problem in O(n * m^2), and the Bellman-Fort algorithm to find the negative cycles in O(m * n). Time complexity: O (n * m^2 * C * U).

    Parameters

    Returns [Graph, number, number]

    The optimal graph, the maximum flow and the minimum cost.

dfs

  • dfs(graph: Graph | GraphData, sourceNodeId: number, sinkNodeId?: undefined | number): Map<number, number> | number[]
  • The Depth-First Search algorithm finds the tree of the shortest directed paths from the source node to the other nodes of the graph and returns it as map of the <node, previous node> pairs. If a sink node is specified the algorithm return the specific directed path from the source node to the sink node as an array. This algorithm use a stack data structure to visit the nodes, and in JavaScript can be used the 'push' and 'pop' array methods. Time complexity: O(n + m) = O(m).

    Parameters

    • graph: Graph | GraphData
    • sourceNodeId: number
    • Optional sinkNodeId: undefined | number

    Returns Map<number, number> | number[]

    The tree of the shortest paths or the path between the source node and the sink node.

edmondsKarp

  • The Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow between two nodes in a flow network. The algorithm uses the Breadth-First Search algorithm to find the augmenting path between the source and the sink node, and increment the maximum flow with the minimum arc capacity for each path using the residual graph. Returns the optimal graph, the maximum flow, the source and the sink nodes. Time complexity: O(n * m^2).

    Parameters

    Returns [Graph, number, number, number]

    The optimal flow graph, the maximum flow, the source and sink nodes.

extendGraph

  • extendGraph(graph: Graph): [number, number]
  • Extends the graph with two new source and sink nodes. For each node with balance greater than 0, it creates an arc with capacity = balance from the new source node to this node. For each node with balance less than 0, it creates an arc with capacity = -balance from the node to the new sink nodes. This allows you to compute a feasible graph, where the mass balance constraint is respected. Time complexity: O(n).

    Parameters

    Returns [number, number]

    The new source and sink nodes.

getOptimalGraph

  • Convert the residual graph in an optimal graph in which the residual capacity is converted in flow. Time complexity: O(m).

    Parameters

    Returns Graph

    The optimal graph.

getResidualCapacity

  • getResidualCapacity(graph: Graph, path: number[]): number
  • Returns the arc minimum residual capacity of the path. Time complexity: O(n).

    Parameters

    • graph: Graph
    • path: number[]

    Returns number

    The minimum capacity.

getResidualGraph

  • Converts a graph in a residual graph, in which the new arc flow represent the residual capacity. Time complexity: O(m).

    Parameters

    Returns Graph

    The residual graph.

retrievePath

  • retrievePath(predecessors: Map<number, number>, nodeId: number): number[]
  • Retrieves the path from a node of the graph to the source node using the predecessors map. If there is a cycle return the cycle path. Time complexity: O(n).

    Parameters

    • predecessors: Map<number, number>
    • nodeId: number

    Returns number[]

    The path from a node to the source node or a cycle path.

sendFlow

  • sendFlow(graph: Graph, path: number[], flow: number): void
  • Augments the path in the graph updating the flow of the arcs. Time complexity: O(n).

    Parameters

    • graph: Graph
    • path: number[]
    • flow: number

    Returns void

Legend

  • Constructor
  • Property
  • Method
  • Private property

Generated using TypeDoc