Select a Chapter: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Back to the Main Page
Chapter Nineteen listings: 14 classes

public class HamGraph extends ListGraph 
{
     /** Create a graph on n vertices with at least 1.5 * n 
      *  randomly chosen edges, but the graph cannot be connected 
      *  (it must have at least two components). */


     public void createUnConnectedGraph (int n)  
     {    this.clear();
          this.addVertex (new Vertex (n, null));
          for (int k = 1;  k < 1.5 * this.getNumVertices();  k++)
               this.addEdgeChosenRandomly();
          if (this.isConnected())
               this.createUnConnectedGraph (n);
     } //================================================


     /** Add 1 randomly chosen edge at a time until this graph 
      *  becomes connected.  */

     public void makeTheGraphConnected()  
     {    while ( ! isConnected())
               addEdgeChosenRandomly();
     } //================================================


     /** Tell whether this graph is connected.  STUBBED*/

     public boolean isConnected()
     {    return false;
     } //================================================


     /** Add a randomly chosen edge not already in the graph. */

     private void addEdgeChosenRandomly()  
     {    int one = 1 + (int) (Math.random() * getNumVertices());
          int two = 1 + (int) (Math.random() * getNumVertices());
          Edge e = new Edge (getVertex (one), getVertex (two));
          if (this.contains (e))
               addEdgeChosenRandomly();
          else
          {    this.add (e);
               this.add (new Edge (getVertex (two), getVertex (one)));
               // in the opposite direction, for an undirected graph
          }
     } //================================================
}


import java.util.ArrayList;
import java.util.Iterator;

public abstract class Graph
{
     private ArrayList itsVertices = new ArrayList();


     /** Create a graph with zero vertices and zero edges.  The
      *  vertices always have ids ranging 1...getNumVertices(). */

     public Graph()
     {    super();  // to remind you of the default constructor
     } //================================================


     /** Return the current number of vertices. */

     public final int getNumVertices()  
     {    return itsVertices.size();
     } //================================================


     /** Return the Vertex object for the given id.  Throw a
      *  RuntimeException if the id is not 1...getNumVertices(). */

     public final Vertex getVertex (int id)  
     {    return (Vertex) itsVertices.get (id - 1);
     } //================================================


     /** Return an iteration over all Vertex objects. */

     public final Iterator vertices()  
     {    return itsVertices.iterator();
     } //================================================


     /** Add the given vertex to the graph if it has no vertex with 
      *  the same id number; ignore non-positive ids.  Add vertices
      *  as needed for all positive ints below id, with null data. 
      *  Throw a RuntimeException if the given vertex is null. */

     public void addVertex (Vertex v)  
     {    if (v.ID > itsVertices.size())
          {    for (int k = itsVertices.size() + 1;  k < v.ID;  k++)
                    itsVertices.add (new Vertex (k, null));
               itsVertices.add (v);  // added at the end of the list
          }
     } //================================================


     /** Remove all edges from the Graph.  Leave the vertices. */

     public abstract void clear();


     /** The following methods throw a RuntimeException if the
      *  parameter is null or its vertex ids are not in the range 
      *  1...getNumVertices(), except they may simply ignore 0.  
      *  Do not use a Graph iterator to remove anything.  */


     /** Tell whether this graph contains the given Edge. */

     public abstract boolean contains (Edge given);


     /** Remove the given Edge if it is in there and return true.
      *  But if the Edge is not in there, simply return false. */

     public abstract boolean remove (Edge given);


     /** Add the given Edge if it is not in there and return true.
      *  But if the Edge is in there, simply return false. */

     public abstract void add (Edge given);


     /** Return an iteration over all edges that exit Vertex v. */

     public abstract Iterator edgesFrom (Vertex v);


     /** Return the number of Edges that end at that Vertex. */

     public abstract int inDegree (Vertex given);


     /** Return the number of Edges that start at that Vertex. */

     public int outDegree (Vertex given)
     {    Iterator it = edgesFrom (given);
          int count = 0;
          while (it.hasNext())
          {    it.next();
               count++;
          }
          return count;
     }    //================================================
}


public class Vertex extends GraphPart
{
     public final int ID;
     public final Object DATA;


     public Vertex (int id, Object data)
     {    ID = id;
          DATA = data;
     } //================================================
}
//#####################################################



public class GraphPart
{
     private int itsMark = 0;


     public final int getMark()  
     {    return itsMark;
     } //================================================


     public final void setMark (int given)  
     {    itsMark = given;
     } //================================================
}
//#####################################################



public class Edge extends GraphPart
{
     public final Vertex TAIL;  // vertex where it begins
     public final Vertex HEAD;  // vertex where it ends
     public final double WEIGHT;


     public Edge (Vertex from, Vertex to)
     {    TAIL = from;
          HEAD = to;
          WEIGHT = 1;
     } //================================================


     public boolean equals (Object ob)  
     {    return ob instanceof Edge && this.HEAD == ((Edge) ob).HEAD
                                    && this.TAIL == ((Edge) ob).TAIL;
     } //================================================


     public Edge (Vertex from, Vertex to, double weight)
     {    TAIL = from;
          HEAD = to;
          WEIGHT = weight > 0.0 ? weight : 1.0;
     } //================================================
}


public class MatrixGraph extends Graph
{
     private Edge[][] edgeAt;
     private int[] itsIns;

     /** Specify the maximum number of vertices the graph can have.  
      *  This number cannot be changed by later method calls. */

     public MatrixGraph (int maxVerts)
     {    super();
          edgeAt = new Edge[maxVerts + 1][maxVerts + 1]; // all null
          itsIns = new int[maxVerts + 1];
     } //================================================


     public final void addVertex (Vertex v)
     {    if (v.ID >= edgeAt.length)
               throw new IllegalArgumentException ("not with matrix");
          super.addVertex (v);
     } //================================================


     public final void clear()             
     {    int maxVerts = edgeAt.length;
          edgeAt = new Edge[maxVerts + 1][maxVerts + 1]; // all null
     } //================================================


     public final boolean contains (Edge given) 
     {    return edgeAt[given.TAIL.ID][given.HEAD.ID] != null;
     } //================================================


     public final boolean remove (Edge given)  
     {    Edge e = edgeAt[given.TAIL.ID][given.HEAD.ID];
          edgeAt[given.TAIL.ID][given.HEAD.ID] = null;
          if (e != null)
               itsIns[given.HEAD.ID]--;
          return e != null;
     } //================================================


     public final void add (Edge given)        
     {    if (edgeAt[given.TAIL.ID][given.HEAD.ID] == null)
               itsIns[given.HEAD.ID]++;
           edgeAt[given.TAIL.ID][given.HEAD.ID] = given;
     } //================================================
     

     public final java.util.Iterator edgesFrom (Vertex v)  
     {    ArrayList list = new ArrayList();
          for (int k = 1;  k <= getNumVertices();  k++)
          {    if (edgeAt[v.ID][k] != null)
                    list.add (edgeAt[v.ID][k]);
          }
          return list.iterator();
     }
     } //================================================


     public int inDegree (Vertex given) 
     {    return itsIns[given.ID];
     } //================================================


     public int outDegree (Vertex given) // in MatrixGraph
     {    int count = 0;
          for (int k = 1;  k <= getNumVertices();  k++)
          {    if (edgeAt[given.ID][k] != null)
                    count++;
          }
          return count;
     }    //===========================================


     public boolean hasTwoWayEdge (Vertex given) // in MatrixGraph 
     {    for (int k = 1;  k <= getNumVertices();  k++)
          {    if (edgeAt[given.ID][k] != null 
                               && edgeAt[k][given.ID] != null)
                    return true;
          }
          return false;
     }    //===========================================
}


import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class ListGraph extends Graph
{
     private ArrayList itsList = new ArrayList();


     public ListGraph()
     {    super();
          itsList.add (null);  // we do not use the value at index 0
     } //================================================


     public final void addVertex (Vertex v)  
     {    super.addVertex (v);
          if (v.ID >= itsList.size())
          {    for (int k = itsList.size();  k <= v.ID;  k++)
                    itsList.add (new ArrayList());
          }
     } //================================================


     /** Remove all edges from the graph, but not the vertices. */

     public final void clear()  
     {    for (int k = 1;  k <= getNumVertices();  k++)
               itsList.set (k, new ArrayList());
     } //================================================


     public final boolean contains (Edge given)
     {    return ((Collection) itsList.get (given.TAIL.ID))
                         .contains (given);
     } //================================================


     public final boolean remove (Edge given)
     {    return ((Collection) itsList.get (given.TAIL.ID))
                         .remove (given);
     } //================================================


     public final void add (Edge given)
     {    if (given.HEAD.ID < 1 || given.HEAD.ID > getNumVertices())
               throw new IllegalArgumentException ("bad vertex");
          Collection z = (Collection) itsList.get (given.TAIL.ID);
          if (z.contains (given))
               z.remove (given);
          z.add (given);
     } //================================================


     public final Iterator edgesFrom (Vertex v)  
     {    return ((Collection) itsList.get (v.ID)).iterator();
     } //================================================


     public int inDegree (Vertex given) 
     {    int count = 0;
          for (int k = 1;  k <= getNumVertices();  k++)
          {    if (contains (new Edge (getVertex (k), given)))
                    count++;
          }
          return count;
     } //================================================


     public int outDegree (Vertex given)  // for ListGraph
     {    return ((Collection) itsList.get (given.ID)).size();
     }    //================================================
}


public class GraphStuff extends ListGraph // for instance
{

     private void getStarters (QueueADT toCheck)
     {    Iterator verts = vertices();
          while (verts.hasNext())
          {    Vertex v = (Vertex) verts.next();
               int numPredecessors = inDegree (v);
               if (numPredecessors == 0)
                    toCheck.enqueue (v);
               else
                    v.setMark (numPredecessors);
          }
     }    //===========================================


     private void sort (QueueADT toCheck, QueueADT sorted)
     {    getStarters (toCheck);
          while ( ! toCheck.isEmpty())   // once per Vertex
          {    Vertex ok = (Vertex) toCheck.dequeue();
               sorted.enqueue (ok);
               Iterator edges = edgesFrom (ok);
               while (edges.hasNext())
               {    Vertex v = ((Edge) edges.next()).HEAD;
                    v.setMark (v.getMark() - 1);
                    if (v.getMark() == 0)
                         toCheck.enqueue (v);
               }
          }
     }    //===========================================


     /** Mark 1 on each vertex reachable from the given Vertex. */

     private void markReachables (Vertex given)
     {    given.setMark (1);                                     //1
          Iterator it = edgesFrom (given);                       //2
          while (it.hasNext())                                   //3
          {    Vertex v = ((Edge) it.next()).HEAD;               //4
               if (v.getMark() == 0)                             //5
                    markReachables (v);                          //6
          }                                                      //7
     } //================================================


     /** Tell whether you can reach each vertex from vertex #1. */

     public boolean isConnected()
     {    markReachables (getVertex (1));                        //8
          Iterator it = vertices();                              //9
          int count = 0;                                         //10
          while (it.hasNext())                                   //11
          {    Vertex v = (Vertex) it.next();                    //12
               if (v.getMark() == 1)                             //13
               {    count++;                                     //14
                    v.setMark (0);                               //15
               }                                                 //16
          }                                                      //17
          return count == getNumVertices();                      //18
     } //================================================


     /** Find a path from given through all unmarked vertices and
      *  mark each vertex with its sequence number in that path. */

     private boolean solveSalesman (Vertex given, int seqNum)
     {    given.setMark (seqNum);                                //19
          if (seqNum == getNumVertices())                        //20
               return true;                                      //21
          Iterator it = edgesFrom (given);                       //22
          while (it.hasNext())                                   //23
          {    Vertex v = ((Edge) it.next()).HEAD;               //24
               if (v.getMark() == 0)                             //25
               {    if (solveSalesman (v, seqNum + 1))           //26
                         return true;                            //27
               }                                                 //28
          }                                                      //29
          given.setMark (0);                                     //30
          return false;                                          //31
     }    //===========================================


     private void markDistance (Vertex given, QueueADT queue)
     {    given.setMark (1);
          queue.enqueue (given);
          while (! queue.isEmpty())
          {    Vertex current = (Vertex) queue.dequeue();
               Iterator it = this.edgesFrom (current);
               while (it.hasNext())
               {    Vertex v = ((Edge) it.next()).HEAD;
                    if (v.getMark() == 0)
                    {    v.setMark (current.getMark() + 1);
                         queue.enqueue (v);
                    }
               }
          }
     }    //===========================================


     public double averageWeight (Vertex given)
     {    Iterator it = edgesFrom (given);
          double total = ((Edge) it.next()).WEIGHT;
          int count = 1;
          while (it.hasNext())
          {    total += ((Edge) it.next()).WEIGHT;
               count++;
          }
          return total / count;
     } //================================================


// KRUSKAL'S ALGORITHM

     /** Return a stack containing the edges on an MST for an
      *  undirected graph.  If the graph is not connected, the
      *  edges should form one MST for each connected part. */

     public StackADT Kruskals()
     {    StackADT spanner = new NodeStack();                    //1
          PriQue queue = new TreePriQue (new ByWeight());        //2
          putEdgesOnPriorityQueueByWeight (queue);               //3
          constructMST (spanner, queue, getNumVertices());       //4
          return spanner;                                        //5
     } //================================================


     /** Put all Edges of the Graph on the priority queue with
      *  lighter Edges having higher priority. 
      *  Precondition:  the queue is not null.  */

     private void putEdgesOnPriorityQueueByWeight (PriQue queue)
     {    Iterator it = vertices();                              //6
          while (it.hasNext())                                   //7
          {    Iterator edges = edgesFrom ((Vertex) it.next());  //8
               while (edges.hasNext())                           //9
               {    Edge e = (Edge) edges.next();                //10
                    if (e.TAIL.ID < e.HEAD.ID)                   //11
                         queue.add (e);                          //12
               }                                                 //13
          }                                                      //14
     }   //================================================


     /** Check each Edge in order from lightest to heaviest.  Put
      *  the Edge in spanner whenever its two endpoints do not
      *  have a path between them using Edges already in spanner.
      *  Precondition:  spanner and queue are not null.  */

     private static void constructMST (StackADT spanner, 
                    PriQue queue, int numLeft)
     {    UnionFind group = new UnionFind (numLeft + 1);         //15
          while (! queue.isEmpty() && numLeft > 1)               //16
          {    Edge e = (Edge) queue.removeMin();                //17
               if (! group.equates (e.TAIL.ID, e.HEAD.ID))       //18
               {    spanner.push (e);                            //19
                    group.unite (e.TAIL.ID, e.HEAD.ID);          //20
                    numLeft--;                                   //21
               }                                                 //22
          }                                                      //23
     } //================================================


     private static class ByWeight implements java.util.Comparator 
     {
          public boolean prior (Object one, Object two)
          {    double diff = ((Edge) one).WEIGHT - ((Edge) two).WEIGHT;
               return diff > 0 ? 1 : diff < 0 ? -1 : 0;          //25
          }
     } //================================================


// DIJKSTRA'S ALGORITHM

     /** Return an array of doubles in which the kth component is
      *  the minimum distance from the given vertex to vertex #k.
      *  A component value of 0.0 means it is not reachable. */

     public double[] Dijkstras (Vertex start)
     {    ArrayList fringe = new ArrayList();                   //1
          double[] dist = new double [getNumVertices() + 1];    //2
          updateFringe (start, fringe, dist);                   //3
          dist[start.ID] = -1.0;                                //4
          while (! fringe.isEmpty())                            //5
          {    Vertex best = findClosest (fringe, dist);        //6
               updateFringe (best, fringe, dist);               //7
          }                                                     //8
          return dist;                                          //9
     }    //================================================


     /** Add to the fringe each vertex reachable from vert but
      *  not previously processed. Update the shortest distance 
      *  array for any vertex that is reachable from vert. */

     private void updateFringe (Vertex vert, ArrayList fringe,
                                double[] dist)
     {    Iterator it = edgesFrom (vert);                       //10
          while (it.hasNext())                                  //11
          {    Edge e = (Edge) it.next();                       //12
               double newDist = dist[vert.ID] + e.WEIGHT;       //13
               if (dist[e.HEAD.ID] == 0.00) //not on fringe list//14
               {    dist[e.HEAD.ID] = newDist;                  //15
                    fringe.add (e.HEAD);     // add to list     //16
               }                                                //17
               else if (newDist < dist[e.HEAD.ID])              //18
                    dist[e.HEAD.ID] = newDist;                  //19
          }                                                     //20
     } //================================================


     /** Find and return the vertex in the fringe that has the 
      *  smallest dist value, after removing it from the fringe. */

     private Vertex findClosest (ArrayList fringe, double[] dist)
     {    Vertex best = (Vertex) fringe.get (0);                //21
          int indexBest = 0;                                    //22
          for (int k = 1;  k < fringe.size();  k++)             //23
          {    Vertex v = (Vertex) fringe.get (k);              //24
               if (dist[v.ID] < dist[best.ID])                  //25
               {    best = v;                                   //26
                    indexBest = k;                              //27
               }                                                //28
          }                                                     //29
          fringe.remove (indexBest);                            //30
          return best;                                          //31
     } //================================================
}


public class UnionFind_0    // simple array implementation
{
     private final int itsLength;
     private int[] itsItem;


     /** Create a partition of the int values 0...numValues-1,
      *  initially with each int in its own 1-element group.  Use
      *  1 in place of numValues if numValues is not positive. */

     public UnionFind_0 (int numValues)
     {    itsLength = numValues > 0  ?  numValues  :  1;
          itsItem = new int[itsLength];
          for (int k = 0;  k < itsLength;  k++)
               itsItem[k] = k;
     } //================================================


     /** Tell whether one and two are in the same group. */

     public boolean equates (int one, int two)
     {    return one >= 0 && one < itsLength && two >= 0
                     && two < itsLength && itsItem[one] == itsItem[two];
     } //================================================


     /** Assure that one and two are in the same group. 
      *  No effect if one or two is not in 0...numValues-1. */

     public void unite (int one, int two)
     {    if (one >= 0 && one < itsLength && two >= 0 
                  && two < itsLength && itsItem[one] != itsItem[two])
          {    for (int k = 0;  k < itsLength;  k++)
               {    if (itsItem[k] == itsItem[two])
                         itsItem[k] = itsItem[one];
               }
          }
     }    //===========================================
}


public class UnionFind    // Queue of Nodes implementation
{
     private final int itsLength;
     private Queue[] itsItem;    // Queue is a nested class
     // equates is unchanged.  The constructor is an exercise.


     /** Assure that one and two are in the same group. 
      *  No effect if one or two is not in 0...numValues-1. */

     public void unite (int one, int two)
     {    if (one >= 0 && one < itsLength && two >= 0 
                    && two < itsLength && itsItem[one] != itsItem[two])
          {    if (itsItem[one].itsSize >= itsItem[two].itsSize)
                    combineQueues (itsItem[one], itsItem[two]);
               else  // swap the order so the larger is first
                    combineQueues (itsItem[two], itsItem[one]);
          }
     }    //===========================================


     private void combineQueues (Queue first, Queue second)
     {    first.itsRear.itsNext = second.itsFront;
          first.itsRear = second.itsRear;
          first.itsSize += second.itsSize;
          for (Node p = second.itsFront; p != null; p = p.itsNext)
               itsItem[p.itsData] = first;
     }    //===========================================


     /** Tell whether one and two are in the same group. */

     public boolean equates (int one, int two)
     {    return one >= 0 && one < itsLength && two >= 0
                     && two < itsLength && itsItem[one] == itsItem[two];
     }    //================================================


     private static class Queue
     {
          public Node itsFront;
          public Node itsRear;
          public int itsSize;

          public Queue (int given)
          {    itsFront = new Node (given, null);
               itsRear = itsFront;
               itsSize = 1;
          }
     }    //===========================================


     private static class Node
     {
          public int itsData;
          public Node itsNext;

          public Node (int data, Node next)
          {    itsData = data;
               itsNext = next;
          }
     }    //===========================================


     public UnionFind (int numValues)
     {    itsLength = numValues > 0  ?  numValues  :  1;
          itsItem = new Queue[itsLength];
          for (int k = 0;  k < itsLength;  k++)
               itsItem[k] = new Queue (k);
     }    //===========================================
}


public class Fibonacci
{
     public static final int MAX = 10000;
     private static int[] answer = new int[MAX];


     /** Return the nth Fibonacci number, where fib(0) = 1 and
      *  fib(1) = 1 and otherwise fib(n) = fib(n-2) + fib(n-1). 
      *  But return 1 if n >= MAX. */

     public static int fib (int n)
     {    if (n <= 1 || n >= MAX)
               return 1;
          if (answer[n] == 0)  // the first request for this value
               answer[n] = fib (n - 2) + fib (n - 1);
          return answer[n];
     }    //================================================
}


public class MergeCount
{
     public static final int MAX = 10000;
     private static int[] answer = new int[MAX];


     /** Return the nth compsMS number, which is the maximum
      *  number of comparisons required to sort n values using 
      *  the merge sort logic.  But return 0 if n >= MAX. */

     public static int compsMS (int n)
     {    if (n <= 1 || n >= MAX)
               return 0;
          if (answer[n] == 0)  // the first request for this value
               answer[n] = compsMS (n / 2) + compsMS (n - n / 2) + n - 1;
          return answer[n];
     }    //================================================
}


public class TreeCount
{
     public static final int MAX = 10000;
     private static int[] answer = new int[MAX];

     /** Return the nth trees number, which is the number of 
      *  different binary trees.  But return n if n >= MAX. */

     public static int trees (int n)
     {    if (n <= 2 || n >= MAX)
               return n;
          if (answer[n] == 0)  // the first request for this value
          {    int total = trees (n - 1);
               for (int k = 2;  k <= n / 2;  k++)
                    total += trees (k - 1) * trees (n - k);
               answer[n] = (n % 2 == 0)  ?  2 * total
                     : 2 * total + trees (n / 2) * trees (n / 2);
          }
          return answer[n];
     }    //================================================
}


public class LongestCommonSubsequence
{
     public static final int MAX = 1000;
     private static int[][] answer = new int[MAX][MAX];
     private static String one;
     private static String two;


     /** Return the length of the longest common subsequence of
      *  the two given Strings. Return 0 if either is null or
      *  has MAX or more characters.  */

     public static int longest (String first, String second)
     {    if (first == null || second == null 
                  || first.length() >= MAX || second.length() >= MAX)
               return 0;
          for (int row = 0;  row <= first.length();  row++)
          {    for (int col = 0;  col <= second.length();  col++)
                    answer[row][col] = row * col == 0  ?  0  :  -1;
          }
          one = first;
          two = second;
          return longest (one.length(), two.length());
     }    //================================================


     private static int longest (int len1, int len2)
     {    if (answer[len1][len2] >= 0)
               return answer[len1][len2];
          if (one.charAt (len1 - 1) == two.charAt (len2 - 1))
               answer[len1][len2] = longest (len1 - 1, len2 - 1) + 1;
          else
               answer[len1][len2] = Math.max (longest (len1 - 1, len2),
                                             longest (len1, len2 - 1));
          return answer[len1][len2];
     }    //================================================


     /** Return the length of the LCS of the first len1 characters
      *  of the first String and the first len2 characters of the
      *  second String.  Throw an Exception for bad indexes. */

     public static int lcs (int len1, int len2)
     {    return answer[len1][len2];
     }    //================================================


     private static int longest_0 (int len1, int len2)
     {    for (int row = 1;  row <= len1;  row++)
               for (int col = 1;  col <= len2;  col++)
               {    if (one.charAt (row - 1) == two.charAt (col - 1))
                         answer[row][col] = answer[row - 1][col - 1] + 1;
                    else if (answer[row - 1][col] > answer[row][col - 1])
                         answer[row][col] = answer[row - 1][col];
                    else
                         answer[row][col] = answer[row][col - 1];
               }
          return answer[len1][len2];
     }    //================================================
}

All information Copyright (c)1999 - Dr. William C. Jones, Jr.
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved.