graph.h

这是数据结构、算法与应用-C++语言描述的代码

// abstract class graph
// abstract data type specification for graph data structure
// includes methods that are representation independent

#ifndef graph_
#define graph_

#include "edge.h"
#include "vertexIterator.h"
#include "arrayQueue.h"
#include "arrayStack.h"
#include "myExceptions.h"
#include "binNode.h"
#include "weightedEdge.h"
#include "minHeap.h"
#include "fastUnionFind.h"
#include "arrayListWithIterator.h"

using namespace std;

template<class T>
class graph 
{
   public:
      virtual ~graph() {}
      virtual int numberOfVertices() const = 0;
      virtual int numberOfEdges() const = 0;
      virtual bool existsEdge(int, int) const = 0;
      virtual void insertEdge(edge<T>*) = 0;
      virtual void eraseEdge(int, int) = 0;
      virtual int degree(int) const = 0;
      virtual int inDegree(int) const = 0;
      virtual int outDegree(int) const = 0;
      virtual bool directed() const = 0;
      virtual bool weighted() const = 0;
      virtual vertexIterator<T>* iterator(int) = 0;
      virtual void output(ostream&) const = 0;

      // implementation independent methods
      virtual void bfs(int v, int reach[], int label)
      {// Breadth-first search. reach[i] is set to label for
       // all vertices reachable from vertex v.
         arrayQueue<int> q(10);
         reach[v] = label;
         q.push(v);
         while (!q.empty())
         {
            // remove a labeled vertex from the queue
            int w = q.front();
            q.pop();
   
            // mark all unreached vertices adjacent from w
            vertexIterator<T> *iw = iterator(w);
            int u;
            while ((u = iw->next()) != 0)
               // visit an adjacent vertex of w
               if (reach[u] == 0)
               {// u is an unreached vertex
                  q.push(u);
                  reach[u] = label; // mark reached
               }
            delete iw;
         }
      }

      void dfs(int v, int reach [], int label)
      {// Depth-first search. reach[i] is set to label for all
       // vertices reachable from vertex v
         graph<T>::reach = reach;
         graph<T>::label = label;
         rDfs(v);
      }

      int* findPath(int theSource, int theDestination)
      {// Find a path from theSource to theDestination. Return the
       // path in an array using positions 1 on up. path[0] is
       // path length. Return NULL if there is no path.
         // initialize for recursive path finder
         int n = numberOfVertices();
         path = new int [n + 1];
         path[1] = theSource;      // first vertex is always s
         length = 1;               // current path length + 1
         destination = theDestination;
         reach = new int [n + 1];
         for (int i = 1; i <= n; i++)
            reach[i] = 0;
         
         // search for path
         if (theSource == theDestination || rFindPath(theSource))
            // a path was found
            path[0] = length - 1;
         else
         {
            delete [] path;
            path = NULL;
         }
        
         delete [] reach;
         return path;
      }

      bool connected()
      {// Return true iff graph is connected.
         // make sure this is an undirected graph
         if (directed())
            throw undefinedMethod
            ("graph::connected() not defined for directed graphs");
   
         int n = numberOfVertices();
      
         reach = new int [n + 1];  // by default 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;
      }

      int labelComponents(int c[])
      {// Label the components of an undirected graph. 
       // Return the number of components.
       // Set c[i] to be the component number of vertex i.
         // make sure this is an undirected graph
         if (directed())
            throw undefinedMethod
            ("graph::labelComponents() not defined for directed graphs");
   
         int n = numberOfVertices();
      
         // 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;
      }
      
      bool topologicalOrder(int *theOrder)
      {// Return false iff the digraph has no topological order.
       // theOrder[0:n-1] is set to a topological order when
       // such an order exists.
         // make sure this is a digraph
         if (!directed())
            throw undefinedMethod
            ("graph::topologicalOrder() not defined for undirected graphs");
   
         int n = numberOfVertices();
         
         // compute in-degrees
         int *inDegree = new int [n + 1];
         fill(inDegree + 1, inDegree + n + 1, 0);
         for (int i = 1; i <= n; i++)
         {// edges out of vertex i
            vertexIterator<T> *ii = iterator(i);
            int u;
            while ((u = ii->next()) != 0)
               // visit an adjacent vertex of i
               inDegree[u]++;
         }
         
         // stack vertices with zero in-degree
         arrayStack<int> stack;
         for (int i = 1; i <= n; i++)
            if (inDegree[i] == 0)
               stack.push(i);
         
         // generate topological order
         int j = 0;  // cursor for array theOrder
         while (!stack.empty())
         {// select from stack
            int nextVertex = stack.top();
            stack.pop();
            theOrder[j++] = nextVertex;
            // update in-degrees
            vertexIterator<T> *iNextVertex = iterator(nextVertex);
            int u;
            while ((u = iNextVertex->next()) != 0)
            {// visit an adjacent vertex of nextVertex
               inDegree[u]--;
               if (inDegree[u] == 0)
                  stack.push(u);
            }
         }
         return (j == n);
      }


      int bipartiteCover(int *theLabel, int *theCover)
      {// Return -1 if the bipartite graph has no cover.
       // Return cover size if there is a cover.
       // theLabel is bipartite labeling, theLabel[i] = 1 iff i is in A.
       // theCover[i], i >= 0 is set to the cover (if there is one).
         int n = numberOfVertices();
      
         // create structures
         int sizeOfA = 0;
         for (int i = 1; i <= n; i++) // find size of set A
            if (theLabel[i] == 1)
               sizeOfA++;
         int sizeOfB = n - sizeOfA;
         createBins(sizeOfB, n);
         int *newVerticesCovered = new int [n + 1];
            // vertex i covers newVerticesCovered[i] uncovered vertices of B
         bool *changed = new bool [n + 1];
            // changed[i] is true iff newVerticesCovered[i] has changed
            fill(changed + 1, changed + n + 1, false);
         bool *covered = new bool [n + 1];
            // covered[i] is true iff vertex i is covered
            fill(covered + 1, covered + n + 1, false);
         arrayStack<int> stack;
         
         // initialize
         for (int i = 1; i <= n; i++)
            if (theLabel[i] == 1)
            {// i is in A
               newVerticesCovered[i] = degree(i); // i covers this many
               insertBins(newVerticesCovered[i], i);
            }
         
         // construct cover
         int numberCovered = 0, // # of B vertices covered
             maxBin = sizeOfB;  // max bin that may be nonempty
         int coverSize = 0;     // number of A vertices in cover
         while (maxBin > 0)     // search all bins
            if (bin[maxBin] != 0)            // bin maxBin is not empty
            {
               int v = bin[maxBin];          // first vertex
               theCover[coverSize++] = v;    // add v to cover
               // label newly covered vertices
               vertexIterator<T> *iv = iterator(v);
               int j;
               while ((j = iv->next()) != 0)
               {
                  if (!covered[j])          // j not covered yet
                  {
                     covered[j] = true;
                     numberCovered++;
                     // update newVerticesCovered
                     vertexIterator<T> *ij = iterator(j);
                     int k;
                     while ((k = ij->next()) != 0)
                     {
                        newVerticesCovered[k]--;        // j does not count