1  import java.util.*;
  2  
  3  public class WeightedGraph<V> extends UnweightedGraph<V> {
  4    /** Construct an empty */
  5    public WeightedGraph() {
  6    }
  7    
  8    /** Construct a WeightedGraph from vertices and edged in arrays */
  9    public WeightedGraph(V[] vertices, int[][] edges) {
 10      createWeightedGraph(java.util.Arrays.asList(vertices), edges);
 11    }
 12  
 13    /** Construct a WeightedGraph from vertices and edges in list */
 14    public WeightedGraph(int[][] edges, int numberOfVertices) {
 15      List<V> vertices = new ArrayList<>();
 16      for (int i = 0; i < numberOfVertices; i++)
 17        vertices.add((V)(new Integer(i)));
 18      
 19      createWeightedGraph(vertices, edges);
 20    }
 21  
 22    /** Construct a WeightedGraph for vertices 0, 1, 2 and edge list */
 23    public WeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
 24      createWeightedGraph(vertices, edges);
 25    }
 26  
 27    /** Construct a WeightedGraph from vertices 0, 1, and edge array */
 28    public WeightedGraph(List<WeightedEdge> edges,
 29        int numberOfVertices) {
 30      List<V> vertices = new ArrayList<>();
 31      for (int i = 0; i < numberOfVertices; i++)
 32        vertices.add((V)(new Integer(i)));
 33      
 34      createWeightedGraph(vertices, edges);
 35    }
 36  
 37    /** Create adjacency lists from edge arrays */
 38    private void createWeightedGraph(List<V> vertices, int[][] edges) {
 39      this.vertices = vertices;     
 40  
 41      for (int i = 0; i < vertices.size(); i++) {
 42        neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
 43      }
 44  
 45      for (int i = 0; i < edges.length; i++) {
 46        neighbors.get(edges[i][0]).add(
 47          new WeightedEdge(edges[i][0], edges[i][1], edges[i][2]));
 48      }
 49    }
 50  
 51    /** Create adjacency lists from edge lists */
 52    private void createWeightedGraph(
 53        List<V> vertices, List<WeightedEdge> edges) {
 54      this.vertices = vertices;     
 55  
 56      for (int i = 0; i < vertices.size(); i++) {
 57        neighbors.add(new ArrayList<Edge>()); // Create a list for vertices
 58      }
 59  
 60      for (WeightedEdge edge: edges) {      
 61        neighbors.get(edge.u).add(edge); // Add an edge into the list
 62      }
 63    }
 64  
 65    /** Return the weight on the edge (u, v) */
 66    public double getWeight(int u, int v) throws Exception {
 67      for (Edge edge : neighbors.get(u)) {
 68        if (edge.v == v) {
 69          return ((WeightedEdge)edge).weight;
 70        }
 71      }
 72      
 73      throw new Exception("Edge does not exit");
 74    }
 75    
 76    /** Display edges with weights */
 77    public void printWeightedEdges() {
 78      for (int i = 0; i < getSize(); i++) {
 79        System.out.print(getVertex(i) + " (" + i + "): ");
 80        for (Edge edge : neighbors.get(i)) {
 81          System.out.print("(" + edge.u +
 82            ", " + edge.v + ", " + ((WeightedEdge)edge).weight + ") ");
 83        }
 84        System.out.println();
 85      }
 86    }
 87   
 88    /** Add an edge (u, v, weight) to the graph. */  
 89    public boolean addEdge(int u, int v, double weight) {
 90      return addEdge(new WeightedEdge(u, v, weight));
 91    }
 92  
 93    /** Get a minimum spanning tree rooted at vertex 0 */
 94    public MST getMinimumSpanningTree() {
 95      return getMinimumSpanningTree(0);
 96    }
 97    
 98    /** Get a minimum spanning tree rooted at a specified vertex */
 99    public MST getMinimumSpanningTree(int startingVertex) {
100      // cost[v] stores the cost by adding v to the tree
101      double[] cost = new double[getSize()];
102      for (int i = 0; i < cost.length; i++) {
103        cost[i] = Double.POSITIVE_INFINITY; // Initial cost 
104      }
105      cost[startingVertex] = 0; // Cost of source is 0
106  
107      int[] parent = new int[getSize()]; // Parent of a vertex
108      parent[startingVertex] = -1; // startingVertex is the root
109      double totalWeight = 0; // Total weight of the tree thus far
110  
111      List<Integer> T = new ArrayList<>();
112      
113      // Expand T
114      while (T.size() < getSize()) {
115        // Find smallest cost u in V - T 
116        int u = -1; // Vertex to be determined
117        double currentMinCost = Double.POSITIVE_INFINITY;
118        for (int i = 0; i < getSize(); i++) {
119          if (!T.contains(i) && cost[i] < currentMinCost) {
120            currentMinCost = cost[i];
121            u = i;
122          }
123        }
124  
125        if (u == -1) break; else T.add(u); // Add a new vertex to T
126        totalWeight += cost[u]; // Add cost[u] to the tree
127  
128        // Adjust cost[v] for v that is adjacent to u and v in V - T
129        for (Edge e : neighbors.get(u)) {
130          if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) {
131            cost[e.v] = ((WeightedEdge)e).weight;
132            parent[e.v] = u; 
133          }
134        }
135      } // End of while
136  
137      return new MST(startingVertex, parent, T, totalWeight);
138    }
139  
140    /** MST is an inner class in WeightedGraph */
141    public class MST extends SearchTree {
142      private double totalWeight; // Total weight of all edges in the tree
143  
144      public MST(int root, int[] parent, List<Integer> searchOrder,
145          double totalWeight) {
146        super(root, parent, searchOrder);
147        this.totalWeight = totalWeight;
148      }
149  
150      public double getTotalWeight() {
151        return totalWeight;
152      }
153    }
154  
155    /** Find single source shortest paths */
156    public ShortestPathTree getShortestPath(int sourceVertex) {
157      // cost[v] stores the cost of the path from v to the source
158      double[] cost = new double[getSize()];
159      for (int i = 0; i < cost.length; i++) {
160        cost[i] = Double.POSITIVE_INFINITY; // Initial cost set to infinity
161      }
162      cost[sourceVertex] = 0; // Cost of source is 0
163  
164      // parent[v] stores the previous vertex of v in the path
165      int[] parent = new int[getSize()];
166      parent[sourceVertex] = -1; // The parent of source is set to -1
167      
168      // T stores the vertices whose path found so far
169      List<Integer> T = new ArrayList<>();
170      
171      // Expand T
172      while (T.size() < getSize()) {
173        // Find smallest cost v in V - T 
174        int u = -1; // Vertex to be determined
175        double currentMinCost = Double.POSITIVE_INFINITY;
176        for (int i = 0; i < getSize(); i++) {
177          if (!T.contains(i) && cost[i] < currentMinCost) {
178            currentMinCost = cost[i];
179            u = i;
180          }
181        }
182        
183        if (u == -1) break; else T.add(u); // Add a new vertex to T
184        
185        // Adjust cost[v] for v that is adjacent to u and v in V - T
186        for (Edge e : neighbors.get(u)) {
187          if (!T.contains(e.v) 
188              && cost[e.v] > cost[u] + ((WeightedEdge)e).weight) {
189            cost[e.v] = cost[u] + ((WeightedEdge)e).weight;
190            parent[e.v] = u; 
191          }
192        }
193      } // End of while
194  
195      // Create a ShortestPathTree
196      return new ShortestPathTree(sourceVertex, parent, T, cost);
197    }
198  
199    /** ShortestPathTree is an inner class in WeightedGraph */
200    public class ShortestPathTree extends SearchTree {
201      private double[] cost; // cost[v] is the cost from v to source
202  
203      /** Construct a path */
204      public ShortestPathTree(int source, int[] parent, 
205          List<Integer> searchOrder, double[] cost) {
206        super(source, parent, searchOrder);
207        this.cost = cost;
208      }
209  
210      /** Return the cost for a path from the root to vertex v */
211      public double getCost(int v) {
212        return cost[v];
213      }
214  
215      /** Print paths from all vertices to the source */
216      public void printAllPaths() {
217        System.out.println("All shortest paths from " +
218          vertices.get(getRoot()) + " are:");
219        for (int i = 0; i < cost.length; i++) {
220          printPath(i); // Print a path from i to the source
221          System.out.println("(cost: " + cost[i] + ")"); // Path cost
222        }
223      }
224    }
225  }