examples/graph/minimum_spanning_tree.rb in wukong-3.0.0.pre vs examples/graph/minimum_spanning_tree.rb in wukong-3.0.0.pre2

@@ -1,73 +1,73 @@
-require Pathname.path_to(:examples, 'graph/union_find')
-require 'gorillib/model/serialization'
+# require Pathname.path_to(:examples, 'graph/union_find')
+# require 'gorillib/model/serialization'
 
-class Airfare
-  include Gorillib::Model
+# class Airfare
+#   include Gorillib::Model
 
-  field :from,  String
-  field :into,  String
-  field :price, Integer
-  field :from_name, String
-  field :into_name, String
+#   field :from,  String
+#   field :into,  String
+#   field :price, Integer
+#   field :from_name, String
+#   field :into_name, String
 
-  def undirected_edge
-    [from, into].sort
-  end
-end
+#   def undirected_edge
+#     [from, into].sort
+#   end
+# end
 
 
-airfares = File.open(Pathname.path_to(:data, 'graph/airfares.tsv')).
-  readlines.
-  map{|line| line.split("\t").map(&:strip) }.
-  map{|vals| Airfare.from_tuple(*vals) }
+# airfares = File.open(Pathname.path_to(:data, 'graph/airfares.tsv')).
+#   readlines.
+#   map{|line| line.split("\t").map(&:strip) }.
+#   map{|vals| Airfare.from_tuple(*vals) }
 
-# airfares.sort_by(&:undirected_edge).each do |airfare|
-#   puts "%-7s\t%-7s\t%-7s\t%-7s\t%d" % [*airfare.undirected_edge, airfare.from, airfare.into, airfare.price]
-# end
+# # airfares.sort_by(&:undirected_edge).each do |airfare|
+# #   puts "%-7s\t%-7s\t%-7s\t%-7s\t%d" % [*airfare.undirected_edge, airfare.from, airfare.into, airfare.price]
+# # end
 
-cities = airfares.map(&:from).uniq | airfares.map(&:into)
+# cities = airfares.map(&:from).uniq | airfares.map(&:into)
 
-edges   = {}
-airfares.each do |airfare|
-  edge = airfare.undirected_edge
-  edges[edge] = airfare.price unless edges.include?(edge) && edges[edge] <= airfare.price
-end
+# edges   = {}
+# airfares.each do |airfare|
+#   edge = airfare.undirected_edge
+#   edges[edge] = airfare.price unless edges.include?(edge) && edges[edge] <= airfare.price
+# end
 
-mst = Hash.new{|h,k| h[k] = {} }
-forest = Wukong::Widget::DisjointForest.new
+# mst = Hash.new{|h,k| h[k] = {} }
+# forest = Wukong::Widget::DisjointForest.new
 
-edges.sort_by(&:last).each do |(city_a, city_b), price|
-  forest.add(city_a) if not forest.include?(city_a)
-  forest.add(city_b) if not forest.include?(city_b)
-  next if forest.find(city_a) == forest.find(city_b)
-  forest.union(city_a, city_b)
-  mst[city_a][city_b] = price
-end
+# edges.sort_by(&:last).each do |(city_a, city_b), price|
+#   forest.add(city_a) if not forest.include?(city_a)
+#   forest.add(city_b) if not forest.include?(city_b)
+#   next if forest.find(city_a) == forest.find(city_b)
+#   forest.union(city_a, city_b)
+#   mst[city_a][city_b] = price
+# end
 
-$mst_both = Hash.new{|h,k| h[k] = {} }
-mst.each{|city_a, hsh| hsh.each{|city_b, price|
-    $mst_both[city_a][city_b] = price
-    $mst_both[city_b][city_a] = price
-}}
-def dfs(city, seen)
-  seen << city
-  children = $mst_both[city].keys - seen
-  # [children, children.map{|child| dfs(child, seen) } ]
-  children.map{|child| [ child, dfs(child, seen) ] }
-end
-sorted_cities = ['LAS', dfs('LAS', [])]
+# $mst_both = Hash.new{|h,k| h[k] = {} }
+# mst.each{|city_a, hsh| hsh.each{|city_b, price|
+#     $mst_both[city_a][city_b] = price
+#     $mst_both[city_b][city_a] = price
+# }}
+# def dfs(city, seen)
+#   seen << city
+#   children = $mst_both[city].keys - seen
+#   # [children, children.map{|child| dfs(child, seen) } ]
+#   children.map{|child| [ child, dfs(child, seen) ] }
+# end
+# sorted_cities = ['LAS', dfs('LAS', [])]
 
-gv_filename = Pathname.path_to(:tmp, 'airfares_mst')
-File.open("#{gv_filename}.dot", 'w') do |gv_file|
-  gv_file.puts "graph AirfareMST {\n  label=\"#{Time.now}\"; height= 800; labelloc = t; mindist = 1.5 ; "
-  # gv_file.puts "mode = hier;"
-  gv_file.puts 'node [ shape = "plaintext" ]; '
-  sorted_cities.flatten.each{|city| gv_file.puts "  #{city};" }
-  mst.sort_by(&:first).each do |from, hsh|
-    hsh.sort_by(&:first).each do |into, price|
-      gv_file.puts " %-7s -- %-7s [ label = \"%d\" ];" % [from, into, price]
-    end
-  end
-  gv_file.puts "}"
-end
-`neato -Tpng #{gv_filename}.dot -o #{gv_filename}.png`
+# gv_filename = Pathname.path_to(:tmp, 'airfares_mst')
+# File.open("#{gv_filename}.dot", 'w') do |gv_file|
+#   gv_file.puts "graph AirfareMST {\n  label=\"#{Time.now}\"; height= 800; labelloc = t; mindist = 1.5 ; "
+#   # gv_file.puts "mode = hier;"
+#   gv_file.puts 'node [ shape = "plaintext" ]; '
+#   sorted_cities.flatten.each{|city| gv_file.puts "  #{city};" }
+#   mst.sort_by(&:first).each do |from, hsh|
+#     hsh.sort_by(&:first).each do |into, price|
+#       gv_file.puts " %-7s -- %-7s [ label = \"%d\" ];" % [from, into, price]
+#     end
+#   end
+#   gv_file.puts "}"
+# end
+# `neato -Tpng #{gv_filename}.dot -o #{gv_filename}.png`