GTDH: Algorithms API - GraphTheoryDeepHole/syzoj-ng-app GitHub Wiki

path: src/pages/graph-editor/algorithm/

Chapter 5 Matching & Network Flow

Matching

path: ./matching/

Maximum Matching in Bipartite Graph

file: ./BipartiteMatching.ts

class: HungarianDFS

DFS version of Hungarian algorithm for Maximum Matching in Bipartite Graph

Run Param

graph: BipartiteGraph

Step Info

node.datum:
  side: string
    enum:
      - "left"
      - "right"
  mark: number
    default: -1
    description: $id of node to be matched with $this after flipping the augmenting path
  match: number
    default: -1
    description: $id of node currently matched with $this
  tag: number
    defalut: 0
    enum:
      - 0: unchecked
      - 1: matched
      - 2: checked but unmatched
edge.datum:
  marked: boolean
    description: $this to be used after flipping
  matched: boolean
    description: $this currently used

Return Value

{matched: number}

Maximum Weighted Matching in Bipartite Graph

file: ./WeightedBipartiteMatching.ts

class: KuhnMunkres

Kuhn-Munkres algorithm for Maximum Weighted Matching in Bipartite Graph

Run Param

graph: BipartiteMatrix

Step Info

node.datum:
  side: string
    enum:
      - "left"
      - "right"
  match: number
    default: -1
    description: $id of node currently matched with $this
  in: boolean
    description: $this in set S(left node) or T(right node)
  l: number
    description: bound of $this, l[x] + l[y] >= w[x][y]
edge.datum:
  weight: number
  marked: boolean
    description: $this to be used after flipping
  matched: boolean
    description: $this currently used
  valid: boolean
    description: $this satisfied l[x] + l[y] == w[x][y]

Return Value

{weight: number}

Maximum Matching in General Graph

file: ./Matching.ts

class: Gabow

Gabow algorithm for Maximum Matching in General Graph

Run Param

graph: Graph // undirected, no self loop, no mutiple edges

Step Info

node.datum:
  match: number
    default: -1
    description: $id of node currently matched with $this
  lable: number
    default: 0
    enum:
      - 0: unvisited
      - 1: inner node
      - 2: outer node
  first: number
    default: -1
    description: $id of first inner node of $this.path
edge.datum:
  marked: boolean
    description: $this to be used after flipping
  matched: boolean
    description: $this currently used

Return Value

{matched: number}

Network Flow

path: ./networkflow/

Maximum Network Flow

file: ./FordFulkerson.ts

class: FordFulkerson

Ford-Fulkerson algorithm for Maximum Network Flow

Run Param

graph: Graph, // weighted, directed, no self loop
Spos: number, // id of source node
Tpos: number  // id of target node 

edge.datum:
  flow: number
    description: maximum flow of $this

Step Info

node.datum: empty
edge.datum:
  flow: number
    description: maximum flow of $this
  used: number
    defalut: 0
    description: used flow of $this
  mark: number
    defalut: 0
    description: direction of $this in augmenting path
    enum:
      - 0: $this not in augumenting path
      - 1: same direction of $this
      - -1: opposite direction of $this

Return Value

{flow: number}

file: ./EdmondsKarp.ts

class: EdmondsKarp

Edmonds-Karp algorithm for Maximum Network Flow

Run Param

graph: Graph, // weighted, directed, no self loop
Spos: number, // id of source node
Tpos: number  // id of target node 

edge.datum:
  flow: number
    description: maximum flow of $this

Step Info

node.datum: empty
edge.datum:
  flow: number
    description: maximum flow of $this
  used: number
    defalut: 0
    description: used flow of $this
  mark: number
    defalut: 0
    description: direction of $this in augmenting path
    enum:
      - 0: $this not in augumenting path
      - 1: same direction of $this
      - -1: opposite direction of $this

Return Value

{flow: number}

file: ./Dinic.ts

class: Dinic

Dinic algorithm for Maximum Network Flow

Run Param

graph: Graph, // weighted, directed, no self loop
Spos: number, // id of source node
Tpos: number  // id of target node 

edge.datum:
  flow: number
    description: maximum flow of $this

Step Info

node.datum:
  depth: number
    defalut: -1
    description: depth of $this, generated by BFS starting from $Tpos
edge.datum:
  flow: number
    description: maximum flow of $this
  used: number
    defalut: 0
    description: used flow of $this
  mark: number
    defalut: 0
    description: direction of $this in augmenting path
    enum:
      - 0: $this not in augumenting path
      - 1: same direction of $this
      - -1: opposite direction of $this
  valid: number
    defalut: 0
    description: valid direction of $this
    enum:
      - 0: none direction of $this
      - 1: same direction of $this
      - -1: opposite direction of $this

Return Value

{flow: number}

Minimum-Cost Network Flow

file: ./MinCostFlow.ts

class: MinCostFlow

classic algorithm for Minimum-Cost Network Flow

Run Param

graph: Graph, // weighted, directed, no self loop
Spos: number, // id of source node
Tpos: number, // id of target node
limit: number = Infinity // limitation of total flow, defalut: infinity

edge.datum:
  flow: number
    description: maximum flow of $this
  cost: number
    description: cost per flow of $this

Step Info

node.datum:
  dist: number
    default: Infinity
    description: minimum distance of $this from $Spos 
edge.datum:
  flow: number
    description: maximum flow of $this
  used: number
    defalut: 0
    description: used flow of $this
  cost: number
    description: cost per flow of $this
  mark: number
    defalut: 0
    description: direction of $this in augmenting path
    enum:
      - 0: $this not in augumenting path
      - 1: same direction of $this
      - -1: opposite direction of $this
  valid: number
    default: 0
    enum:
      - 0: $this not on SSSP Graph
      - 1: $this on SSSP Graph

Return Value

{flow: number, cost: number}

file: ./ZkwMCF.ts

class: ZkwMCF

Zkw's algorithm for Minimum-Cost Network Flow

Run Param

graph: Graph, // weighted, directed, no self loop
Spos: number, // id of source node
Tpos: number, // id of target node
limit: number = Infinity // limitation of total flow, defalut: infinity

edge.datum:
  flow: number
    description: maximum flow of $this
  cost: number
    description: cost per flow of $this

Step Info

node.datum:
  dist: number
    default: Infinity
    description: minimum distance of $this from $Spos 
edge.datum:
  flow: number
    description: maximum flow of $this
  used: number
    defalut: 0
    description: used flow of $this
  cost: number
    description: cost per flow of $this
  mark: number
    defalut: 0
    description: direction of $this in augmenting path
    enum:
      - 0: $this not in augumenting path
      - 1: same direction of $this
      - -1: opposite direction of $this
  valid: number
    default: 0
    enum:
      - 0: $this not on SSSP Graph
      - 1: $this on SSSP Graph

Return Value

{flow: number, cost: number}