2011年2月1日火曜日

経路問題はウロボロスの香り

経路のパターンを洗い出す問題にて、
仕事場のプログラマーがいつまで経っても作れない…
ループする経路がないという限定条件なはずなんだけど…

というわけでサンプルを15分で書いて、
もう15分できれいにしたのがこちらです。
ハッシュテーブルに格納しているのは、
この方が実際に使うデータ構造に近かったからです。

public class Sandbox {

    public static void main(String[] args) {
        HashMap<String, Node> map = new HashMap<String, Node>();
        // ノードの作成
        map.put("A", new Node("A"));
        map.put("B", new Node("B"));
        map.put("C", new Node("C"));
        map.put("D", new Node("D"));
        map.put("E", new Node("E"));
        map.put("F", new Node("F"));
        map.put("G", new Node("G"));
        map.put("H", new Node("H"));
        map.put("I", new Node("I"));
        map.put("J", new Node("J"));
        map.put("K", new Node("K"));

        // ノードの連結
        map.get("A").addChildren(new Node[]{map.get("B"), map.get("C")});
        map.get("B").addChildren(new Node[]{map.get("D")});
        map.get("C").addChildren(new Node[]{map.get("D"), map.get("E")});
        map.get("D").addChildren(new Node[]{map.get("H"), map.get("I")});
        map.get("E").addChildren(new Node[]{map.get("F"), map.get("G")});
        map.get("F").addChildren(new Node[]{map.get("J")});
        map.get("G").addChildren(new Node[]{map.get("J")});
        map.get("H").addChildren(new Node[]{map.get("K")});
        map.get("I").addChildren(new Node[]{map.get("K")});
        map.get("J").addChildren(new Node[]{map.get("K")});
        map.get("K").addChildren(new Node[]{});

        // 走査を開始する
        preorder(map.get("A"), map.get("A").getValue());
    }

    public static void preorder(Node node, String message) {
        // 子供がいない場合
        if (node.getChildren().size() == 0) {
            System.out.println(message);
        }
        // 子供がいる場合
        for (Node t : node.getChildren()) {
            preorder(t, message + ":" + t.getValue());
        }
    }

    public static class Node {
        private String value = null;
        private ArrayList<Node> children = new ArrayList<Node>();

        public Node(String value) {
            this.value = value;
        }

        public String getValue() {
            return value;
        }

        public ArrayList<Node> getChildren() {
            return children;
        }

        public void addChildren(Node[] nodes) {
            for (Node n : nodes) {
                children.add(n);
            }
        }
    }
}

追記:TreeModelクラスなんてものが…見なかったことにしよう。

0 件のコメント:

コメントを投稿