Class: MaxFlow

Inherits:
Object
  • Object
show all
Defined in:
lib/max_flow.rb

Overview

MaxFlowGraph

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ MaxFlow

Returns a new instance of MaxFlow.



3
4
5
6
7
 
# File 'lib/max_flow.rb', line 3

def initialize(n)
  @n   = n
  @pos = []
  @g   = Array.new(n) { [] }
end

Instance Method Details

#[](i) ⇒ Object Also known as: get_edge, edge

return edge = [from, to, cap, flow]



38
39
40
41
42
43
44
45
 
# File 'lib/max_flow.rb', line 38

def [](i)
  from, from_id = @pos[i]

  to, to_id, cap = @g[from][from_id]    # edge
  _from, _from_id, flow = @g[to][to_id] # reverse edge

  [from, to, cap + flow, flow]
end

#add(x, to = nil, cap = nil) ⇒ Object 



28
29
30
 
# File 'lib/max_flow.rb', line 28

def add(x, to = nil, cap = nil)
  cap ? add_edge(x, to, cap) : add_edges(x)
end

#add_edge(from, to, cap) ⇒ Object 



9
10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/max_flow.rb', line 9

def add_edge(from, to, cap)
  edge_number = @pos.size

  @pos << [from, @g[from].size]

  from_id = @g[from].size
  to_id   = @g[to].size
  to_id += 1 if from == to
  @g[from] << [to,   to_id,   cap]
  @g[to]   << [from, from_id, 0]

  edge_number
end

#add_edges(edges) ⇒ Object 



23
24
25
26
 
# File 'lib/max_flow.rb', line 23

def add_edges(edges)
  edges.each{ |from, to, cap| add_edge(from, to, cap) }
  self
end

#change_edge(i, new_cap, new_flow) ⇒ Object 



57
58
59
60
61
62
63
64
 
# File 'lib/max_flow.rb', line 57

def change_edge(i, new_cap, new_flow)
  from, from_id = @pos[i]

  e = @g[from][from_id]
  re = @g[e[0]][e[1]]
  e[2]  = new_cap - new_flow
  re[2] = new_flow
end

#edges ⇒ Object 



49
50
51
52
53
54
55
 
# File 'lib/max_flow.rb', line 49

def edges
  @pos.map do |(from, from_id)|
    to, to_id, cap = @g[from][from_id]
    _from, _from_id, flow = @g[to][to_id]
    [from, to, cap + flow, flow]
  end
end

#flow(s, t, flow_limit = 1 << 64) ⇒ Object Also known as: max_flow 



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/max_flow.rb', line 66

def flow(s, t, flow_limit = 1 << 64)
  flow = 0
  while flow < flow_limit
    level = bfs(s, t)
    break if level[t] == -1

    iter = [0] * @n
    while flow < flow_limit
      f = dfs(t, flow_limit - flow, s, level, iter)
      break if f == 0

      flow += f
    end
  end

  flow
end

#min_cut(s) ⇒ Object 



85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/max_flow.rb', line 85

def min_cut(s)
  visited = Array.new(@n, false)
  que = [s]
  while (q = que.shift)
    visited[q] = true
    @g[q].each do |(to, _rev, cap)|
      if cap > 0 && !visited[to]
        visited[to] = true
        que << to
      end
    end
  end
  visited
end

#push(edge) ⇒ Object Also known as: << 



32
33
34
 
# File 'lib/max_flow.rb', line 32

def push(edge)
  add_edge(*edge)
end