Author: Jacob Park
A graph $G$ is a pair $(V, E)$ where $V$ is a set of vertices and $E$ is a set of edges.
package graphs;
import java.util.*;
public class ListGraph {
private final ArrayList<LinkedList<Integer>> adjacencyList;
private final int vertices;
public ListGraph(int vertices) {
this.adjacencyList = new ArrayList<>(vertices);
this.vertices = vertices;
for (int vertex = 0; vertex < vertices; vertex++) {
this.adjacencyList.add(new LinkedList<>());
}
}
public void addEdge(int v, int w) {
adjacencyList.get(v).add(w);
}
public int getVertices() {
return vertices;
}
public Iterable<Integer> getAdjacents(int v) {
return adjacencyList.get(v);
}
}
package graphs;
import java.util.*;
public class MatrixGraph {
private final boolean[][] adjacencyMatrix;
private final int vertices;
public MatrixGraph(int vertices) {
this.adjacencyMatrix = new boolean[vertices][vertices];
this.vertices = vertices;
}
public void addEdge(int v, int w) {
adjacencyMatrix[v][w] = true;
}
public int getVertices() {
return vertices;
}
public Iterable<Integer> getAdjacents(int v) {
final boolean[] adjacencyVector = adjacencyMatrix[v];
final LinkedList<Integer> adjacencyList = new LinkedList<>();
for (int vertex = 0; vertex < vertices; vertex++) {
if (adjacencyVector[vertex]) {
adjacencyList.add(vertex);
}
}
return adjacencyList;
}
}
package graphs;
public class WeightedEdge implements Comparable<WeightedEdge> {
private final int v;
private final int w;
private final int weight;
public WeightedEdge(int v, int w, int weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public int getV() {
return v;
}
public int getW() {
return w;
}
public int getWeight() {
return weight;
}
@Override
public int compareTo(WeightedEdge other) {
return Integer.compare(this.weight, other.weight);
}
}
package graphs;
import java.util.*;
public class WeightedEdgeListGraph {
private final ArrayList<LinkedList<WeightedEdge>> adjacencyList;
private final int vertices;
public WeightedEdgeListGraph(int vertices) {
this.adjacencyList = new ArrayList<>(vertices);
this.vertices = vertices;
for (int vertex = 0; vertex < vertices; vertex++) {
this.adjacencyList.add(new LinkedList<>());
}
}
public void addEdge(int v, int w, int weight) {
adjacencyList.get(v).add(new WeightedEdge(v, w, weight));
}
public int getVertices() {
return vertices;
}
public Iterable<WeightedEdge> getAdjacents(int v) {
return adjacencyList.get(v);
}
public Iterable<WeightedEdge> getEdges() {
final LinkedList<WeightedEdge> edges = new LinkedList<>();
for (int vertex = 0; vertex < vertices; vertex++) {
edges.addAll(adjacencyList.get(vertex));
}
return edges;
}
}
package graphs;
import java.util.*;
public class WeightedEdgeMatrixGraph {
private final WeightedEdge[][] adjacencyMatrix;
private final int vertices;
public WeightedEdgeMatrixGraph(int vertices) {
this.adjacencyMatrix = new WeightedEdge[vertices][vertices];
this.vertices = vertices;
}
public void addEdge(int v, int w, int weight) {
if (adjacencyMatrix[v][w] == null) {
adjacencyMatrix[v][w] = new WeightedEdge(v, w, weight);
}
}
public int getVertices() {
return vertices;
}
public Iterable<WeightedEdge> getAdjacents(int v) {
final WeightedEdge[] adjacencyVector = adjacencyMatrix[v];
final LinkedList<WeightedEdge> adjacencyList = new LinkedList<>();
for (int vertex = 0; vertex < vertices; vertex++) {
if (adjacencyVector[vertex] != null) {
adjacencyList.add(adjacencyVector[vertex]);
}
}
return adjacencyList;
}
public Iterable<WeightedEdge> getEdges() {
final LinkedList<WeightedEdge> edges = new LinkedList<>();
for (int rowVertex = 0; rowVertex < vertices; rowVertex++) {
for (int colVertex = 0; colVertex < vertices; colVertex++) {
if (adjacencyMatrix[rowVertex][colVertex] != null) {
edges.add(adjacencyMatrix[rowVertex][colVertex]);
}
}
}
return edges;
}
}
package graphs.dfs;
import graphs.*;
import java.util.*;
import java.util.function.*;
public class DepthFirstSearch {
public static void depthFirstSearch(
ListGraph graph,
int v,
Consumer<Integer> action) {
final Set<Integer> visitedSet = new HashSet<>();
final Stack<Integer> stack = new Stack<>();
stack.push(v);
while (!stack.isEmpty()) {
final int currentVertex = stack.pop();
visitedSet.add(currentVertex);
action.accept(currentVertex);
final Iterable<Integer> adjacents = graph.getAdjacents(currentVertex);
for (int adjacentVertex : adjacents) {
if (!visitedSet.contains(adjacentVertex)) {
stack.push(adjacentVertex);
}
}
}
}
}
package graphs.dfs;
import graphs.*;
final ListGraph graph = new ListGraph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
DepthFirstSearch.depthFirstSearch(graph, 2, (vertex) -> System.out.println(vertex));
package graphs.bfs;
import graphs.*;
import java.util.*;
import java.util.function.*;
public class BreadthFirstSearch {
public static void breadthFirstSearch(
ListGraph graph,
int v,
Consumer<Integer> action) {
final Set<Integer> visitedSet = new HashSet<>();
final Deque<Integer> queue = new ArrayDeque<>();
queue.offer(v);
while (!queue.isEmpty()) {
final int currentVertex = queue.poll();
visitedSet.add(currentVertex);
action.accept(currentVertex);
final Iterable<Integer> adjacents = graph.getAdjacents(currentVertex);
for (int adjacentVertex : adjacents) {
if (!visitedSet.contains(adjacentVertex)) {
queue.offer(adjacentVertex);
}
}
}
}
}
package graphs.bfs;
import graphs.*;
final ListGraph graph = new ListGraph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
BreadthFirstSearch.breadthFirstSearch(graph, 2, (vertex) -> System.out.println(vertex));
package graphs.dijkstra;
import graphs.*;
import java.util.*;
public class Dijkstra {
public static class VertexDistancePair implements Comparable<VertexDistancePair> {
private final int vertex;
private final double distance;
public VertexDistancePair(int vertex, double distance) {
this.vertex = vertex;
this.distance = distance;
}
public int getVertex() {
return vertex;
}
public double getDistance() {
return distance;
}
@Override
public int compareTo(VertexDistancePair other) {
return Double.compare(this.distance, other.distance);
}
}
/*
* Dijkstra's Algorithm:
* 1. Assume all vertices are an infinite distance from the source vertex.
* 2. Assume the source vertex is zero distance from itself.
* 3. Perform breadth-first search using a priority queue by distance.
* 4. For every adjacent vertex visited, relax its edge.
*/
public static List<WeightedEdge> shortestPath(
WeightedEdgeListGraph graph,
int source,
int destination) {
final Map<Integer, Double> distanceTo = new HashMap<>();
final Map<Integer, WeightedEdge> edgeTo = new HashMap<>();
final PriorityQueue<VertexDistancePair> priorityQueue = new PriorityQueue<>();
for (int vertex = 0; vertex < graph.getVertices(); vertex++) {
distanceTo.put(vertex, Double.POSITIVE_INFINITY);
}
distanceTo.put(source, 0.0);
priorityQueue.offer(new VertexDistancePair(source, distanceTo.get(source)));
while (!priorityQueue.isEmpty()) {
final int minimumVertex = priorityQueue.poll().getVertex();
final Iterable<WeightedEdge> adjacents = graph.getAdjacents(minimumVertex);
for (WeightedEdge adjacentEdge : adjacents) {
final int v = adjacentEdge.getV();
final int w = adjacentEdge.getW();
final int weight = adjacentEdge.getWeight();
if (distanceTo.get(w) > distanceTo.get(v) + weight) {
distanceTo.put(w, distanceTo.get(v) + weight);
edgeTo.put(w, adjacentEdge);
priorityQueue.offer(new VertexDistancePair(w, distanceTo.get(w)));
}
}
}
return buildPath(edgeTo, destination);
}
private static List<WeightedEdge> buildPath(
Map<Integer, WeightedEdge> edgeTo,
int destination) {
final LinkedList<WeightedEdge> path = new LinkedList<>();
int currentVertex = destination;
while (edgeTo.containsKey(currentVertex)) {
path.addFirst(edgeTo.get(currentVertex));
currentVertex = edgeTo.get(currentVertex).getV();
}
return path;
}
}
package graphs.dijkstra;
import graphs.*;
import java.util.*;
final WeightedEdgeListGraph graph = new WeightedEdgeListGraph(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 4, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 0, 7);
graph.addEdge(3, 2, 6);
graph.addEdge(4, 1, 3);
graph.addEdge(4, 2, 9);
graph.addEdge(4, 3, 2);
final List<WeightedEdge> path = Dijkstra.shortestPath(graph, 0, 2);
path.forEach(edge -> {
System.out.println(String.format("%d -> %d", edge.getV(), edge.getW()));
});
package graphs.bellman_ford;
import graphs.*;
import java.util.*;
public class BellmanFord {
/*
* Bellman-Ford Algorithm:
* 1. Assume all vertices are an infinite distance from the source vertex.
* 2. Assume the source vertex is zero distance from itself.
* 3. For every vertex, relax all the edges.
* 4. Check for negative-weight cycles.
*/
public static List<WeightedEdge> shortestPath(
WeightedEdgeListGraph graph,
int source,
int destination) {
final Map<Integer, Double> distanceTo = new HashMap<>();
final Map<Integer, WeightedEdge> edgeTo = new HashMap<>();
for (int vertex = 0; vertex < graph.getVertices(); vertex++) {
distanceTo.put(vertex, Double.POSITIVE_INFINITY);
}
distanceTo.put(source, 0.0);
for (int vertex = 0; vertex < graph.getVertices(); vertex++) {
final Iterable<WeightedEdge> edges = graph.getEdges();
for (WeightedEdge edge : edges) {
final int v = edge.getV();
final int w = edge.getW();
final int weight = edge.getWeight();
if (distanceTo.get(w) > distanceTo.get(v) + weight) {
distanceTo.put(w, distanceTo.get(v) + weight);
edgeTo.put(w, edge);
}
}
}
final Iterable<WeightedEdge> edges = graph.getEdges();
for (WeightedEdge edge : edges) {
final int v = edge.getV();
final int w = edge.getW();
final int weight = edge.getWeight();
if (distanceTo.get(w) > distanceTo.get(v) + weight) {
throw new IllegalStateException("Negative-Weight Cycle Detected!");
}
}
return buildPath(edgeTo, destination);
}
private static List<WeightedEdge> buildPath(
Map<Integer, WeightedEdge> edgeTo,
int destination) {
final LinkedList<WeightedEdge> path = new LinkedList<>();
int currentVertex = destination;
while (edgeTo.containsKey(currentVertex)) {
path.addFirst(edgeTo.get(currentVertex));
currentVertex = edgeTo.get(currentVertex).getV();
}
return path;
}
}
package graphs.bellman_ford;
import graphs.*;
import java.util.*;
final WeightedEdgeListGraph graph = new WeightedEdgeListGraph(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 4, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 0, 7);
graph.addEdge(3, 2, 6);
graph.addEdge(4, 1, 3);
graph.addEdge(4, 2, 9);
graph.addEdge(4, 3, 2);
final List<WeightedEdge> path = BellmanFord.shortestPath(graph, 0, 2);
path.forEach(edge -> {
System.out.println(String.format("%d -> %d", edge.getV(), edge.getW()));
});
package graphs.floyd_warshall;
import graphs.*;
import java.util.*;
public class FloydWarshall {
private final WeightedEdgeListGraph graph;
private final double[][] distanceTo;
private final WeightedEdge[][] edgeTo;
/*
* Floyd-Warshall Algorithm:
* 1. Assume all pairs of vertices have an infinite distance from each other.
* 2. Initialize the distance of each pair of vertices of an edge to the weight.
* 3. Initialize the distance of each pair of identical vertices to zero.
* 4. For every intermediary vertex, relax all pairs of vertices through a
* path with the intermediary vertex.
*/
public FloydWarshall(WeightedEdgeListGraph graph) {
this.graph = graph;
this.distanceTo = new double[graph.getVertices()][graph.getVertices()];
this.edgeTo = new WeightedEdge[graph.getVertices()][graph.getVertices()];
for (int vVertex = 0; vVertex < graph.getVertices(); vVertex++) {
for (int wVertex = 0; wVertex < graph.getVertices(); wVertex++) {
distanceTo[vVertex][wVertex] = Double.POSITIVE_INFINITY;
}
}
for (WeightedEdge edge : graph.getEdges()) {
distanceTo[edge.getV()][edge.getW()] = edge.getWeight();
edgeTo[edge.getV()][edge.getW()] = edge;
}
for (int vertex = 0; vertex < graph.getVertices(); vertex++) {
distanceTo[vertex][vertex] = 0.0;
edgeTo[vertex][vertex] = null;
}
for (int iVertex = 0; iVertex < graph.getVertices(); iVertex++) {
for (int vVertex = 0; vVertex < graph.getVertices(); vVertex++) {
if (edgeTo[vVertex][iVertex] == null) {
continue;
}
for (int wVertex = 0; wVertex < graph.getVertices(); wVertex++) {
if (distanceTo[vVertex][wVertex] >
distanceTo[vVertex][iVertex] + distanceTo[iVertex][wVertex]) {
distanceTo[vVertex][wVertex] =
distanceTo[vVertex][iVertex] + distanceTo[iVertex][wVertex];
edgeTo[vVertex][wVertex] = edgeTo[iVertex][wVertex];
}
}
if (distanceTo[vVertex][vVertex] < 0.0) {
throw new IllegalStateException("Negative-Weight Cycle Detected!");
}
}
}
}
public List<WeightedEdge> shortestPath(int source, int destination) {
final LinkedList<WeightedEdge> path = new LinkedList<>();
if (distanceTo[source][destination] < Double.POSITIVE_INFINITY) {
for (WeightedEdge edge = edgeTo[source][destination];
edge != null;
edge = edgeTo[source][edge.getV()]) {
path.addFirst(edge);
}
}
return path;
}
}
package graphs.floyd_warshall;
import graphs.*;
import java.util.*;
final WeightedEdgeListGraph graph = new WeightedEdgeListGraph(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 4, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 0, 7);
graph.addEdge(3, 2, 6);
graph.addEdge(4, 1, 3);
graph.addEdge(4, 2, 9);
graph.addEdge(4, 3, 2);
final FloydWarshall floydWarshall = new FloydWarshall(graph);
final List<WeightedEdge> path = floydWarshall.shortestPath(0, 2);
path.forEach(edge -> {
System.out.println(String.format("%d -> %d", edge.getV(), edge.getW()));
});
package graphs.disjoint_set;
public class DisjointSet {
private final int[] parent;
private final byte[] rank;
private int count;
public DisjointSet(int count) {
this.parent = new int[count];
this.rank = new byte[count];
this.count = count;
for (int i = 0; i < count; i++) {
this.parent[i] = i;
this.rank[i] = 0;
}
}
/*
* Merge components p and q by having the root of the smaller rank
* point to the root of the larger rank.
*/
public void union(int p, int q) {
final int rootP = find(p);
final int rootQ = find(q);
if (rootP == rootQ) {
return;
}
if (rank[rootP] < rank[rootQ]) {
parent[rootP] = rootQ;
} else if (rank[rootQ] < rank[rootP]) {
parent[rootQ] = rootP;
} else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
/*
* Finds the root of component p by traversing the parents for
* a component who only points to themselves.
*/
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
/*
* Two components are connected if they have the same root.
*/
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/*
* The number of components.
*/
public int count() {
return count;
}
}
package graphs.kruskal;
import graphs.*;
import graphs.disjoint_set.*;
import java.util.*;
public class Kruskal {
/*
* Kruskal's Algorithm:
* 1. Assign every vertex into its own component.
* 2. Greedily, by increasing weight, connect two components by
* including the connecting edge into the MST.
*/
public static List<WeightedEdge> minimumSpanningTree(
WeightedEdgeListGraph graph) {
final DisjointSet disjointSet = new DisjointSet(graph.getVertices());
final PriorityQueue<WeightedEdge> priorityQueue = new PriorityQueue<>();
for (WeightedEdge edge : graph.getEdges()) {
priorityQueue.offer(edge);
}
final LinkedList<WeightedEdge> mst = new LinkedList<>();
while (!priorityQueue.isEmpty() && mst.size() < graph.getVertices() - 1) {
final WeightedEdge currentEdge = priorityQueue.poll();
if (!disjointSet.connected(currentEdge.getV(), currentEdge.getW())) {
disjointSet.union(currentEdge.getV(), currentEdge.getW());
mst.add(currentEdge);
}
}
return mst;
}
}
package graphs.kruskal;
import graphs.*;
import java.util.*;
final WeightedEdgeListGraph graph = new WeightedEdgeListGraph(4);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);
final List<WeightedEdge> mst = Kruskal.minimumSpanningTree(graph);
mst.forEach(edge -> {
System.out.println(String.format("%d -> %d", edge.getV(), edge.getW()));
});
package graphs.topological_sort;
import graphs.*;
import java.util.*;
public class TopologicalSort {
/*
* Given a directed graph, list the vertices in order such that all
* its directed edges point from a vertex earlier in the order to
* a vertex later in the order.
*/
public static List<Integer> topologicalSort(ListGraph graph) {
final LinkedList<Integer> topologicalOrder = new LinkedList<>();
final Set<Integer> temporarySet = new HashSet<>();
final Set<Integer> visitedSet = new HashSet<>();
for (int vertex = 0; vertex < graph.getVertices(); vertex++) {
if (!visitedSet.contains(vertex)) {
depthFirstSearch(
graph,
vertex,
topologicalOrder,
temporarySet,
visitedSet);
}
}
return topologicalOrder;
}
private static void depthFirstSearch(
ListGraph graph,
int v,
LinkedList<Integer> topologicalOrder,
Set<Integer> temporarySet,
Set<Integer> visitedSet) {
visitedSet.add(v);
temporarySet.add(v);
final Iterable<Integer> adjacents = graph.getAdjacents(v);
for (int adjacentVertex : adjacents) {
if (!visitedSet.contains(adjacentVertex)) {
depthFirstSearch(
graph,
adjacentVertex,
topologicalOrder,
temporarySet,
visitedSet);
continue;
}
if (temporarySet.contains(adjacentVertex)) {
throw new IllegalStateException("Cycle Detected!");
}
}
temporarySet.remove(v);
topologicalOrder.addFirst(v);
}
}
package graphs.topological_sort;
import graphs.*;
import java.util.*;
final ListGraph graph = new ListGraph(6);
graph.addEdge(5, 2);
graph.addEdge(5, 0);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
final List<Integer> topologicalOrder = TopologicalSort.topologicalSort(graph);
System.out.println(topologicalOrder.toString());
package graphs.kosaraju;
import graphs.*;
import java.util.*;
public class Kosaraju {
/*
* Kosaraju's Algorithm:
* 1. Construct the reverse post-order, depth-first search ordering
* of the directed graph.
* 2. Construct the reverse of the directed graph.
* 3. For every vertex in 1., if the current vertex does not belong
* to any component, create a new component and fill it
* with the vertices visited from a depth-first search starting
* from the current vertex.
*/
public static List<List<Integer>> stronglyConnectedComponents(ListGraph graph) {
final List<List<Integer>> components = new LinkedList<>();
final List<Integer> reversePostOrderVertices = reversePostOrder(graph);
final ListGraph reverseGraph = reverse(graph);
final Set<Integer> visitedSet = new HashSet<>();
for (int currentVertex : reversePostOrderVertices) {
if (!visitedSet.contains(currentVertex)) {
final LinkedList<Integer> component = new LinkedList<>();
reversePostOrderDepthFirstSearch(
reverseGraph,
currentVertex,
visitedSet,
component);
components.add(component);
visitedSet.addAll(component);
}
}
return components;
}
private static LinkedList<Integer> reversePostOrder(ListGraph graph) {
final LinkedList<Integer> results = new LinkedList<>();
final Set<Integer> visitedSet = new HashSet<>();
for (int vertex = 0; vertex < graph.getVertices(); vertex++) {
if (!visitedSet.contains(vertex)) {
reversePostOrderDepthFirstSearch(graph, vertex, visitedSet, results);
}
}
return results;
}
private static void reversePostOrderDepthFirstSearch(
ListGraph graph,
int v,
Set<Integer> visitedSet,
LinkedList<Integer> results) {
visitedSet.add(v);
final Iterable<Integer> adjacents = graph.getAdjacents(v);
for (int adjacentVertex : adjacents) {
if (!visitedSet.contains(adjacentVertex)) {
reversePostOrderDepthFirstSearch(
graph,
adjacentVertex,
visitedSet,
results);
}
}
results.addFirst(v);
}
private static ListGraph reverse(ListGraph graph) {
final ListGraph reversedGraph = new ListGraph(graph.getVertices());
for (int v = 0; v < graph.getVertices(); v++) {
for (int w : graph.getAdjacents(v)) {
reversedGraph.addEdge(w, v);
}
}
return reversedGraph;
}
}
package graphs.kosaraju;
import graphs.*;
import java.util.*;
final ListGraph graph = new ListGraph(7);
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 0);
graph.addEdge(1, 4);
graph.addEdge(2, 1);
graph.addEdge(2, 6);
graph.addEdge(4, 3);
graph.addEdge(5, 2);
graph.addEdge(5, 4);
graph.addEdge(6, 5);
final List<List<Integer>> stronglyConnectedComponents =
Kosaraju.stronglyConnectedComponents(graph);
stronglyConnectedComponents.forEach(component -> {
System.out.println(component.toString());
});
package graphs.maximum_flow;
public class FlowEdge {
private static final double EPSILON = 1E-10;
private final int v;
private final int w;
private final double capacity;
private double flow;
public FlowEdge(int v, int w, double capacity) {
if (v == w) {
throw new IllegalArgumentException(
String.format("No Self Loops (v, w): (%d, %d)", v, w));
}
if (capacity < 0.0) {
throw new IllegalArgumentException(
String.format("Positive Capacity Only: %f", capacity));
}
this.v = v;
this.w = w;
this.capacity = capacity;
this.flow = 0.0;
}
public int getV() {
return v;
}
public int getW() {
return w;
}
public double getCapacity() {
return capacity;
}
public double getFlow() {
return flow;
}
public int getOther(int vertex) {
if (vertex == v) {
return w;
} else if (vertex == w) {
return v;
} else {
throw new IllegalArgumentException(
String.format("Illegal Vertex: %d", vertex));
}
}
public double getResidualCapacityTo(int vertex) {
if (vertex == v) {
return flow;
} else if (vertex == w) {
return capacity - flow;
} else {
throw new IllegalArgumentException(
String.format("Illegal Vertex: %d", vertex));
}
}
public void addResidualFlowTo(int vertex, double delta) {
if (delta < 0.0) {
throw new IllegalArgumentException(
String.format("Positive Delta Only: %f", delta));
}
// Mutation:
if (vertex == v) {
flow -= delta;
} else if (vertex == w) {
flow += delta;
} else {
throw new IllegalArgumentException(
String.format("Illegal Vertex: %d", vertex));
}
// Rounding:
if (Math.abs(flow) <= EPSILON) {
flow = 0;
}
if (Math.abs(flow - capacity) <= EPSILON) {
flow = capacity;
}
}
}
package graphs.maximum_flow;
import java.util.*;
public class FlowNetwork {
private final ArrayList<LinkedList<FlowEdge>> adjacencyList;
private final int vertices;
public FlowNetwork(int vertices) {
this.adjacencyList = new ArrayList<>(vertices);
this.vertices = vertices;
for (int vertex = 0; vertex < vertices; vertex++) {
this.adjacencyList.add(new LinkedList<>());
}
}
public void addEdge(int v, int w, double capacity) {
final FlowEdge flowEdge = new FlowEdge(v, w, capacity);
adjacencyList.get(v).add(flowEdge);
adjacencyList.get(w).add(flowEdge);
}
public int getVertices() {
return vertices;
}
public Iterable<FlowEdge> getAdjacents(int v) {
return adjacencyList.get(v);
}
public Iterable<FlowEdge> getEdges() {
final LinkedList<FlowEdge> edges = new LinkedList<>();
for (int vertex = 0; vertex < vertices; vertex++) {
edges.addAll(adjacencyList.get(vertex));
}
return edges;
}
}
package graphs.maximum_flow;
import java.util.*;
public class FordFulkerson {
/*
* Ford-Fulkerson Algorithm:
* 1. Given a capacitated network in which every original edge has a reverse edge,
* the residual capacity of a original edge is the initial capacity
* while the residual capacity of a reverse edge is zero.
* 2. Calculate the initial flow to the destination.
* 3. Execute breadth-first search to find a path from the source to the destination.
* 4. Traverse the breadth-first search path to find the bottleneck capacity.
* 5. Modify the network along the breadth-first search path by
* increasing the flow of the original edge while decreasing the flow of the
* reverse edge.
*
* Key Idea:
* The idea is that increasing the flow decreases the amount of flow that can go
* through the edges in the future. On the other hand, it is possible to cancel flow
* later using the reverse edges if it turns out that it would be beneficial to route the flow
* in another way. The algorithm increases the flow as long as there is a path from
* the source to the sink through positive-weight edges. Then, if there are no such
* paths, the algorithm terminates and the maximum flow has been found.
*
* Minimum Cut:
* - Let A be the vertices that can be reached from the source using the original
* edges.
* - Let B be the vertices that can reach the destination using the original edges.
* - Thus, the minimum cut is the set of edges starting from A and ending in B.
* 1. Perform a depth-first search on a maximum-flow network, to determine partitions
* A and B.
* 2. Construct the minimum cut as the edges starting from A and ending in B.
*/
public static double maximumFlow(
FlowNetwork network,
int source,
int destination,
Set<FlowEdge> minimumCut
) {
double maximumFlow = initialFlow(network, destination);
final Map<Integer, FlowEdge> edgeTo = new HashMap<>();
while (hasBreadthFirstSearchPath(network, source, destination, edgeTo)) {
// 1. Find Bottleneck Capacity by Traversing Path
double bottleneckCapacity = Double.POSITIVE_INFINITY;
for (int vertex = destination;
vertex != source;
vertex = edgeTo.get(vertex).getOther(vertex)) {
bottleneckCapacity = Math.min(
bottleneckCapacity,
edgeTo.get(vertex).getResidualCapacityTo(vertex));
}
// 2. Modify Flow Network by Traversing Path
for (int vertex = destination;
vertex != source;
vertex = edgeTo.get(vertex).getOther(vertex)) {
edgeTo.get(vertex).addResidualFlowTo(vertex, bottleneckCapacity);
}
// 3. Update Maximum Flow
maximumFlow += bottleneckCapacity;
}
// Calculate Minimum Cut
minimumCut(network, source, minimumCut);
return maximumFlow;
}
private static double initialFlow(
FlowNetwork network,
int vertex) {
double flow = 0.0;
final Iterable<FlowEdge> adjacents = network.getAdjacents(vertex);
for (FlowEdge adjacentEdge : adjacents) {
if (vertex == adjacentEdge.getV()) {
flow -= adjacentEdge.getFlow();
} else if (vertex == adjacentEdge.getW()) {
flow += adjacentEdge.getFlow();
} else {
throw new IllegalArgumentException(
String.format("Illegal Vertex: %d", vertex));
}
}
return flow;
}
private static boolean hasBreadthFirstSearchPath(
FlowNetwork network,
int source,
int destination,
Map<Integer, FlowEdge> edgeTo) {
// Clear When Finding New Path
edgeTo.clear();
final Set<Integer> visitedSet = new HashSet<>();
final Deque<Integer> queue = new ArrayDeque<>();
queue.offer(source);
while (!queue.isEmpty()) {
final int currentVertex = queue.poll();
visitedSet.add(currentVertex);
// Quit Eagerly If Path Found
if (visitedSet.contains(destination)) {
break;
}
final Iterable<FlowEdge> adjacents = network.getAdjacents(currentVertex);
for (FlowEdge adjacentEdge : adjacents) {
final int otherVertex = adjacentEdge.getOther(currentVertex);
if (!visitedSet.contains(otherVertex)) {
// Path Exists Only If Capacity Is Available
if (adjacentEdge.getResidualCapacityTo(otherVertex) > 0) {
edgeTo.put(otherVertex, adjacentEdge);
queue.offer(otherVertex);
}
}
}
}
return visitedSet.contains(destination);
}
private static void minimumCut(
FlowNetwork network,
int source,
Set<FlowEdge> minimumCut) {
final Set<Integer> visitedSet = new HashSet<>();
depthFirstSearch(network, source, visitedSet);
for (int vertex = 0; vertex < network.getVertices(); vertex++) {
final Iterable<FlowEdge> adjacents = network.getAdjacents(vertex);
for (FlowEdge adjacentEdge : adjacents) {
final boolean isOriginalEdge = vertex == adjacentEdge.getV();
final boolean inA = visitedSet.contains(adjacentEdge.getV());
final boolean inB = !visitedSet.contains(adjacentEdge.getW());
if (isOriginalEdge && inA && inB) {
minimumCut.add(adjacentEdge);
}
}
}
}
private static void depthFirstSearch(
FlowNetwork network,
int v,
Set<Integer> visitedSet) {
visitedSet.add(v);
final Iterable<FlowEdge> adjacents = network.getAdjacents(v);
for (FlowEdge adjacentEdge : adjacents) {
final int otherVertex = adjacentEdge.getOther(v);
if (!visitedSet.contains(otherVertex)) {
if (adjacentEdge.getResidualCapacityTo(otherVertex) > 0) {
depthFirstSearch(network, otherVertex, visitedSet);
}
}
}
}
}
package graphs.maximum_flow;
import java.util.*;
final FlowNetwork network = new FlowNetwork(6);
network.addEdge(0, 1, 5.0);
network.addEdge(0, 3, 4.0);
network.addEdge(1, 2, 6.0);
network.addEdge(2, 4, 8.0);
network.addEdge(2, 5, 5.0);
network.addEdge(3, 1, 3.0);
network.addEdge(3, 4, 1.0);
network.addEdge(4, 5, 2.0);
final Set<FlowEdge> minimumCut = new HashSet<>();
final double maximumFlow = FordFulkerson.maximumFlow(network, 0, 5, minimumCut);
System.out.println(String.format("Maximum Flow: %f", maximumFlow));
System.out.println("Minimum Cut:");
minimumCut.forEach(edge -> {
System.out.println(String.format("%d -> %d", edge.getV(), edge.getW()));
});