Finding Negative Cycle in Java

Finding Negative Cycle

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

IntegerNumberSystem NS = IntegerNumberSystem.getInstance();

// consturct a simple graph.
MutableDirectedWeightedGraph<String, Integer> g = MutableDirectedWeightedGraph.create();
g.insertVertex("A");
g.insertVertex("B");
g.insertVertex("C");
g.addEdge("A", "B", 100);
g.addEdge("B", "C", 200);
g.addEdge("C", "A", -100);

// there is no negative cycles yet. so cycled is false
boolean cycled1 = NegativeCycleFinder.find(g, NS).hasCycle();

// now, insert another edge to create a negative cycle.

g.addEdge("C", "A", -400);

// then, there is a negative cycle.

boolean cycled2 = NegativeCycleFinder.find(g, NS).hasCycle();
Collection<DirectedWeightedEdge<String, Integer>> path = NegativeCycleFinder.find(g, NS).getPath();

Implementation

NegativeCycleFinder.java in GitHub