fork download
copy 
  1. class RandomizedGlobalMinCut; end
  2. class << RandomizedGlobalMinCut
  3.   private
  4.   def make_graph_representation(es)
  5.     ve = {}; ev = {}; v_living = []; e_living = []; v_max = -1
  6.     es.each.with_index do |vs,i|
  7.       v0,v1 = vs
  8.       ve[v0] ? (ve[v0] << i):(ve[v0] = [i])
  9.       ve[v1] ? (ve[v1] << i):(ve[v1] = [i])
  10.       ev[i] = [v0,v1]
  11.       v_living << v0; v_living << v1; e_living << i
  12.       m = [v0,v1].max
  13.       v_max = m if v_max < m
  14.     end
  15.     [ve,ev,v_living.uniq,e_living,v_max]
  16.   end
  17.   def calc_main(g)
  18.     ve,ev,v_living,e_living,v_max = g
  19.     closure = {}
  20.     v_living.each do |v|
  21.       closure[v] = [v]
  22.     end
  23.     while v_living.length > 2
  24.       e = e_living[Random.rand(e_living.length)]
  25.       v0,v1 = ev[e]
  26.       v = v_max+1
  27.       [v0,v1].each do |w|
  28.         ve[w].each do |f|
  29.           ev[f].map!{|x| x == w ? v : x}
  30.         end
  31.       end
  32.       ve[v] = (ve[v0].select{|x|x!=e} + ve[v1].select{|x|x!=e}).uniq
  33.       ve.delete(v0); ve.delete(v1); ev.delete(e)
  34.       v_living = v_living - [v0,v1] + [v]
  35.       e_living = e_living - [e]
  36.       closure[v] = (closure[v0] + closure[v1]).uniq
  37.       v_max += 1
  38.     end
  39.     v0,v1 = v_living
  40.     [closure[v0],closure[v1]]
  41.   end
  42.   def cut_val(es, cut)
  43.     count = 0
  44.     es.each do |e|
  45.       count += 1 if cut[0].include?(e[0]) && cut[1].include?(e[1]) || cut[1].include?(e[0]) && cut[0].include?(e[1])
  46.     end
  47.     count
  48.   end
  49.   public
  50.   def calc(es)
  51.     g = make_graph_representation(es)
  52.     vn = g[2].length
  53.     iter_n = ((vn*(vn-1)/2)*Math.log(vn)).ceil
  54.     min_cut = nil
  55.     min_val = 10**10
  56.     iter_n.times do
  57.       g = make_graph_representation(es)
  58.       cut = calc_main(g)
  59.       val = cut_val(es,cut)
  60.       if val < min_val
  61.         min_val = val
  62.         min_cut = cut
  63.       end
  64.     end
  65.     [min_val,min_cut]
  66.   end
  67. end
  68.  
  69. def k_n(n)
  70.   es = []
  71.   (0...n).each do |j|
  72.     (j...n).each do |i|
  73.       es << [i,j] if i != j
  74.     end
  75.   end
  76.   es
  77. end
  78.  
  79. if __FILE__ == $0
  80.   p RandomizedGlobalMinCut::calc(k_n(13))
  81. end
Success #stdin #stdout 0.35s 7608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[12, [[3], [12, 6, 4, 1, 11, 10, 8, 7, 2, 5, 0, 9]]]
https://ideone.com/t3juju
language:
Ruby (ruby 2.5.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!