2
J'essaye d'implémenter un algorithme de chemin le plus long en Java avec jGraphT, mais j'obtiens un java.lang.StackOverflowError quand je compile. Le message d'erreur pointe vers la ligne où je copie le graphique et vers la ligne où la méthode s'appelle elle-même dans l'algorithme. La description de l'algorithme que j'utilise est Liao Wong longest path à la page 11.JGraphT: Erreur de dépassement de pile avec l'algorithme de plus long chemin de Liao Wong?
Où et quoi ai-je mal fait?
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;
}
}