Chapter 9: /graphs/ desktop.ini

[ViewState]
Mode=
Vid=
FolderType=NotSpecified

Chapter 9: /graphs/ WeightedGraph.java

// Incomplete version

//----------------------------------------------------------------------------
// WeightedGraph.java            by Dale/Joyce/Weems                 Chapter 9
//
// Implements a directed graph with weighted edges.
// Vertices are objects of class T and can be marked as having been visited.
// Edge weights are integers.
// Equivalence of vertices is determined by the vertices' equals method.
//
// General precondition: Except for the addVertex and hasVertex methods, 
// any vertex passed as an argument to a method is in this graph.
//----------------------------------------------------------------------------

package ch09.graphs;

import ch05.queues.*;

public class WeightedGraph implements WeightedGraphInterface
{
  public static final int NULL_EDGE = 0;
  private static final int DEFCAP = 50;  // default capacity
  private int numVertices;
  private int maxVertices;
  private T[] vertices;
  private int[][] edges;
  private boolean[] marks;  // marks[i] is mark for vertices[i]

  public WeightedGraph()
  // Instantiates a graph with capacity DEFCAP vertices.
  {
    numVertices = 0;
    maxVertices = DEFCAP;
    vertices = (T[]) new Object[DEFCAP];
    marks = new boolean[DEFCAP];
    edges = new int[DEFCAP][DEFCAP];
  }
 
  public WeightedGraph(int maxV)
  // Instantiates a graph with capacity maxV.
  {
    numVertices = 0;
    maxVertices = maxV;
    vertices = (T[]) new Object[maxV];
    marks = new boolean[maxV];
    edges = new int[maxV][maxV];
  }

  public boolean isEmpty()
  // Returns true if this graph is empty; otherwise, returns false.
  {
  }

  public boolean isFull()
  // Returns true if this graph is full; otherwise, returns false.
  {
  }

  public void addVertex(T vertex)
  // Preconditions:   This graph is not full.
  //                  Vertex is not already in this graph.
  //                  Vertex is not null.
  //
  // Adds vertex to this graph.
  {
    vertices[numVertices] = vertex;
    for (int index = 0; index < numVertices; index++)
    {
      edges[numVertices][index] = NULL_EDGE;
      edges[index][numVertices] = NULL_EDGE;
    }
    numVertices++;
  }

  public boolean hasVertex(T vertex)
  // Returns true if this graph contains vertex; otherwise, returns false.
  {
  }
  
  private int indexIs(T vertex)
  // Returns the index of vertex in vertices.
  {
    int index = 0;
    while (!vertex.equals(vertices[index]))
      index++;
    return index;
  }

  public void addEdge(T fromVertex, T toVertex, int weight)
  // Adds an edge with the specified weight from fromVertex to toVertex.
  {
    int row;
    int column;
 
    row = indexIs(fromVertex);
    column = indexIs(toVertex);
    edges[row][column] = weight;
  }

  public int weightIs(T fromVertex, T toVertex)
  // If edge from fromVertex to toVertex exists, returns the weight of edge;
  // otherwise, returns a special ìnull-edgeî value.
  {
    int row;
    int column;
 
    row = indexIs(fromVertex);
    column = indexIs(toVertex);
    return edges[row][column];
  }

  public UnboundedQueueInterface getToVertices(T vertex)
  // Returns a queue of the vertices that are adjacent from vertex.
  {
    UnboundedQueueInterface adjVertices = new LinkedUnbndQueue();
    int fromIndex;
    int toIndex;
    fromIndex = indexIs(vertex);
    for (toIndex = 0; toIndex < numVertices; toIndex++)
      if (edges[fromIndex][toIndex] != NULL_EDGE)
        adjVertices.enqueue(vertices[toIndex]);
    return adjVertices;
  }

  public void clearMarks()
  // Sets marks for all vertices to false.
  {
  }

  public void markVertex(T vertex)
  // Sets mark for vertex to true.
  {
  }

  public boolean isMarked(T vertex)
  // Returns true if vertex is marked; otherwise, returns false.
  {
  }
  
  public T getUnmarked()
  // Returns an unmarked vertex if any exist; otherwise, returns null.
  {
  }
}

Chapter 9: /graphs/ WeightedGraphInterface.java

//----------------------------------------------------------------------------
// WeightedGraphInterface.java       by Dale/Joyce/Weems             Chapter 9
//
// Interface for a class that implements a directed graph with weighted edges.
// Vertices are objects of class T and can be marked as having been visited.
// Edge weights are integers.
// Equivalence of vertices is determined by the vertices' equals method.
//
// General precondition: Except for the addVertex and hasVertex methods, 
// any vertex passed as an argument to a method is in this graph.
//----------------------------------------------------------------------------

package ch09.graphs;

import ch05.queues.*;

public interface WeightedGraphInterface
{
  boolean isEmpty();
  // Returns true if this graph is empty; otherwise, returns false.

  boolean isFull();
  // Returns true if this graph is full; otherwise, returns false.
  
  void addVertex(T vertex);
  // Preconditions:   This graph is not full.
  //                  Vertex is not already in this graph.
  //                  Vertex is not null.
  //
  // Adds vertex to this graph.

  boolean hasVertex(T vertex);
  // Returns true if this graph contains vertex; otherwise, returns false.

  void addEdge(T fromVertex, T toVertex, int weight);
  // Adds an edge with the specified weight from fromVertex to toVertex.

  int weightIs(T fromVertex, T toVertex);
  // If edge from fromVertex to toVertex exists, returns the weight of edge;
  // otherwise, returns a special ìnull-edgeî value.

  UnboundedQueueInterface getToVertices(T vertex);
  // Returns a queue of the vertices that are adjacent from vertex.

  void clearMarks();
  // Sets marks for all vertices to false.

  void markVertex(T vertex);
  // Sets mark for vertex to true.

  boolean isMarked(T vertex);
  // Returns true if vertex is marked; otherwise, returns false.
  
  T getUnmarked();
  // Returns an unmarked vertex if any exist; otherwise, returns null.
  
}

Chapter 9: /priorityQueues/ desktop.ini

[ViewState]
Mode=
Vid=
FolderType=NotSpecified

Chapter 9: /priorityQueues/ Heap.java

//----------------------------------------------------------------------------
// Heap.java               by Dale/Joyce/Weems                       Chapter 9
//
// Defines all constructs for a heap.
// The dequeue method returns the largest element in the heap.
//----------------------------------------------------------------------------

package ch09.priorityQueues;

import java.util.*;

public class Heap> implements PriQueueInterface
{
  private ArrayList elements;  // priority queue elements
  private int lastIndex;          // index of last element in priority queue
  private int maxIndex;           // index of last position in ArrayList

  public Heap(int maxSize)
  {
    elements = new ArrayList(maxSize);
    lastIndex = -1;
    maxIndex = maxSize - 1;
  }

  public boolean isEmpty()
  // Returns true if this priority queue is empty; otherwise, returns false.
  {
    return (lastIndex == -1);
  }

  public boolean isFull()
  // Returns true if this priority queue is full; otherwise, returns false.
  {
    return (lastIndex == maxIndex);
  }

  private void reheapUp(T element)
  // Current lastIndex position is empty.
  // Inserts element into the tree and ensures shape and order properties.
  {
    int hole = lastIndex;
    while ((hole > 0)    // hole is not root and element > hole's parent
           &&                                               
      (element.compareTo(elements.get((hole - 1) / 2)) > 0)) 
      {
      // move hole's parent down and then move hole up
      elements.set(hole,elements.get((hole - 1) / 2)); 
      hole = (hole - 1) / 2;                                
    }
    elements.set(hole, element);  // place element into final hole
  }

  public void enqueue(T element) throws PriQOverflowException
  // Throws PriQOverflowException if this priority queue is full;
  // otherwise, adds element to this priority queue.
  {
    if (lastIndex == maxIndex)
      throw new PriQOverflowException("Priority queue is full");
    else
    {
      lastIndex++;
      elements.add(lastIndex,element);
      reheapUp(element);
    }
  }

  private int newHole(int hole, T element)
  // If either child of hole is larger than element, return the index
  // of the larger child; otherwise, return the index of hole.
  {
    int left = (hole * 2) + 1;
    int right = (hole * 2) + 2;

    if (left > lastIndex)
      // hole has no children
      return hole;         
    else
    if (left == lastIndex)
      // hole has left child only
      if (element.compareTo(elements.get(left)) < 0)             
        // element < left child
        return left;
      else
        // element >= left child
        return hole;
    else
    // hole has two children 
    if (elements.get(left).compareTo(elements.get(right)) < 0)
      // left child < right child
      if (elements.get(right).compareTo(element) <= 0)
        // right child <= element
        return hole;
      else
        // element < right child
        return right;
    else
    // left child >= right child
    if (elements.get(left).compareTo(element) <= 0)
      // left child <= element
      return hole;
    else
      // element < left child
      return left;
  }

  private void reheapDown(T element)
  // Current root position is "empty";
  // Inserts element into the tree and ensures shape and order properties.
  {
    int hole = 0;      // current index of hole
    int newhole;       // index where hole should move to

    newhole = newHole(hole, element);   // find next hole
    while (newhole != hole)
    {
      elements.set(hole,elements.get(newhole));  // move element up
      hole = newhole;                            // move hole down
      newhole = newHole(hole, element);          // find next hole
    }
    elements.set(hole, element);           // fill in the final hole
  }

  public T dequeue() throws PriQUnderflowException
  // Throws PriQUnderflowException if this priority queue is empty;
  // otherwise, removes element with highest priority from this 
  // priority queue and returns it.
  {
    T hold;      // element to be dequeued and returned
    T toMove;    // element to move down heap

    if (lastIndex == -1)
      throw new PriQUnderflowException("Priority queue is empty");
    else
    {
      hold = elements.get(0);              // remember element to be returned
      toMove = elements.remove(lastIndex); // element to reheap down
      lastIndex--;                         // decrease priority queue size
      if (lastIndex != -1)
         reheapDown(toMove);               // restore heap properties
      return hold;                         // return largest element
    }
  }

  public String toString()
  // Returns a string of all the heap elements.
  {
    String theHeap = new String("the heap is:\n");
    for (int index = 0; index <= lastIndex; index++)
      theHeap = theHeap + index + ". " + elements.get(index) + "\n";
    return theHeap;
  }
}

Chapter 9: /priorityQueues/ PriQOverflowException.java

package ch09.priorityQueues;

class PriQOverflowException extends RuntimeException
{
  public PriQOverflowException()
  {
    super();
  }

  public PriQOverflowException(String message)
  {
    super(message);
  }
}

Chapter 9: /priorityQueues/ PriQueueInterface.java

//----------------------------------------------------------------------------
// PriQueueInterface.java          by Dale/Joyce/Weems               Chapter 9
//
// Interface for a class that implements a priority queue of Comparable objects.
//----------------------------------------------------------------------------

package ch09.priorityQueues;

public interface PriQueueInterface>
{
  boolean isEmpty();
  // Returns true if this priority queue is empty; otherwise, returns false.

  boolean isFull();
  // Returns true if this priority queue is full; otherwise, returns false.

  void enqueue(T element); 
  // Precondition: element is Comparable
  //
  // Throws PriQOverflowException if this priority queue is full;
  // otherwise, adds element to this priority queue.

  T dequeue();
  // Throws PriQUnderflowException if this priority queue is empty;
  // otherwise, removes element with highest priority from this 
  // priority queue and returns it.
}

Chapter 9: /priorityQueues/ PriQUnderflowException.java

package ch09.priorityQueues;

class PriQUnderflowException extends RuntimeException
{
  public PriQUnderflowException()
  {
    super();
  }

  public PriQUnderflowException(String message)
  {
    super(message);
  }
}

Chapter 9: UseGraph.java

//----------------------------------------------------------------------------
// UseGraph.java             by Dale/Joyce/Weems                     Chapter 9
//
// Examples of uses of the Graph ADT.
//----------------------------------------------------------------------------

import ch05.queues.*;
import ch03.stacks.*;
import answers.ch09.graphs.*;     // remove answers.
import ch09.priorityQueues.*;
import support.Flight;

public class UseGraph
{
private static void shortestPaths(WeightedGraphInterface graph,
                                  String startVertex  )

// Writes the shortest distance from startVertex to every 
// other reachable vertex in graph.
{
  Flight flight;
  Flight saveFlight;         // for saving on priority queue
  int minDistance;
  int newDistance;

  PriQueueInterface pq = new Heap(20);   // Assume at most 20 vertices
  String vertex;
  UnboundedQueueInterface vertexQueue = new LinkedUnbndQueue();
  
  graph.clearMarks();
  saveFlight = new Flight(startVertex, startVertex, 0);
  pq.enqueue(saveFlight);

  System.out.println("Last Vertex   Destination   Distance");
  System.out.println("------------------------------------");
 
  do
  {
    flight = pq.dequeue();
    if (!graph.isMarked(flight.getToVertex()))
    {
      graph.markVertex(flight.getToVertex());
      System.out.println(flight);
      flight.setFromVertex(flight.getToVertex());
      minDistance = flight.getDistance();
      vertexQueue = graph.getToVertices(flight.getFromVertex());
      while (!vertexQueue.isEmpty())
      {
        vertex = vertexQueue.dequeue();
        if (!graph.isMarked(vertex))
        {
          newDistance = minDistance 
                        + graph.weightIs(flight.getFromVertex(), vertex);
          saveFlight = new Flight(flight.getFromVertex(), vertex, newDistance);
          pq.enqueue(saveFlight);
        }
      }
    }
  } while (!pq.isEmpty());
  System.out.println();
  System.out.println("The unreachable vertices are:");
  vertex = graph.getUnmarked();
  while (vertex != null)
  {
    System.out.println(vertex);
    graph.markVertex(vertex);
    vertex = graph.getUnmarked();
  }
  System.out.println();
}

private static boolean isPath(WeightedGraphInterface graph,
                              String startVertex, 
                              String endVertex    )

// Returns true if a path exists on graph, from startVertex to endVertex; 
// otherwise returns false. Uses depth-first search algorithm.

{
  UnboundedStackInterface stack = new LinkedStack();
  UnboundedQueueInterface vertexQueue = new LinkedUnbndQueue();
 
  boolean found = false;
  String vertex;
  String item;
 
  graph.clearMarks();
  stack.push(startVertex);
  do
  {
    vertex = stack.top();
    stack.pop();
    if (vertex == endVertex)
       found = true;
    else
    {
      if (!graph.isMarked(vertex))
      {
        graph.markVertex(vertex);
        vertexQueue = graph.getToVertices(vertex);
 
        while (!vertexQueue.isEmpty())
        {
          item = vertexQueue.dequeue();
          if (!graph.isMarked(item))
            stack.push(item);
        }
      }
    }
  } while (!stack.isEmpty() && !found);
  
  return found;
}

private static boolean isPath2(WeightedGraphInterface graph,
                               String startVertex, 
                               String endVertex    )

// Returns true if a path exists on graph, from startVertex to endVertex; 
// otherwise returns false. Uses breadth-first search algorithm.

{
  UnboundedQueueInterface queue = new LinkedUnbndQueue();
  UnboundedQueueInterface vertexQueue = new LinkedUnbndQueue();
 
  boolean found = false;
  String vertex;
  String item;

  graph.clearMarks();
  queue.enqueue(startVertex);
  do
  {
    vertex = queue.dequeue();
    if (vertex == endVertex)
       found = true;
    else
    {
      if (!graph.isMarked(vertex))
      {
        graph.markVertex(vertex);
        vertexQueue = graph.getToVertices(vertex);
 
        while (!vertexQueue.isEmpty())
        {
          item = vertexQueue.dequeue();
          if (!graph.isMarked(item))
            queue.enqueue(item);
        }
      }
    }
  } while (!queue.isEmpty() && !found);
  
  return found;
}


  public static void main(String[] args) 
  {
    WeightedGraphInterface graph = new WeightedGraph();
    String s0 = new String("Atlanta   ");
    String s1 = new String("Austin    ");
    String s2 = new String("Chicago   ");
    String s3 = new String("Dallas    ");
    String s4 = new String("Denver    ");
    String s5 = new String("Houston   ");
    String s6 = new String("Washington");

    graph.addVertex(s0);
    graph.addVertex(s1);
    graph.addVertex(s2);
    graph.addVertex(s3);
    graph.addVertex(s4);
    graph.addVertex(s5);
    graph.addVertex(s6);

    graph.addEdge(s0, s5, 800);
    graph.addEdge(s0, s6, 600);
    graph.addEdge(s1, s3, 200);
    graph.addEdge(s1, s5, 160);
    graph.addEdge(s2, s4, 1000);
    graph.addEdge(s3, s1, 200);
    graph.addEdge(s3, s2, 900);
    graph.addEdge(s3, s4, 780);
    graph.addEdge(s4, s0, 1400);
    graph.addEdge(s4, s2, 1000);
    graph.addEdge(s5, s0, 800);
    graph.addEdge(s6, s0, 600);
    graph.addEdge(s6, s3, 1300);

    boolean result;

    System.out.println("depth first ...");
    result = isPath(graph, s1, s2);
    System.out.println("s1 s2 " + result);
    result = isPath(graph, s1, s6);
    System.out.println("s1 s6 " + result);
    result = isPath(graph, s6, s5);
    System.out.println("s6 s5 " + result);
    result = isPath(graph, s6, s3);
    System.out.println("s6 s3 " + result);
    result = isPath(graph, s6, s1);
    System.out.println("s6 s1 " + result);
    
    System.out.println();
    System.out.println("breadth first ...");
    result = isPath2(graph, s1, s2);
    System.out.println("s1 s2 " + result);
    result = isPath2(graph, s1, s6);
    System.out.println("s1 s6 " + result);
    result = isPath2(graph, s6, s5);
    System.out.println("s6 s5 " + result);
    result = isPath2(graph, s6, s3);
    System.out.println("s6 s3 " + result);
    result = isPath2(graph, s6, s1);
    System.out.println("s6 s1 " + result);
    System.out.println();
    shortestPaths(graph, s6);
	 
    System.out.println();
    System.out.println();
    shortestPaths(graph, s4);


    System.out.println();
    System.out.println();
	 
    System.out.println("a new graph without Wash - Dallas leg");
    System.out.println();

    graph = new WeightedGraph();
    s0 = new String("Atlanta   ");
    s1 = new String("Austin    ");
    s2 = new String("Chicago   ");
    s3 = new String("Dallas    ");
    s4 = new String("Denver    ");
    s5 = new String("Houston   ");
    s6 = new String("Washington");

    graph.addVertex(s0);
    graph.addVertex(s1);
    graph.addVertex(s2);
    graph.addVertex(s3);
    graph.addVertex(s4);
    graph.addVertex(s5);
    graph.addVertex(s6);

    graph.addEdge(s0, s5, 800);
    graph.addEdge(s0, s6, 600);
    graph.addEdge(s1, s3, 200);
    graph.addEdge(s1, s5, 160);
    graph.addEdge(s2, s4, 1000);
    graph.addEdge(s3, s1, 200);
    graph.addEdge(s3, s2, 900);
    graph.addEdge(s3, s4, 780);
    graph.addEdge(s4, s0, 1400);
    graph.addEdge(s4, s2, 1000);
    graph.addEdge(s5, s0, 800);
    graph.addEdge(s6, s0, 600);
//    graph.addEdge(s6, s3, 1300);

    System.out.println("depth first ...");
    result = isPath(graph, s1, s2);
    System.out.println("s1 s2 " + result);
    result = isPath(graph, s1, s6);
    System.out.println("s1 s6 " + result);
    result = isPath(graph, s6, s5);
    System.out.println("s6 s5 " + result);
    result = isPath(graph, s6, s3);
    System.out.println("s6 s3 " + result);
    result = isPath(graph, s6, s1);
    System.out.println("s6 s1 " + result);
    
    System.out.println();
    System.out.println("breadth first ...");
    result = isPath2(graph, s1, s2);
    System.out.println("s1 s2 " + result);
    result = isPath2(graph, s1, s6);
    System.out.println("s1 s6 " + result);
    result = isPath2(graph, s6, s5);
    System.out.println("s6 s5 " + result);
    result = isPath2(graph, s6, s3);
    System.out.println("s6 s3 " + result);
    result = isPath2(graph, s6, s1);
    System.out.println("s6 s1 " + result);
    System.out.println();
    shortestPaths(graph, s6);
	 
    System.out.println();
    System.out.println();
    shortestPaths(graph, s4);


  } 
} 

Chapter 9: UseHeap.java

//----------------------------------------------------------------------------
// UseHeap.java              by Dale/Joyce/Weems                     Chapter 9
//
// Example of a simple use of the Heap.
//----------------------------------------------------------------------------

import ch09.priorityQueues.*;

public class UseHeap
{
  public static void main(String[] args)
  { 
    PriQueueInterface h = new Heap(10);
    h.enqueue("J");
    h.enqueue("A");
    h.enqueue("M");
    h.enqueue("B");
    h.enqueue("L");
    h.enqueue("E");
    
    System.out.println(h);
    
    System.out.println(h.dequeue() + "\n");
    
    System.out.println(h);
  }
}