001// Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/)
002package algs41;
003import stdlib.*;
004import algs13.Bag;
005
006/**
007 *  The {@code Graph} class represents an undirected graph of vertices
008 *  named {@code 0} through {@code V-1}.
009 *  It supports the following operations: add an edge to the graph,
010 *  iterate over all of the neighbors adjacent 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/51undirected">Section 5.1</a> of
014 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
015 */
016public class Graph {
017        private final int V;
018        private int E;
019        private final Bag<Integer>[] adj;
020
021        /**
022         * Create an empty graph with V vertices.
023         */
024        @SuppressWarnings("unchecked")
025        public Graph(int V) {
026                if (V < 0) throw new Error("Number of vertices must be nonnegative");
027                this.V = V;
028                this.E = 0;
029                this.adj = new Bag[V];
030                for (int v = 0; v < V; v++) {
031                        adj[v] = new Bag<>();
032                }
033        }
034        
035        /**
036         * Return the number of vertices in the graph.
037         */
038        public int V() { return V; }
039
040        /**
041         * Return the number of edges in the graph.
042         */
043        public int E() { return E; }
044
045
046        /**
047         * Add the undirected edge v-w to graph.
048         * @throws java.lang.IndexOutOfBoundsException unless both {@code 0 <= v < V} and {@code 0 <= w < V}
049         */
050        public void addEdge(int v, int w) {
051                if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
052                if (w < 0 || w >= V) throw new IndexOutOfBoundsException();
053                E++;
054                adj[v].add(w);
055                adj[w].add(v);
056        }
057
058
059        /**
060         * Return the list of neighbors of vertex v as in Iterable.
061         * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= v < V}
062         */
063        public Iterable<Integer> adj(int v) {
064                if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
065                return adj[v];
066        }
067        
068    /**
069     * Returns the degree of vertex {@code v}.
070     *
071     * @param  v the vertex
072     * @return the degree of vertex {@code v}
073     * @throws IllegalArgumentException unless {@code 0 <= v < V}
074     */
075    public int degree(int v) {
076                if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
077                return adj[v].size();
078    }
079
080        /**
081         * Return a string representation of the graph.
082         */
083        public String toString() {
084                StringBuilder s = new StringBuilder();
085                String NEWLINE = System.getProperty("line.separator");
086                s.append(V + " vertices, " + E + " edges " + NEWLINE);
087                for (int v = 0; v < V; v++) {
088                        s.append(v + ": ");
089                        for (int w : adj[v]) {
090                                s.append(w + " ");
091                        }
092                        s.append(NEWLINE);
093                }
094                return s.toString();
095        }
096
097        /**
098         * Save a graphviz representation of the graph.
099         * See <a href="http://www.graphviz.org/">graphviz.org</a>.
100         */
101        public void toGraphviz(String filename) {
102                GraphvizBuilder gb = new GraphvizBuilder ();
103                for (int v = 0; v < V; v++) {
104                        gb.addNode (v);
105                        boolean showSelfLoop = false;
106                        for (int w : adj[v]) {
107                                if (v < w) // only once each edge
108                                        gb.addEdge (v, w);
109                                if (v == w) {
110                                        showSelfLoop = !showSelfLoop;
111                                        if (showSelfLoop)
112                                                gb.addEdge (v, w);
113                                }
114                        }
115                }
116                gb.toFileUndirected (filename);
117        }
118
119        /**
120         * Test client.
121         */
122        public static void main(String[] args) {
123                //args = new String [] { "data/tinyCG.txt" };
124                args = new String [] { "data/tinyG.txt" };
125                //args = new String [] { "20", "40" };
126
127                Graph G;
128                if (args.length == 1) {
129                        In in = new In(args[0]);
130                        G = GraphGenerator.fromIn (in);
131                } else {
132                        int V = Integer.parseInt (args[0]);
133                        int E = Integer.parseInt (args[1]);
134                        G = GraphGenerator.simple(V, E);
135                }
136                StdOut.println(G);
137                G.toGraphviz ("g.png");
138        }
139}