Skip to content

Latest commit

 

History

History

isap

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
__test__
__test__
 
 
src
src
 
 
CHANGELOG.md
CHANGELOG.md
 
 
README.md
README.md
 
 
package.json
package.json
 
 
project.json
project.json
 
 
tsconfig.lib.json
tsconfig.lib.json
 
 

README.md

@algorithm.ts/isap


A typescript implementation of the ISAP (Improved SAP) algorithm.

The ISAP algorithm is an algorithm for solving network flow problems.

Install

  • npm

    npm install --save @algorithm.ts/isap

  • yarn

    yarn add @algorithm.ts/isap

Usage

  • Simple

    import { Isap } from '@algorithm.ts/isap'

const isap = createIsap()
isap.init(0, 1, 4)
isap.addEdge(0, 2, 1)
isap.addEdge(0, 3, 2)
isap.addEdge(3, 1, 1)

isap.maxFlow() // => 1

// Access current residual network.
class CustomIsap extends Isap {
  public getSnapshot() {
    return {
      N: this._N,
      source: this._source,
      sink: this._sink,
      G: this.G,
      edges: this._edges,
      edgesTot: this._edgesTot,
      dist: this._dist
    }
  }
}

Example

  • A solution for Codeforces contest 1082 Problem G (https://codeforces.com/contest/1082/problem/G):

    import { Isap } from '@algorithm.ts/isap'

const isap = new Isap()
export function solveCodeforces1082G(
  nodes: number[],
  edges: Array<[u: number, v: number, weight: number]>,
): number {
  const n: number = nodes.length
  const m: number = edges.length

  const source = 0
  const target: number = n + m + 1
  isap.init(source, target, n + m + 2)

  for (let i = 0; i < n; ++i) {
    const weight: number = nodes[i]
    isap.addEdge(i + 1, target, weight)
  }

  let answer = 0
  for (let i = 0; i < m; ++i) {
    const [u, v, weight] = edges[i]
    const x = n + i
    answer += weight
    isap.addEdge(source, x, weight)
    isap.addEdge(x, u, Number.MAX_SAFE_INTEGER)
    isap.addEdge(x, v, Number.MAX_SAFE_INTEGER)
  }
  answer -= isap.maxflow()
  return answer
}

  • A solution for leetcode "Maximum Students Taking Exam" (https://leetcode.com/problems/maximum-students-taking-exam/):

    import { Isap } from '@algorithm.ts/isap'

export function maxStudents(seats: string[][]): number {
  const R: number = seats.length
  if (R <= 0) return 0

  const C: number = seats[0].length
  if (C <= 0) return 0

  let total = 0
  const seatCodes: number[][] = new Array(R)
  for (let r = 0; r < R; ++r) seatCodes[r] = new Array(C).fill(-1)

  for (let r = 0; r < R; ++r) {
    for (let c = 0; c < C; ++c) {
      if (seats[r][c] === '.') seatCodes[r][c] = total++
    }
  }

  if (total <= 0) return 0
  if (total === 1) return 1

  const source: number = total * 2
  const target: number = source + 1
  isap.init(source, target, target + 1)

  for (let r = 0; r < R; ++r) {
    for (let c = 0; c < C; ++c) {
      const u: number = seatCodes[r][c]
      if (u > -1) {
        isap.addEdge(source, u, 1)
        isap.addEdge(u + total, target, 1)
        if (r > 0) {
          // Check upper left
          if (c > 0 && seatCodes[r - 1][c - 1] > -1) {
            const v: number = seatCodes[r - 1][c - 1]
            isap.addEdge(u, v + total, 1)
            isap.addEdge(v, u + total, 1)
          }

          // Check upper right
          if (c + 1 < C && seatCodes[r - 1][c + 1] > -1) {
            const v: number = seatCodes[r - 1][c + 1]
            isap.addEdge(u, v + total, 1)
            isap.addEdge(v, u + total, 1)
          }
        }

        // Check left
        if (c > 0 && seatCodes[r][c - 1] > -1) {
          const v: number = seatCodes[r][c - 1]
          isap.addEdge(u, v + total, 1)
          isap.addEdge(v, u + total, 1)
        }
      }
    }
  }

  const totalPaired: number = isap.maxflow() / 2
  return total - totalPaired
}

Related