
package dataStructures;

import java.util.*;
import exceptions.*;
import applications.*;
import utilities.*;

public abstract class Graph
{
   // ADT methods
   public abstract int vertices();
   public abstract int edges();
   public abstract boolean existsEdge(int i, int j);
   public abstract void putEdge(Object theEdge);
   public abstract void removeEdge(int i, int j);
   public abstract int degree(int i);
   public abstract int inDegree(int i);
   public abstract int outDegree(int i);

   // create an enumerator for vertex i
   public abstract Enumeration elements(int i);

   // class data members
   private static int [] reach;  // used to label vertices
   private static int label;     // the label to use
   private static int destination;
   private static int [] path;   // used to store a path
   private static int length;    // path length

   // implementation independent methods
   /** breadth-first search
     * reach[i] is set to label for all vertices reachable
     * from vertex v */
   public void bfs(int v, int [] reach, int label)
   {
      ArrayQueue q = new ArrayQueue(10);
      reach[v] = label;
      q.put(new Integer(v));
      while (!q.isEmpty())
      {
         // remove a labeled vertex from the queue
         int w = ((Integer) q.remove()).intValue();

         // mark all unreached vertices adjacent from w
         Enumeration ew = elements(w);
         while (ew.hasMoreElements())
         {// visit an adjacent vertex of w
            int u = ((EdgeNode) ew.nextElement()).vertex; 
            if (reach[u] == 0)
            {// u is an unreached vertex
               q.put(new Integer(u));
               reach[u] = label; // mark reached
            }
         }
      }
   }
   
   /** depth-first search
     * reach[i] is set to label for all vertices reachable
     * from vertex v */
   public void dfs(int v, int [] reach, int label)
   {
      Graph.reach = reach;
      Graph.label = label;
      rDfs(v);
   }
   
   /** recursive dfs method */
   private void rDfs(int v)
   {
      reach[v] = label;
      Enumeration ev = elements(v);
      while (ev.hasMoreElements())
      {// visit an adjacent vertex of v
         int u = ((EdgeNode) ev.nextElement()).vertex; 
         if (reach[u] == 0)  // u is an unreached vertex
            rDfs(u);
      }
   }

   /** find a path from s to d
     * @return the path in an array using positions 0 on up
     * @return null if there is no path */
   public int [] findPath(int s, int d)
   {
      // initialize for recursive path finder
      int n = vertices();
      path = new int [n];
      path[0] = s;   // first vertex is always s
      length = 0;    // current path length
      destination = d;
      reach = new int [n + 1];
      for (int i = 1; i <= n; i++)
         reach[i] = 0;
      
      // search for path
      if (s == d || rFindPath(s))
      {// a path was found, trim array to path size
         int [] newPath = new int [length + 1];
         // copy from old space to new space
         System.arraycopy(path, 0, newPath, 0, length + 1);
         return newPath;
      }
      else
         return null;
   }
   
   /** real path finder, performs a depth-first search
     * @param s source vertex not equal to  destination
     * @return true iff a path to destination is found */
   private boolean rFindPath(int s)
   {
      reach[s] = 1;
      Enumeration es = elements(s);
      while (es.hasMoreElements())
      {// visit an adjacent vertex of s
         int u = ((EdgeNode) es.nextElement()).vertex; 
         if (reach[u] == 0)   // u is an unreached vertex
         {// move to vertex u
            length++;
            path[length] = u; // add u to path
            if (u == destination) return true;
            if (rFindPath(u))
               return true;
            // no path from u to destination
            length--;         // remove u from path
         }
      }
      return false;
   }

   /** verify that the graph is an undirected graph
     * @exception UndefinedMethodException if graph is directed  */
   public void verifyUndirected(String theMethodName)
   {
      Class c = getClass();   // class of this
      if (c == AdjacencyGraph.class ||
          c == AdjacencyWGraph.class ||
          c == LinkedGraph.class ||
          c == LinkedWGraph.class)
         return;

      // not an undirected graph
      throw new UndefinedMethodException
         ("Graph." + theMethodName + " is for undirected graphs only");
   }

   /** verify that the graph is a directed graph
     * @exception UndefinedMethodException if graph is undirected  */
   public void verifyDirected(String theMethodName)
   {
      Class c = getClass();   // class of this
      if (c == AdjacencyDigraph.class ||
          c == AdjacencyWDigraph.class ||
          c == LinkedDigraph.class ||
          c == LinkedWDigraph.class)
         return;

      // not a digraph
      throw new UndefinedMethodException
         ("Graph." + theMethodName + " is for directed graphs only");
   }

   /** verify that the graph is a weighted undirected graph
     * @exception UndefinedMethodException if graph is not
     * weighted and undirected  */
   public void verifyWeightedUndirected(String theMethodName)
   {
      Class c = getClass();   // class of this
      if (c == AdjacencyWGraph.class ||
          c == LinkedWGraph.class)
         return;

      // not weighted and undirected
      throw new UndefinedMethodException
         ("Graph." + theMethodName + " is for weighted undirected graphs only");
   }

   /** verify that the graph is a weighted directed graph
     * @exception UndefinedMethodException if graph is not
     * weighted and directed  */
   public void verifyWeightedDirected(String theMethodName)
   {
      Class c = getClass();   // class of this
      if (c == AdjacencyWDigraph.class ||
          c == LinkedWDigraph.class)
         return;

      // not weighted and undirected
      throw new UndefinedMethodException
         ("Graph." + theMethodName + " is for weighted directed graphs only");
   }

   /** verify that the graph is a weighted graph
     * @exception UndefinedMethodException if graph is not weighted */
   public void verifyWeighted(String theMethodName)
   {
      Class c = getClass();   // class of this
      if (c == AdjacencyWDigraph.class ||
          c == AdjacencyWGraph.class ||
          c == LinkedWDigraph.class ||
          c == LinkedWGraph.class)
         return;

      // not weighted
      throw new UndefinedMethodException
         ("Graph." + theMethodName + " is for weighted graphs only");
   }

   /** verify that the graph is a weighted graph
     * @exception UndefinedMethodException if graph is not weighted */
   public void verifyWeighted(String theMethodName)
   {
      Class c = getClass();   // class of this
      if (c == AdjacencyWGraph.class ||
          c == LinkedWGraph.class ||
          c == AdjacencyWDigraph.class ||
          c == LinkedWDigraph.class)
         return;

      // not weighted
      throw new UndefinedMethodException
         ("Graph." + theMethodName + " is for weighted graphs only");
   }

   /** @return true iff graph is connected */
   public boolean connected()
   {
      // make sure this is an undirected graph
      verifyUndirected("connected");

      int n = vertices();
   
      // set all vertices as not reached
      reach = new int [n + 1];
      for (int i = 1; i <= n; i++)
         reach[i] = 0;
      
      // mark vertices reachable from vertex 1
      dfs(1, reach, 1);
      
      // check if all vertices marked
      for (int i = 1; i <= n; i++)
         if (reach[i] == 0)
            return false;
      return true;
   }

   /** label the components of an undirected graph
    *  @return the number of components
    *  set c[i] to be the component number of vertex i */
   public int labelComponents(int [] c)
   {
      // make sure this is an undirected graph
      verifyUndirected("labelComponents");

      int n = vertices();
   
      // assign all vertices to no component
      for (int i = 1; i <= n; i++)
         c[i] = 0;
   
      label = 0;  // ID of last component
      // identify components
      for (int i = 1; i <= n; i++)
         if (c[i] == 0)  // vertex i is unreached
         {// vertex i is in a new component
            label++;
            bfs(i, c, label); // mark new component
         }
   
      return label;
   }

   /** @return false iff the digraph has no topological order
     * @param s[0:n-1] is set to a topological order when
     * such an order exists */
   public boolean topologicalOrder(int [] s)
   {
      // make sure this is a digraph
      verifyDirected("topologicalOrder");

      int n = vertices();
      
      // compute in-degrees, default initial values are 0
      int [] inDegree = new int [n + 1];
      for (int i = 1; i <= n; i++)
      {// edges out of vertex i
         Enumeration ei = elements(i);
         while (ei.hasMoreElements())
         {// visit an adjacent vertex of i
            int u = ((EdgeNode) ei.nextElement()).vertex; 
            inDegree[u]++;
         }
      }
      
      // stack vertices with zero in-degree
      ArrayStack stack = new ArrayStack(10);
      for (int i = 1; i <= n; i++)
         if (inDegree[i] == 0)
            stack.push(new Integer(i));
      
      // generate topological order
      int i = 0;  // cursor for array s
      while (!stack.empty())
      {// select from stack
         int w = ((Integer) stack.pop()).intValue(); // next vertex
         s[i++] = w;
         // update in-degrees
         Enumeration ew = elements(w);
         while (ew.hasMoreElements())
         {// visit an adjacent vertex of w
            int u = ((EdgeNode) ew.nextElement()).vertex; 
            inDegree[u]--;
            if (inDegree[u] == 0)
               stack.push(new Integer(u));
         }
      }
      return (i == n);
   }

   /** bipartite cover support class, data members, and methods */
   private static class NodeType
   {
      // data members
      int left,  // pointer to previous node
          right; // pointer to next node
   }
   
   // class data member of Graph
   static int [] bin;   // pointer to first node in bin
   static NodeType [] node;

   /** create b empty bins and n nodes */
   private static void createBins(int b, int n)
   {
      bin = new int [b + 1];
      node = new NodeType [n + 1];
      for (int i = 1; i <= n; i++)
         node[i] = new NodeType();
   }
   
   /** insert v into bin b unless b is zero */
   private static void insertBins(int b, int v)
   {
      if (b == 0)
         return;   // do not insert in bin 0

      node[v].left = b; // add at left end of bin b
      if (bin[b] != 0)  // bin b is not empty
         node[bin[b]].left = v;
      node[v].right = bin[b];
      bin[b] = v;
   }
   
   /** move vertex v from its current bin to bin toBin
     * @param bMax rightmost nonempty bin */
   private static void moveBins(int bMax, int toBin, int v)
   {
      // nodes to the left and right of v
      int l = node[v].left;
      int r = node[v].right;
   
      // delete v from current bin
      if (r != 0)  // v has a node to its left
         node[r].left = node[v].left;
      if (l > bMax || bin[l] != v) // not left-most one
         node[l].right = r;
      else  // left-most in bin l
         bin[l] = r;
   
      // add to bin toBin
      insertBins(toBin, v);
   }
   
   /** @return -1 if the bipartite graph has no cover
     * @return cover size if there is a cover
     * @param l is bipartite labeling, l[i] = 1 iff i is in A
     * @param c c[i], i >= 0 is set to the cover (if there is one) */
   public int bipartiteCover(int [] l, int [] c)
   {
      int n = vertices();
   
      // create structures
      int sizeOfA = 0;
      for (int i = 1; i <= n; i++) // find size of set A
         if (l[i] == 1) sizeOfA++;
      int sizeOfB = n - sizeOfA;
      createBins(sizeOfB, n);
      int [] newCov = new int [n + 1];
         // vertex i covers newCov[i] uncovered vertices of B
      boolean [] change = new boolean [n + 1];
         // change[i] is true iff newCov[i] has changed
      boolean [] cov = new boolean [n + 1];
         // cov[i] is true iff vertex i is covered
      ArrayStack s = new ArrayStack(10);
      
      // initialize
      for (int i = 1; i <= n; i++)
         if (l[i] == 1)
         {// i is in A
            newCov[i] = degree(i); // i covers this many
            insertBins(newCov[i], i);
         }
      
      // construct cover
      int covered = 0,       // # of covered vertices
          maxBin = sizeOfB;  // max bin that may be
                             // nonempty
      int m = 0;             // cursor for c
      while (maxBin > 0)     // search all bins
         if (bin[maxBin] != 0)  // bin maxBin is not empty
         {
            int v = bin[maxBin]; // first vertex
            c[m++] = v;          // add v to cover
            // label newly covered vertices
            Enumeration ev = elements(v);
            while (ev.hasMoreElements())
            {
               int j = ((EdgeNode) ev.nextElement()).vertex; 
               if (!cov[j]) // j not covered yet
               {
                  cov[j] = true;
                  covered++;
                  // update New
                  Enumeration ej = elements(j);
                  while (ej.hasMoreElements())
                  {
                     int k = ((EdgeNode) ej.nextElement()).vertex; 
                     newCov[k]--;     // j does not count
                     if (!change[k])
                     {
                        s.push(new Integer(k));  // stack once only
                        change[k] = true;
                     }
                  }
               }   
            }
            // update bins
            while (!s.empty())
            {
               int k = ((Integer) s.pop()).intValue();
               change[k] = false;
               moveBins(sizeOfB, newCov[k], k);
            }
         }
         else maxBin--; // go to next bin
      
      return (covered == sizeOfB) ? m : -1;
   }

   /** find a min cost spanning tree using Kruskal's method
     * @return false iff the weighted undirected graph is not connected
     * @param t[0:n-2] has the min cost tree edges when done */
   public boolean kruskal(WeightedEdge [] t)
   {
      verifyWeightedUndirected("kruskal");

      int n = vertices();
      int e = edges();
      // set up array of graph edges
      WeightedEdge [] edge = new WeightedEdge [e + 1];
      int k = 0;        // cursor for edge[]
      for (int i = 1; i <= n; i++)
      {// get all edges incident to i
         Enumeration ei = elements(i);
         while (ei.hasMoreElements())
         {
            WeightedEdgeNode w = (WeightedEdgeNode) ei.nextElement();
            if (i < w.vertex)  // add w to edge array
               edge[++k] = new WeightedEdge(i, w.vertex, w.weight);
         }
      }
      // put edges in min heap
      MinHeap minHeap = new MinHeap(1);
      minHeap.initialize(edge, e);
      
      FastUnionFind uf = new FastUnionFind(n); // union/find structure
      
      // extract edges in cost order and select/reject
      k = 0;  // use as cursor for t now
      while (e > 0  && k < n - 1)
      {// spanning tree not complete & edges remain
         WeightedEdge x = (WeightedEdge) minHeap.removeMin();
         e--;
         int a = uf.find(x.vertex1);
         int b = uf.find(x.vertex2);
         if (a != b)
         {// select edge
            t[k++] = x;
            uf.union(a,b);
         }
      }
      return (k == n - 1);
   }

   /** @return edges defining breadth first spanning tree rooted
     * at vertex i in an array [0:n-2]
     * @return null iff there is no depth first spanning tree
     * @exception UndefinedMethodException if graph is directed  */
   public Edge[] bfSpanningTree(int i)
   {
      // make sure this is an undirected graph
      verifyUndirected("bfSpanningTree");

      int n = vertices();

      // perform a breadth-first search from vertex i
      // saving edges used to reach new vertices
   
      // define the array reach, default initial values are 0
      reach = new int [n + 1];
   
      // initialize class data members
      Edge [] theTree = new Edge [n - 1];      // edges in spanning tree
      int edges = 0;                           // number of edges so far
      label = 1;                               // label for reached vertices
   
      // do the breadth first search starting at vertex i
      ArrayQueue q = new ArrayQueue(10);
      reach[i] = label;
      q.put(new Integer(i));
      while (!q.isEmpty())
      {
         // remove a labeled vertex from the queue
         int w = ((Integer) q.remove()).intValue();

         // mark all unreached vertices adjacent from w
         Enumeration ew = elements(w);
         while (ew.hasMoreElements())
         {// visit an adjacent vertex of w
            int u = ((EdgeNode) ew.nextElement()).vertex; 
            if (reach[u] == 0)
            {// u is an unreached vertex
               // add edge (w, u) to spanning tree
               theTree[edges++] = new Edge(w, u);
               q.put(new Integer(u));
               reach[u] = label; // mark reached
            }
         }
      }
   
      // spanning tree found only if edges = n - 1
      if (edges == n - 1)
         return theTree;
      else
         return null;
   }

   // class data members of Graph
   static Edge [] theTree;      // spanning tree edges
   static int edges;            // number of edges in theTree so far

   /** @return edges defining depth first spanning tree rooted
     * at vertex i in an array [0:n-2]
     * @return null iff there is no depth first spanning tree
     * @exception UndefinedMethodException if graph is directed  */
   public Edge[] dfSpanningTree(int i)
   {
      // make sure this is an undirected graph
      verifyUndirected("dfSpanningTree");

      int n = vertices();

      // perform a depth-first search from vertex i
      // saving edges used to reach new vertices
   
      // define the array reach, default initial values are 0
      reach = new int [n + 1];
   
      // initialize class data members
      theTree = new Edge [n - 1];      // edges in spanning tree
      edges = 0;                       // number of edges so far
      label = 1;                       // label for reached vertices
   
      rdfSpanningTree(i); // do the dfs
   
      // spanning tree found only if edges = n - 1
      if (edges == n - 1)
         return theTree;
      else
         return null;
   }
   
   /** do a depth first search from vertex v, put edges used
     * into the array theTree */
   void rdfSpanningTree(int v)
   {
      reach[v] = label;
      Enumeration ev = elements(v);
      while (ev.hasMoreElements())
      {// visit an adjacent vertex of v
         int u = ((EdgeNode) ev.nextElement()).vertex; 
         if (reach[u] == 0)  // u is an unreached vertex
         {
             // add edge (v, u) to spanning tree
             theTree[edges++] = new Edge(v, u);

             rdfSpanningTree(u);
         }  
      }
   }

   /** @return true iff the undirected graph has a cycle */
   public boolean cycle()
   {
      // make sure this is an undirected graph
      verifyUndirected("cycle");

      int n = vertices();
   
      // create the array reach, default initial values are 0
      reach = new int [n + 1];
   
      // examine each component
      for (int i = 1; i <= n; i++)
         if (reach[i] == 0)  // vertex i is unreached
            // vertex i is in a new component
            if (cycle(i, 0))
               return true;

      // no component has a cycle
      return false;
   }

   /** recursive depth first search for a cycle, pv is the parent of v
     * @return true iff a cycle is found */
   boolean cycle(int v, int pv)
   {// dfs from vertex v
      reach[v] = 1;
      Enumeration ev = elements(v);
      while (ev.hasMoreElements())
      {// visit an adjacent vertex of v
         int u = ((EdgeNode) ev.nextElement()).vertex; 
         if (reach[u] == 0)  // u is an unreached vertex
         {
            if (cycle(u,v))  // dfs
               return true;
         }
         else
            // vertex u was reached before
            if (u != pv) // (u,v) is not in the
                         // spanning tree for this component
                         // so, the component has a cycle
               return true;
      }
   
      return false;
   }

   /** Label the vertices such that every edge connects
     * a vertex with label 1 to one with label 2
     * @return null iff there is no such labeling
     * @return an array of labels when the graph has such a labeling */
   public int [] bipartite()
   {
      // make sure this is an undirected graph
      verifyUndirected("bipartite");

      int n = vertices();

      // create label array, default initial values are 0
      int [] label = new int [n + 1];
   
      // do a breadth first search in each component
      ArrayQueue q = new ArrayQueue(10);
      for (int v = 1; v <= n; v++)
         if (label[v] == 0)
         {// new component, label the vertices in this component
            label[v] = 1;
            q.put(new Integer(v));
            while (!q.isEmpty())
            {    
               // remove a labeled vertex from the queue
               int w = ((Integer) q.remove()).intValue();
      
               // mark all unreached vertices adjacent from w
               Enumeration ew = elements(w);
               while (ew.hasMoreElements())
               {// visit an adjacent vertex of w
                  int u = ((EdgeNode) ew.nextElement()).vertex; 
                  if (label[u] == 0)
                  {// u is an unreached vertex
                     q.put(new Integer(u));
                     label[u] = 3 - label[w]; // assign u the other label
                  }
                  else
                     // u already labeled
                     if (label[u] == label[w])
                        // both ends of edge assigned same label
                        return null;
               }
            }     
         }   

      // labeling successful
      return label;
   }  

   /** @return the transitive closure matrix tc of the undirected graph */
   public int [][] undirectedTC()
   {
      // make sure this is an undirected graph
      verifyUndirected("transitive closure");

      int n = vertices();
      
      // create transitive closure array, default initial values are 0
      int [][] tc = new int [n + 1][n + 1];

      // first label each vertex according to component
      int [] c = new int [n + 1];  // label array
      labelComponents(c);
   
      // now compute tc
   
      // for i != j, tc[i][j] is 1 iff i and j are in the same component
      for (int i = 1; i <= n; i++)
         for (int j = i + 1; j <= n; j++)
            if (c[i] == c[j])
               tc[i][j] = tc[j][i] = 1;
   
      // tc[i][i] is 1 iff the degree of i is nonzero
      for (int i = 1; i <= n; i++)
      {
         Enumeration ei = elements(i);
         if (ei.hasMoreElements())
            tc[i][i] = 1;
      }

      return tc;
   }

   // class data members of Graph
   static int [][] tc;       // transitive closure array
   static int theRow;        // row of tc that is being computed

   /** @return the transitive closure of a directed graph */
   public int [][] directedTC()
   {
      int n = vertices();
      reach = new int [n + 1];
   
      // create transitive closure array, default initial values are 0
      tc = new int [n + 1][n + 1];
   
      // compute tc row by row using depth first search
      for (theRow = 1; theRow <= n; theRow++)
      {
         // initialize reach
         for (int j = 1; j <= n; j++)
            reach[j] = 0;

         // set row i of tc
         tcRow(theRow);
      }
      return tc;
   }
   
   /** set row theRow of transitive closure array tc
     * @param v is vertex for depth first search */
   void tcRow(int v)
   {
      reach[v] = 1;
      Enumeration ev = elements(v);
      while (ev.hasMoreElements())
      {// visit an adjacent vertex of v
         int u = ((EdgeNode) ev.nextElement()).vertex; 
         if (reach[u] == 0)  
         {// u is an unreached vertex
            tc[theRow][u] = 1;
            tcRow(u);
         }
         else
            // u is reachable from theRow, need next line to catch tc[u][u]
            tc[theRow][u] = 1;
      }
   }

   /** find an independent set using the greedy method
     * @return an array v[0:v.length-1] that contains the
     * independent set vertices */
   public int [] maxIndependentSet()
   {
      // make sure this is an undirected graph
      verifyUndirected("maxIndependentSet");

      int n = vertices();
      int [] c = new int [n + 1];  // candidate array
                                   // i is a candidate iff c[i] = 2
      // count[i] is the number of candidate vertices i is not adjacent to
      int [] count = new int [n + 1];
   
      // initialize candidate array
      for (int i = 1; i <= n; i++)
         c[i] = 2;
   
      // find vertex with min degree
      int minDegree = degree(1);
      int minV = 1;
      for (int i = 2; i <= n; i++)
      {
        int m = degree(i);
        if (m < minDegree)
        {
           minDegree = m;
           minV = i;
        }
     }
   
      // minV is first vertex in independent set
      c[minV] = 1;
      int sizeOfIndependentSet = 1;
   
      // vertices adjacent to minV are no longer candidates
      Enumeration ev = elements(minV);
      while (ev.hasMoreElements())
         c[((EdgeNode) ev.nextElement()).vertex] = 0;
   
      // create candidate chain
      Chain candV = new Chain();
      for (int i = 1; i <= n; i++)
         if (c[i] == 2)
            candV.insertElementAt(new Integer(i), 0);
   
      // find next vertex to add to independent set 
      // this is a candidate vertex which is adjacent to
      // to the fewest other candidate vertices
      minDegree = n + 1;
      // define a chain enumerator to go down chain of candidates
      Enumeration ec = candV.elements();
      while (ec.hasMoreElements())
      {
         int u = ((Integer) ec.nextElement()).intValue();
         // vertex u is a candidate
         // find number of other candidates adjacent to it
         Enumeration eu = elements(u);
         count[u] = 0;
         while (eu.hasMoreElements())
         {
            int v = ((EdgeNode) eu.nextElement()).vertex;
            // if v is a candidate, increment count[u]
            if (c[v] == 2)
               count[u]++;
         }
   
         // is this better vertex to add next?
         if (count[u] < minDegree)
         {// yes it is
            minDegree = count[u];
            minV = u;
         }
      }
   
      // add additional vertices to independent set and
      // create a chain of eliminated candidates
      Chain elimV = new Chain();
      while (minDegree < n + 1)
      {// minV will be added to independent set and
       // adjacent candidate vertices will be eliminated
   
         // label eliminated candidates
         ev = elements(minV);
         while (ev.hasMoreElements())
         {
            int v = ((EdgeNode) ev.nextElement()).vertex;
            // v is to be eliminated, but first
            // make sure it was a candidate
            if (c[v] == 2)
            {// it was a candidate
               c[v] = 0;
               elimV.insertElementAt(new Integer(v), 0);
            }
         }
   
         // add minV to independent set
         c[minV] = 1;
         sizeOfIndependentSet++;
   
         // now set up chain of new candidates
         Chain newV = new Chain();
         ec = candV.elements();
         while (ec.hasMoreElements())
         {
            int u = ((Integer) ec.nextElement()).intValue();
            if (c[u] == 2)
              // u remains a candidate
              newV.insertElementAt(new Integer(u), 0);
         }
         candV = newV;
   
         // update count to account for eliminated
         // candidates and selection of minV
         Enumeration ee = elimV.elements();
         while (ee.hasMoreElements())
         {
            int u = ((Integer) ee.nextElement()).intValue();
            // u has been eliminated
            // reduce count of adjacent candidates
            Enumeration eu = elements(u);
            while (eu.hasMoreElements())
               // easier to reduce everyone's count
               count[((EdgeNode) eu.nextElement()).vertex]--;
         }
   
         // update minV
         minDegree = n + 1;
         ec = candV.elements();
         while (ec.hasMoreElements())
         {
            int u = ((Integer) ec.nextElement()).intValue();
            if (count[u] < minDegree)
            {
               minDegree = count[u];
               minV = u;
            }
         }
      }
         
      // put independent vertices into an array
      int [] indepSet = new int [sizeOfIndependentSet];
      int s = -1;
      for (int i = 1; i <= n; i++)
         if (c[i] == 1)
            indepSet[++s] = i;
          
      return indepSet;
   }

   /** find a min cost spanning tree using Prim's method
     * @return false iff the weighted undirected graph is not connected
     * @param t[0:n-2] has the min cost tree edges when done */
   public boolean prim(WeightedEdge [] t)
   {
      verifyWeightedUndirected("prim");

      int n = vertices();
      boolean [] selected = new boolean [n + 1];
              // selected[i] is true iff vertex i already in spanning tree
      WeightedEdgeNode [] nearNbr = new WeightedEdgeNode [n + 1];
              // nearNbr[i].vertex is nearest spanning tree neighbor of vertex i
              // nearNbr[i].weight is distance to this nearest neighbor
   
      // start with vertex 1 in the spanning tree
      // initialize nearNbr and list of unselected adjacent vertices
      selected[1] = true;
      GraphChain l = new GraphChain(); // list of unselected adjacent vertices
      Enumeration ev = elements(1);  // vertices adjacent to vertex 1
      while (ev.hasMoreElements())
      {
         WeightedEdgeNode we = (WeightedEdgeNode) ev.nextElement();
         nearNbr[we.vertex] = new WeightedEdgeNode(1, we.weight);
         l.insertElementAt(new EdgeNode(we.vertex), 0);
      }
   
      // include remaining vertices into the spanning tree using Prim's method
      int i = 0;  // number of edges in spanning tree
      while (!l.isEmpty())
      {// there is an adjacent unselected vertex
         // find adjacent unselected vertex v with least edge cost
         Enumeration el = l.elements();
         int v = ((EdgeNode) el.nextElement()).vertex;
         while (el.hasMoreElements())
         {
            int w = ((EdgeNode) el.nextElement()).vertex;
            if (nearNbr[w].weight.lessThan(nearNbr[v].weight))
               v = w;
         }

         // select vertex v and associated edge
         t[i++] = new WeightedEdge(v, nearNbr[v].vertex, nearNbr[v].weight);
         selected[v] = true;
   
         // delete v from l and update nearNbr
         l.removeElement(v);

         // update distances
         ev = elements(v);
         while (ev.hasMoreElements())
         { 
            WeightedEdgeNode w = (WeightedEdgeNode) ev.nextElement();
            if (!selected[w.vertex])
            {
               if (nearNbr[w.vertex] == null)
               {// w.vertex not in min heap
                  nearNbr[w.vertex] = new WeightedEdgeNode(v, w.weight);
                  l.insertElementAt(new EdgeNode(w.vertex), 0);
               }
               else
                  // w.vertex is in l
                  if (nearNbr[w.vertex].weight.greaterThan(w.weight))
                  {// found a closer neighbor
                     nearNbr[w.vertex].weight = w.weight;
                     nearNbr[w.vertex].vertex = v;
                  }
            }
         } 
      }   

      // see if spanning tree was found
      if (i == n - 1)
         return true;
      else
         return false;
   }
     
   /** find a clique using the greedy method
     * @return the clique size and put the clique
     * vertices in cliqueVertices[0:size-1] */
   public int maxClique(int [] cliqueVertices)
   {
      // make sure this is an undirected graph
      verifyUndirected("maxClique");

      int n = vertices();
      if (n == 0)
         // graph has no vertices
         return 0;
   
      // c is an array of candidate clique vertices
      // i is candidate iff c[i] = 2, default initial values are zero
      int [] c = new int [n + 1];
   
      // count[i] is number of candidate vertices i is adjacent to
      int [] count = new int [n + 1];
   
      // find vertex with max degree
      int maxDegree = degree(1);
      int maxV = 1;
      for (int i = 2; i <= n; i++)
      {
        int m = degree(i);
        if (m > maxDegree)
        {
           maxDegree = m;
           maxV = i;
        }
     }
   
      // maxV is first vertex in clique
      c[maxV] = 1;
   
      // define a chain for candidate vertices
      Chain candidateChain = new Chain();
   
      // remaining candidates for clique are the vertices adjacent to maxV
      // create a chain of these candidates
      Enumeration eMaxV = elements(maxV);
      while (eMaxV.hasMoreElements())
      {
         int v = ((EdgeNode) eMaxV.nextElement()).vertex;
         c[v] = 2;
         candidateChain.insertElementAt(new Integer(v), 0);
      }
   
   
      // candidateChain is now a chain of candidates
      // find next vertex to add to clique 
      // this is a candidate vertex which is adjacent to
      // to the most other candidate vertices
      maxDegree = -1;
   
      // define a chain enumerator to go down chain of candidates
      Enumeration eCandidateChain = candidateChain.elements();
      while (eCandidateChain.hasMoreElements())
      {
         // get a candidate vertex u
         int u = ((Integer) eCandidateChain.nextElement()).intValue();
   
         // find number of other candidates adjacent to vertex u
         Enumeration eu = elements(u);
         count[u] = 0;
         while (eu.hasMoreElements())
         {// examine an adjacent vertex v
            int v = ((EdgeNode) eu.nextElement()).vertex;
            
            // if v is a candidate, increment count[u]
            if (c[v] == 2)
               count[u]++;
         }
   
         // is vertex u a better vertex to add next?
         if (count[u] > maxDegree)
         {// yes it is
            maxDegree = count[u];
            maxV = u;
         }
      }
   
      // add additional vertices to clique
      while (maxDegree > -1)
      {// MaxV will be added to clique and nonadjacent
       // candidate vertices will be eliminated
   
         // find candidates that remain after maxV selected
         // these are current candidates that are adjacent to maxV
         Chain newChain = new Chain();
         eMaxV = elements(maxV);
         while (eMaxV.hasMoreElements())
         {
            int v = ((EdgeNode) eMaxV.nextElement()).vertex;
            if (c[v] == 2)
               // v remains a candidate for later addition to the clique
               newChain.insertElementAt(new Integer(v), 0);
         }
   
         // update c to reflect remaining candidates
         // first invalidate old candidates
         eCandidateChain = candidateChain.elements();
         while (eCandidateChain.hasMoreElements())
            c[((Integer) eCandidateChain.nextElement()).intValue()] = 0;
   
         // add maxV to clique
         c[maxV] = 1;
   
         // now set up new candidates
         Enumeration eNewChain = newChain.elements();
         while (eNewChain.hasMoreElements())
            c[((Integer) eNewChain.nextElement()).intValue()] = 2;
   
         // update count to account for eliminated
         // candidates and selection of maxV
         eCandidateChain = candidateChain.elements();
         while (eCandidateChain.hasMoreElements())
         {
            int u = ((Integer) eCandidateChain.nextElement()).intValue();
   
            // is u still a candidate?
            if (c[u] != 2)
            {// u is no longer a candidate
              // reduce count of its adjacent candidates
               Enumeration eu = elements(u);
               while (eu.hasMoreElements())
                  // easier to reduce everyone's count
                  count[((EdgeNode) eu.nextElement()).vertex]--;
            }   
         }
   
         // update maxV
         maxDegree = -1;
         eNewChain = newChain.elements();
         while (eNewChain.hasMoreElements())
         {
            int u = ((Integer) eNewChain.nextElement()).intValue();
            if (count[u] > maxDegree)
            {
               maxDegree = count[u];
               maxV = u;
            }
         }
   
         candidateChain = newChain;
      }
         
      // put clique vertices into cliqueVertices[]
      int s = -1;  // last occupied spot of cliqueVertices[]
      for (int i = 1; i <= n; i++)
         if (c[i] == 1)
            cliqueVertices[++s] = i;
   
      return s + 1;
   }

   /** @return length of longest path
     * @param zero is the additive zero for edge weights
     * set l[i] to be length of longest path from vertex i
     * set kay[i] to be next vertex on longest path from vertex i */
   Operable longestPath(Operable [] l, int [] kay, Operable zero)
   {
      int n = vertices();
      Operable maxLength = zero;  // length of longest path
   
      for (int i = n; i > 0; i--)
      {// compute l[i] and kay[i]
         l[i] = zero;
         kay[i] = 0;
         Enumeration ei = elements(i);
         while (ei.hasMoreElements())
         {// there is an adjacent vertex
            WeightedEdgeNode w = (WeightedEdgeNode) ei.nextElement();
            if (w.vertex <= i)
               // improper digraph or vertex numbering
               // w.vertex should be > i
               throw new IllegalArgumentException("Graph.longestPath: "
                                + "graph vertices are not numbered properly");
   
            if (l[i].lessThan(l[w.vertex].add(w.weight)))
            {// path through w.vertex is longer
               l[i] = (Operable) l[w.vertex].add(w.weight);
               kay[i] = w.vertex;
            }
         }

         if (maxLength.lessThan(l[i]))
            maxLength = l[i];
      }

      return maxLength;
   }
   
   /** output the longest path using l and kay as computed by longestPath */
   public void outputLongestPath(Operable [] l, int [] kay)
   {
      int n = vertices();
   
      // find start vertex of longest path
      // this is vertex with maximum l[]
      int start = 1;
      for (int i = 2; i <= n; i++)
         if (l[i].greaterThan(l[start]))
            start = i;
   
      // now output the path
      System.out.println("The longest path is");
      while (start != 0)
      {
         System.out.print(start + " ");
         start = kay[start];
      }
      System.out.println();
   }

   /** find shortest paths from vertex s
     * @return shortest distances in d
     * @return predecessor information in p */
   public void shortestPaths(int s, Operable [] d, int [] p)
   {
      verifyWeighted("shortestPaths");

      int n = vertices();

      if (s < 1 || s > n)
         throw new IllegalArgumentException
               ("Graph.shortestPaths: source vertex "
                + "cannot be " + s);

      GraphChain l = new GraphChain(); // list of reachable vertices for
                                       // which paths have yet to be found
      // initialize d, p, and l
      // first set all d values to null and all p values to -1
      for (int i = 1; i <= n; i++)
      {
          d[i] = null;
          p[i] = -1;
      }
      // now change d and p values for vertices adjacent from s
      Enumeration es = elements(s);
      while (es.hasMoreElements())
      {
         WeightedEdgeNode wNode = (WeightedEdgeNode) es.nextElement();
         d[wNode.vertex] = wNode.weight;
         d[s] = (Operable) wNode.weight.zero();
         p[wNode.vertex] = s; 
         l.insertElementAt(new EdgeNode(wNode.vertex), 0);
      }
      p[s] = 0;  // source vertex has no predecessor
   
      // update d and p
      while (!l.isEmpty())
      {// more paths exist
         // find vertex v in l with least d
         Enumeration el = l.elements();
         int v = ((EdgeNode) el.nextElement()).vertex;
         while (el.hasMoreElements())
         {
            int w = ((EdgeNode) el.nextElement()).vertex;
            if (d[w].lessThan(d[v]))
               v = w;
         }
   
         // next shortest path is to vertex v
         // delete v from l and update d
         l.removeElement(v);
         Enumeration ev = elements(v);
         while (ev.hasMoreElements())
         {
            WeightedEdgeNode wNode = (WeightedEdgeNode) ev.nextElement();
            int j = wNode.vertex;
      	    if (p[j] == -1 || d[j].greaterThan(d[v].add(wNode.weight)))
            {
               // d[j] decreases
               d[j] = (Operable) d[v].add(wNode.weight);
               // add j to l if not already in l
               if (p[j] == -1)
                  l.insertElementAt(new EdgeNode(j), 0);
               p[j] = v;
            }
         }
      }
   }

   /** Bellman and Ford algorithm to find the shortest paths from vertex s.
     * Graph may have edges with negative cost but should
     * not have a cycle with negative cost.
     * @param theZero equals zero weight
     * @return shortest distances from s are returned in d
     * @return predecessor info in returned p */
   public void bellmanFord(int s, Operable [] d, int [] p, Operable theZero)
   {
      verifyWeighted("bellmanFord");
   
      int n = vertices();
      if (s < 1 || s > n)
         throw new IllegalArgumentException
                   ("Graph.bellmanFord: illegal source vertex");
   
      // define two chains for vertices whose d has changed
      Chain c1 = new Chain();
      Chain c2 = new Chain();
      // define an array to record vertices that are in C2
      boolean [] inC2 = new boolean [n+1];
   
      // initialize p[1:n] = 0 and inC2[1:n] = false
      for (int i = 0; i <= n; i++)
      {
         p[i] = 0;
         inC2[i] = false;
      }

      // set d[s] = d^0(s)
      d[s] = (Operable) theZero.zero();
      p[s] = s;  // p[i] != 0 means vertex i has been reached
   
      // initialize c1
      c1.insertElementAt(new Integer(s), 0);
      
      // do n - 1 rounds of updating d
      for (int k = 1; k < n; k++)
      {
         if (c1.isEmpty())
            break;  // no more changes possible
         // process vertices on c1
         Enumeration ec1 = c1.elements();
         while (ec1.hasMoreElements())
         {
            // get a vertex u whose d value has changed
            int u = ((Integer) ec1.nextElement()).intValue();
   
            // update d for the neighbors v of u
            Enumeration eu = elements(u);
            while (eu.hasMoreElements())
            {
               WeightedEdgeNode vEdge = (WeightedEdgeNode) eu.nextElement();
               if (p[vEdge.vertex] == 0 ||
                  ((Operable) d[u].add(vEdge.weight)).lessThan(d[vEdge.vertex]))
               {
                  // this is either the first path to vEdge.vertex
                  // or is a shorter path than earlier ones
                  d[vEdge.vertex] = (Operable) d[u].add(vEdge.weight);
                  p[vEdge.vertex] = u;
                  // put vEdge.vertex into c2 unless it is already there
                  if (!inC2[vEdge.vertex])
                  {
                     c2.insertElementAt(new Integer(vEdge.vertex), 0);
                     inC2[vEdge.vertex] = true;
                  }
               }
            }
         }
   
         // set c1 and c2 for next update round
         c1 = c2;
         c2 = new Chain();
   
         // reset inC2[1:n] to false
         ec1 = c1.elements();
         while (ec1.hasMoreElements())
            inC2[((Integer) ec1.nextElement()).intValue()] = false;
      }
   }
}
