Реализация графа с несколькими родителями и детьми - PullRequest
Новая
       49

Реализация графа с несколькими родителями и детьми

2 голосов
/ 25 января 2020

Мне нужно реализовать древовидную структуру данных, где у каждого узла есть несколько родителей и потомков и, следовательно, несколько корней.

Новые узлы будут добавляться в дерево только как root без родителей или дочерний элемент от одного или нескольких родителей.

Узлы не будут начинаться с дочерних узлов, но любой существующий узел может получить другой дочерний узел с любым количеством других родительских узлов

tree example

1 Ответ

0 голосов
/ 26 января 2020

Я смог создать класс Node и класс Graph. Я дал каждому Node a List<Node> их родительский и дочерний узлы.

Каждый Node отслеживает своих непосредственных детей и родителей.

Реализация узла 

public class Node<T>{
    private T data;
    private List<Node<T>> parents;
    private List<Node<T>> children = new ArrayList<>();//this can be initialized because a node will not start with children
    public Node(T data){//adding a node without parents
        this.data = data;
        parents = new ArrayList<>();//make parents an empty ArrayList so other methods won't break with a null value
    }
    public Node(T data, List<Node<T>> parents){//adding a node with parents
        this.data = data;
        this.parents = parents;
    }

    //search methods
    public List<Node<T>> getChildren(){return children;}//return only direct children
    public List<Node<T>> getChildren(int level){return getChildren(new ArrayList<>(Collections.singletonList(this)),new ArrayList<>(),level);}//convenience method to find only this node's children to a certain level
    public List<Node<T>> getChildren(List<Node<T>> find, List<Node<T>> found, int level){//level can be -1 to search through all children or a positive integer to only search the first n level of children.
        if(level!=0){//setting level to -1 will never stop the search until all children have been found because level only goes down, because the level will never reach zero
            for(Node<T> node:find){//can find the children of multiple nodes
                if(node.hasChild()) {
                    for (Node<T> child : node.getChildren()) {
                        if (!found.contains(child)) {//trees can intersect, so the child may have already been found, so only add if it hasn't
                            found.add(child);
                        }
                    }
                    getChildren(node.getChildren(),found,level--);//recursively find the remaining children of the current node
                }
            }
        }
        return found;
    }
    //a method that finds parents can be implemented by modifying the getChildren() methods

    //examples of other methods that can be added
    public T getData(){return data;}
    public boolean hasChild(){return children.size()>0;}
    void addChild(Node<T> node){children.add(node);}
    void addChildren(List<Node<T>> nodes){children.addAll(nodes);}
    public List<Node<T>> getParents(){return parents;}
    public boolean hasParent(){return parents.size()>0;}
    void addParent(Node<T> node){parents.add(node);}
    void addParent(List<Node<T>> nodes){parents.addAll(nodes);}
}

Класс Graph используется только для отслеживания корней графа. root - это просто Node без родителей. Области применения каждого метода могут быть скорректированы для вашего конкретного c варианта использования. Предполагается, что этот класс будет расширен более конкретным c классом, который включает методы для работы с указанным вами c типом данных.

Реализация графика: 

public class Graph<T> {
    private List<Node<T>> roots;
    protected Tree(List<Node<T>> roots){this.roots = roots;}//Graph class can be initialized with or without existing roots 
    protected Tree(){roots = new ArrayList<>();}
    public List<Node<T>> getRoots(){return roots;}
    public List<Node<T>> getAllNodes(){
        List<Node<T>> nodes = roots.get(0).getChildren(roots,new ArrayList<>(),-1);//loop through all roots with an empty list for nodes already found, because no nodes have been found yet
        nodes.addAll(roots);
        return nodes;
    }
    public void addNode(Node<T> node){
        for(Node<T> parent:node.getParents()){//for each parent node add this node as their child
            parent.addChild(node);
        }
        if(!node.hasParent())roots.add(node);
    }
    public void addNodes(List<Node<T>> nodes){
        for(Node<T> node:nodes){
            addNode(node);
        }
    }
}

При добавлении new Node с родителями, класс Graph получает родителей и добавляет Node как потомок этих родителей, чтобы родительские узлы знали, что у них есть дочерний узел.

...