min_cut.h

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_base_and_derived.hpp>

#ifndef MIN_CUT_H
#define MIN_CUT_H

using namespace std;
using namespace boost;

namespace SCIL {

template <typename Graph>
class MC {
   public:
      typedef graph_traits<Graph> GraphTraits;
      typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
     int value;
     list<vertex_descriptor> nodes;
     MC()
        : value(0)
     {};
     MC(int val, list<vertex_descriptor> nod)
        : value(val) {
           nodes = nod;
        }
     ~MC() {
        nodes.clear();
     }
     MC<Graph>& operator= ( const MC<Graph>& x ) {
        value = x.value;
        nodes = x.nodes;
     }
};

/* See the paper 'A Simple Min-Cut Algorithm' (Journal of the ACM, Vol. 44,
   No. 4, July 1997, pp. 585-591) for a detailed description of the algorithm.
   You need to provide an undirected Graph and a map<edge_descriptor, int>
   that provides positive weights for all edges. 
   After that you can start the algorithm by calling the function run(), which
   will return a pair<int, list<vertex_descriptor> > containing the minimum 
   weight of the cut and the vertices in the min-cut in the list.
 */

template <typename Graph>
class MIN_CUT {

   public:
      MC<Graph> minCutOfPhase;
      MC<Graph> minCut;

   private:
      typedef graph_traits<Graph> GraphTraits;
      typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
      typedef typename GraphTraits::edge_descriptor edge_descriptor;
      const Graph &G_ref; 
      Graph G; 

      map<vertex_descriptor, vertex_descriptor> GtoG_ref;
      map<vertex_descriptor, vertex_descriptor> merged_vertex;
      map<edge_descriptor, int> w; 
      set<vertex_descriptor> vertices_of_G; 

      /* The most tightly connected vertex with the set of previously most 
         tightly connected vertices is determined and added to the set until 
         just one vertex is left. The cut between this vertex and the set is a 
         possible minimum cut and returned to run() for evaluation.
       */
      void MinCutPhase();

      /* Vertex t is removed and edges of t are added to s. If an edge, which 
         should be added, already exists in s, the weights of both edges are 
         summed up. 
       */
      void contract(vertex_descriptor s, vertex_descriptor t);

      /* Since vertices in G might be merged, the function has to return a list
         and add all the vertices that have been merged into vertex t to it.
       */
      void getCutOfPhase(int w, vertex_descriptor t);

   public:
      /* Used to create an object of MIN_CUT. Furthermore a copy of the input-
         graph is created and some check for feasibility of input are run.
         G_ should be a reference to the graph and w_ a map, which maps all
         edges to their appropriate weight.
       */
      MIN_CUT(const Graph &G_, const map<edge_descriptor, int> &w_);

      /* This function returns the integer value of the minimum cut and a list
         of the vertices in the minimum cut.
         The actual algorithm is just executed for graphs with more than 2 
         vertices. For 2 vertices the solution is trivial and for less than 2 
         vertices there is no minimum cut.
       */
      void run();
};

#include "../../../src/core/min_cut.cc"

}

#endif

---