java - ツリーグラフを動的に作成し、その周りを歩きます

Question

外部ソースを使用して供給されるグラフがあります。これまでのところ、大まかな構造は次のようなものです。

TreeGraph、このようにフィットするように示されています。そこでは、赤い線はノードの兄弟を表しています。これは依存関係である可能性がありますが、親子関係自体ではありません。存在する場合と存在しない場合があります。

現在、ノードごとに次のコードがあります。



    public class TreeNode {    
        private int id;
        private int container; 
        private int status;
        private int value;  
        private boolean visited;
        private String node_name;       
        private ArrayList children = new ArrayList();
        private ArrayList siblings = new ArrayList();
        private ArrayList parents = new ArrayList();

        public TreeNode()
        {
            this.id = 0;
            this.status = 0;
            this.visited = false;
            this.node_name="";
        }
        //Getters and setters below.    
        //parents/siblings/children are added through addParent(treeNode);
    }

次に、値を設定するための次のコードがあります。



    public class TreeSetter {

        public static void main(String[] args) {

            TreeNode A = new TreeNode();        
            TreeNode B = new TreeNode();
            TreeNode C = new TreeNode();
            TreeNode D = new TreeNode();        
            TreeNode E = new TreeNode();
            TreeNode F = new TreeNode();
            TreeNode G = new TreeNode();
            TreeNode H = new TreeNode();

            A.setId(1);
            A.setNode_name("A");
            A.setStatus(1);
            A.addParent(null);

            B.setId(2);
            B.setNode_name("B");
            B.setStatus(1);
            B.addParent(A);
            A.addChildren(B);

            C.setId(3);
            C.setNode_name("C");
            C.setStatus(1);
            C.addParent(A);
            A.addChildren(C);

            D.setId(4);
            D.setNode_name("D");
            D.setStatus(1);
            D.addParent(A);
            A.addChildren(D);

            E.setId(5);
            E.setNode_name("E");
            E.setStatus(1);
            E.addParent(B);
            E.addParent(C);
            E.addParent(D);
            B.addChildren(E);
            C.addChildren(E);
            D.addChildren(E);
            E.addSiblings(F);
            E.addSiblings(G);
            E.addSiblings(H);       

            F.setId(6);
            F.setNode_name("F");
            F.setStatus(1);
            F.addParent(B);
            F.addParent(C);
            F.addParent(D);
            B.addChildren(F);
            C.addChildren(F);
            D.addChildren(F);
            F.addSiblings(E);
            F.addSiblings(G);
            F.addSiblings(H);

            G.setId(7);
            G.setNode_name("G");
            G.setStatus(1);
            G.addParent(B);
            G.addParent(C);
            G.addParent(D);
            B.addChildren(G);
            C.addChildren(G);
            D.addChildren(G);
            G.addSiblings(E);
            G.addSiblings(F);
            G.addSiblings(H);

            H.setId(8);
            H.setNode_name("H");
            H.setStatus(1);
            H.addParent(B);
            H.addParent(C);
            H.addParent(D);
            B.addChildren(H);
            C.addChildren(H);
            D.addChildren(H);
            H.addSiblings(E);
            H.addSiblings(F);
            H.addSiblings(G);
            //Set all other nodes

            //Set all node values.  
        }    
    }

だから、私が必要としているのは、Hが与えられたとすると、私は知る必要があるとしましょう：

H-> I-> L（H + I + L）からの値は何ですか
Hが変更された場合に影響を受けるのは誰か。H-> B、C、D-> A
Hの依存関係は何ですか？F、G、E。

これを考えると、私の問題は次のとおりです。

ツリーを動的に作成するにはどうすればよいですか？たとえば、12ノードではなく1000ノードがあるとします。私のコードを使用すると、すべてのオブジェクトを手動で作成しているため、値とリレーションを設定するためだけに多くの行が必要になります。1000個のオブジェクトを作成するには、リフレクション、ファクトリパラダイムを使用する必要がありますか？
どうやって木を歩くのですか？たとえば、Dが与えられた場合、D-> H-> I-> L（というように）移動します。再帰が最も簡単でクリーンな方法であることは知っていますが、それを実装する方法がわかりません:(

score 1 · Accepted Answer

ツリーを動的に作成するにはどうすればよいですか。

public class Tree {

    private class Node {
        public int value;
        public List<Node> = new children ArrayList<Node>();
        public List<Node> = new parents ArrayList<Node>();
        public static final INFINITY = Integer.MAX_VALUE;

        public void addChild(Node n) {
            children.add(n);
        }

        public void addParent(Node n) {
            parents.add(n);
        }

        public int getValue() {return value;}

        //What is the value from H -> I -> L (H+I+L):
        int getValueToNode(Node Destination, HashSet<Node> s) {
           int minValue = INFINITY;
           int value = 0;

           if(s.contains(this)) return INFINITY; //we already checked this
           s.add(this);
           if(this.equals(Destination)) return Destination.value();

           for(int i = 0; i < children.size(); i++) {
               Node c = children.get(i);
               int value = c.getValueToNode(Destination);
               if (value != Integer.MAX_VALUE && value < minValue) {
                   minValue = value + this.getValue();
               }
           }

           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               value = p.getValueToNode(Destination);
               if (value != Integer.MAX_VALUE && value < minValue) {
                   minValue = value + this.getValue();
               }
           }
           return minValue;
        }

        //Who will be affected if H changes. H -> B,C,D -> A
        public int getDependency(ArrayList<Node> affected) {
          for(int i = 0; i < children.size(); i++) {
               Node c = children.get(i);
               affected.add(c);
           }

           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               affected.add(p);
           }
        }

        //What are the dependencies of H? F, G, E.
        List<Node> getDependency() {
           List<Node> dependency = new ArrayList<Node>();
           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               for(int j= 0 ; j < p.children.size(); j++) {
                   Node c = p.children.get(i);
                   if(!c.equals(this)) dependency.add(c);
               }
           }
           return dependency;
        }
    }

    //data here.
    private Map<String, Node> mapping = new HashMap<String, Node>();

    public connectParentToChild(String parent, String child) {
        Node p = getNode(parent);
        Node c = getNode(child);
        p.addChild(c);
        c.addParent(p);
    }

    public int getValue(String first, String second) {
        a = getNode(first);
        b = getNode(second);
        HashSet<Node> s = new HashSet<Node>();
        return a.getValueToNode(b, s);
    }

    private Node getNode(String s) {
        if(!mapping.containsKey(s)) {
           mapping.put(s, new Node(...));
        }
        return mapping.get(s);
    }

    //members here.
}

これは、ノードを動的に追加する簡単な方法です。

public static void main(String[] args) {
    Tree t;
    t.connectParentToChild("A", "D");
    t.connectParentToChild("A", "B");
    t.connectParentToChild("A", "C");
    t.connectParentToChild("B", "C");
    t.connectParentToChild("B", "H");
    t.connectParentToChild("B", "F");
    t.connectParentToChild("B", "E");
    //Set all other nodes
    t.getValue("H", "L");
}

score 0 · Accepted Answer

public void printWholeNode(Node root) {
    if (root.getChildren().size() == 0) {
        if (root.visited == false) {
            System.out.println(root.name);
            root.visited = true;
        }
        return ;
    } else {
        System.out.println(root.name);
        root.visited = true;
        for (Node childNode : root.getChildren()) {
            printWholeNode(childNode);
        }
    }
}

java - ツリーグラフを動的に作成し、その周りを歩きます

2 に答える 2

Related

Reference