『今流行のお題を出してみた』に Groovy で挑戦
お題：はてなブログに移行しました
問題をみて「グラフが強連結であること」ってところまでは調べたんだが
強連結であることを判定するアルゴリズムはあっても強連結なグラフを作るものがみあたらない。
何回かグラフ関連のアルゴリズムをあさっていたら気がついた。
ある点から全域木を2回張って一方は葉へもう一方は根へ移動すれば全ての点からある点を経由してどの点にも移動できる。
全域木は最小である必要はないが一方を最小、一方を最大*1とした。
グラフのアルゴリズムは実装しても*2よかったがライブラリの解説ページがあったのでそれを使用することにした。
いくつか自分の中でも未解決なことがあるので間違っているかも知れない。
- サンプルを参考に実装してみただけなので意味がわかっていない箇所がある*3
- ランダムに重みをつけて最小全域木を求めると辺の数が 99 になるのだがこれは固定なんだろうか？
- そうであれば最悪往復で重複がなくても 198 / 360 で 55% にはなる
- ある点を一致させる処理は入っていないが一致しているのか
- 強連結を判定するアルゴリズムを見つけられなかったのでテストしていない
サンプルの実行*4
@Grab(group='net.sf.jung', module='jung-samples', version='2.0.1') import edu.uci.ics.jung.samples.* MinimumSpanningTreeDemo.main([] as String[])
解答*5
@Grab(group='net.sf.jung', module='jung-graph-impl', version='2.0.1') @Grab(group='net.sf.jung', module='jung-io', version='2.0.1') @Grab(group='net.sf.jung', module='jung-visualization', version='2.0.1') import java.awt.Dimension; import java.awt.geom.Point2D; import javax.swing.JFrame; import edu.uci.ics.jung.algorithms.layout.* import edu.uci.ics.jung.graph.* import edu.uci.ics.jung.graph.util.* import edu.uci.ics.jung.io.* import edu.uci.ics.jung.visualization.* import edu.uci.ics.jung.algorithms.shortestpath.* import org.apache.commons.collections15.Transformer final int MAX = 5 final int W = 10 final int H = 10 final int SIZE = 500 final int MARGIN = 100 def edgeNum = 0 // 辺の番号 def graph = new UndirectedSparseGraph() // 全ての辺があるグラフ [1..W, 1..H].combinations().eachWithIndex { p, i -> if (p[0] != W) graph.addEdge(edgeNum++, p, [p[0]+1, p[1]]) if (p[1] != H) graph.addEdge(edgeNum++, p, [p[0], p[1]+1]) } def weights1 = { e -> Math.floor(Math.random() * MAX) }.memoize() as Transformer def weights2 = { e -> MAX - weights1.transform(e) }.memoize() as Transformer // 最小全域木を求める // root -> 他のノード & 他のノード -> root => 全てのノード間で移動可能 graph1 = new PrimMinimumSpanningTree(DelegateTree.getFactory(), weights1).transform(graph) graph2 = new PrimMinimumSpanningTree(DelegateTree.getFactory(), weights2).transform(graph) // rootをあわせる必要があると思ったが一致するのでとりあえずこのまま assert graph1.root == graph2.root graph2.edges.each { e -> def pair = graph2.getEndpoints(e) if (graph1.findEdge(pair.second, pair.first) == null) { graph1.addEdge(edgeNum++, new Pair(pair.second, pair.first), EdgeType.DIRECTED) } } assert 0.60 >= graph1.edges.size() / (4 * W * H - 2 * (W + H)) // Layout def layout = new StaticLayout(graph1) graph1.vertices.each { v -> layout.setLocation(v, new Point2D.Double(SIZE / W * v[0], SIZE / H * v[1])) } // GraphML フォーマットで XML を出力 if (args && args[0] == 'xml') { new GraphMLWriter().save(graph1, new PrintWriter(System.out)) return } // Swing で表示 def panel = new BasicVisualizationServer(layout, new Dimension(SIZE + MARGIN, SIZE + MARGIN)) def frame = new JFrame("Maze") frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE) frame.getContentPane().add(panel) frame.pack() frame.setVisible(true)
これを Haskell に移植はまだ無理。
まずは id:route150 氏の http://d.hatena.ne.jp/route150/20110409/1302358656 を読めるようにならないと。*6
2011-04-11 追記
できるだけ往路と復路で被らないようにしていたけど被った方が % が下がるので両方ランダムにしてみたら 50%弱になった。
def weights1 = { e -> Math.random() }.memoize() as Transformer def weights2 = { e -> Math.random() }.memoize() as Transformer
できるだけ往路と同じパスになるようにしてみたが大して下がらなかった。
def graph1, graph2 def weights1 = { e -> Math.random() }.memoize() as Transformer def weights2 = { e -> def pair = graph.getEndpoints(e) graph1.findEdge(pair.second, pair.first) != null ? 0.0d : 1.0d }.memoize() as Transformer
考えてみたら往路の葉から戻ってくる必要はあるが途中のノードから戻ってくる必要はないから全域木で戻ってくる限りあまり変わらない。
% はどこまで下げられるか追求すると巡回セールスマン問題になるような気がする。全ての部屋に1回入るから 100/360 で 27% 以下にはならない。*7
他のみんなのプログラムを調べながら読んでいるところだけど検索していたら Rosetta Code を発見した。2007年からあるみたいだが、はてなではあまりブックマークされていないみたいだ。偶然なんだけど、みんなに感謝する。
