// 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)

//

// TODO: complete the following, using only Graph and GraphGenerator.

// You may copy code from other classes in algs41, but you should not use the classes themselves.

// In particular, you may not use BreadthFirstPaths although you may copy code from there.

//

// Definitions:

// - The "distance" from vertex v to vertex w is the length of the shortest path from v to w.

// - The "eccentricity" of a vertex v is distance to the farthest 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. The center is not necessarily unique.

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 = GraphGenerator.fromIn (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 = GraphGenerator.fromIn (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 ());

}

}

End of Question

_________________________________________________________________________________________________

Extra information:

package algs41;

import stdlib.*;

import algs13.Bag;

/**

* 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<>();

}

}

/**

* 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 = GraphGenerator.fromIn (in);

} else {

int V = Integer.parseInt (args[0]);

int E = Integer.parseInt (args[1]);

G = GraphGenerator.simple(V, E);

}

StdOut.println(G);

G.toGraphviz ("g.png");

}

}

____________________________________________________________________________________________

package algs41;

import java.util.Arrays;

import stdlib.*;

public class GraphGenerator {

/**

* Create a graph from input stream.

*/

public static Graph fromIn (In in) {

Graph G = new Graph (in.readInt());

int E = in.readInt();

for (int i = 0; i < E; i++) {

int v = in.readInt();

int w = in.readInt();

G.addEdge(v, w);

}

return G;

}

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);

}

}