001// Exercise 4.3.43 (Solution published at http://algs4.cs.princeton.edu/)
002package algs43;
003import stdlib.*;
004import algs13.Bag;
005import algs15.WeightedUF;
006/* ***********************************************************************
007 *  Compilation:  javac BoruvkaMST.java
008 *  Execution:    java BoruvkaMST filename.txt
009 *  Dependencies: EdgeWeightedGraph.java Edge.java Bag.java
010 *                UF.java In.java StdOut.java
011 *  Data files:   http://algs4.cs.princeton.edu/43mst/tinyEWG.txt
012 *                http://algs4.cs.princeton.edu/43mst/mediumEWG.txt
013 *                http://algs4.cs.princeton.edu/43mst/largeEWG.txt
014 *
015 *  Compute a minimum spanning forest using Boruvka's algorithm.
016 *
017 *  % java BoruvkaMST tinyEWG.txt
018 *  0-2 0.26000
019 *  6-2 0.40000
020 *  5-7 0.28000
021 *  4-5 0.35000
022 *  2-3 0.17000
023 *  1-7 0.19000
024 *  0-7 0.16000
025 *  1.81000
026 *
027 *************************************************************************/
028
029
030public class BoruvkaMST {
031        private final Bag<Edge> mst = new Bag<>();    // edges in MST
032        private double weight;                      // weight of MST
033
034        // Boruvka's algorithm
035        public BoruvkaMST(EdgeWeightedGraph G) {
036                WeightedUF uf = new WeightedUF(G.V());
037
038                // repeat at most log V times or until we have V-1 edges
039                for (int t = 1; t < G.V() && mst.size() < G.V() - 1; t = t + t) {
040
041                        // foreach tree in forest, find closest edge
042                        // if edge weights are equal, ties are broken in favor of first edge in G.edges()
043                        Edge[] closest = new Edge[G.V()];
044                        for (Edge e : G.edges()) {
045                                int v = e.either(), w = e.other(v);
046                                int i = uf.find(v), j = uf.find(w);
047                                if (i == j) continue;   // same tree
048                                if (closest[i] == null || less(e, closest[i])) closest[i] = e;
049                                if (closest[j] == null || less(e, closest[j])) closest[j] = e;
050                        }
051
052                        // add newly discovered edges to MST
053                        for (int i = 0; i < G.V(); i++) {
054                                Edge e = closest[i];
055                                if (e != null) {
056                                        int v = e.either(), w = e.other(v);
057                                        // don't add the same edge twice
058                                        if (!uf.connected(v, w)) {
059                                                mst.add(e);
060                                                weight += e.weight();
061                                                uf.union(v, w);
062                                        }
063                                }
064                        }
065                }
066
067                // check optimality conditions
068                assert check(G);
069        }
070
071
072        // edges in minimum spanning forest, as an Iterable
073        public Iterable<Edge> edges() {
074                return mst;
075        }
076
077        // weight of minimum spanning forest
078        public double weight() {
079                return weight;
080        }
081
082        // is the weight of edge e strictly less than that of edge f?
083        private static boolean less(Edge e, Edge f) {
084                return e.weight() < f.weight();
085        }
086
087        // check optimality conditions (takes time proportional to E V lg* V)
088        private boolean check(EdgeWeightedGraph G) {
089
090                // check weight
091                double totalWeight = 0.0;
092                for (Edge e : edges()) {
093                        totalWeight += e.weight();
094                }
095                double EPSILON = 1E-12;
096                if (Math.abs(totalWeight - weight()) > EPSILON) {
097                        System.err.format("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight());
098                        return false;
099                }
100
101                // check that it is acyclic
102                WeightedUF uf = new WeightedUF(G.V());
103                for (Edge e : edges()) {
104                        int v = e.either(), w = e.other(v);
105                        if (uf.connected(v, w)) {
106                                System.err.println("Not a forest");
107                                return false;
108                        }
109                        uf.union(v, w);
110                }
111
112                // check that it is a spanning forest
113                for (Edge e : edges()) {
114                        int v = e.either(), w = e.other(v);
115                        if (!uf.connected(v, w)) {
116                                System.err.println("Not a spanning forest");
117                                return false;
118                        }
119                }
120
121                // check that it is a minimal spanning forest (cut optimality conditions)
122                for (Edge e : edges()) {
123                        int v = e.either(), w = e.other(v);
124
125                        // all edges in MST except e
126                        uf = new WeightedUF(G.V());
127                        for (Edge f : mst) {
128                                int x = f.either(), y = f.other(x);
129                                if (f != e) uf.union(x, y);
130                        }
131
132                        // check that e is min weight edge in crossing cut
133                        for (Edge f : G.edges()) {
134                                int x = f.either(), y = f.other(x);
135                                if (!uf.connected(x, y)) {
136                                        if (f.weight() < e.weight()) {
137                                                System.err.println("Edge " + f + " violates cut optimality conditions");
138                                                return false;
139                                        }
140                                }
141                        }
142
143                }
144
145                return true;
146        }
147
148        public static void main(String[] args) {
149                In in = new In(args[0]);
150                EdgeWeightedGraph G = new EdgeWeightedGraph(in);
151                BoruvkaMST mst = new BoruvkaMST(G);
152                for (Edge e : mst.edges()) {
153                        StdOut.println(e);
154                }
155                StdOut.format("%.5f\n", mst.weight());
156        }
157
158}