Class: Equalshares::MaxFlow

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

Overview

Dinic's maximum-flow algorithm with integer capacities. Used by the maximin support rule to compute the exact minimum max-load (a max-density subgraph) via a parametric max-flow, keeping the gem pure-Ruby and dependency-free.

Instance Method Summary collapse

Constructor Details

#initialize(num_nodes) ⇒ MaxFlow

Returns a new instance of MaxFlow.



8
9
10
11
 
# File 'lib/equalshares/max_flow.rb', line 8

def initialize(num_nodes)
  @num_nodes = num_nodes
  @graph = Array.new(num_nodes) { [] } # node -> array of edges [to, cap, rev_index]
end

Instance Method Details

#add_edge(from, to, cap) ⇒ Object 



13
14
15
16
 
# File 'lib/equalshares/max_flow.rb', line 13

def add_edge(from, to, cap)
  @graph[from] << [to, cap, @graph[to].size]
  @graph[to] << [from, 0, @graph[from].size - 1]
end

#max_flow(source, sink) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
 
# File 'lib/equalshares/max_flow.rb', line 18

def max_flow(source, sink)
  flow = 0
  while build_levels(source, sink)
    @iter = Array.new(@num_nodes, 0)
    while (pushed = augment(source, sink, Float::INFINITY)).positive?
      flow += pushed
    end
  end
  flow
end

#reachable_from(source) ⇒ Object

Nodes reachable from source in the residual graph (the source side of a minimum cut after max_flow has run).



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/equalshares/max_flow.rb', line 31

def reachable_from(source)
  visited = Array.new(@num_nodes, false)
  visited[source] = true
  queue = [source]
  until queue.empty?
    node = queue.shift
    @graph[node].each do |edge|
      to, cap, = edge
      next unless cap.positive? && !visited[to]

      visited[to] = true
      queue << to
    end
  end
  visited
end