```001// Exercise 4.1.16
002package algs41;
003
004import stdlib.*;
005
006// This is problem 4.1.16 from the textbook
007//
008// You need only change the constructor.
009// You can also change the main method.
010// But you should not change eccentricity(), diameter(), radius(), center() or isCenter()
011// You can (and should!) add more private methods (such as bfs or dfs)
012//
013// TODO: complete the following, using only Graph and GraphGenerator.
014// You may copy code from other classes in algs41, but you should not use the classes themselves.
015// In particular, you may not use BreadthFirstPaths although you may copy code from there.
016//
017// The "distance" from vertex v to vertex w is the length of the shortest path
018// from v to w.
019// The "eccentricity" of a vertex v is distance to the farthest vertex from v.
020// The "diameter" of a graph is the maximum eccentricity of any vertex.
021// The "radius" of a graph is the smallest eccentricity of any vertex.
022// A "center" is a vertex whose eccentricity is the radius.
023// The center is not necessarily unique.
024
025public class MyGraphProperties {
026        int[] eccentricity;
027        int diameter;
029        int center;
030
031        // Constructor can be linear in G.V() * G.E()
032        public MyGraphProperties(Graph G) {
033                this.eccentricity = new int[G.V()];
034                int diameter = Integer.MIN_VALUE;
036                int center = -1;
037                // If G.V()==0, then these are the correct values.
038                // If G is not connected, you should throw a new IllegalArgumentException()
039                // I suggest that you first get it to work for a connected graph
040                // This will require that you traverse the graph starting from some node (say 0)
041                // You can then adjust your code so that it throws an exception in the case that all nodes are not visited
042
043                // TODO
044                // compute the eccentricity, diameter, radius and center
045                // The center of the graph is not unique, set center to SOME center --- it does not matter which one
046                this.diameter = diameter;
048                this.center   = center;
049        }
050
051        // Do not change the following constant time methods
052        public int eccentricity(int v) { return eccentricity[v]; }
053        public int diameter()          { return diameter; }
055        public int center()            { return center; }
056        public boolean isCenter(int v) { return eccentricity[v] == radius; }
057
058        public static void main(String[] args) {
059                //Graph G = GraphGenerator.fromIn (new In("data/tinyG.txt")); // this is non-connected -- should throw an exception
060                //Graph G = GraphGenerator.connected (10, 20, 2); // Random non-connected graph -- should throw an exception
061
062                Graph G = GraphGenerator.fromIn (new In("data/tinyCG.txt")); // diameter=2, radius=2, every node is a center
063                //Graph G = GraphGenerator.binaryTree (10); // A complete binary tree
064                //Graph G = GraphGenerator.path (10); // A path -- diameter=V-1
065                //Graph G = GraphGenerator.connected (20, 400); // Random connected graph
066
067                StdOut.println(G);
068                G.toGraphviz ("g.png");
069
070                MyGraphProperties gp = new MyGraphProperties(G);
071                for (int v = 0; v < G.V(); v++)
072                        StdOut.format ("eccentricity of %d: %d\n", v, gp.eccentricity (v));
074        }
075}

```