JGraphT: Ошибка переполнения стека с алгоритмом длинного пути Ляо Вонга?

Question

Я пытаюсь реализовать алгоритм самого длинного пути в Java с jGraphT, но я получаю java.lang.StackruError, когда я компилирую. Сообщение об ошибке указывает на строку, куда я копирую график, и на строку, где метод вызывает себя внутри алгоритма. Описание алгоритма, которое я использую, здесь - самый длинный путь Ляо Вонга на странице 11.

Где и что я сделал не так?

import org.jgrapht.*;
import org.jgrapht.graph.*;
import java.util.*;

public class LongestPath {
    private DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge> graph;
    private double product;
    private ArrayList<DefaultWeightedEdge> edges;

    public LongestPath(DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge> theGraph) {
        this.graph = theGraph;
        this.product = 1.0;
        this.edges = new ArrayList<DefaultWeightedEdge>();
    }

    public ArrayList<DefaultWeightedEdge> liaoWongLongestPath(Vertice source) {
        DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge> copyGraph =     (DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge>) graph.clone();
        boolean flag;

        for (int j = 1;j <= (copyGraph.edgeSet().size() + 1);j++) {

            edges = this.liaoWongLongestPath(source);

            flag = true;

            for (DefaultWeightedEdge dwe : edges) {

                if (copyGraph.getEdgeWeight(copyGraph.getEdge(source, copyGraph.getEdgeTarget(dwe))) < (copyGraph.getEdgeWeight(copyGraph.getEdge(source, copyGraph.getEdgeSource(dwe))) + copyGraph.getEdge(copyGraph.getEdgeSource(dwe), copyGraph.getEdgeTarget(dwe)).getWeight())) { 
                    //product = (copyGraph.getEdgeWeight(copyGraph.getEdge(source, copyGraph.getEdgeSource(dwe))) * copyGraph.getEdge(copyGraph.getEdgeSource(dwe), copyGraph.getEdgeTarget(dwe)).getWeight());
                    flag = false;
                    boolean status = edges.add(copyGraph.getEdge(source, copyGraph.getEdgeTarget(dwe)));
                }
            }
            if (flag) {
                System.out.println("Product: " + product + ".");
                return edges;
            }
        }

        return edges;
    }
}

Answer 1

Вы делаете рекурсивный вызов в своем коде, и вы делаете копию всего графа в каждой итерации. Это очень дорого, и в целом это приведет к исключению переполнения стека. Попробуйте удалить рекурсивную сложность этой программы и / или повторно использовать график (вы можете использовать класс MaskSubgraph).

Пожалуйста, посмотрите на это: Что такое ошибка StackruError?