// 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; }

HERE IS THE BREADTHFIRSTSEARCH CODE WE WERE REQUESTED TO USE:

public class BreadthFirstPaths {

private static final int INFINITY = Integer.MAX_VALUE;

private final boolean[] marked; // marked[v] = is there an s-v path

private final int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path

private final int[] distTo; // distTo[v] = number of edges shortest s-v path

// single source

public BreadthFirstPaths(Graph G, int s) {

marked = new boolean[G.V()];

distTo = new int[G.V()];

edgeTo = new int[G.V()];

bfs(G, s);

}

private void bfs(Graph G, int s) {

Queue q = new Queue();

for (int v = 0; v

distTo[s] = 0;

marked[s] = true;

q.enqueue(s);

while (!q.isEmpty()) {

int v = q.dequeue();

for (int w : G.adj(v)) {

if (!marked[w]) {

edgeTo[w] = v;

distTo[w] = distTo[v] + 1;

marked[w] = true;

q.enqueue(w);

}

}

}

}

}

4.1.16 The eccentricity of a vertex v is the the length of the shortest path from that ver- tex 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 GraphProperties GraphProperties(Graph G) constructor (exception ifG not connected int eccentricity(inteccentricity ofv int diameterO int radiusO int centerO diameter of G radius ofG a center of