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; 028 int radius; 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; 035 int radius = Integer.MAX_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; 047 this.radius = radius; 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; } 054 public int radius() { return radius; } 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)); 073 StdOut.format ("diameter=%d, radius=%d, center=%d\n", gp.diameter(), gp.radius (), gp.center ()); 074 } 075}