001package algs64; 002import stdlib.*; 003 004/* *********************************************************************** 005 * Compilation: javac FlowEdge.java 006 * Execution: java FlowEdge 007 * 008 * Capacitated edge with a flow in a flow network. 009 * 010 *************************************************************************/ 011 012/** 013 * The {@code FlowEdge} class represents a capacitated edge with a flow 014 * in a digraph. 015 * <p> 016 * For additional documentation, see <a href="/algs4/74or">Section 7.4</a> of 017 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 018 */ 019 020 021public class FlowEdge { 022 private final int v; // from 023 private final int w; // to 024 private final double capacity; // capacity 025 private double flow; // flow 026 027 public FlowEdge(int v, int w, double capacity) { 028 if (capacity < 0) throw new IllegalArgumentException("Negative edge capacity"); 029 this.v = v; 030 this.w = w; 031 this.capacity = capacity; 032 this.flow = 0; 033 } 034 035 public FlowEdge(int v, int w, double capacity, double flow) { 036 if (capacity < 0) throw new IllegalArgumentException("Negative edge capacity"); 037 this.v = v; 038 this.w = w; 039 this.capacity = capacity; 040 this.flow = flow; 041 } 042 043 // copy constructor 044 public FlowEdge(FlowEdge e) { 045 this.v = e.v; 046 this.w = e.w; 047 this.capacity = e.capacity; 048 this.flow = e.flow; 049 } 050 051 // accessor methods 052 public int from() { return v; } 053 public int to() { return w; } 054 public double capacity() { return capacity; } 055 public double flow() { return flow; } 056 057 058 public int other(int vertex) { 059 if (vertex == v) return w; 060 else if (vertex == w) return v; 061 else throw new IllegalArgumentException("Illegal endpoint"); 062 } 063 064 public double residualCapacityTo(int vertex) { 065 if (vertex == v) return flow; // backward edge 066 else if (vertex == w) return capacity - flow; // forward edge 067 else throw new IllegalArgumentException("Illegal endpoint"); 068 } 069 070 public void addResidualFlowTo(int vertex, double delta) { 071 if (vertex == v) flow -= delta; // backward edge 072 else if (vertex == w) flow += delta; // forward edge 073 else throw new IllegalArgumentException("Illegal endpoint"); 074 } 075 076 077 public String toString() { 078 return v + "->" + w + " " + flow + "/" + capacity; 079 } 080 081 082 /** 083 * Test client. 084 */ 085 public static void main(String[] args) { 086 FlowEdge e = new FlowEdge(12, 23, 3.14); 087 StdOut.println(e); 088 } 089 090}