graph.h

datastucutre and algorithms, application, in C

                        if (!changed[k])
                        {
                           stack.push(k);  // stack once only
                           changed[k] = true;
                        }
                     }
                  }   
               }
               // update bins
               while (!stack.empty())
               {
                  int k = stack.top();
                  stack.pop();
                  changed[k] = false;
                  moveBins(sizeOfB, newVerticesCovered[k], k);
               }
            }
            else maxBin--; // go to next bin
         
         return (numberCovered == sizeOfB) ? coverSize : -1;
      }

      bool kruskal(weightedEdge<T> *spanningTreeEdges)
      {// Find a min cost spanning tree using Kruskal's method.
       // Return false iff the weighted undirected graph is not connected.
       // spanningTreeEdges[0:n-2] has the min-cost-tree edges when done.
         if (directed() || !weighted())
            throw undefinedMethod
            ("graph::kruskal() not defined for unweighted and directed graphs");
   
         int n = numberOfVertices();
         int e = numberOfEdges();
         // set up array of graph edges
         weightedEdge<T> *edge = new weightedEdge<T> [e + 1];
         int k = 0;        // cursor for edge[]
         for (int i = 1; i <= n; i++)
         {// get all edges incident to i
            vertexIterator<T> *ii = iterator(i);
            int j;
            T w;
            while ((j = ii->next(w)) != 0)
               if (i < j)  // add to edge array
                  edge[++k] = weightedEdge<int> (i, j, w);
         }
         // put edges in min heap
         minHeap<weightedEdge<T> > heap(1);
         heap.initialize(edge, e);
         
         fastUnionFind uf(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<T> x =  heap.top();
            heap.pop();
            e--;
            int a = uf.find(x.vertex1());
            int b = uf.find(x.vertex2());
            if (a != b)
            {// select edge x
               spanningTreeEdges[k++] = x;
               uf.unite(a,b);
            }
         }
         return (k == n - 1);
      }

      void bellmanFord(int s, T *d, int *p)
      {// 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.
       // Shortest distances from s are returned in d.
       // Predecessor info in returned p.
         if (!weighted())
            throw undefinedMethod
            ("graph::bellmanFord() not defined for unweighted graphs");
      
         int n = numberOfVertices();
         if (s < 1 || s > n)
            throw illegalParameterValue("illegal source vertex");
      
         // define two lists for vertices whose d has changed
         arrayList<int> *list1 = new arrayList<int>;
         arrayList<int> *list2 = new arrayList<int>;
        
         // define an array to record vertices that are in list2
         bool *inList2 = new bool [n+1];
      
         // initialize p[1:n] = 0 and inList2[1:n] = false
         fill(p + 1, p + n + 1, 0);
         fill(inList2 + 1, inList2 + n + 1, false);
      
         // set d[s] = d^0(s) = 0
         d[s] = 0;
         p[s] = s;  // p[i] != 0 means vertex i has been reached
                    // will later reset p[s] = 0
      
         // initialize list1
         list1->insert(0, s);
         
         // do n - 1 rounds of updating d
         for (int k = 1; k < n; k++)
         {
            if (list1->empty())
               break;  // no more changes possible
            // process vertices on list1
            for (arrayList<int>::iterator iList1 = list1->begin();
                 iList1 != list1->end(); ++iList1)
            {// update d for the neighbors v of vertex u = *iList1
               int u = *iList1;
               vertexIterator<T> *iu = iterator(u);
               int v;
               T w;
               while ((v = iu->next(w)) != 0)
               {
                  if (p[v] == 0 || d[u] + w < d[v])
                  {
                     // this is either the first path to v
                     // or is a shorter path than earlier ones
                     d[v] = d[u] + w;
                     p[v] = u;
                     // put v into list2 unless it is already there
                     if (!inList2[v])
                     {// put at end of list
                        list2->insert(list2->size(), v);
                        inList2[v] = true;
                     }
                  }
               }
            }
      
            // set list1 and list2 for next update round
            list1 = list2;
            list2 = new arrayList<int>;
      
            // reset inList2[1:n] to false
            for (arrayList<int>::iterator iList1 = list1->begin();
                 iList1 != list1->end(); ++iList1)
               inList2[*iList1] = false;
         }
         p[s] = 0;  // s has no predecessor
      }
   protected:
      static int *reach;
      static int *path;
      static int label;
      static int length;
      static int destination;
      static int* bin;   // pointer to first node in bin
      static binNode* node;

      void rDfs(int v)
      {// Recursive dfs method.
         reach[v] = label;
         vertexIterator<T> *iv = iterator(v);
         int u;
         while ((u = iv->next()) != 0)
            // visit an adjacent vertex of v
            if (reach[u] == 0) 
               rDfs(u);  // u is an unreached vertex
         delete iv;
      }
      
      bool rFindPath(int s)
      {// Real path finder, performs a depth-first search from s.
       // s should not equal the destination.
       // Return true iff a path to destination is found.
         reach[s] = 1;
         vertexIterator<T>* is = iterator(s);
         int u;
         while ((u = is->next()) != 0)
         {// visit an adjacent vertex of s
            if (reach[u] == 0)   // u is an unreached vertex
            {// move to vertex u
               path[++length] = u; // add u to path
               if (u == destination || rFindPath(u))
                  return true;
               // no path from u to destination
               length--;    // remove u from path
            }
         }
         delete is;
         return false;
      }

      void createBins(int b, int n)
      {// Create b empty bins and n nodes.
         bin = new int [b + 1];
         fill(bin, bin + b + 1, 0);
         node = new binNode [n + 1];
      }
      
      void insertBins(int b, int v)
      {// Insert v into bin b unless b is zero.
         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;
      }
      
      void moveBins(int bMax, int toBin, int v)
      {// Move vertex v from its current bin to bin toBin.
       // bMax is rightmost nonempty bin.
         // 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);
      }
};

int* graph<bool>::reach;
int graph<bool>::label;
int* graph<bool>::path;
int graph<bool>::length;
int graph<bool>::destination;
int* graph<bool>::bin;
binNode* graph<bool>::node;
int* graph<int>::reach;
int graph<int>::label;
int* graph<int>::path;
int graph<int>::length;
int graph<int>::destination;
int* graph<int>::bin;
binNode* graph<int>::node;
int* graph<float>::reach;
int graph<float>::label;
int* graph<float>::path;
int graph<float>::length;
int graph<float>::destination;
int* graph<float>::bin;
binNode* graph<float>::node;
int* graph<double>::reach;
int graph<double>::label;
int* graph<double>::path;
int graph<double>::length;
int graph<double>::destination;
int* graph<double>::bin;
binNode* graph<double>::node;
#endif