Tuesday 28 February 2017

Chapter 30 Exercise 3, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

30.3 (Raise flags) Rewrite Listing 15.13 using a thread to animate a flag being
raised. Compare the program with Listing 15.13 by setting the delay time to 10
in both programs. Which one runs the animation faster?

import java.applet.Applet;
import java.applet.AudioClip;
import java.awt.*;

import javax.swing.*;

public class Exercise03 extends JApplet{
 private static final long serialVersionUID = 1L;

 
 public Exercise03() {
  FlagPanel flagPanel = new FlagPanel();
  add(flagPanel);
  Thread thread = new Thread(flagPanel);
  thread.start();
 }

 public static void main(String[] args) {
  JFrame frame = new JFrame();
  frame.add(new Exercise03());
  frame.setTitle("Exercise03");
  frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  frame.setSize(500, 500);
  frame.setMinimumSize(new Dimension(frame.getWidth(), frame.getHeight()));
  frame.setLocationRelativeTo(null);
  frame.setVisible(true);
 }

 class FlagPanel extends JPanel implements Runnable {
  private int currentFlag = 0;
  private ImageIcon imageIcon;
  private int x;
  private int y;
  private static final long serialVersionUID = 1L;
  private boolean newFlag = true;
  private AudioClip[] audioClip = new AudioClip[7];
  private Image image;
  
  public FlagPanel() {
   for (int i = 0; i < audioClip.length; i++) {
    audioClip[i] = Applet.newAudioClip(this.getClass().getResource("anthem" + i + ".mid")); 
   }   
  }
  
  @Override
  protected void paintComponent(Graphics g) {
   super.paintComponent(g);
   if (newFlag) {
    audioClip[currentFlag].play();
    y = getHeight();
    newFlag = false;
    imageIcon = new ImageIcon(this.getClass().getResource("flag" + currentFlag + ".gif"));
    image = imageIcon.getImage();
   }
   x = (getWidth() - imageIcon.getIconWidth()) / 2;
   g.drawImage(image, x,  y, imageIcon.getIconWidth(), imageIcon.getIconHeight(), this);
   if (y + imageIcon.getIconHeight() <= 0) {
    newFlag = true;
    audioClip[currentFlag].stop();
    currentFlag++;
    if (currentFlag > 6) {
     currentFlag = 0;
    }    
   }
  }

  @Override
  public void run() {
   try {
    while (true) {
     Thread.sleep(10);
     y--;          
     repaint();
    }
   } catch (InterruptedException e) {
    e.printStackTrace();
   }
  }
 }
}

Chapter 30 Exercise 2, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

30.2 (Racing cars) Rewrite Programming Exercise 15.29 using a thread to control car racing. Compare the program with Programming Exercise 15.29 by setting the delay time to 10 in both programs. Which one runs the animation faster?

import java.awt.*;
import java.awt.event.*;

import javax.swing.*;
import javax.swing.border.LineBorder;

public class Exercise02 extends JApplet {

 private static final long serialVersionUID = 1L;
 private CarPanel carPanel1 = new CarPanel();
 private CarPanel carPanel2 = new CarPanel();
 private CarPanel carPanel3 = new CarPanel();
 private CarPanel carPanel4 = new CarPanel();
 private JTextField jTextField1 = new JTextField("100");
 private JTextField jTextField2 = new JTextField("100");
 private JTextField jTextField3 = new JTextField("100");
 private JTextField jTextField4 = new JTextField("100");
 
 
 public static void main(String[] args) {
  JFrame frame = new JFrame();
  frame.add(new Exercise02());
  frame.setTitle("Exercise02");
  frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  frame.setSize(600, 400);
  frame.setLocationRelativeTo(null);
  frame.setVisible(true);
 }

 
 public Exercise02() {
  JPanel panel2 = new JPanel(new GridLayout(1, 8));
  jTextField1.addKeyListener(new KeyAdapter() {   
   @Override
   public void keyReleased(KeyEvent e) {
    try {
     carPanel1.setSpeed(Integer.parseInt(jTextField1.getText()));     
    } catch (NumberFormatException e2) {
    }
   }
  });
  jTextField2.addKeyListener(new KeyAdapter() {   
   @Override
   public void keyReleased(KeyEvent e) {
    try {
     carPanel2.setSpeed(Integer.parseInt(jTextField2.getText()));     
    } catch (NumberFormatException e2) {
    }
   }
  });
  jTextField3.addKeyListener(new KeyAdapter() {   
   @Override
   public void keyReleased(KeyEvent e) {
    try {
     carPanel3.setSpeed(Integer.parseInt(jTextField3.getText()));     
    } catch (NumberFormatException e2) {
    }
   }
  });
  jTextField4.addKeyListener(new KeyAdapter() {   
   @Override
   public void keyReleased(KeyEvent e) {
    try {
     carPanel4.setSpeed(Integer.parseInt(jTextField4.getText()));     
    } catch (NumberFormatException e2) {
    }
   }
  });
  panel2.add(new JLabel("Car 1: ", JLabel.RIGHT));
  panel2.add(jTextField1);
  panel2.add(new JLabel("Car 2: ", JLabel.RIGHT));
  panel2.add(jTextField2);
  panel2.add(new JLabel("Car 3: ", JLabel.RIGHT));
  panel2.add(jTextField3);
  panel2.add(new JLabel("Car 4: ", JLabel.RIGHT));
  panel2.add(jTextField4);
  add(panel2, BorderLayout.NORTH);
  JPanel panel1 = new JPanel(new GridLayout(4, 1));
  panel1.add(carPanel1);
  panel1.add(carPanel2);
  panel1.add(carPanel3);
  panel1.add(carPanel4);
  add(panel1, BorderLayout.CENTER);
 }

 class CarPanel extends JPanel  implements Runnable  {
  private int yPos;
  private int xPos;
  private int size = 20;
  private int speed = 100;
  private boolean firstRun = true;
  private static final long serialVersionUID = 1L;

  public CarPanel() {
   setBorder(new LineBorder(Color.BLACK));
   Thread thread = new Thread(this);
   thread.start();
  }
  
  public void setSpeed(int speed) {
   if (speed < 1) {
    speed = 1;
   }
   this.speed = speed;
  }
  
  @Override
  protected void paintComponent(Graphics g) {
   super.paintComponent(g);
   if (firstRun) {
    xPos = - 5* size;
    firstRun = false;
   }
   yPos = getHeight();
   g.setColor(Color.BLACK);
   g.fillOval(xPos + size, yPos - size, size, size);
   g.fillOval(xPos + 3 * size, yPos - size, size, size);
   g.setColor(Color.RED);
   g.fillRect(xPos, yPos - 2 * size, 5 * size, size);
   g.setColor(Color.BLUE);
   Polygon p = new Polygon();
   p.addPoint(xPos + size, yPos - 2 * size);
   p.addPoint(xPos + 2 * size, yPos - 3 * size);
   p.addPoint(xPos + 3 * size, yPos - 3 * size);
   p.addPoint(xPos + 4 * size, yPos - 2 * size);
   g.fillPolygon(p);
  }
 
  @Override
  public void run() {
   try {
    while (true) {
     Thread.sleep(speed);
     xPos += 1;
     if (xPos >= getWidth()) {
      xPos = -5 * size;
     }
     repaint();
    }
   } catch (InterruptedException e) {
    e.printStackTrace();
   }
  }

 }
}

Chapter 30 Exercise 1, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

30.1  (Revise Listing 30.1) Rewrite Listing 30.1 to display the output in a text area, as shown in Figure 30.30.

public class Exercise01 {
 public static void main(String[] args) {
  // Create tasks
  Runnable printA = new PrintChar('a', 100, 200);
  Runnable printB = new PrintChar('b', 100, 100);
  Runnable print100 = new PrintNum(100);

  // Create threads
  Thread thread3 = new Thread(print100);
  Thread thread1 = new Thread(printA);
  Thread thread2 = new Thread(printB);
  

  // Start threads
  thread1.start();
  thread2.start();
  thread3.start();
 }
}

// The task for printing a specified character in specified times
class PrintChar implements Runnable {
 private char charToPrint; // The character to print
 private int times; // The times to repeat
 private int ms;

 /**
  * Construct a task with specified character and number of times to print
  * the character
  */
 public PrintChar(char c, int t, int ms) {
  charToPrint = c;
  times = t;
  this.ms = ms;
 }

 @Override
 /** Override the run() method to tell the system
  *  what the task to perform
  */
 public void run() {
  try {
   Thread.sleep(50);
   System.out.print(charToPrint);
   Thread.sleep(ms);
   for (int i = 1; i < times; i++) {
    System.out.print(charToPrint);
   }
  } catch (InterruptedException e) {
   e.printStackTrace();
  }  
 }
}

// The task class for printing number from 1 to n for a given n
class PrintNum implements Runnable {
 private int lastNum;

 /** Construct a task for printing 1, 2, ... i */
 public PrintNum(int n) {
  lastNum = n;
 }

 @Override
 /** Tell the thread how to run */
 public void run() {
  try {
   System.out.print(" 1");
   Thread.sleep(100);
   for (int i = 2; i <= lastNum; i++) {
    System.out.print(" " + i);
   }
  } catch (InterruptedException e) {
   e.printStackTrace();
  } 
 }
}

Chapter 29 Exercise 20, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

29.20 (Test if a vertex u is in T efficiently) Since T is implemented using a list
in the getMinimumSpanningTree and getShortestPath methods in
Listing 29.2 WeightedGraph.java, testing whether a vertex u is in T by invoking
T.contains(u) takes O(n) time. Modify these two methods by introducing
an array named isInT. Set isInT[u] to true when a vertex u is added to T.
Testing whether a vertex u is in T can now be done in O(1) time. Write a test
program using the following code, where graph1 is created from Figure 29.1.
WeightedGraph<String> graph1 = new WeightedGraph<>(edges, vertices);
WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
System.out.println("Total weight is " + tree1.getTotalWeight());
tree1.printTree();
WeightedGraph<String>.ShortestPathTree tree2 =
graph1.getShortestPath(graph1.getIndex("Chicago"));
tree2.printAllPaths();


import java.util.*;

public class Exercise20 {
  public static void main(String[] args) {
    String[] vertices = { "Seattle", "San Francisco", "Los Angeles", "Denver",
        "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami",
        "Dallas", "Houston" };

    int[][] edges = { { 0, 1, 807 }, { 0, 3, 1331 }, { 0, 5, 2097 },
        { 1, 0, 807 }, { 1, 2, 381 }, { 1, 3, 1267 }, { 2, 1, 381 },
        { 2, 3, 1015 }, { 2, 4, 1663 }, { 2, 10, 1435 }, { 3, 0, 1331 },
        { 3, 1, 1267 }, { 3, 2, 1015 }, { 3, 4, 599 }, { 3, 5, 1003 },
        { 4, 2, 1663 }, { 4, 3, 599 }, { 4, 5, 533 }, { 4, 7, 1260 },
        { 4, 8, 864 }, { 4, 10, 496 }, { 5, 0, 2097 }, { 5, 3, 1003 },
        { 5, 4, 533 }, { 5, 6, 983 }, { 5, 7, 787 }, { 6, 5, 983 },
        { 6, 7, 214 }, { 7, 4, 1260 }, { 7, 5, 787 }, { 7, 6, 214 },
        { 7, 8, 888 }, { 8, 4, 864 }, { 8, 7, 888 }, { 8, 9, 661 },
        { 8, 10, 781 }, { 8, 11, 810 }, { 9, 8, 661 }, { 9, 11, 1187 },
        { 10, 2, 1435 }, { 10, 4, 496 }, { 10, 8, 781 }, { 10, 11, 239 },
        { 11, 8, 810 }, { 11, 9, 1187 }, { 11, 10, 239 } };

      WeightedGraph<String> graph1 = 
        new WeightedGraph<>(edges, vertices);
      WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
      System.out.println("Total weight is " + tree1.getTotalWeight());
      tree1.printTree();
      System.out.println();
      WeightedGraph<String>.ShortestPathTree tree2 = 
        graph1.getShortestPath(graph1.getIndex("Chicago"));
      tree2.printAllPaths();
  }

  public static interface Graph<V> {
    /** Return the number of vertices in the graph */
    public int getSize();

    /** Return the vertices in the graph */
    public java.util.List<V> getVertices();

    /** Return the object for the specified vertex index */
    public V getVertex(int index);

    /** Return the index for the specified vertex object */
    public int getIndex(V v);

    /** Return the neighbors of vertex with the specified index */
    public java.util.List<Integer> getNeighbors(int index);

    /** Return the degree for a specified vertex */
    public int getDegree(int v);

    /** Print the edges */
    public void printEdges();

    /** Clear graph */
    public void clear();

    /** Add a vertex to the graph */
    public boolean addVertex(V vertex);

    /** Add an edge to the graph */
    public boolean addEdge(int u, int v);

    /** Obtain a depth-first search tree */
    public AbstractGraph<V>.Tree dfs(int v);

    /** Obtain a breadth-first search tree */
    public AbstractGraph<V>.Tree bfs(int v);
  }

  public static abstract class AbstractGraph<V> implements Graph<V> {
    protected List<V> vertices = new ArrayList<V>(); // Store vertices
    protected List<List<Integer>> neighbors 
      = new ArrayList<List<Integer>>(); // Adjacency lists

    /** Construct an empty graph */
    protected AbstractGraph() {
    }
    
    /** Construct a graph from edges and vertices stored in arrays */
    protected AbstractGraph(int[][] edges, V[] vertices) {
      for (int i = 0; i < vertices.length; i++)
        addVertex(vertices[i]);
      
      createAdjacencyLists(edges, vertices.length);
    }

    /** Construct a graph from edges and vertices stored in List */
    protected AbstractGraph(List<Edge> edges, List<V> vertices) {
      for (int i = 0; i < vertices.size(); i++)
        addVertex(vertices.get(i));
          
      createAdjacencyLists(edges, vertices.size());
    }

    /** Construct a graph for integer vertices 0, 1, 2 and edge list */
    protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
      for (int i = 0; i < numberOfVertices; i++) 
        addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}
      
      createAdjacencyLists(edges, numberOfVertices);
    }

    /** Construct a graph from integer vertices 0, 1, and edge array */
    protected AbstractGraph(int[][] edges, int numberOfVertices) {
      for (int i = 0; i < numberOfVertices; i++) 
        addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}
      
      createAdjacencyLists(edges, numberOfVertices);
    }

    /** Create adjacency lists for each vertex */
    private void createAdjacencyLists(
        int[][] edges, int numberOfVertices) {
      for (int i = 0; i < edges.length; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        addEdge(u, v);
      }
    }

    /** Create adjacency lists for each vertex */
    private void createAdjacencyLists(
        List<Edge> edges, int numberOfVertices) {
      for (Edge edge: edges) {
        addEdge(edge.u, edge.v);
      }
    }

    @Override /** Return the number of vertices in the graph */
    public int getSize() {
      return vertices.size();
    }

    @Override /** Return the vertices in the graph */
    public List<V> getVertices() {
      return vertices;
    }

    @Override /** Return the object for the specified vertex */
    public V getVertex(int index) {
      return vertices.get(index);
    }

    @Override /** Return the index for the specified vertex object */
    public int getIndex(V v) {
      return vertices.indexOf(v);
    }

    @Override /** Return the neighbors of the specified vertex */
    public List<Integer> getNeighbors(int index) {
      return neighbors.get(index);
    }

    @Override /** Return the degree for a specified vertex */
    public int getDegree(int v) {
      return neighbors.get(v).size();
    }

    @Override /** Print the edges */
    public void printEdges() {
      for (int u = 0; u < neighbors.size(); u++) {
        System.out.print(getVertex(u) + " (" + u + "): ");
        for (int j = 0; j < neighbors.get(u).size(); j++) {
          System.out.print("(" + u + ", " +
            neighbors.get(u).get(j) + ") ");
        }
        System.out.println();
      }
    }

    @Override /** Clear graph */
    public void clear() {
      vertices.clear();
      neighbors.clear();
    }
    
    @Override /** Add a vertex to the graph */  
    public boolean addVertex(V vertex) {
      if (!vertices.contains(vertex)) {
        vertices.add(vertex);
        neighbors.add(new ArrayList<Integer>());
        return true;
      }
      else {
        return false;
      }
    }

    @Override /** Add an edge to the graph */  
    public boolean addEdge(int u, int v) {
      if (u < 0 || u > getSize() - 1)
        throw new IllegalArgumentException("No such index: " + u);

      if (v < 0 || v > getSize() - 1)
        throw new IllegalArgumentException("No such index: " + v);
      
      if (!neighbors.get(u).contains(v)) {
        neighbors.get(u).add(v);
        return true;
      }
      else {
        return false;
      }
    }
    
    /** Edge inner class inside the AbstractGraph class */
    public static class Edge {
      public int u; // Starting vertex of the edge
      public int v; // Ending vertex of the edge

      /** Construct an edge for (u, v) */
      public Edge(int u, int v) {
        this.u = u;
        this.v = v;
      }
    }
    
    @Override /** Obtain a DFS tree starting from vertex v */
    /** To be discussed in Section 30.6 */
    public Tree dfs(int v) {
      List<Integer> searchOrder = new ArrayList<Integer>();
      int[] parent = new int[vertices.size()];
      for (int i = 0; i < parent.length; i++)
        parent[i] = -1; // Initialize parent[i] to -1

      // Mark visited vertices
      boolean[] isVisited = new boolean[vertices.size()];

      // Recursively search
      dfs(v, parent, searchOrder, isVisited);

      // Return a search tree
      return new Tree(v, parent, searchOrder);
    }

    /** Recursive method for DFS search */
    private void dfs(int v, int[] parent, List<Integer> searchOrder,
        boolean[] isVisited) {
      // Store the visited vertex
      searchOrder.add(v);
      isVisited[v] = true; // Vertex v visited

      for (int w : neighbors.get(v)) {
        if (!isVisited[w]) {
          parent[w] = v; // The parent of vertex i is v
          dfs(w, parent, searchOrder, isVisited); // Recursive search
        }
      }
    }

    @Override /** Starting bfs search from vertex v */
    /** To be discussed in Section 27.7 */
    public Tree bfs(int v) {
      List<Integer> searchOrder = new ArrayList<Integer>();
      int[] parent = new int[vertices.size()];
      for (int i = 0; i < parent.length; i++)
        parent[i] = -1; // Initialize parent[i] to -1

      java.util.LinkedList<Integer> queue =
        new java.util.LinkedList<Integer>(); // list used as a queue
      boolean[] isVisited = new boolean[vertices.size()];
      queue.offer(v); // Enqueue v
      isVisited[v] = true; // Mark it visited

      while (!queue.isEmpty()) {
        int u = queue.poll(); // Dequeue to u
        searchOrder.add(u); // u searched
        for (int w : neighbors.get(u)) {
          if (!isVisited[w]) {
            queue.offer(w); // Enqueue w
            parent[w] = u; // The parent of w is u
            isVisited[w] = true; // Mark it visited
          }
        }
      }

      return new Tree(v, parent, searchOrder);
    }

    /** Tree inner class inside the AbstractGraph class */
    /** To be discussed in Section 27.5 */
    public class Tree {
      private int root; // The root of the tree
      private int[] parent; // Store the parent of each vertex
      private List<Integer> searchOrder; // Store the search order

      /** Construct a tree with root, parent, and searchOrder */
      public Tree(int root, int[] parent, List<Integer> searchOrder) {
        this.root = root;
        this.parent = parent;
        this.searchOrder = searchOrder;
      }

      /** Return the root of the tree */
      public int getRoot() {
        return root;
      }

      /** Return the parent of vertex v */
      public int getParent(int v) {
        return parent[v];
      }

      /** Return an array representing search order */
      public List<Integer> getSearchOrder() {
        return searchOrder;
      }

      /** Return number of vertices found */
      public int getNumberOfVerticesFound() {
        return searchOrder.size();
      }
      
      /** Return the path of vertices from a vertex to the root */
      public List<V> getPath(int index) {
        ArrayList<V> path = new ArrayList<V>();

        do {
          path.add(vertices.get(index));
          index = parent[index];
        }
        while (index != -1);

        return path;
      }

      /** Print a path from the root to vertex v */
      public void printPath(int index) {
        List<V> path = getPath(index);
        System.out.print("A path from " + vertices.get(root) + " to " +
          vertices.get(index) + ": ");
        for (int i = path.size() - 1; i >= 0; i--)
          System.out.print(path.get(i) + " ");
      }

      /** Print the whole tree */
      public void printTree() {
        System.out.println("Root is: " + vertices.get(root));
        System.out.print("Edges: ");
        for (int i = 0; i < parent.length; i++) {
          if (parent[i] != -1) {
            // Display an edge
            System.out.print("(" + vertices.get(parent[i]) + ", " +
              vertices.get(i) + ") ");
          }
        }
        System.out.println();
      }
    }
  }

  public static class WeightedGraph<V> extends AbstractGraph<V> {
    // Priority adjacency lists
    private List<PriorityQueue<WeightedEdge>> queues
      = new ArrayList<PriorityQueue<WeightedEdge>>();

    /** Construct a WeightedGraph from edges and vertices in arrays */
    public WeightedGraph() {
    }
    
    /** Construct a WeightedGraph from edges and vertices in arrays */
    public WeightedGraph(int[][] edges, V[] vertices) {
      super(edges, vertices);
      createQueues(edges, vertices.length);
    }

    /** Construct a WeightedGraph from edges and vertices in List */
    public WeightedGraph(int[][] edges, int numberOfVertices) {
      super(edges, numberOfVertices);
      createQueues(edges, numberOfVertices);
    }

    /** Construct a WeightedGraph for vertices 0, 1, 2 and edge list */
    public WeightedGraph(List<WeightedEdge> edges, List<V> vertices) {
      super((List)edges, vertices);
      createQueues(edges, vertices.size());
    }

    /** Construct a WeightedGraph from vertices 0, 1, and edge array */
    public WeightedGraph(List<WeightedEdge> edges,
        int numberOfVertices) {
      super((List)edges, numberOfVertices);
      createQueues(edges, numberOfVertices);
    }

    /** Create priority adjacency lists from edge arrays */
    private void createQueues(int[][] edges, int numberOfVertices) {
      for (int i = 0; i < numberOfVertices; i++) {
        queues.add(new PriorityQueue<WeightedEdge>()); // Create a queue
      }

      for (int i = 0; i < edges.length; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        int weight = edges[i][2];
        // Insert an edge into the queue
        queues.get(u).offer(new WeightedEdge(u, v, weight));
      }
    }

    /** Create priority adjacency lists from edge lists */
    private void createQueues(List<WeightedEdge> edges,
        int numberOfVertices) {
      for (int i = 0; i < numberOfVertices; i++) {
        queues.add(new PriorityQueue<WeightedEdge>()); // Create a queue
      }

      for (WeightedEdge edge: edges) {
        queues.get(edge.u).offer(edge); // Insert an edge into the queue
      }
    }

    /** Display edges with weights */
    public void printWeightedEdges() {
      for (int i = 0; i < queues.size(); i++) {
        System.out.print(getVertex(i) + " (" + i + "): ");
        for (WeightedEdge edge : queues.get(i)) {
          System.out.print("(" + edge.u +
            ", " + edge.v + ", " + edge.weight + ") ");
        }
        System.out.println();
      }
    }

    /** Get the edges from the weighted graph */  
    public List<PriorityQueue<WeightedEdge>> getWeightedEdges() {
      return queues;
    }
    
    /** Clears the weighted graph */
    public void clear() {
      vertices.clear();
      neighbors.clear();
      queues.clear();
    }
    
    /** Add vertices to the weighted graph */  
    public boolean addVertex(V vertex) {
      if (super.addVertex(vertex)) {
        if (queues == null) 
          queues = new ArrayList<PriorityQueue<WeightedEdge>>();
        queues.add(new PriorityQueue<WeightedEdge>());
        return true;
      }
      else {
        return false;
      }
    }

    /** Add edges to the weighted graph */  
    public void addEdge(int u, int v, double weight) {
      if (super.addEdge(u, v)) {
        queues.get(u).add(new WeightedEdge(u, v, weight));
      }
    }

    /** Get a minimum spanning tree rooted at vertex 0 */
    public MST getMinimumSpanningTree() {
      return getMinimumSpanningTree(0);
    }
    
    /* NEW IMPLEMENTATION */
    /** Get a minimum spanning tree rooted at a specified vertex */
    public MST getMinimumSpanningTree(int startingVertex) {
      List<Integer> T = new ArrayList<Integer>();
      // T initially contains the startingVertex;
      T.add(startingVertex);

      // Track if a vertex is in T
      boolean[] isInT = new boolean[vertices.size()];
      isInT[startingVertex] = true;
      
      int numberOfVertices = vertices.size(); // Number of vertices
      int[] parent = new int[numberOfVertices]; // Parent of a vertex
      // Initially set the parent of all vertices to -1
      for (int i = 0; i < parent.length; i++)
        parent[i] = -1;
      double totalWeight = 0; // Total weight of the tree thus far

      // Clone the priority queue, so to keep the original queue intact
      List<PriorityQueue<WeightedEdge>> queues = deepClone(this.queues);

      // All vertices are found?
      while (T.size() < numberOfVertices) {
        // Search for the vertex with the smallest edge adjacent to
        // a vertex in T
        int v = -1;
        double smallestWeight = Double.MAX_VALUE;
        for (int u: T) { 
          while (!queues.get(u).isEmpty() &&
              isInT[queues.get(u).peek().v]) {
            // Remove the edge from queues[u] if the adjacent
            // vertex of u is already in T
            queues.get(u).remove();
          }

          if (!queues.get(u).isEmpty()) {
            // Current smallest weight on an edge adjacent to u
            WeightedEdge edge = queues.get(u).peek();
            if (edge.weight < smallestWeight) {
              v = edge.v;
              smallestWeight = edge.weight;
              // If v is added to the tree, u will be its parent
              parent[v] = u;
            }
          }
        } // End of for

        if (v != -1) {
          T.add(v); // Add a new vertex to the tree
          isInT[v] = true;
          totalWeight += smallestWeight;
        }
        else 
          return null; // The tree is not connected, a partial MST is found
      } // End of while

      return new MST(startingVertex, parent, T, totalWeight);
    }

    /** Clone an array of queues */
    private List<PriorityQueue<WeightedEdge>> deepClone(
      List<PriorityQueue<WeightedEdge>> queues) {
      List<PriorityQueue<WeightedEdge>> copiedQueues =
        new ArrayList<PriorityQueue<WeightedEdge>>();

      for (int i = 0; i < queues.size(); i++) {
        copiedQueues.add(new PriorityQueue<WeightedEdge>());
        for (WeightedEdge e : queues.get(i)) {
          copiedQueues.get(i).add(e);
        }
      }

      return copiedQueues;
    }

    /** MST is an inner class in WeightedGraph */
    public class MST extends Tree {
      private double totalWeight; // Total weight of all edges in the tree

      public MST(int root, int[] parent, List<Integer> searchOrder,
          double totalWeight) {
        super(root, parent, searchOrder);
        this.totalWeight = totalWeight;
      }

      public double getTotalWeight() {
        return totalWeight;
      }
    }

    /** Find single source shortest paths */
    public ShortestPathTree getShortestPath(int sourceVertex) {
      // T stores the vertices whose path found so far
      List<Integer> T = new ArrayList<Integer>();
      
      // T initially contains the sourceVertex
      T.add(sourceVertex);

      // Track if a vertex is in T
      boolean[] isInT = new boolean[vertices.size()];
      isInT[sourceVertex] = true;
      
      // parent[v] stores the previous vertex of v in the path
      int[] parent = new int[vertices.size()];
      parent[sourceVertex] = -1; // The parent of source is set to -1

      // cost[v] stores the cost of the path from v to the source
      double[] cost = new double[vertices.size()];
      for (int i = 0; i < cost.length; i++) {
        cost[i] = Double.POSITIVE_INFINITY; // Initial cost set to infinity
      }
      cost[sourceVertex] = 0; // Cost of source is 0

      // Get a copy of queues
      List<PriorityQueue<WeightedEdge>> queues = deepClone(this.queues);

      // Set cost for the neighbors of sourceVertex
      while (!queues.get(sourceVertex).isEmpty()) {
        WeightedEdge e = queues.get(sourceVertex).poll();
        cost[e.v] = e.weight;
        parent[e.v] = sourceVertex;
      }
      
      // Expand T
      while (T.size() < vertices.size()) {
        // Find smallest cost v in V - T 
        int u = -1; // Vertex to be determined
        double currentMinCost = Double.POSITIVE_INFINITY;
        for (int i = 0; i < getSize(); i++) {
          if (!isInT[i] && cost[i] < currentMinCost) {
            currentMinCost = cost[i];
            u = i;
          }
        }
        
        if (u != -1) {
          T.add(u); // Add a new vertex to T
          isInT[u] = true;
          
          // Adjust cost[v] for v that is adjacent to u and v in V - T
          while (!queues.get(u).isEmpty()) {
            WeightedEdge e = queues.get(u).poll();
            if (!isInT[e.v] && cost[e.v] > cost[u] + e.weight) {
              cost[e.v] = cost[u] + e.weight;
              parent[e.v] = u; 
            }
          }
        }
        else
          return null; // s cannot reach to all vertices
      } // End of while

      // Create a ShortestPathTree
      return new ShortestPathTree(sourceVertex, parent, T, cost);
    }

    /** ShortestPathTree is an inner class in WeightedGraph */
    public class ShortestPathTree extends Tree {
      private double[] cost; // cost[v] is the cost from v to source

      /** Construct a path */
      public ShortestPathTree(int source, int[] parent, 
          List<Integer> searchOrder, double[] cost) {
        super(source, parent, searchOrder);
        this.cost = cost;
      }

      /** Return the cost for a path from the root to vertex v */
      public double getCost(int v) {
        return cost[v];
      }

      /** Print paths from all vertices to the source */
      public void printAllPaths() {
        System.out.println("All shortest paths from " +
          vertices.get(getRoot()) + " are:");
        for (int i = 0; i < cost.length; i++) {
          printPath(i); // Print a path from i to the source
          System.out.println("(cost: " + cost[i] + ")"); // Path cost
        }
      }
    }
  }
  
 static class WeightedEdge extends AbstractGraph.Edge implements Comparable<WeightedEdge> {
  public double weight; // The weight on edge (u, v)

  /** Create a weighted edge on (u, v) */
  public WeightedEdge(int u, int v, double weight) {
   super(u, v);
   this.weight = weight;
  }

  /** Compare two edges on weights */
  public int compareTo(WeightedEdge edge) {
   if (weight > edge.weight) {
    return 1;
   } else if (weight == edge.weight) {
    return 0;
   } else {
    return -1;
   }
  }
  
  @Override
  public boolean equals(Object obj) {
   if (obj instanceof WeightedEdge) {
    WeightedEdge that = (WeightedEdge)obj;
    return (u == that.u) && (v == that.v) && (weight == that.weight);   
   } else {
    return false;
   }
  }
  
  @Override
  public String toString() {
   return "(" + u + ", " + v + ", " + weight + ")";
  }
 }

}