undirect.h

一本全面剖析C++数据结构算法的书籍

// file undirect.h
// functions for undirected graphs

#ifndef Undirected_
#define Undirected_

#include "network.h"
#include "lstack.h"

class NodeType {
   friend class Undirected;
   private:
      int left, right;
};

class Undirected : virtual public Network {
   public:
      virtual int Degree(int i) const = 0;
      bool Connected();
      int LabelComponents(int L[]);
      bool BipartiteCover(int L[], int C[], int& m);
   private:
      void CreateBins(int b, int n);
      void DestroyBins() {delete [] node;
                          delete [] bin;}
      void InsertBins(int b, int v);
      void MoveBins(int bMax, int ToBin, int v);
      int *bin;
      NodeType *node;
};

bool Undirected::Connected()
{// Return true iff graph is connected.

   int n = Vertices();

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

int Undirected::LabelComponents(int L[])
{// Label the components of the graph.
 // Return the number of components and set L[1:n]
 // to represent a labeling of vertices by component.

   int n = Vertices();

   // assign all vertices to no component
   for (int u = 1; u <= n; u++)
      L[u] = 0;

   int label = 0;  // ID of last component
   // identify components
   for (int u = 1; u <= n; u++)
      if (!L[u]) {// unreached vertex
         // vertex u is in a new component
         label++;
         BFS(u, L, label);} // mark new component

   return label;
}

void Undirected::CreateBins(int b, int n)
{// Create b empty bins and n nodes.
   node = new NodeType [n+1];
   bin = new int [b+1];
   // set bins empty
   for (int u = 1; u <= b; u++)
      bin[u] = 0;
}

void Undirected::InsertBins(int b, int v)
{// Insert v into bin b unless b is zero.
   if (!b) return;   // do not insert in bin 0
   node[v].left = b; // add at left end
   if (bin[b]) node[bin[b]].left = v;
   node[v].right = bin[b];
   bin[b] = v;
}

void Undirected::MoveBins(int bMax, int ToBin, int v)
{// Move vertex v from its current bin to bin ToBin.
   // nodes to the left and right of v
   int l = node[v].left;
   int r = node[v].right;

   // delete from current bin
   if (r) node[r].left = node[v].left;
   if (l > bMax || bin[l] != v) // not left-most one
      node[l].right = r;
   else bin[l] = r;             // left-most in bin l

   // add to bin ToBin
   InsertBins(ToBin, v);
}

bool Undirected::BipartiteCover(int L[], int C[], int& m)
{// Find a cover of the bipartite graph.
 // L is the input vertex labeling, L[i] = 1 iff i is
 // in A.  C is an output array that identifies the
 // cover.  Return false if the graph has no cover.
 // If the graph has a cover, return true;
 // return cover size in m; and cover in C[0:m-1].

   int n = Vertices();

   // create structures
   int SizeOfA = 0;
   for (int u = 1; u <= n; u++) // find size of set A
      if (L[u] == 1) SizeOfA++;
   int SizeOfB = n - SizeOfA;
   CreateBins(SizeOfB, n);
   int *New = new int [n+1];
      // vertex i covers New[i] uncovered vertices of B
   bool *Change = new bool [n+1];
      // Change[i] is true iff New[i] has changed
   bool *Cov = new bool [n+1];
      // Cov[i] is true iff vertex i is covered
   InitializePos();
   LinkedStack<int> S;
   
   // initialize
   for (int u = 1; u <= n; u++) {
      Cov[u] = Change[u] = false;
      if (L[u] == 1) {// u is in A
         New[u] = Degree(u); // u covers this many
         InsertBins(New[u], u);}}
   
   // construct cover
   int covered = 0,       // # of covered vertices
       MaxBin = SizeOfB;  // max bin that may be
                          // nonempty
   m = 0;                 // cursor for C
   while (MaxBin > 0) {   // search all bins
      // select a vertex
      if (bin[MaxBin]) {      // bin not empty
         int v = bin[MaxBin]; // first vertex
         C[m++] = v;          // add v to cover
         // label newly covered vertices
         int j = Begin(v), k;
         while (j) {
            if (!Cov[j]) {// j not covered yet
               Cov[j] = true;
               covered++;
               // update New
               k = Begin(j);
               while (k) {
                  New[k]--;     // j does not count
                  if (!Change[k]) {
                     S.Add(k);  // stack once only
                     Change[k] = true;}
                  k = NextVertex(j);}
               }
            j = NextVertex(v);}

         // update bins
         while (!S.IsEmpty()) {
            S.Delete(k);
            Change[k] = false;
            MoveBins(SizeOfB, New[k], k);}
         }
      else MaxBin--;
      }
   
   DeactivatePos();
   DestroyBins();
   delete [] New;
   delete [] Change;
   delete [] Cov;
   return (covered == SizeOfB);
}
  
#endif