// File: Graph.java from the package EDU.colorado.graphs // Complete documentation is available from the Graph link in // http://www.cs.colorado.edu/~main/docs/ package edu.colorado.graphs; /****************************************************************************** * A Graph is a labeled graph with a fixed number of vertices. * *

Java Source Code for this class:

* * http://www.cs.colorado.edu/~main/EDU/colorado/collections/Graph.java * * * @author Michael Main * (main@colorado.edu) * * @version * Jun 12, 1998 ******************************************************************************/ public class Graph implements Cloneable { // Invariant of the Graph class: // 1. The vertex numbers range from 0 to labels.length-1. // 2. For each vertex number i, labels[i] contains the label for vertex i. // 3. For any two vertices i and j, edges[i][j] is true if there is a // vertex from i to j; otherwise edges[i][j] is false. private boolean[ ][ ] edges; private Object[ ] labels; /** * Initialize a Graph with n vertices, * no edges, and null labels. * @param n * the number of vertices for this

Graph
   *

Precondition:


   *   n is nonnegative.
   *

Postcondition:


   *   This Graph has n vertices, numbered 
   *   0 to n-1. It has no edges and all
   *   vertex labels are null.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for the specified number of nodes.
   * @exception NegativeArraySizeException
   *   Indicates that n is negative. 
   **/   
   public Graph(int n)
   {
      edges = new boolean[n][n];  // All values initially false
      labels = new Object[n];     // All values initially null
   }
   
   
   /**
   * Add a new edge to this Graph.
   * @param source
   *   the vertex number of the source of the new edge
   * @param target
   *   the vertex number of the target of the new edge
   *

Precondition:


   *   Both source and target are nonnegative and
   *   less than size().
   *

Postcondition:


   *   This Graph has all the edges that it originally had plus
   *   another edge from the specified source to the specified
   *   target. (If the edge was already present, then this
   *   Graph is unchanged.)
   * @exception ArrayIndexOutOfBoundsException
   *   Indicates that the source or target was not a
   *   valid vertex number.
   **/
   public void addEdge(int source, int target)   
   {
      edges[source][target] = true;
   }
   
      
   /**
   * Generate a copy of this Graph.
   * @param - none
   * @return
   *   The return value is a copy of this Graph. Subsequent changes to the
   *   copy will not affect the original, nor vice versa. Note that the return
   *   value must be type cast to a Graph before it can be used.
   * @throws OutOfMemoryError
   *   Indicates insufficient memory for creating the clone.
   **/ 
   public Object clone( )
   {  // Clone a Graph object.
      Graph answer;
      
      try
      {
         answer = (Graph) super.clone( );
      }
      catch (CloneNotSupportedException e)
      {  // This would indicate an internal error in the Java runtime system
         // because super.clone always works for an Object.
         throw new InternalError(e.toString( ));
      }
      
      answer.edges = (boolean [ ][ ]) edges.clone( );
      answer.labels = (Object [ ]) labels.clone( );
      
      return answer;
   }
   

   /**
   * Static method to print the labels of a graph with a depth-first search.
   * @param g
   *   a nonnull Graph
   * @param start
   *   a vertex number from the Graph g
   *

Precondition:


   *   start is nonnegative and less than g.size().
   *

Postcondition:


   *   A depth-first search of g has been conducted, starting at
   *   the specified start vertex. Each vertex visited has its label printed 
   *   using System.out.println. Note that vertices that are not 
   *   connected to the start will not be visited.
   * @throws NullPointerException
   *   Indicates that g is null.
   * @throws ArrayIndexOutOfBoundsException
   *   Indicates that the vertex was not a valid vertex number.
   * @throws OutOfMemoryError
   *   Indicates that there is insufficient memory for an array of boolean values 
   *   used by this method.
   **/
   public static void depthFirstPrint(Graph g, int start)
   {
      boolean[ ] marked = new boolean [g.size( )];
      
      depthFirstRecurse(g, start, marked);
      
   }
   
   
   /**
   * Recursive method to carry out the work of depthFirstPrint.
   * @param g
   *   a nonnull Graph
   * @param v
   *   a vertex number from the Graph g
   * @param marked
   *   an array to indicate which vertices of g have already
   *   been visited
   *

Precondition:


   *   v is nonnegative and less than g.size().
   *   marked.length is equal to g.size();
   *   for each vertex x of g

, marked[x] * is true if x has already been visited by this * search; otherwise marked[x] is false. * The vertex v is an unmarked vertex that the search has * just arrived at. *

Postcondition:

* The depth-first search of g has been continued through * vertex v and beyond to all vertices that can be reached * from v via a path of unmarked vertices. Each vertex visited * has its label printed using System.out.println. * @throws NullPointerException * Indicates that g is null. * @throws ArrayIndexOutOfBoundsException * Indicates that the vertex was not a valid vertex number, or * marked was the wrong size. **/ public static void depthFirstRecurse(Graph g, int v, boolean[ ] marked) { int[ ] connections = g.neighbors(v); int i; int nextNeighbor; marked[v] = true; System.out.println(g.getLabel(v)); // Traverse all the neighbors, looking for unmarked vertices: for (i = 0; i < connections.length; i++) { nextNeighbor = connections[i]; if (!marked[nextNeighbor]) depthFirstRecurse(g, nextNeighbor, marked); } } /** * Accessor method to get the label of a vertex of this Graph. * @param vertex * a vertex number *

Precondition:

* vertex is nonnegative and * less than size(). * @return * the label of the specified vertex in this Graph * @exception ArrayIndexOutOfBoundsException * Indicates that the vertex was not a * valid vertex number. **/ public Object getLabel(int vertex) { return labels[vertex]; } /** * Accessor method to determine whether this Graph contains * a specified edge. * @param source * the vertex number of the source of the specified edge * @param target * the vertex number of the target of the specified edge *

Precondition:

* Both source and target are nonnegative and * less than size(). * @return * The return value is true if this Graph has an edge from the * specified source to the specified target. * Otherwise the return value is false. * @exception ArrayIndexOutOfBoundsException * Indicates that the source or target was not a * valid vertex number. **/ public boolean isEdge(int source, int target) { return edges[source][target]; } /** * Accessor method to obtain a list of neighbors of a specified vertex of * this Graph * @param vertex * a vertex number * @param target * a vertex number *

Precondition:

* Both source and target are nonnegative and * less than size(). *

Precondition:

* vertex is nonnegative and * less than size(). * @return * The return value is an array that contains all the vertex numbers of * vertices that are targets for edges with a source at the specified * vertex. * @exception ArrayIndexOutOfBoundsException * Indicates that the source or target was not a * valid vertex number. **/ public int[ ] neighbors(int vertex) { int i; int count; int[ ] answer; // First count how many edges have the vertex as their source count = 0; for (i = 0; i < labels.length; i++) { if (edges[vertex][i]) count++; } // Allocate the array for the answer answer = new int[count]; // Fill the array for the answer count = 0; for (i = 0; i < labels.length; i++) { if (edges[vertex][i]) answer[count++] = i; } return answer; } /** * Remove an edge from this Graph. * @param source * the vertex number of the source of the removed edge * @param target * the vertex number of the target of the removed edge *

Precondition:

* Both source and target are nonnegative and * less than size(). *

Postcondition:

* This Graph has all the edges that it originally had minus * the edge from the specified source to the specified * target. (If the edge was not present, then this * Graph is unchanged.) * @exception ArrayIndexOutOfBoundsException * Indicates that the source or target was not a * valid vertex number. **/ public void removeEdge(int source, int target) { edges[source][target] = false; } /** * Modification method to change the label of a vertex of this Graph. * @param vertex * a vertex number * @param newLabel * a new label (which may be null) *

Precondition:

* vertex is nonnegative and * less than size(). *

Postcondition:

* The label of the specified vertex in this Graph has been * changed to the newLabel. * @exception ArrayIndexOutOfBoundsException * Indicates that the vertex was not a * valid vertex number. **/ public void setLabel(int vertex, Object newLabel) { labels[vertex] = newLabel; } /** * Determine the number of vertices in this Graph. * @param - none * @return * the number of vertices in this Graph **/ public int size( ) { return labels.length; } }