《算法》第六章部分程序 part 5

▶ 书中第六章部分程序，包括在加上自己补充的代码，网络最大流 Ford - Fulkerson 算法，以及用到的流量边类和剩余流量网络类

● 网络最大流 Ford - Fulkerson 算法

  1 package package01;
  2 
  3 import edu.princeton.cs.algs4.StdOut;
  4 import edu.princeton.cs.algs4.FlowEdge;
  5 import edu.princeton.cs.algs4.FlowNetwork;
  6 import edu.princeton.cs.algs4.Queue;
  7 
  8 public class class01
  9 {
 10     private static final double FLOATING_POINT_EPSILON = 1E-11;
 11 
 12     private final int V;          // 顶点数
 13     private boolean[] marked;     // 已搜索顶点，marked[v] = true 表示从起点 s 到顶点 v 存在一条具有剩余流量的路径
 14     private FlowEdge[] edgeTo;    // s -> v 路径上的最后一条边
 15     private double value;         // 当前最大流量
 16 
 17     public class01(FlowNetwork G, int s, int t)
 18     {
 19         V = G.V();
 20         if (s == t || !isFeasible(G, s, t))
 21             throw new IllegalArgumentException("
<constructor> Source == Sink || !isFeasible(G, s, t).
");
 22         for (value = excess(G, t); hasAugmentingPath(G, s, t);)             // 初始流量为顶点 t 净流量，只要还存在具有剩余容量的路径就要扩容
 23         {
 24             double bottle = Double.POSITIVE_INFINITY;                       // 沿着找到的路径走一遍，最小剩余容量作为扩容量
 25             for (int v = t; v != s; v = edgeTo[v].other(v))
 26                 bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
 27             for (int v = t; v != s; v = edgeTo[v].other(v))                 // 扩容
 28                 edgeTo[v].addResidualFlowTo(v, bottle);
 29             value += bottle;                                                // 总流量也要增加
 30         }
 31     }
 32 
 33     public double value()
 34     {
 35         return value;
 36     }
 37 
 38     public boolean inCut(int v)                                             // 顶点 v 是否在 s-切分中
 39     {
 40         return marked[v];
 41     }
 42 
 43     private boolean hasAugmentingPath(FlowNetwork G, int s, int t)  // 判断是否存在从 s 到 t 的剩余容量路径
 44     {
 45         edgeTo = new FlowEdge[G.V()];
 46         marked = new boolean[G.V()];
 47         Queue<Integer> queue = new Queue<Integer>();                // 广度优先搜索，保持所有搜索过的路径都有剩余容量
 48         for (queue.enqueue(s), marked[s] = true; !queue.isEmpty() && !marked[t];)
 49         {
 50             int v = queue.dequeue();
 51             for (FlowEdge e : G.adj(v))
 52             {
 53                 int w = e.other(v);
 54                 if (e.residualCapacityTo(w) > 0)                    // 如果取出的边关于终点 w 有剩余流量，则将其入队
 55                 {
 56                     if (!marked[w])
 57                     {
 58                         edgeTo[w] = e;
 59                         marked[w] = true;
 60                         queue.enqueue(w);
 61                     }
 62                 }
 63             }
 64         }
 65         return marked[t];                                           // 如果搜索到过 t，说明存在一条具有剩余容量的路径
 66     }
 67 
 68     private double excess(FlowNetwork G, int v)                     // 计算顶点 v 的净流量
 69     {
 70         double excess = 0.0;
 71         for (FlowEdge e : G.adj(v))                                 // 入边增加，出边减少
 72             excess += (v == e.to() ? e.flow() : -e.flow());
 73         return excess;
 74     }
 75 
 76     private boolean isFeasible(FlowNetwork G, int s, int t)         // 节点流量异常检查
 77     {
 78         for (int v = 0; v < G.V(); v++)
 79         {
 80             for (FlowEdge e : G.adj(v))
 81             {
 82                 if (e.flow() < -FLOATING_POINT_EPSILON || e.flow() > e.capacity() + FLOATING_POINT_EPSILON) // 某条边的流量异常
 83                 {
 84                     System.err.println("Edge does not satisfy capacity constraints: " + e);
 85                     return false;
 86                 }
 87             }
 88         }
 89         if (Math.abs(value + excess(G, s)) > FLOATING_POINT_EPSILON)// 当前起点净流量（<0）加上图流量非零，异常
 90         {
 91             System.err.println("Excess at source = " + excess(G, s) + "Max flow         = " + value);
 92             return false;
 93         }
 94         if (Math.abs(value - excess(G, t)) > FLOATING_POINT_EPSILON)// 当前终点净流量（>0）减去图流量非零，异常
 95         {
 96             System.err.println("Excess at sink   = " + excess(G, t) + "Max flow         = " + value);
 97             return false;
 98         }
 99         for (int v = 0; v < G.V(); v++)                             // 其他节点净流量应该为零
100         {
101             if (v == s || v == t)
102                 continue;
103             if (Math.abs(excess(G, v)) > FLOATING_POINT_EPSILON)
104             {
105                 System.err.println("Net flow out of " + v + " doesn't equal zero");
106                 return false;
107             }
108         }
109         return true;
110     }
111 
112     public static void main(String[] args)
113     {
114         int V = Integer.parseInt(args[0]), E = Integer.parseInt(args[1]), s = 0, t = V - 1;
115         FlowNetwork G = new FlowNetwork(V, E);
116         StdOut.println(G);
117         class01 maxflow = new class01(G, s, t);
118         StdOut.println("Max flow from " + s + " to " + t);
119         for (int v = 0; v < G.V(); v++)                             // 打印所有具有流量的边
120         {
121             for (FlowEdge e : G.adj(v))
122             {
123                 if ((v == e.from()) && e.flow() > 0)
124                     StdOut.println("   " + e);
125             }
126         }
127         StdOut.print("Min cut: ");                                  // 输出最小切分
128         for (int v = 0; v < G.V(); v++)
129             if (maxflow.inCut(v)) StdOut.print(v + " ");
130         StdOut.println("
Max flow value = " + maxflow.value());
131     }
132 }

● 流量边类

  1 package package01;
  2 
  3 public class class01
  4 {
  5     private static final double FLOATING_POINT_EPSILON = 1E-10;
  6 
  7     private final int v;             // 起点
  8     private final int w;             // 终点
  9     private final double capacity;   // 容量
 10     private double flow;             // 流量
 11 
 12     public class01(int inputV, int inputW, double inputCapacity)    // 三种构造函数
 13     {
 14         if (inputV < 0 || inputW < 0 || inputCapacity<0)
 15             throw new IllegalArgumentException("
<constructor> inputV < 0 || inputW < 0 || inputCapacity < 0.
");
 16         v = inputV;
 17         w = inputW;
 18         capacity = inputCapacity;
 19         flow = 0.0;
 20     }
 21 
 22     public class01(int inputV, int inputW, double inputCapacity, double inputFlow)
 23     {
 24         if (inputV < 0 || inputW < 0 || inputCapacity<0 || inputFlow < 0.0 || inputFlow > inputCapacity)
 25             throw new IllegalArgumentException("
<constructor> inputV < 0 || inputW < 0 || inputCapacity < 0 || flow < 0.0 || flow > capacity.
");
 26         v = inputV;
 27         w = inputW;
 28         capacity = inputCapacity;
 29         flow = inputFlow;
 30     }
 31 
 32     public class01(class01 e)
 33     {
 34         v = e.v;
 35         w = e.w;
 36         capacity = e.capacity;
 37         flow = e.flow;
 38     }
 39 
 40     public int from()
 41     {
 42         return v;
 43     }
 44 
 45     public int to()
 46     {
 47         return w;
 48     }
 49 
 50     public double capacity()
 51     {
 52         return capacity;
 53     }
 54 
 55     public double flow()
 56     {
 57         return flow;
 58     }
 59 
 60     public int other(int vertex)
 61     {
 62         if (vertex == v)
 63             return w;
 64         else if (vertex == w)
 65             return v;
 66         throw new IllegalArgumentException("
<other> invalid endpoint.
");
 67     }
 68 
 69     public double residualCapacityTo(int vertex)    // 计算一条边关于某个顶点的流通能力
 70     {
 71         if (vertex == v)                            // 起点，返回边的现有流量
 72             return flow;
 73         else if (vertex == w)                       // 终点，返回边的剩余容量
 74             return capacity - flow;
 75         throw new IllegalArgumentException("
<residualCapacityTo> invalid endpoint.
");
 76     }
 77 
 78     public void addResidualFlowTo(int vertex, double delta)         // 改变边的流量
 79     {
 80         if (delta < 0.0)
 81             throw new IllegalArgumentException("
<addResidualFlowTo> delta < 0.0.
");
 82         if (vertex == v)                            // 起点，边流量减少
 83             flow -= delta;
 84         else if (vertex == w)                       // 终点，边流量增加
 85             flow += delta;
 86         else
 87             throw new IllegalArgumentException("
<addResidualFlowTo> invalid endpoint.
");
 88         if (Math.abs(flow) <= FLOATING_POINT_EPSILON)               // 流量归零
 89             flow = 0;
 90         if (Math.abs(flow - capacity) <= FLOATING_POINT_EPSILON)    // 流量达到容量
 91             flow = capacity;
 92         if (flow < 0.0)                                             // 流量异常
 93             throw new IllegalArgumentException("
<addResidualFlowTo> flow <0.
");
 94         if (flow > capacity)
 95             throw new IllegalArgumentException("
<addResidualFlowTo> flow > capacity.
");
 96     }
 97 
 98     public String toString()
 99     {
100         return v + "->" + w + " " + flow + "/" + capacity;
101     }
102 
103     public static void main(String[] args)
104     {
105         class01 e = new class01(12, 23, 4.56);
106         StdOut.println(e);
107     }
108 }

● 剩余流量网络类

  1 package package01;
  2 
  3 import edu.princeton.cs.algs4.In;
  4 import edu.princeton.cs.algs4.StdOut;
  5 import edu.princeton.cs.algs4.StdRandom;
  6 import edu.princeton.cs.algs4.FlowEdge;
  7 import edu.princeton.cs.algs4.Bag;
  8 
  9 public class class01
 10 {
 11     private static final String NEWLINE = System.getProperty("line.separator");
 12 
 13     private final int V;
 14     private int E;
 15     private Bag<FlowEdge>[] adj;
 16 
 17     public class01(int inputV)
 18     {
 19         if (V < 0)
 20             throw new IllegalArgumentException("
<constructor> inputV < 0.
");
 21         V = inputV;
 22         E = 0;
 23         adj = (Bag<FlowEdge>[]) new Bag[V];
 24         for (int v = 0; v < V; v++)
 25             adj[v] = new Bag<FlowEdge>();
 26     }
 27 
 28     public class01(int inputV, int inputE)
 29     {
 30         this(inputV);
 31         if (E < 0)
 32             throw new IllegalArgumentException("
<constructor> inputE < 0.
");
 33         for (int i = 0; i < E; i++)
 34             addEdge(new FlowEdge(StdRandom.uniform(V), StdRandom.uniform(V), StdRandom.uniform(100)));
 35     }
 36 
 37     public class01(In in)
 38     {
 39         this(in.readInt());
 40         E = in.readInt();
 41         for (int i = 0; i < E; i++)
 42             addEdge(new FlowEdge(in.readInt(), in.readInt(), in.readDouble()));
 43     }
 44 
 45     public int V()
 46     {
 47         return V;
 48     }
 49 
 50     public int E()
 51     {
 52         return E;
 53     }
 54 
 55     public void addEdge(FlowEdge e)     // 添加一条边
 56     {
 57         adj[e.from()].add(e);
 58         adj[e.to()].add(e);
 59         E++;
 60     }
 61 
 62     public Iterable<FlowEdge> adj(int v)// 一个顶点上出边的迭代器，就是该顶点的单链表
 63     {
 64         return adj[v];
 65     }
 66 
 67     public Iterable<FlowEdge> edges()   // 所有边的迭代器，和搜集所有顶点处的出边
 68     {
 69         Bag<FlowEdge> list = new Bag<FlowEdge>();
 70         for (int v = 0; v < V; v++)
 71         {
 72             for (FlowEdge e : adj(v))
 73             {
 74                 if (e.to() != v)
 75                     list.add(e);
 76             }
 77         }
 78         return list;
 79     }
 80 
 81     public String toString()
 82     {
 83         StringBuilder s = new StringBuilder();
 84         s.append(V + " " + E + NEWLINE);
 85         for (int v = 0; v < V; v++)
 86         {
 87             s.append(v + ":  ");
 88             for (FlowEdge e : adj[v])
 89                 if (e.to() != v) s.append(e + "  ");
 90             s.append(NEWLINE);
 91         }
 92         return s.toString();
 93     }
 94 
 95     public static void main(String[] args)
 96     {
 97         In in = new In(args[0]);
 98         class01 G = new class01(in);
 99         StdOut.println(G);
100     }
101 }