Обновление графика JGraphT работает неправильно

Я пытаюсь реализовать своего рода метод суммирования графа, где я проверяю, есть ли у узла какие-либо дочерние элементы или нет, если нет, то узел сворачивается в своего родителя. У меня есть 2 фрагмента кода для этого, но один из них не работает из-за ошибки в getEdgeSource, по крайней мере, я так думаю. При использовании 1-й реализации я могу пометить узлы, которые должны быть свернуты, после этого я снова перебираю все узлы в графе и добавляю их к соответствующему родителю, а затем удаляю их. Это работает отлично. Другой фрагмент кода должен делать то же самое, но узлы не добавляются к родителю, а только удаляются. Вот фрагменты ниже: Сначала мой класс Node:

public class Node implements Serializable{
    private static final long serialVersionUID = 1L;
    public String nodeID;
    public String timestamp;
    public ArrayList<Node> children = new ArrayList<Node>();
    public boolean tagged;
    public boolean isRoot;

    public Node(String a) {
        nodeID = a;
    }

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

    public int getSize(){
        return children.size();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof Node)) {
            return false;
        }
        Node other = (Node) obj;
        return this.nodeID.equals(other.nodeID);
    }
    @Override
    public int hashCode() {
        return nodeID.hashCode();
    }
}

(Рабочий код, но более сложная по времени):

    public void oneLevelCollapse(DirectedGraph<Node, Edge> graph) {
    graphCopy = (DirectedGraph<Node, Edge>) ((AbstractBaseGraph<Node, Edge>)graph).clone();

    // iterate over every node and tag nodes to collapse
    for (Node node : graphCopy.vertexSet()) {
        // remove node if it has no children and only one parent
        if (graphCopy.outDegreeOf(node) == 0 && graphCopy.inDegreeOf(node) == 1) {
            node.tagged = true;
        }
    }
    // iterate over every node again and collapse/delete
    for (Node node : graphCopy.vertexSet()) {
        for (Edge edge : graphCopy.outgoingEdgesOf(node)) {
            Node child = graph.getEdgeTarget(edge);
            if (child.tagged) {
                node.addChild(child);
                graph.removeVertex(child);
            }
        }
    }
}

(Код, который должен работать, но не работает):

public void oneLevelCollapse(DirectedGraph<Node, Edge> graph) {
    graphCopy = (DirectedGraph<Node, Edge>) ((AbstractBaseGraph<Node, Edge>)graph).clone();

    // iterate over every node and tag nodes to collapse
    for (Node node : graphCopy.vertexSet()) {
        // remove node if it has no children and only one parent
        if (graphCopy.outDegreeOf(node) == 0 && graphCopy.inDegreeOf(node) == 1) {
            for (Edge edge : graphCopy.incomingEdgesOf(node)) {
                graph.getEdgeSource(edge).addChild(node);
                graph.removeVertex(node);
            }
        }
    }

}

График не имеет циклов, график — это график, который я изменяю, сохраняя при этом копию исходного графика, который называется graphCopy.


java graph directed-acyclic-graphs jgrapht
person Kira    schedule 25.10.2016    source источник
comment
Пожалуйста, убедитесь, что вы разместили свой фактический код. В настоящее время есть несколько синтаксических ошибок.   -  person Andy Turner    schedule 25.10.2016
comment
я обновил код   -  person Kira    schedule 25.10.2016
comment
вы можете мне помочь? я тоже пытаюсь использовать Jgrapht stackoverflow.com/questions/40306916/   -  person Piero Tozzi    schedule 28.10.2016

Ответы (1)


arrow_upward
0
arrow_downward

Вы не предоставили код для своего класса Edge, но с DefaultEdge для класса Edge обе ваши реализации oneLevelCollapse(...) работают и пройдут этот модульный тест:

public void testJgraph() {
    DirectedGraph<Node, DefaultEdge> graph = new SimpleDirectedGraph<>(DefaultEdge.class);
    Node v1 = new Node("a");
    Node v2 = new Node("b");
    Node v3 = new Node("c");
    graph.addVertex(v1);
    graph.addVertex(v2);
    graph.addVertex(v3);

    graph.addEdge(v1, v2);
    graph.addEdge(v2, v3);

    oneLevelCollapse(graph);

    assertEquals(2, graph.vertexSet().size());
    assertTrue(graph.vertexSet().contains(v1));
    assertTrue(graph.vertexSet().contains(v2));
    assertEquals(v3, v2.children.get(0));

}
person Graeme Ahokas    schedule 04.11.2016