package rpi.goldsd.graph;

import java.io.*;
import java.util.Enumeration;
import java.util.Stack;
import java.util.Vector;
import rpi.goldsd.container.*;

/**
 * The <tt>Algorithms</tt> class provides a set of static methods that operate
 * on graphs and other graph-related objects.  In particular, a number of the
 * algorithms and methods provided produce <tt>Tree</tt> or <tt>Path</tt>
 * objects.
 *
 * @see GraphBase
 * @version 2.1, 4/20/98
 * @author David Goldschmidt
 */
public class Algorithms
{
  /* ******************  STATIC CLASS ATTRIBUTES  ****************** */

  /**
   * Used by methods of the static <tt>Algorithms</tt> class to label
   * a <tt>Vertex</tt> or <tt>Edge</tt> object as being part of a tree
   * or path.
   */
  public static final int IN_TREE_OR_PATH = 1;


  /**
   * Used by methods of the static <tt>Algorithms</tt> class to label
   * a <tt>Vertex</tt> or <tt>Edge</tt> object as being a <i>fringe</i>
   * vertex or edge.
   */
  public static final int FRINGE = 2;


  /**
   * Used by methods of the static <tt>Algorithms</tt> class to label
   * a <tt>Vertex</tt> or <tt>Edge</tt> object as being unseen.
   */
  public static final int UNSEEN = 3;


  /**
   * Used by methods of the static <tt>Algorithms</tt> class to label
   * an <tt>Edge</tt> object as being traversed.
   */
  public static final int TRAVERSED = 4;



  /* ******************  STATIC CLASS METHODS  ****************** */

  /**
   * Returns a breadth-first traversal tree for the graph starting
   * from the given vertex.  Note that the vertex must be associated
   * with an existing graph.
   * @param startVertex the vertex to start the breadth-first traversal from.
   * @return a breadth-first traversal tree for the associated graph.
   * @exception IllegalArgumentException if the given vertex is not
   *                                     associated with any graph.
   */
  public static final Tree breadthFirstTraversal( Vertex startVertex )
    throws IllegalArgumentException
  {
    if ( ! startVertex.isInGraph() ) throw
      new IllegalArgumentException( "Vertex " + startVertex + " not in a graph." );

    // Determine if the Graph is a weighted graph ...
    boolean weightedGraph = startVertex.graph().isWeighted();

    // Construct a new root Vertex by cloning the given startVertex ...
    Vertex root = (Vertex)startVertex.clone();

    // Construct a new Tree with the given root Vertex ...
    Tree T = new Tree( root, "BFS Tree" );

    // Construct a queue for the BFS algorithm and add the startVertex
    // and the cloned root Vertex to this queue ...
    LinkedList queue = new LinkedList();
    queue.addToTail( new ListNode( startVertex ) );
    queue.addToTail( new ListNode( root ) );

    // Iterate through all vertices ...
    while ( ! queue.isEmpty() )
    {
      // Remove the next graph and tree vertices from the queue ...
      Vertex graphV = (Vertex)queue.removeFromHead().getData();
      Vertex treeV = (Vertex)queue.removeFromHead().getData();

      // For each incident Edge and destination Vertex that is not yet
      // in the BFS Tree, add the Edge and Vertex to the BFS Tree ...
      Enumeration e = graphV.incidentEdges();
      while ( e.hasMoreElements() )
      {
        Edge graphE = (Edge)e.nextElement();
        Vertex graphW = graphE.traverseFrom( graphV );

        if ( ! T.contains( graphW ) )
        {
          Vertex treeW = (Vertex)graphW.clone();
          Edge treeE = cloneEdge( treeV, treeW, graphE );
          T.add( treeE, treeW );

          // Add new Vertex to the queue such that its children
          // are subsequently processed ...
          queue.addToTail( new ListNode( graphW ) );
          queue.addToTail( new ListNode( treeW ) );
        }
      }
    }

    return T;
  }


  /**
   * Returns a breadth-first traversal tree for the given graph starting
   * at an arbitrary vertex.
   * @param G the graph to perform the breadth-first traversal on.
   * @return a breadth-first traversal tree for the given graph.
   * @exception IllegalArgumentException if the given graph is empty
   *                                     (i.e. contains no vertices).
   */
  public static final Tree breadthFirstTraversal( Graph G )
    throws IllegalArgumentException
  {
    Enumeration e = G.vertices();
    if ( e.hasMoreElements() )
      return ( breadthFirstTraversal( (Vertex)e.nextElement() ) );
    else
      throw new IllegalArgumentException( "Graph contains no vertices." );
  }


  /**
   * Since the <tt>Edge</tt> class does not implement the <tt>Cloneable</tt>
   * interface, the static <tt>cloneEdge()</tt> exists for copying both
   * directed and undirected edges.
   * @param startVertex the first endpoint vertex of the new edge.
   * @param endVertex the second endpoint vertex of the new edge.
   * @param originalEdge the edge to copy.
   * @return the new <tt>Edge</tt> or <tt>DirectedEdge</tt> object.
   */
  public static final Edge cloneEdge( Vertex startVertex, Vertex endVertex,
                                      Edge originalEdge )
  {
    Hashable data = originalEdge.data();
    Edge E = null;
    
    if ( originalEdge instanceof DirectedEdge )
    {
      if ( originalEdge.isWeighted() )
        E = new DirectedEdge( startVertex, endVertex, data,
                              originalEdge.weight() );
      else
        E = new DirectedEdge( startVertex, endVertex, data );
    }
    else  /* undirected edge */
    {
      if ( originalEdge.isWeighted() )
        E = new Edge( startVertex, endVertex, data, originalEdge.weight() );
      else
        E = new Edge( startVertex, endVertex, data );
    }

    return E;
  }


  /**
   * Returns a graph that is the complement of the given graph.
   * The new graph contains a clone of all vertices of the given
   * graph.
   * @param H the given graph.
   * @return a graph that is the complement of the given graph.
   */
  public static final Graph complement( GraphBase H )
  {
    Graph G = new Graph( "Complement of " + H.name() );

    // Clone all vertices of the original GraphBase object ...
    Enumeration e = H.vertices();
    while ( e.hasMoreElements() )
    {
      Vertex j = (Vertex)e.nextElement();
      G.add( (Vertex)j.clone() );
    }

    Enumeration v = H.vertices();
    while ( v.hasMoreElements() )
    {
      Vertex q = (Vertex)v.nextElement();

      Enumeration w = H.vertices();
      while ( w.hasMoreElements() )
      {
        Vertex r = (Vertex)w.nextElement();
        if ( q != r && ! H.isEdgeBetween( q, r ) )
        {
          Vertex qq = G.mapToVertex( q.data() );
          Vertex rr = G.mapToVertex( r.data() );
          if ( ! G.isEdgeBetween( qq, rr ) )
            G.add( new Edge( qq, rr ) );
        }
      }
    }

    return G;
  }


  /**
   * Returns a depth-first traversal tree for the graph starting
   * from the given vertex.  Note that the vertex must be associated
   * with an existing graph.
   * @param startVertex the vertex to start the depth-first traversal from.
   * @return a depth-first traversal tree for the associated graph.
   */
  public static final Tree depthFirstTraversal( Vertex startVertex )
  {
    if ( ! startVertex.isInGraph() ) throw new
      IllegalArgumentException( "Vertex " + startVertex + " not in a graph." );

    // Construct a new root Vertex by cloning the given startVertex ...
    Vertex root = (Vertex)startVertex.clone();

    // Construct a new Tree with the given root Vertex ...
    Tree T = new Tree( root, "DFS Tree" );

    // Recursively construct the DFS Tree via the DFS() method ...
    DFS( startVertex, root, T );

    return T;
  }


  /**
   * Returns a depth-first traversal tree for the given graph starting
   * at an arbitrary vertex.
   * @param G the graph to perform the depth-first traversal on.
   * @return a depth-first traversal tree for the given graph.
   * @exception IllegalArgumentException if the given graph is empty
   *                                     (i.e. contains no vertices).
   */
  public static final Tree depthFirstTraversal( Graph G )
  {
    Enumeration e = G.vertices();
    if ( e.hasMoreElements() )
      return ( depthFirstTraversal( (Vertex)e.nextElement() ) );
    else
      throw new IllegalArgumentException( "Graph contains no vertices." );
  }



  private static final void DFS( Vertex graphVertex, Vertex treeVertex, Tree T )
  {
    // For each incident Edge and destination Vertex that is not yet
    // in the DFS Tree, add the Edge and Vertex to the DFS Tree.  Then
    // recursively call the DFS() method with the destination Vertex ...
    Enumeration e = graphVertex.incidentEdges();
    while ( e.hasMoreElements() )
    {
      Edge E = (Edge)e.nextElement();
      Vertex dest = E.traverseFrom( graphVertex );

      if ( ! T.contains( dest ) )
      {
        Vertex V = (Vertex)dest.clone();
        Edge newE = cloneEdge( treeVertex, V, E );
        T.add( newE, V );
        DFS( dest, V, T );
      }
    }
  }


  /**
   * After invoking the <tt>findBicomponents()</tt> method, this method
   * simply displays the <i>biconnected components</i> of the given
   * <tt>Graph</tt> object.
   * @param G the graph in which the biconnected components are to be
   *          determined.
   */
  public static final void displayBicomponents( Graph G )
  {
    Stack S = Algorithms.findBicomponents( G );

    System.out.println( "There are " + S.size() +
                        " bicomponents in the given graph:" );

    while ( ! S.isEmpty() )
    {
      Vertex V = (Vertex)S.pop();
      V.rank += V.min.parent.rank + 1 - G.numVertices();
      System.out.print( "  Bicomponent " + V + " (rank " + V.rank + "): " + V.min );
      Enumeration e = G.vertices();
      while ( e.hasMoreElements() )
      {
        Vertex U = (Vertex)e.nextElement();
        if ( U.parent == V )
          System.out.print( ", " + U );
      }
      System.out.println( "." );
    }
  }


  /**
   * Finds the <i>biconnected components</i> of the given <tt>Graph</tt>
   * object by using a depth-first traversal and the <i>utility</i> fields
   * of the <tt>Vertex</tt> class.
   * @param G the graph in which the biconnected components are to be
   *          determined
   * @return a <tt>Stack</tt> representing the set of biconnected components.
   */
  public static final Stack findBicomponents( Graph G )
  {
    return findBicomponents( G, null, null );
  }


  /**
   * Finds the <i>biconnected components</i> of the given <tt>Graph</tt>
   * object by using a depth-first traversal and the <i>utility</i> fields
   * of the <tt>Vertex</tt> class.  This method is used by the
   * <tt>findLongestPath2()</tt> method and therefore contains two
   * additional arguments: <tt>N</tt> and <tt>goal</tt>.
   * @param G the graph in which the biconnected components are to be
   *          determined
   * @param N the <tt>backtrackNode</tt> representing the set of vertices
   *          and edges in the backtrack tree.
   * @param goal the goal <tt>Vertex</tt> object.
   * @return a <tt>Stack</tt> representing the set of biconnected components.
   */
  public static final Stack findBicomponents( Graph G, backtrackNode N,
                                              Vertex goal )
  {
    boolean verbose = false;

    // Mark all vertices unseen by setting their ranks to 0 ...
    Enumeration e = G.vertices();
    while ( e.hasMoreElements() )
    {
      Vertex V = (Vertex)e.nextElement();
      V.rank = 0;
    }

    // Mark all edges as un-traversed ...
    e = G.edges();
    while ( e.hasMoreElements() )
    {
      Edge E = (Edge)e.nextElement();
      E.status = UNSEEN;
    }

    // Mark all vertices in the backtrack tree as being seen by
    // setting their ranks to "infinity" ...
    if ( N != null )
    {
      while ( N != null )
      {
        N.sourceVertex.rank = G.numVertices();  // a little redundant ...
        N.targetVertex.rank = G.numVertices();
        N = N.previous;
      }
    }

    int nextRank = 1;
    Stack activeStack = new Stack();
    Stack settledStack = new Stack();
    Vertex dummy = new Vertex();
    dummy.rank = 0;

    boolean done = false;
    e = G.vertices();
    while ( e.hasMoreElements() && ! done )
    {
      Vertex V;

      // If the goal is not null, determine bicomponents from goal ...
      if ( goal == null )
        V = (Vertex)e.nextElement();
      else
      {
        V = goal;
        done = true;
      }

      if ( V.rank == 0 )
      {
        // Perform a DFS with V as the root to find bicomponents ...
        if ( verbose )
          System.out.println( "Root vertex: " + V + "." );
        V.parent = dummy;
        V.rank = nextRank++;
        activeStack.push( V );
        V.min = V.parent;

        Vertex articPoint = null;

        do
        {
          Edge E = null;
          Enumeration f = V.incidentEdges();
          while ( f.hasMoreElements() )
          {
            E = (Edge)f.nextElement();
            if ( E.status == UNSEEN )
              break;
          }

          if ( E != null && E.status == UNSEEN )
          {
            Vertex U = E.traverseFrom( V );
            E.status = TRAVERSED;
            if ( U.rank != 0 )
            {
              if ( U.rank < V.min.rank )
                V.min = U;
            }
            else
            {
              U.parent = V;
              V = U;
              V.rank = nextRank++;
              activeStack.push( V );
              V.min = V.parent;
            }
          }
          else  // All edges from V have been traversed ...
          {
            Vertex U = V.parent;
            if ( V.min == U )
            {
              if ( verbose && U == dummy )
              {
                if ( articPoint != null )
                  System.out.println( " and " + articPoint +
                          " (this ends a connected component of the graph)." );
                else
                  System.out.println( "Isolated vertex " + V + "." );

                activeStack = new Stack();
                articPoint = null;
              }
              else if ( U != dummy )
              {
                if ( verbose && articPoint != null )
                  System.out.println( " and articulation point " + articPoint + "." );

                int count = 0;
                Vertex T = (Vertex)activeStack.pop();
                if ( verbose )
                  System.out.print( "Bicomponent " + V );

                if ( T == V && verbose )
                  System.out.println();

                if ( T != V )
                {
                  if ( verbose )
                    System.out.println( " also includes:" );

                  while ( T != V )
                  {
                    count++;
                    T.parent = V;

                    if ( verbose )
                      System.out.println( "  " + T );

                    T = (Vertex)activeStack.pop();
                  }
                }

                V.parent = V;
                V.rank = count + G.numVertices();
                settledStack.push( V );

                articPoint = U;
              }
            }
            else if ( V.min.rank < U.min.rank )
            {
              U.min = V.min;
            }

            V = U;
          }
        }
        while ( V != dummy );
      }
    }

    return settledStack;
  }


  /**
   * Attempts to find an <i>Euler Path</i> in a connected graph starting from
   * an arbitrary vertex of the given graph.
   * @param G the given graph.
   * @return a <tt>Path</tt> object that traverses all edges of the
   *         given graph exactly once.
   * @exception IllegalArgumentException if the given graph is empty
   *                                     (i.e. contains no vertices).
   */
  public static final Path findEulerPath( Graph G )
    throws IllegalArgumentException
  {
    Enumeration e = G.vertices();
    if ( e.hasMoreElements() )
      return findEulerPath( (Vertex)e.nextElement() );
    else
      throw new IllegalArgumentException( "Graph contains no vertices." );
  }


  /**
   * Attempts to find an <i>Euler Path</i> in a connected graph starting from
   * a given vertex.  
   * @param startVertex the <tt>Vertex</tt> object at which to begin
   *                    the Euler Path.
   * @return a <tt>Path</tt> object that traverses all edges of the
   *         given graph exactly once.
   * @exception IllegalArgumentException if the given <tt>Vertex</tt> object
   *            is not associated with a graph, or the graph associated with
   *            the given <tt>Vertex</tt> object is not a <tt>Graph</tt>
   *            object.
   * @exception PathDoesNotExistException if the given graph is not connected,
   *            or if an undirected graph contains a <tt>Vertex</tt> of an odd
   *            degree, or if a directed graph contains a <tt>Vertex</tt> whose
   *            in-degree does not equal that of its out-degree.
   */
  public static final Path findEulerPath( Vertex startVertex )
    throws IllegalArgumentException, PathDoesNotExistException
  {
    boolean verbose = false;

    if ( startVertex.graph() == null ) throw
      new IllegalArgumentException( "Vertex must be associated with a graph." );

    if ( ! ( startVertex.graph() instanceof Graph ) ) throw
      new IllegalArgumentException( "Must be applied to Graph object only." );

    Graph G = (Graph)startVertex.graph();

    // Ensure that G is a connected graph ...
    if ( ! G.isConnected() ) throw
      new PathDoesNotExistException( "Graph must be connected." );

    // Ensure that an Euler Path exists in the given graph ...
    Enumeration e = G.vertices();
    if ( G.isDigraph() )
    {
      while ( e.hasMoreElements() )
      {
        Vertex V = (Vertex)e.nextElement();
        if ( V.inDegree() != V.outDegree() ) throw
          new PathDoesNotExistException();
      }
    }
    else  /* undirected graph */
    {
      while ( e.hasMoreElements() )
      {
        Vertex V = (Vertex)e.nextElement();
        if ( V.degree() % 2 != 0 ) throw
          new PathDoesNotExistException();
      }
    }

    // Instantiate a Path and add the initial startVertex ...
    Path Euler = new Path( startVertex );

    // Mark all edges as UNSEEN ...
    e = G.edges();
    while ( e.hasMoreElements() )
      ((Edge)e.nextElement()).status = UNSEEN;

    // Find a cycle in G ...
    findCycle( Euler );
    if ( verbose )
      System.out.println( "Found cycle: " + Euler );

    while ( Euler.length() < G.numEdges() )
    {
      // Find untraversed edge from given path ...
      e = Euler.vertices();
      Edge E = null;
      Vertex V = null;
      boolean foundEdge = false;

      while ( ! foundEdge && e.hasMoreElements() )
      {
        V = (Vertex)e.nextElement();
        Enumeration f = V.incidentEdges();
        while ( ! foundEdge && f.hasMoreElements() )
        {
          E = (Edge)f.nextElement();
          if ( E.status == UNSEEN ) foundEdge = true;
        }
      }

      // Find next cycle ...
      Path newEuler = new Path( V );
      newEuler.add( E );
      E.status = IN_TREE_OR_PATH;
      findCycle( newEuler );
      if ( verbose )
        System.out.println( "\n\nNext cycle: " + newEuler );

      // Splice together Euler and newEuler paths ...
      Euler.insertAfter( newEuler, V );
    }

    return Euler;
  }


  /**
   * Attempts to find a cycle in a graph.  The given <tt>Path</tt> argument
   * should initially consist of a single start <tt>Vertex</tt> object.  As
   * a utility method that is used by the <tt>findEulerPath()</tt> method,
   * the <tt>findCycle()</tt> method makes use of the <tt>status</tt> field
   * of the <tt>Edge</tt> class.  Thus, to use this method, all edges of
   * the associated graph should be marked as <tt>UNSEEN</tt>.
   * @param P initially a single-vertex path, the <tt>P</tt> argument will
   *          contain a cycle of the given graph, if a cycle exists.
   * @return <tt>true</tt> if a cycle is successfully found; <tt>false</tt>
   *         otherwise.
   */
  public static final boolean findCycle( Path P )
  {
    // Extend the given Path by attempting to traverse an Edge that
    // is incident with the last Vertex of the given Path ...
    Enumeration e = P.lastVertex().incidentEdges();
    while ( e.hasMoreElements() )
    {
      Edge E = (Edge)e.nextElement();
      if ( E.status == UNSEEN )
      {
        P.add( E );
        E.status = IN_TREE_OR_PATH;
        if ( P.isCycle() || findCycle( P ) ) return true;
        P.backtrack();
        E.status = UNSEEN;
      }
    }

    return false;
  }


  /**
   * Using a simple greedy approach, this method attempts to approximate
   * the longest path between two vertices.
   * @param startVertex the source vertex.
   * @param endVertex the target or goal vertex.
   * @return a <tt>Path</tt> object representing the longest path.
   * @exception IllegalArgumentException if the <tt>Vertex</tt> arguments
   *            are in different graphs, or if the graph is not positively
   *            weighted, or if the <tt>Vertex</tt> arguments refer to the
   *            same vertex.
   * @exception PathDoesNotExistException if this method fails to find a
   *            valid path between the <tt>startVertex</tt> and
   *            <tt>endVertex</tt> vertices.
   */
  public static final Path findLongestPath( Vertex startVertex,
                                            Vertex endVertex )
    throws IllegalArgumentException, PathDoesNotExistException
  {
    GraphBase G = startVertex.graph();
    if ( G == null ) throw
      new IllegalArgumentException( "Vertex arguments must be in a graph." );
    else if ( G != endVertex.graph() ) throw
      new IllegalArgumentException( "Start and end vertices must be in same graph." );
    else if ( ! G.isWeighted() ) throw
      new IllegalArgumentException( "Graph must be a weighted graph." );
    else if ( findMinWeightEdge( G ).weight() <= 0.0 )
      new IllegalArgumentException( "Graph must contain edges with positive weights." );
    else if ( startVertex == endVertex )
      new IllegalArgumentException( "Vertex arguments must refer to different vertices." );

    boolean isDigraph = G.isDigraph();

    Enumeration e = G.vertices();
    while ( e.hasMoreElements() )
    {
      Vertex V = (Vertex)e.nextElement();
      V.status = UNSEEN;
      V.parent = null;
    }

    Path P = new Path( startVertex );
    startVertex.status = IN_TREE_OR_PATH;

    Vertex currentVertex = startVertex;

    while ( currentVertex != endVertex )
    {
      // update parent vertices to show which are reachable ...
      Stack S = new Stack();
      endVertex.parent = currentVertex;
      S.push( endVertex );
      while ( ! S.isEmpty() )
      {
        Vertex V = (Vertex)S.pop();
  
        if ( isDigraph )
          e = V.incomingEdges();
        else
          e = V.incidentEdges();
  
        while ( e.hasMoreElements() )
        {
          Edge E = (Edge)e.nextElement();
          Vertex src;
          if ( isDigraph )
            src = ((DirectedEdge)E).tail();
          else
            src = E.traverseFrom( V );
          if ( src.status == UNSEEN && src.parent != currentVertex )
          {
            src.parent = currentVertex;
            S.push( src );
          }
        }
      }

      e = currentVertex.incidentEdges();
      Edge best_edge, last_edge;
      best_edge = last_edge = null;
      double maxWeight = -10000.0;
      while ( e.hasMoreElements() )
      {
        Edge E = (Edge)e.nextElement();
        if ( E.weight() > maxWeight )
        {
          Vertex dest = E.traverseFrom( currentVertex );
          if ( dest.parent == currentVertex )
          {
            if ( dest == endVertex )
              last_edge = E;
            else
            {
              best_edge = E;
              maxWeight = E.weight();
            }
          }
        }
      }

      Edge newEdge;

      if ( maxWeight == -10000 )
        newEdge = last_edge;
      else
        newEdge = best_edge;

      if ( newEdge == null ) throw
        new PathDoesNotExistException( "Cannot determine longest path." );

      P.add( newEdge );
      currentVertex = newEdge.traverseFrom( currentVertex );
      currentVertex.status = IN_TREE_OR_PATH;
    }

    return P;
  }




  private static final class backtrackNode
  {
    public Edge game; // Game from the current team to the next team ...
    public Vertex sourceVertex;
    public Vertex targetVertex;
    public double tot_len; // Accumulated length from start to here ...

    public backtrackNode previous;  // Node that gave us the current team ...
    public backtrackNode next;  // list reference to node in same stratum ...

    public backtrackNode( backtrackNode N, Edge game, Vertex startVertex )
    {
      this.game = game;
      this.previous = N;

      if ( N == null )
      {
        this.sourceVertex = startVertex;
        this.targetVertex = game.traverseFrom( startVertex );
        this.tot_len = game.weight();
      }
      else
      {
        this.sourceVertex = N.targetVertex;
        this.targetVertex = game.traverseFrom( N.targetVertex );
        this.tot_len = N.tot_len + game.weight();
      }
    }

    public backtrackNode( Edge game, Vertex sourceVertex, Vertex targetVertex,
                          int tot_len, backtrackNode previous,
                          backtrackNode next )
    {
      this.game = game;
      this.sourceVertex = sourceVertex;
      this.targetVertex = targetVertex;
      this.tot_len = tot_len;
      this.previous = previous;
      this.next = next;
    }
  }


  /**
   * Using an algorithm involving <i>stratified greed</i>, this method
   * attempts to approximate the longest path between two vertices.
   * This method typically out-performs the original <tt>findLongestPath()</tt>
   * method in terms of the path produced.
   * @param startVertex the source vertex.
   * @param endVertex the target or goal vertex.
   * @param width the <i>width</i> is defined as the number of candidate
   *              vertices and edges to maintain at each stratum.
   * @return a <tt>Path</tt> object representing the longest path.
   * @exception IllegalArgumentException if the <tt>Vertex</tt> arguments
   *            are in different graphs, or if the graph is not positively
   *            weighted, or if the <tt>Vertex</tt> arguments refer to the
   *            same vertex, or if the <tt>width</tt> argument is less than 1.
   * @exception PathDoesNotExistException if this method fails to find a
   *            valid path between the <tt>startVertex</tt> and
   *            <tt>endVertex</tt> vertices.
   */
  public static final Path findLongestPath2( Vertex startVertex,
                                             Vertex endVertex, int width )
    throws IllegalArgumentException, PathDoesNotExistException
  {
    if ( ! ( startVertex.graph() instanceof Graph ) ) throw
      new IllegalArgumentException( "Must be applied to Graph object only." );

    Graph G = (Graph)startVertex.graph();

    if ( G == null ) throw
      new IllegalArgumentException( "Vertex arguments must be in a graph." );
    else if ( G != endVertex.graph() ) throw
      new IllegalArgumentException( "Start and end vertices must be in same graph." );
    else if ( ! G.isWeighted() ) throw
      new IllegalArgumentException( "Graph must be a weighted graph." );
    else if ( findMinWeightEdge( G ).weight() <= 0.0 )
      new IllegalArgumentException( "Graph must contain edges with positive weights." );
    else if ( startVertex == endVertex )
      new IllegalArgumentException( "Vertex arguments must refer to different vertices." );
    else if ( width < 1 ) throw
      new IllegalArgumentException( "The width argument must be positive." );

    boolean verbose = false;

//21//
    backtrackNode list[] = new backtrackNode[G.numVertices()];
    int size[] = new int[G.numVertices()];

    for ( int i = 0 ; i < G.numVertices() ; i++ )
    {
      list[i] = null;
      size[i] = 0;
    }

//19//
    backtrackNode currentNode = null;
    int m = G.numVertices() - 1;

    do
    {
//28&30//
      Stack S = Algorithms.findBicomponents( G, currentNode, endVertex );

//34//
      while ( ! S.isEmpty() )
      {
        Vertex V = (Vertex)S.pop();
        V.rank += V.min.parent.rank + 1 - G.numVertices();

        if ( verbose )
        {
          System.out.print( "Bicomponent " + V + " (rank " + V.rank + "): " + V.min );
          Enumeration e = G.vertices();
          while ( e.hasMoreElements() )
          {
            Vertex U = (Vertex)e.nextElement();
            if ( U.parent == V )
              System.out.print( ", " + U );
          }
          System.out.println( "." );
        }
      }


//27//
      Enumeration e = null;
      if ( currentNode == null )
        e = startVertex.incidentEdges();
      else
        e = currentNode.targetVertex.incidentEdges();

      while ( e.hasMoreElements() )
      {
        Edge E = (Edge)e.nextElement();

        Vertex U = null;
        if ( currentNode != null )
          U = E.traverseFrom( currentNode.targetVertex );
        else
          U = E.traverseFrom( startVertex );

        boolean foundUnseenEdge = false;
        Enumeration f = U.incidentEdges();
        while ( ! foundUnseenEdge && f.hasMoreElements() )
        {
          if ( ((Edge)f.nextElement()).status == UNSEEN )
            foundUnseenEdge = true;
        }

        if ( ! foundUnseenEdge )
        {
          backtrackNode X = new backtrackNode( currentNode, E, startVertex );

//35//
          // Set h to the number of vertices on paths between U and goal ...
          int h = U.parent.rank;

//22//
          if ( verbose )
            System.out.println( "ADDING VERTEX " + U + " TO LIST[" + h + "]." );

          boolean dropNode = false;
          if ( ( h > 0 && size[h] == width ) || ( h == 0 && size[0] > 0 ) )
          {
            if ( X.tot_len <= list[h].tot_len )
              dropNode = true;
            else
              list[h] = list[h].next;  // Drop one node from the list[h] ...
          }
          else
            size[h]++;

          if ( ! dropNode )
          {
            backtrackNode p, q;
            p = list[h];
            q = null;
            while ( p != null )
            {
              if ( X.tot_len <= p.tot_len )
                break;
              q = p;
              p = p.next;
            }
            X.next = p;
            if ( q != null )
              q.next = X;
            else
              list[h] = X;
          }
        }
      }



//19//
      while ( list[m] == null || size[m] == 0 )
      {
//23//
        backtrackNode r = null, s = list[--m], t;
        while ( s != null )
        {
          t = s.next;
          s.next = r;
          r = s;
          s = t;
        }
        list[m] = r;
      }


      currentNode = list[m];
      list[m] = currentNode.next;  // Remove a node from highest stratum ...

    }
    while ( m > 0 );


    Stack S = new Stack();
    backtrackNode t;

    do
    {
      t = currentNode;
      currentNode = t.previous;
      S.push( t );
    }
    while ( currentNode != null );

    backtrackNode firstNode = (backtrackNode)S.pop();
    Path P = new Path( firstNode.sourceVertex );
    P.add( firstNode.game );

    while ( ! S.isEmpty() )
      P.add( ((backtrackNode)S.pop()).game );


    return P;
  }


  /**
   * The <tt>findMaxWeightEdge()</tt> method performs a linear search through
   * the edges of the given graph to find the edge with the maximum weight.
   * @param G the graph to be examined.
   * @return the <tt>Edge</tt> object with the maximum weight.
   * @exception IllegalArgumentException if the given graph contains no edges
   *                                     or is not a weighted graph.
   */
  public static final Edge findMaxWeightEdge( GraphBase G )
    throws IllegalArgumentException
  {
    if ( G.numEdges() == 0 ) throw
      new IllegalArgumentException( "Graph must contain at least 1 edge." );
    else if ( ! G.isWeighted() ) throw
      new IllegalArgumentException( "Graph must be a weighted graph." );

    Enumeration e = G.edges();
    Edge maximum = (Edge)e.nextElement();
    while ( e.hasMoreElements() )
    {
      Edge E = (Edge)e.nextElement();
      if ( E.weight() < maximum.weight() )
        maximum = E;
    }

    return maximum;
  }


  /**
   * The <tt>findMinWeightEdge()</tt> method performs a linear search through
   * the edges of the given graph to find the edge with the minimum weight.
   * @param G the graph to be examined.
   * @return the <tt>Edge</tt> object with the minimum weight.
   * @exception IllegalArgumentException if the given graph contains no edges
   *                                     or is not a weighted graph.
   */
  public static final Edge findMinWeightEdge( GraphBase G )
    throws IllegalArgumentException
  {
    if ( G.numEdges() == 0 ) throw
      new IllegalArgumentException( "Graph must contain at least 1 edge." );
    else if ( ! G.isWeighted() ) throw
      new IllegalArgumentException( "Graph must be a weighted graph." );

    Enumeration e = G.edges();
    Edge minimum = (Edge)e.nextElement();
    while ( e.hasMoreElements() )
    {
      Edge E = (Edge)e.nextElement();
      if ( E.weight() < minimum.weight() )
        minimum = E;
    }

    return minimum;
  }


  /**
   * The <tt>findShortestPath()</tt> method uses Dijkstra's Shortest Path
   * algorithm as presented in Sara Baase's <B>Computer Algorithms</B> book
   * (see reference <B>[BAAS89]</B>).
   * <p>
   * Currently, graphs with edges of negative or zero weights are not
   * accepted (an <tt>IllegalArgumentException</tt> is thrown).
   * @param startVertex the source vertex.
   * @param endVertex the target or goal vertex.
   * @return a <tt>Path</tt> object representing the shortest path.
   * @exception IllegalArgumentException if the <tt>Vertex</tt> arguments
   *            are in different graphs, or if the graph is not positively
   *            weighted.
   * @exception PathDoesNotExistException if this method fails to find a
   *            valid path between the <tt>startVertex</tt> and
   *            <tt>endVertex</tt> vertices.
   */
  public static final Path findShortestPath( Vertex startVertex,
                                             Vertex endVertex )
    throws IllegalArgumentException, PathDoesNotExistException
  {
    GraphBase G = startVertex.graph();
    if ( G == null ) throw
      new IllegalArgumentException( "Vertex arguments must be in a graph." );
    else if ( G != endVertex.graph() ) throw
      new IllegalArgumentException( "Start and end vertices must be in same graph." );
    else if ( ! G.isWeighted() ) throw
      new IllegalArgumentException( "Graph must be a weighted graph." );
    else if ( findMinWeightEdge( G ).weight() <= 0.0 )
      new IllegalArgumentException( "Graph must contain edges with positive weights." );

    Path P = new Path( startVertex );
    if ( startVertex == endVertex )
      return P;

    startVertex.status = IN_TREE_OR_PATH;
    startVertex.distance = 0.0;
    Table fringeSet = new Table();

    Enumeration e = G.vertices();
    while ( e.hasMoreElements() )
    {
      Vertex V = (Vertex)e.nextElement();
      if ( V != startVertex )
      {
        V.status = UNSEEN;
        V.distance = 0.0;
        V.parent = null;
      }
    }

    Vertex X = startVertex;
    boolean stuck = false;

    while ( X != endVertex && ! stuck )
    {
      // Traverse the adjacency list for x ...
      e = X.incidentEdges();
      while ( e.hasMoreElements() )
      {
        Edge E = (Edge)e.nextElement();
        Vertex Y = E.traverseFrom( X );

        if ( Y.status == FRINGE && X.distance + E.weight() < Y.distance )
        {
          // Replace Y's candidate edge by E ...
          Y.parent = X;
          Y.distance = X.distance + E.weight();
        }

        if ( Y.status == UNSEEN )
        {
          // Y is now in the fringe, and E is a candidate edge ...
          Y.status = FRINGE;
          fringeSet.add( Y );
          Y.parent = X;
          Y.distance = X.distance + E.weight();
        }
      }


      // Choose the next vertex and edge ...
      if ( fringeSet.isEmpty() )  stuck = true;
      else
      {
        // Traverse the fringe set to find a vertex with minimum distance ...
        e = fringeSet.elements();
        Vertex minimumDistV = (Vertex)e.nextElement();
        while ( e.hasMoreElements() )
        {
          Vertex V = (Vertex)e.nextElement();
          if ( V.distance < minimumDistV.distance )
            minimumDistV = V; 
        }

        X = minimumDistV;
        fringeSet.remove( X );
        X.status = IN_TREE_OR_PATH;
      }
    }


    if ( stuck ) throw
      new PathDoesNotExistException();

    // Construct the path by stacking up parent vertices ...
    Stack S = new Stack();
    while ( X != startVertex )
    {
      S.push( X );
      X = X.parent;
    }

    while ( ! S.isEmpty() )
    {
      X = (Vertex)S.pop();
      P.add( X );
    }

    return P;
  }


  /**
   * Returns a <tt>String</tt> that contains all edges of the given
   * <tt>Drawable</tt> object.  The format of the generated string is
   * "v1-v2,v2-v3,v3-v4" and so on.  Note that there are no spaces between
   * the commas and that the edges are represented by the '-' character.
   * Also note that the resulting <tt>String</tt> represents directed edges,
   * therefore undirected edges are represented as pairs of edges:
   * "v1-v2,v2-v1".
   * <p>
   * Also note that the Graph Draw applet does not support edges that are
   * self-loops.  Using the notation "v5-v5" does not indicate a loop;
   * instead, if a vertex does not contain any edges, including such a
   * <tt>String</tt> will produce a lone vertex in the Graph Draw applet.
   * @param G the <tt>Drawable</tt> graph or other graph-related object.
   * @return a <tt>String</tt> that contains all edges of the given
   *         <tt>Drawable</tt> object.
   */
  public static final String toGraphDraw( Drawable G )
  {
    String s = "";
    boolean encounteredEdge = false;
    Enumeration e = G.edges();
    while ( e.hasMoreElements() )
    {
      encounteredEdge = true;
      Edge E = (Edge)e.nextElement();
      s += E.startVertex() + "-" + E.endVertex();
      if ( ! ( E instanceof DirectedEdge ) )
        s += "," + E.endVertex() + "-" + E.startVertex();
      if ( e.hasMoreElements() )
        s += ",";
    }

    e = G.vertices();
    while ( e.hasMoreElements() )
    {
      Vertex V = (Vertex)e.nextElement();
      if ( V.numIncidentEdges() == 0 )
      {
        if ( encounteredEdge ) s += ",";
        else encounteredEdge = true;
        s += V + "-" + V;
      }
    }

    return s;
  }


  /**
   * Creates an <tt>HTML</tt> file that contains the edge-representation of
   * the given <tt>Drawable</tt> object.  The <tt>HTML</tt> file, when loaded
   * into a browser, loads the Graph Draw applet and presents the edges of the
   * given <tt>Drawable</tt> object.
   * @param G the <tt>Drawable</tt> graph or other graph-related object.
   * @param filename the name of the <tt>HTML</tt> file to be created.
   */
  public static final void toGraphDraw( Drawable G, String filename )
  {
    try
    {
      FileOutputStream ostream = new FileOutputStream( filename );
      PrintWriter file = new PrintWriter( ostream );
      file.println( "<BASE HREF=\"http://www.cs.rpi.edu/projects/pb/graphdraw/\">" );
      file.println( "<HTML>" );
      file.println( "<HEAD>" );
      file.println( "<TITLE>Graph Drawing Applet</TITLE>" );
      file.println( "</HEAD>" );
      file.println( "<BODY>" );
      file.println( "<APPLET code=\"GraphApplet.class\" width=50 height=30>" );
      file.println( "<PARAM name=\"edges\" value=\"" + toGraphDraw(G) + "\">" );
      file.println( "<PARAM name=\"name\" value=\"" + G.name() + "\">" );
      file.println( "</APPLET>" );
      file.println( "</BODY>" );
      file.println( "</HTML>" );
      file.close();
    }
    catch( IOException e )
    {
      System.err.println( e );
    }
  }
}