Finden Sie negative Zyklen in einem gerichteten kantengewichteten Graph mit JGraph

Question

Ist es möglich, JGrapht zu verwenden, um negative Zyklen in einem gerichteten kantengewichteten Graphen zu finden? Ich habe durch die Javadocs geschaut und festgestellt, dass ich eine CycleDetector verwenden kann, um Zyklen zu erkennen, aber nicht speziell negative Zyklen. CycleDetector findet Zyklen, aber Sie können nicht sagen, ob sie negativ sind oder nicht, ohne sie irgendwie auf andere Weise zu erkunden. Vielen Dank!

Answer 1

Im Allgemeinen könnten Sie BellmanFordShortestPath verwenden, um nach negativen Zyklen in einem Graphen zu suchen, obwohl das Nichtvorhandensein eines kürzesten Pfades nur anzeigt, ob mindestens ein negativer Zyklus existiert. Ich habe die Implementierung BellmanFordShortestPath in JgraphT nicht richtig untersucht, daher kann ich Ihnen dafür keinen Code liefern.

Ansonsten gibt es ein sauberes Papier in https://cs.stackexchange.com/questions/6919/getting-negative-cycle-using-bellman-ford verknüpft. Eine Arbeits Link auf das Papier sollte sein:

https://www.semanticscholar.org/paper/Negative-Weight-Cycle-Algorithms-Huang/dc1391024d74f736aa7a9c24191a35e822589516/pdf

Also, wenn alles andere fehlschlägt, Sie zumindest eine Arbeits Algorithmus selbst implementieren könnte, ein JGraphT Graph mit wie DefaultDirectedWeightedGraph

Answer 2

Sie können versuchen, zu verwenden, Die BellmanFordShortestPath, aber es wird die Schleife nicht finden, wenn Sie nach einem Pfad von einem Scheitelpunkt zu sich selbst suchen, da jeder Scheitelpunkt implizit mit sich selbst verbunden ist mit einer Gewichtung 0.

DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> directedGraph = new DefaultDirectedWeightedGraph<>(DefaultWeightedEdge.class); 

... 

BellmanFordShortestPath<String, DefaultWeightedEdge> algorithm = new BellmanFordShortestPath(graph); 

GraphPath<String, DefaultWeightedEdge> path = algorithm.getPath(node1, node1); 

int length = path.getLength(); // returns 0 
double weight = path.getWeight(); // returns 0.0 

Das Beste, was ich sind die Algorithmen in org.jgrapht.alg.cycle finden können, die Sie alle Zyklen geben und dann haben Sie das Gesamtgewicht des Weges um den Zyklus zu berechnen.

private boolean hasNegativeLoop(DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> graph){ 
    SzwarcfiterLauerSimpleCycles<String, DefaultWeightedEdge> cycleDetector = new SzwarcfiterLauerSimpleCycles<>(graph); 

    List<List<String>> cycles = cycleDetector.findSimpleCycles(); 

    for (List<String> cycle : cycles){ 
     double cycleWeight = getCycleWeight(graph, cycle); 

     if(cycleWeight < 0) return true; 
    } 

    return false; 
} 

private double getCycleWeight(DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> graph, List<String> cycle) { 
    double totalWeight = 0; 

    for(int i = 1; i < cycle.size(); i++){ 
     double weight = graph.getEdgeWeight(graph.getEdge(cycle.get(i-1), cycle.get(i))); 

     totalWeight += weight; 
    } 

    double weightBackToStart = graph.getEdgeWeight(graph.getEdge(cycle.get(cycle.size()-1), cycle.get(0))); 

    return totalWeight + weightBackToStart; 
} 

Dies ist viel effizienter im Vergleich zu Bellman Ford negative Zykluserkennung, könnte aber als Referenz für Ihre Implementierung dienen.