おねえさんを組み合わせ爆発から救う：2分決定木を作る

おねえさんを組み合わせ爆発から救うために、まず格子グラフを作成しました。
http://d.hatena.ne.jp/nowokay/20121015#1350267331

こんどは、そのグラフの辺について、それぞれ通るか通らないかの組み合わせによって、始点から終点までの単純な経路になってるかどうか判定して、それをツリーとして表してみます。

右の実線に行く場合はその辺を通る、左の点線にいく場合はその辺は通らない、ということをあらわします。そして、最終的に始点から終点までの単純な経路になっている場合を「T」なっていない場合を「F」とします。
ここでは、1x1マスのグラフをあらわしているので、「1:3」と「3:4」を通る場合、つまり右に分岐する場合と、「1:2」と「2:4」を通る場合、右に分岐する場合だけが「T」となっています。

判定方法は、ツリーの途中では、始点と終点に入る辺が2本以上になるか、一点に入る辺が3本以上になった場合は単純な経路ではないとして、ツリーの最後では、始点と終点に入る辺があって、経路をたどったときに余りが出ない場合は単純な経路であるという判定をしています。経路をたどったときに余りがあるのは、関係ないところに閉路ができている場合なので、これを省いています。

この決定木の最後の葉の数は、２を辺の数乗したものになります。1マスの場合、辺の数は4本なので、2の4乗で16通りになります。2マスにすると、辺の数は12本なので、2の12乗通りで4096通りになります。3マスだと16777216通りと、探索範囲が爆発していくことがわかります。
辺の数は、マス数×(マス数+1)×2になります。つまり、計算量としてO(2^マス数^2)となるので、これではおねえさんがロボットになってしまうのも無理はありませんね。

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

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

今回のソースは汚いぞー。コンパイルと実行には、前回のソースも必要です。

package simpath;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.HeadlessException;
import java.awt.Stroke;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
import kis.jgraphsample.CreateLattice.LatticeEdge;

public class CreateTree {

    private static void check(EdgeNode root, int finish, Map<Integer, List<LatticeEdge>> counter, List<DiagramNode> lastLayer, boolean b) {
        if(!b){
            if(root.left == null){
                root.left = new LeafNode(false);
                lastLayer.add(root.left);
            }else{
                check((EdgeNode)root.left, finish, counter, lastLayer, b);
            }
            if(root.right == null){
                root.right = new LeafNode(false);
                lastLayer.add(root.right);
            }else{
                check((EdgeNode)root.right, finish, counter, lastLayer, b);
            }
        }else{
            if(root.left == null){
                root.left = new LeafNode(checkRoute(counter, finish));
                lastLayer.add(root.left);
            }else{
                //そのまま次のノードへ
                check((EdgeNode)root.left, finish, counter, lastLayer, b);
            }
            Map<Integer, List<LatticeEdge>> newcounter = new HashMap<>();
            for(Map.Entry<Integer, List<LatticeEdge>> me : counter.entrySet()){
                newcounter.put(me.getKey(), new ArrayList<>(me.getValue()));
            }
            counter = newcounter;
            //fromについて
            int num = root.edge.from.num;
            b = checkWrongRoute(counter, num, root.edge, finish);
            //toについて
            if(b){
                b = checkWrongRoute(counter, root.edge.to.num, root.edge, finish);
            }
            
            if(root.right == null){
                if(b){
                    root.right = new LeafNode(checkRoute(counter, finish));
                    lastLayer.add(root.right);
                }else{
                    root.right = new LeafNode(false);
                    lastLayer.add(root.right);
                }
            }else{
                check((EdgeNode)root.right, finish, counter, lastLayer, b);
            }
        }
    }

    static boolean checkWrongRoute(Map<Integer, List<LatticeEdge>> counter, int num, LatticeEdge edge, int finish) {
        boolean result = true;
        List<LatticeEdge> i = counter.get(num);
        if(i == null){
            i = new ArrayList<>();
            counter.put(num, i);
        }
        i.add(edge);
        if(num == 1 || num == finish){
            //入り口か出口に2本以上の辺があったらだめ
            if(i.size() > 1) result = false;
        }else{
            //一点に3本以上の辺が入ったらだめ
            if(i.size() > 2) result = false;
        }
        return result;
    }
    static boolean checkRoute(Map<Integer, List<LatticeEdge>> counter, int finish) {
        if(!counter.containsKey(1) || !counter.containsKey(finish)){
            //入り口か出口から辺が出てない
            return false;
        }
        for (Map.Entry<Integer, List<LatticeEdge>> me : counter.entrySet()) {
            if(me.getKey() == 1 || me.getKey() == finish) continue;
            if (me.getValue().size() == 1) {
                //切れてる道がある
                return false;
            }
        }
        return checkLoop(counter, finish);
    }
    static boolean checkLoop(Map<Integer, List<LatticeEdge>> counter, int finish) {
        int n = 1;
        for(;;){
            List<LatticeEdge> list = counter.get(n);
            int ne = 0;
            for(Iterator<LatticeEdge> ite = list.iterator(); ite.hasNext();){
                LatticeEdge next = ite.next();
                if(next.from.num == n){
                    ne = next.to.num;
                    ite.remove();
                }else if(next.to.num == n){
                    ne = next.from.num;
                    ite.remove();
                }else{
                    continue;
                }
                List<LatticeEdge> nextList = counter.get(ne);
                for(Iterator<LatticeEdge> jite = nextList.iterator(); jite.hasNext();){
                    LatticeEdge nedge = jite.next();
                    if(next.from.num == nedge.from.num && next.to.num == nedge.to.num){
                        jite.remove();
                    }
                }
                if(nextList.isEmpty()) counter.remove(ne);
                break;
            }
            if(list.isEmpty()){
                counter.remove(n);
            }
            if(ne == 0){
                System.out.println("disconnect");
                return false;
            }
            if(ne == finish) {
                return counter.isEmpty();
            }
            n = ne;
        }
        
    }


    public static abstract class DiagramNode{
        int x;
        int y;
        public void setPosition(int x, int y){
            this.x = x;
            this.y = y;
        }
        public void paint(Graphics2D g){};
    }
    static class EdgeNode extends DiagramNode{
        DiagramNode left;
        DiagramNode right;
        CreateLattice.LatticeEdge edge;

        public EdgeNode(LatticeEdge edge) {
            this.edge = edge;
        }

        @Override
        public void paint(Graphics2D g) {
            String name = edge.toString();
            g.setColor(Color.WHITE);
            Rectangle2D rect = g.getFont().getStringBounds(name, g.getFontRenderContext());
            int w = (int) rect.getWidth();
            int h = (int) rect.getHeight();
            g.fillRoundRect(x - w / 2 - 2, y - h / 2 - 2, w + 4, h + 4, 15, 15);
            g.setColor(Color.BLACK);
            g.drawRoundRect(x - w / 2 - 2, y - h / 2 - 2, w + 4, h + 4, 15, 15);
            g.drawString(name, x - w / 2, y + h / 2 - 2);
        }
        
    }
    static class LeafNode extends DiagramNode{
        boolean value;

        public LeafNode(boolean value) {
            this.value = value;
        }

        @Override
        public void paint(Graphics2D g) {
            if(value){
                g.setColor(Color.WHITE);
            }else{
                g.setColor(Color.LIGHT_GRAY);
            }
            g.fillRect(x - 8, y - 8, 16, 16);
            g.setColor(Color.BLACK);
            g.drawRect(x - 8, y - 8, 16, 16);
            g.drawString(value ? "T" : "F", x - 4, y + 4);
        }
        
    }
    public static void main(String[] args){
        List<CreateLattice.LatticeEdge> edges = new ArrayList<>();
        Map<Integer, CreateLattice.LatticeNode> nodeMap = new LinkedHashMap<>();
        
        CreateLattice.generateGraph(2, nodeMap, edges);
        
        List<List<DiagramNode>> layers = new ArrayList<>();
        List<DiagramNode> layer = new ArrayList<>();
        for(CreateLattice.LatticeEdge ln : edges){
            if(layer.isEmpty()){
                //ルート
                layer.add(new EdgeNode(ln));
            }else{
                List<DiagramNode> nextLayer = new ArrayList<>();
                for(DiagramNode dn : layer){
                    if(dn instanceof EdgeNode){
                        EdgeNode en = (EdgeNode) dn;
                        EdgeNode left = new EdgeNode(ln);
                        en.left = left;
                        nextLayer.add(left);
                        EdgeNode right = new EdgeNode(ln);
                        en.right = right;
                        nextLayer.add(right);
                    }
                }
                layer = nextLayer;
            }
            layers.add(layer);
        }
        
        List<DiagramNode> lastLayer = new ArrayList<>();
        Map<Integer, List<LatticeEdge>> counter = new HashMap<>();
        EdgeNode root = (EdgeNode) layers.get(0).get(0);
        check(root, nodeMap.size(), counter, lastLayer, true);
        layers.add(lastLayer);
        
        int count = 0;
        for(DiagramNode dn : lastLayer){
            if(dn instanceof LeafNode){
                if(((LeafNode)dn).value) ++count;
            }
        }
        System.out.printf("%d/%d%n", count, lastLayer.size());
        //if(true)return;
        paintDiagram(layers, 700, 400, 40, 70);
    }
    static void paintDiagram(List<List<DiagramNode>> layers, int width, int height, int step, int gap) throws HeadlessException {
        //描画
        //位置決め
        int y = 15;
        for(List<DiagramNode> l : layers){
            int x = (width - l.size() * step) / 2;
            for(DiagramNode dn : l){
                dn.x = x;
                dn.y = y;
                x += step;
            }
            
            y += gap;
        }
        //
        Stroke plain = new BasicStroke(1);
        Stroke dotted = new BasicStroke(1, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND, 1, new float[]{2, 4},0);
        BufferedImage img = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = (Graphics2D) img.getGraphics();
        g.setColor(Color.WHITE);
        g.fillRect(0, 0, width, height);
        g.setColor(Color.BLACK);
        for(List<DiagramNode> l : layers){
            for(DiagramNode dn : l){
                if(dn instanceof EdgeNode){
                    EdgeNode en = (EdgeNode) dn;
                    if(en.right != null){
                        g.setStroke(plain);
                        g.drawLine(en.x + 2, en.y, en.right.x + 2, en.right.y);
                    }
                    if(en.left != null){
                        g.setStroke(dotted);
                        g.drawLine(en.x - 2, en.y, en.left.x - 2, en.left.y);
                    }
                }
                g.setStroke(plain);
                dn.paint(g);
            }
            
        }
        /*
         * try {
         * ImageIO.write(img, "png", new File("tree.png"));
         * } catch (IOException ex) {
         * }*/
        //表示
        JFrame jf = new JFrame("tree");
        jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        jf.setSize(width + 20, height + 50);
        JLabel lbl = new JLabel(new ImageIcon(img));
        jf.add(lbl);
        jf.setVisible(true);
    }
}