shitty algorithm to solve the minimum cut

mincut.rb

def non_cyclical_paths adjacency, &block
  adjacency.each do |current, associations|
    _non_cyclical_paths adjacency, [current], &block
  end
end

def _non_cyclical_paths adjacency, path, &block
  current = path.last
  adjacency[current].each do |adjacent|
    next if path.include? adjacent
    new_path = path + [adjacent]
    block.call(new_path)
    _non_cyclical_paths adjacency, new_path, &block
  end
end

# a -- b
# |  \ |
# c -- d -- e
edges = [
  [:a, :b],
  [:a, :c],
  [:a, :d],
  [:b, :d],
  [:c, :d],
  [:d, :e],
]

adjacency = edges.each_with_object({}) { |(left, right), a|
  a[left]  ||= []
  a[right] ||= []
  a[left]  << right
  a[right] << left
}
nodes  = edges.flatten.uniq

counts = nodes.map { |n| [n, Hash.new(0)] }.to_h
non_cyclical_paths adjacency do |path|
  first, *, last = path
  counts[first][last] += 1
end

counts
# => {:a=>{:b=>3, :d=>3, :c=>3, :e=>3},
#     :b=>{:a=>3, :c=>4, :d=>3, :e=>3},
#     :c=>{:a=>3, :b=>4, :d=>3, :e=>3},
#     :d=>{:a=>3, :b=>3, :c=>3, :e=>1},
#     :e=>{:d=>1, :a=>3, :b=>3, :c=>3}}

counts.map { |node, node_counts| node_counts.values.min } # => [3, 3, 3, 1, 1]
      .min                                                # => 1