Network flow algorithms

TypeScript implementation of some network flow algorithms.

Implemented algorithms

• Search problem
  • Depth-first search: O(n + m) = O(m)
  • Breadth-first search: O(n + m) = O(m)
• Shortest path problem
  • Bellman-Ford: O(n * m)
• Maximum flow problem
  • Edmonds-Karp: O(n * m^2)
• Minimum-cost flow problem
  • Cycle-canceling: O(n * m^2 * C * U)

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
• 🕹 Usage
• 🔬 Development
  • Rules
    • Commits
    • Branches
• 🧾 MIT License
• ☎️ Contacts
  • Developers

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

• e-mail : me@cedoor.dev
• github : @cedoor
• website : https://cedoor.dev