Negative Cycle Detection

Community Coding
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Negative Cycle Detection
Hallo,

um einen min-cost-flow mit dem Kreislöschungsalgorithmus zu bestimmen, versuche ich den Algorithmus von Bellman-Ford zu implementieren, der negative Kreis detektiert.

Der Digraph, den die Methode übergeben bekommt, enthält bereits Vorwärts- und Rückwärtskanten. Wenn der Fluss auf der Vorwärtskante z.B. 2 ist, dann ist der Fluss auf der Rückwärtskante 0 und deren Kapazität 2. Verringert sich der Fluss auf der Vorwärtskante, wird auch die Kapazität auf der Rückwärtskante verringert. Wenn also keine Kapazität mehr auf einer Kante übrig ist, dann ignoriere ich diese Kante beim Bellman-Ford Verfahren.

Leider scheint meine Implementierung nicht alle negativen Kreise zu finden. Sieht vielleicht jemand das Problem? Würde mich auch über eine Referenzimplementierung freuen. Im Anhang ist der komplette Code zum Ausprobieren.

public static List<DirectedEdge> bellmanFord(Digraph digraph, final int source) {
        Set<Integer> nodes = digraph.nodes();

        // Initialize distance vector
        Map<Integer, Integer> distances = new HashMap<>(nodes.size());
        Map<Integer, Integer> predecessors = new HashMap<>(nodes.size());
        for (Integer node : nodes) {
            if (source == node) {
                distances.put(node, 0);
            } else {
                distances.put(node, Integer.MAX_VALUE);
            }
            predecessors.put(node, -1);
        }

        // Relaxate |nodes|-1 times
        for (int i=0; i<nodes.size()-1; i++) {
            for (DirectedEdge e : digraph.edges()) {
                // Only consider edges where some capacity is remaining
                if (e.capacity() - e.flow() <= 0) {
                    continue;
                }

                if (distances.get(e.to()) > distances.get(e.from()) + e.costs()) {
                    distances.put(e.to(), distances.get(e.from()) + e.costs()); // update distance label
                    predecessors.put(e.to(), e.from()); // update predecessor
                }
            }
        }

        // Check whether there is an edge (u, v) such that d(u) + W(u, v) < d(v)
        for (DirectedEdge e : digraph.edges()) {
            // Only consider edges where some capacity is remaining
            if (e.capacity() - e.flow() <= 0) {
                continue;
            }

            if (distances.get(e.to()) > distances.get(e.from()) + e.costs()) {
                // Negative cycle detected. Go backward from v along the predecessor chain, until a cycle is found
                List<Integer> nodesInChain = new LinkedList<>();
                List<DirectedEdge> edgesAlongCycle = new LinkedList<>();

                int current = e.to();
                int predecessor = e.from();
                DirectedEdge edge = e;
                while (!nodesInChain.contains(current)) {
                    nodesInChain.add(current);
                    edgesAlongCycle.add(edge);

                    current = predecessor;
                    predecessor = predecessors.get(current);
                    int lowestCost = Integer.MAX_VALUE;
                    Set<DirectedEdge> possibleEdges = digraph.edges(predecessor, current);
                    for (DirectedEdge possibleEdge : possibleEdges) {
                        // Take the one that has capacity remaining of course and the lowest costs
                        if (possibleEdge.capacity() - possibleEdge.flow() <= 0) {
                            continue;
                        }

                        if (possibleEdge.costs() < lowestCost) {
                            edge = possibleEdge;
                            lowestCost = possibleEdge.costs();
                        }
                    }

                    if (Integer.MAX_VALUE == lowestCost) {
                        throw new Exception("No edge found");
                    }
                }

                // Cycle completely found

                // Let's see where the cycle has started
                int startIndex = nodesInChain.indexOf(current);
                // And throw out the earlier edges which are not part of the cycle
                for (int i=0; i<startIndex; i++) {
                    edgesAlongCycle.remove(0);
                }

                // Return the negative cycle
                return edgesAlongCycle;
            }
        }

        // No negative-weight cycles found
        return null;
    }

Attachment:
mincostflow.zip: https://fsi.cs.fau.de/unb-attachments/post_138076/mincostflow.zip

3

Hat sich erledigt, hab eine andere Implementierung aus Princeton gefunden. Die bauen mit den Kanten zu den jeweiligen Vorgängerknoten einen kleineren Graphen auf und suchen dann darin mit Tiefensuche nach Zyklen.

Hier der Quellcode:
BellmanFordSP
EdgeWeightedDirectedCycle

1 Like