おねえさんを組み合わせ爆発から救う：格子グラフを生成する

先月、組み合わせ爆発を数えるおねえさんが話題になりました。
http://d.hatena.ne.jp/nowokay/20120911#1347338066


結びになっている、「おねえさんに教えてあげたい・・・」をこっちにも教えてもらいたかったので、いろいろ調べてみました。
とりあえず、格子のグラフを作る必要があるっぽいので、まずはそのグラフの生成から。
こんな感じのグラフが作成されます。

ここで、左上を始点、右下を終点として、始点から近い順に頂点に番号を振って、幅優先で辺を生成してるところがあとで大切になります。


ネタバレしておくと、この、グラフでの経路の数え上げ問題は、クヌース先生の「The Art of Computer Programming Volume 4, Fascicle 1」の7.1.4二分決定図の章の演習問題225として載っています。

The Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms 日本語版 (ASCII Addison Wesley Programming Se)

The Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms 日本語版 (ASCII Addison Wesley Programming Se)

解答みてもよくわからんのですけど。simpathで検索すると、他の人の解説が出てくるので、それを参考にします。


目次
『フカシギの数え方』 おねえさんといっしょにみんなも25万年数えよう
おねえさんを組み合わせ爆発から救う：格子グラフを生成する
おねえさんを組み合わせ爆発から救う：2分決定木を作る
おねえさんを組み合わせ爆発から救う：無駄を省いてBDDを作る
おねえさんを組み合わせ爆発から救う：ZDDがおねえさんを救う
おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった


とりあえず、格子グラフ生成プログラムのソース

package simpath;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;

public class CreateLattice {
    /**
     * ノード
     */
    public static class LatticeNode{
        int x;
        int y;
        
        int num;
        
        public LatticeNode(int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }
    }
    
    /**
     * エッジ
     */
    public static class LatticeEdge{
        LatticeNode from;
        LatticeNode to;
        
        public LatticeEdge(LatticeNode from, LatticeNode to) {
            this.from = from;
            this.to = to;
        }
        
        @Override
        public String toString() {
            return String.format("%d:%d", from.num, to.num);
        }
        
    }
    public static void main(String[] args) throws IOException{
        List<LatticeEdge> edges = new ArrayList<>();
        Map<Integer, LatticeNode> nodeMap = new LinkedHashMap<>();
        
        generateGraph(3, nodeMap, edges);
        //描画
        BufferedImage img = new BufferedImage(300, 300, BufferedImage.TYPE_INT_RGB);
        Graphics g = img.getGraphics();
        g.setColor(Color.WHITE);
        g.fillRect(0, 0, 300, 300);
        g.setColor(Color.BLACK);
        int gap = 80;int offset = 15;
        //エッジ描画
        ((Graphics2D)g).setStroke(new BasicStroke(1, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND,
                1, new float[]{2, 4}, 0));
        for(LatticeEdge re : edges){
            g.drawLine(re.from.x * gap + offset, re.from.y * gap + offset,
                    re.to.x * gap + offset, re.to. y * gap + offset);
            g.drawString(re.toString(), (re.from.x + re.to. x) * gap / 2 + offset,
                    (re.from.y + re.to.y) * gap / 2 + offset);
        }
        //ノード描画
        ((Graphics2D)g).setStroke(new BasicStroke(1));
        for(LatticeNode nd : nodeMap.values()){
            int x = nd.x * gap + offset - 10;
            int y = nd.y * gap + offset - 10;
            g.setColor(Color.WHITE);
            g.fillOval(x, y, 20, 20);
            g.setColor(Color.BLACK);
            g.drawOval(x, y, 20, 20);
            g.drawString(nd.num + "", x + 7, y + 14);
            
        }
        g.dispose();
        
        //保存
        //ImageIO.write(img, "png", new File("c:/Users/naoki/Desktop/lattice.png"));
        
        //表示
        JFrame jf = new JFrame("lattice");
        jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        JLabel l = new JLabel(new ImageIcon(img));
        jf.add(l);
        jf.setSize(400, 350);
        jf.setVisible(true);
    }
    
    static void generateGraph(int size, Map<Integer, LatticeNode> nodeMap, List<LatticeEdge> edges) {
        LatticeNode root = new LatticeNode(0, 0, 1);
        nodeMap.put(0, root);
        
        List<LatticeNode> tempNodes = Collections.singletonList(root);
        int counter = root.num;
        while(!tempNodes.isEmpty()){
            List<LatticeNode> nextNodes = new ArrayList<>();
            int maxCount = counter;
            for(LatticeNode rn : tempNodes){
                if(rn.x + 1 < size){
                    //横へ
                    maxCount = getNode(size, rn, rn.x + 1, rn.y, nodeMap, nextNodes, edges, maxCount);
                }
                if(rn.y + 1 < size){
                    //下へ
                    maxCount = getNode(size, rn, rn.x, rn.y + 1, nodeMap, nextNodes, edges, maxCount);
                }
            }
            counter = maxCount;
            tempNodes = nextNodes;
        }
    }
    
    static int getNode(int size, LatticeNode rn, int x, int y, Map<Integer, LatticeNode> nodeMap, List<LatticeNode> nextNodes, List<LatticeEdge> edges, int counter){
        int idx = x + y * size;
        LatticeNode nn = nodeMap.get(idx);
        if(nn == null){
            nn = new LatticeNode(x, y, counter + 1);
            nodeMap.put(idx, nn);
            nextNodes.add(nn);
        }

        edges.add(new LatticeEdge(rn, nn));
        
        return nn.num;
    }
}