complete the following, using only Graph and GraphGenerator. You may copy code from other classes, but you should not use the classes themselves.

The eccentricity of a vertex v is the length of the shortest path from that vertex to the furthest vertex from v. The diameter of a graph is the maximum eccentricity of any vertex. The radius of a graph is the smallest eccentricity of any vertex. A center is a vertex whose eccentricity is the radius. Implement the following API.

public class MyGraphProperties { // constructor (exception if G not connected) MyGraphProperties(Graph G) { } // eccentricity of v int eccentricity(int v) { } // diameter of G int diameter() { } // radius of G int radius() { } // a center of G --- any one will do int center() { } } 

// Exercise 4.1.16 package algs41;

import stdlib.*;

// This is problem 4.1.16 from the textbook // // You need only change the constructor. // You can also change the main method. // But you should not change eccentricity(), diameter(), radius(), center() or isCenter() // You can (and should!) add more private methods (such as bfs or dfs) public class MyGraphProperties { int[] eccentricity; int diameter; int radius; int center;

// Constructor can be linear in G.V() * G.E() public MyGraphProperties(Graph G) { this.eccentricity = new int[G.V()]; int diameter = Integer.MIN_VALUE; int radius = Integer.MAX_VALUE; int center = -1; // If G.V()==0, then these are the correct values. // If G is not connected, you should throw a new IllegalArgumentException() // I suggest that you first get it to work for a connected graph // This will require that you traverse the graph starting from some node (say 0) // You can then adjust your code so that it throws an exception in the case that all nodes are not visited

// TODO // compute the eccentricity, diameter, radius and center // The center of the graph is not unique, set center to SOME center --- it does not matter which one this.diameter = diameter; this.radius = radius; this.center = center; }

// Do not change the following constant time methods public int eccentricity(int v) { return eccentricity[v]; } public int diameter() { return diameter; } public int radius() { return radius; } public int center() { return center; } public boolean isCenter(int v) { return eccentricity[v] == radius; }

public static void main(String[] args) { //Graph G = new Graph(new In("data/tinyG.txt")); // this is non-connected -- should throw an exception //Graph G = GraphGenerator.connected (10, 20, 2); // Random non-connected graph -- should throw an exception

Graph G = new Graph(new In("data/tinyCG.txt")); // diameter=2, radius=2, every node is a center //Graph G = GraphGenerator.binaryTree (10); // A complete binary tree //Graph G = GraphGenerator.path (10); // A path -- diameter=V-1 //Graph G = GraphGenerator.connected (20, 400); // Random connected graph

StdOut.println(G); G.toGraphviz ("g.png");

MyGraphProperties gp = new MyGraphProperties(G); for (int v = 0; v < G.V(); v++) StdOut.format ("eccentricity of %d: %d ", v, gp.eccentricity (v)); StdOut.format ("diameter=%d, radius=%d, center=%d ", gp.diameter(), gp.radius (), gp.center ()); } }

package algs41; import stdlib.*; import algs13.Bag; import algs13.Stack;

/** * The Graph class represents an undirected graph of vertices * named 0 through V-1. * It supports the following operations: add an edge to the graph, * iterate over all of the neighbors adjacent to a vertex. * Parallel edges and self-loops are permitted. *

* For additional documentation, see Section 5.1 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class Graph { private final int V; private int E; private final Bag[] adj;

/** * Create an empty graph with V vertices. */ @SuppressWarnings("unchecked") public Graph(int V) { if (V < 0) throw new Error("Number of vertices must be nonnegative"); this.V = V; this.E = 0; this.adj = new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<>(); } }

/** * Create a random graph with V vertices and E edges with no parallel edges or self loops. * Expected running time is proportional to V + E. */ public Graph(int V, int E) { this (V, E, false); } /** * Create a random graph with V vertices and E edges. * Expected running time is proportional to V + E. */ public Graph(int V, int E, boolean allowParallelEdgesAndSelfLoops) { this(V); if (E < 0) throw new Error("Number of edges must be nonnegative"); if (allowParallelEdgesAndSelfLoops) { for (int i = 0; i < E; i++) { int v = (int) (Math.random() * V); int w = (int) (Math.random() * V); addEdge(v, w); } } else { if (E > V*(V-1)/2) throw new Error("Number of edges must be less than V*(V-1)/2"); newEdge: while (E>0) { int v = (int) (Math.random() * V); int w = (int) (Math.random() * V); if (v == w) continue; for (int w2 : adj[v]) if (w == w2) continue newEdge; addEdge(v, w); E--; } } }

/** * Create a digraph from input stream. */ public Graph(In in) { this(in.readInt()); int E = in.readInt(); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); addEdge(v, w); } }

/** * Copy constructor. */ public Graph(Graph G) { this(G.V()); this.E = G.E(); for (int v = 0; v < G.V(); v++) { // reverse so that adjacency list is in same order as original Stack reverse = new Stack<>(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } }

/** * Return the number of vertices in the graph. */ public int V() { return V; }

/** * Return the number of edges in the graph. */ public int E() { return E; }

/** * Add the undirected edge v-w to graph. * @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V */ public void addEdge(int v, int w) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); if (w < 0 || w >= V) throw new IndexOutOfBoundsException(); E++; adj[v].add(w); adj[w].add(v); }

/** * Return the list of neighbors of vertex v as in Iterable. * @throws java.lang.IndexOutOfBoundsException unless 0 <= v < V */ public Iterable adj(int v) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); return adj[v]; }

/** * Return a string representation of the graph. */ public String toString() { StringBuilder s = new StringBuilder(); String NEWLINE = System.getProperty("line.separator"); s.append(V + " vertices, " + E + " edges " + NEWLINE); for (int v = 0; v < V; v++) { s.append(v + ": "); for (int w : adj[v]) { s.append(w + " "); } s.append(NEWLINE); } return s.toString(); }

/** * Save a graphviz representation of the graph. * See graphviz.org. */ public void toGraphviz(String filename) { GraphvizBuilder gb = new GraphvizBuilder (); for (int v = 0; v < V; v++) { gb.addNode (v); boolean showSelfLoop = false; for (int w : adj[v]) { if (v < w) // only once each edge gb.addEdge (v, w); if (v == w) { showSelfLoop = !showSelfLoop; if (showSelfLoop) gb.addEdge (v, w); } } } gb.toFileUndirected (filename); }

/** * Test client. */ public static void main(String[] args) { args = new String [] { "data/tinyCG.txt" }; //args = new String [] { "data/tinyG.txt" }; args = new String [] { "20", "40" };

Graph G; if (args.length == 1) { In in = new In(args[0]); G = new Graph(in); } else { int V = Integer.parseInt (args[0]); int E = Integer.parseInt (args[1]); G = new Graph(V, E, true); } StdOut.println(G); G.toGraphviz ("g.png"); } }

package algs41;

import java.util.Arrays; import stdlib.*;

public class GraphGenerator {

public static Graph complete (int V) { return simple (V, V * (V - 1) / 2); } public static Graph simple (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); if (E > V * (V - 1) / 2) throw new IllegalArgumentException ("Number of edges must be less than V*(V-1)/2"); Graph G = new Graph (V); newEdge: while (E > 0) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); if (v == w) continue; for (int w2 : G.adj (v)) if (w == w2) continue newEdge; G.addEdge (v, w); E--; } return G; } public static Graph simpleConnected (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); if (E > V * (V - 1) / 2) throw new IllegalArgumentException ("Number of edges must be less than V*(V-1)/2"); Graph G = spanningTree (V); newEdge: while (G.E () < E) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); if (v == w) continue; for (int w2 : G.adj (v)) if (w == w2) continue newEdge; G.addEdge (v, w); E--; } return G; } public static Graph connected (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); Graph G = spanningTree (V); while (G.E () < E) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); G.addEdge (v, w); } return G; } public static Graph random (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); Graph G = new Graph (V); while (G.E () < E) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); G.addEdge (v, w); } return G; } public static Graph spanningTree (int V) { if (V < 1) throw new IllegalArgumentException (); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle (vertices); Graph G = new Graph (V); for (int i = 1; i < V; i++) { int v = vertices[StdRandom.uniform (i)]; int w = vertices[i]; G.addEdge (v, w); } return G; } public static Graph path(int V) { if (V < 1) throw new IllegalArgumentException (); Graph G = new Graph(V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle(vertices); for (int i = 0; i < V-1; i++) { G.addEdge(vertices[i], vertices[i+1]); } return G; } public static Graph cycle(int V) { if (V < 1) throw new IllegalArgumentException (); Graph G = new Graph(V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle(vertices); for (int i = 0; i < V-1; i++) { G.addEdge(vertices[i], vertices[i+1]); } G.addEdge(vertices[V-1], vertices[0]); return G; } public static Graph binaryTree (int V) { if (V < 1) throw new IllegalArgumentException (); Graph G = new Graph (V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle (vertices); for (int i = 1; i < V; i++) { G.addEdge (vertices[i], vertices[(i - 1) / 2]); } return G; } public static Graph connected(int V, int E, int c) { if (c >= V || c <= 0) throw new IllegalArgumentException("Number of components must be between 1 and V"); if (E <= (V-c)) throw new IllegalArgumentException("Number of edges must be at least (V-c)"); if (E > V * (V - 1) / 2) throw new IllegalArgumentException("Too many edges");

int[] label = new int[V]; for (int v = 0; v < V; v++) { label[v] = StdRandom.uniform(c); } // The following hack ensures that each color appears at least once { Arrays.sort (label); label[0] = 0; for (int v = 1; v < V; v++) { if (label[v]-label[v-1] > 1 || V-v == c-label[v-1]-1) label[v] = label[v-1]+1; } StdRandom.shuffle (label); }

// make all vertices with label c a connected component Graph G = new Graph(V); for (int i = 0; i < c; i++) { // how many vertices in component c int count = 0; for (int v = 0; v < V; v++) { if (label[v] == i) count++; } int[] vertices = new int[count]; { int j = 0; for (int v = 0; v < V; v++) if (label[v] == i) vertices[j++] = v; } StdRandom.shuffle(vertices);

for (int j = 1; j < count; j++) { int v = vertices[StdRandom.uniform (j)]; int w = vertices[j]; G.addEdge (v, w); } }

while (G.E() < E) { int v = StdRandom.uniform(V); int w = StdRandom.uniform(V); if (v != w && label[v] == label[w]) { G.addEdge(v, w); } }

return G; } public static void print (Graph G, String filename) { if (G == null) return; System.out.println (filename); System.out.println (G); System.out.println (); G.toGraphviz (filename + ".png"); } public static void main (String[] args) { //StdRandom.setSeed (10); args = new String[] { "6", "10", "3" };

int V = Integer.parseInt (args[0]); int E = Integer.parseInt (args[1]); int c = Integer.parseInt (args[2]);

print (GraphGenerator.random (V, E), "random-" + V + "-" + E); print (GraphGenerator.simple (V, E), "simple-" + V + "-" + E); print (GraphGenerator.complete (V), "complete-" + V); print (GraphGenerator.spanningTree (V), "spanningTree-" + V); print (GraphGenerator.simpleConnected (V, E), "simpleConnected-" + V + "-" + E); print (GraphGenerator.connected (V, E), "connected-" + V + "-" + E); print (GraphGenerator.path (V), "path-" + V); print (GraphGenerator.binaryTree (V), "binaryTree-" + V); print (GraphGenerator.cycle (V), "cycle-" + V); if (E <= (V - c)) E = (V - c) + 1; print (GraphGenerator.connected (V, E, c), "connected-" + V + "-" + E + "-" + c); } }