001// Exercise 4.3.9 4.3.17 (Solution published at http://algs4.cs.princeton.edu/)
002package algs43;
003import stdlib.*;
004import algs13.Bag;
005import algs13.Stack;
006/**
007 *  The {@code EdgeWeightedGraph} class represents an undirected graph of vertices
008 *  named 0 through V-1, where each edge has a real-valued weight.
009 *  It supports the following operations: add an edge to the graph,
010 *  in the graph, iterate over all of the neighbors incident to a vertex.
011 *  Parallel edges and self-loops are permitted.
012 *  <p>
013 *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/43mst">Section 4.3</a> of
014 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
015 */
016
017public class EdgeWeightedGraph {
018        private final int V;
019        private int E;
020        private final Bag<Edge>[] adj;
021
022        /**
023         * Create an empty edge-weighted graph with V vertices.
024         */
025        @SuppressWarnings("unchecked")
026        public EdgeWeightedGraph(int V) {
027                if (V < 0) throw new Error("Number of vertices must be nonnegative");
028                this.V = V;
029                this.E = 0;
030                adj = new Bag[V];
031                for (int v = 0; v < V; v++) {
032                        adj[v] = new Bag<>();
033                }
034        }
035
036        /**
037         * Create a random edge-weighted graph with V vertices and E edges with no parallel edges or self loops.
038         * The expected running time is proportional to V + E.
039         */
040        public EdgeWeightedGraph(int V, int E) { this (V, E, false); }
041        /**
042         * Create a random edge-weighted graph with V vertices and E edges.
043         * The expected running time is proportional to V + E.
044         */
045        public EdgeWeightedGraph(int V, int E, boolean allowParallelEdgesAndSelfLoops) {
046                this(V);
047                if (E < 0) throw new Error("Number of edges must be nonnegative");
048                if (allowParallelEdgesAndSelfLoops) {
049                        for (int i = 0; i < E; i++) {
050                                int v = (int) (Math.random() * V);
051                                int w = (int) (Math.random() * V);
052                                double weight = Math.round(100 * Math.random()) / 100.0;
053                                Edge e = new Edge(v, w, weight);
054                                addEdge(e);
055                        }
056                } else {
057                        if (E > V*(V-1)/2) throw new Error("Number of edges must be less than V*(V-1)/2");
058                        newEdge: while (E>0) {
059                                int v = (int) (Math.random() * V);
060                                int w = (int) (Math.random() * V);
061                                if (v == w) continue;
062                                for (Edge e: adj[v])
063                                        if (w == e.other (v))
064                                                continue newEdge;
065                                double weight = Math.round(100 * Math.random()) / 100.0;
066                                Edge e = new Edge(v, w, weight);
067                                addEdge(e);
068                                E--;
069                        }
070                }
071        }
072        /**
073         * Create a weighted graph from input stream.
074         */
075        public EdgeWeightedGraph(In in) {
076                this(in.readInt());
077                int E = in.readInt();
078                for (int i = 0; i < E; i++) {
079                        int v = in.readInt();
080                        int w = in.readInt();
081                        double weight = in.readDouble();
082                        Edge e = new Edge(v, w, weight);
083                        addEdge(e);
084                }
085        }
086
087        /**
088         * Copy constructor.
089         */
090        public EdgeWeightedGraph(EdgeWeightedGraph G) {
091                this(G.V());
092                this.E = G.E();
093                for (int v = 0; v < G.V(); v++) {
094                        // reverse so that adjacency list is in same order as original
095                        Stack<Edge> reverse = new Stack<>();
096                        for (Edge e : G.adj[v]) {
097                                reverse.push(e);
098                        }
099                        for (Edge e : reverse) {
100                                adj[v].add(e);
101                        }
102                }
103        }
104
105        /**
106         * Return the number of vertices in this graph.
107         */
108        public int V() {
109                return V;
110        }
111
112        /**
113         * Return the number of edges in this graph.
114         */
115        public int E() {
116                return E;
117        }
118
119
120        /**
121         * Add the edge e to this graph.
122         */
123        public void addEdge(Edge e) {
124                int v = e.either();
125                int w = e.other(v);
126                adj[v].add(e);
127                adj[w].add(e);
128                E++;
129        }
130
131
132        /**
133         * Return the edges incident to vertex v as an Iterable.
134         * To iterate over the edges incident to vertex v, use foreach notation:
135         * {@code for (Edge e : graph.adj(v))}.
136         */
137        public Iterable<Edge> adj(int v) {
138                return adj[v];
139        }
140
141        /**
142         * Return all edges in this graph as an Iterable.
143         * To iterate over the edges, use foreach notation:
144         * {@code for (Edge e : graph.edges())}.
145         */
146        public Iterable<Edge> edges() {
147                Bag<Edge> list = new Bag<>();
148                for (int v = 0; v < V; v++) {
149                        int selfLoops = 0;
150                        for (Edge e : adj(v)) {
151                                if (e.other(v) > v) {
152                                        list.add(e);
153                                }
154                                // only add one copy of each self loop
155                                else if (e.other(v) == v) {
156                                        if (selfLoops % 2 == 0) list.add(e);
157                                        selfLoops++;
158                                }
159                        }
160                }
161                return list;
162        }
163
164
165
166        /**
167         * Return a string representation of this graph.
168         */
169        public String toString() {
170                String NEWLINE = System.getProperty("line.separator");
171                StringBuilder s = new StringBuilder();
172                s.append(V + " " + E + NEWLINE);
173                for (int v = 0; v < V; v++) {
174                        s.append(v + ": ");
175                        for (Edge e : adj[v]) {
176                                s.append(e + "  ");
177                        }
178                        s.append(NEWLINE);
179                }
180                return s.toString();
181        }
182
183        /**
184         * Save a graphviz representation of the graph.
185         * See <a href="http://www.graphviz.org/">graphviz.org</a>.
186         */
187        public void toGraphviz(String filename) {
188                GraphvizBuilder gb = new GraphvizBuilder ();
189                for (int v = 0; v < V; v++) {
190                        gb.addNode (v);
191                        boolean showSelfLoop = false;
192                        for (Edge e : adj[v]) {
193                                int w = e.other(v);
194                                if (v < w) // only once each edge
195                                        gb.addLabeledEdge (v, w, e.weight ());
196                                if (v == w) {
197                                        showSelfLoop = !showSelfLoop;
198                                        if (showSelfLoop)
199                                                gb.addLabeledEdge (v, w, e.weight ());
200                                }
201                        }
202                }
203                gb.toFileUndirected (filename);
204        }
205
206
207        /**
208         * Test client.
209         */
210        public static void main(String[] args) {
211                //args = new String [] { "data/tinyEWG.txt" };
212                args = new String [] { "20", "40" };
213
214                EdgeWeightedGraph G;
215                if (args.length == 1) {
216                        In in = new In(args[0]);
217                        G = new EdgeWeightedGraph(in);
218                } else {
219                        int V = Integer.parseInt (args[0]);
220                        int E = Integer.parseInt (args[1]);
221                        G = new EdgeWeightedGraph(V, E, false);
222                }
223                StdOut.println(G);
224                G.toGraphviz ("g.png");
225        }
226
227}