finding a min-cut of graph with boost library

Question

Im trying to understand how to build a graph and run the stoer_wagner_min_cut algorithm with boost library.

so far, I built the graph with the adjacency_matrix container.

the problem is the making thestoer_wagner_min_cut work. I red this documentation and I encountered two things:

1. "The graph type must be a model of Vertex List Graph and Incidence Graph."
2. WeightMap weights as an input.

what does the first section means? is adjacency_matrix some type of "Vertex List Graph and Incidence Graph"? is there an example for that?

also, all the edges in the graph have weight of 1. I didn't understand how to assemble that WeightMap weights. and couldn't find any example for that.

EDIT:

this is what I could managed-

#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/stoer_wagner_min_cut.hpp>
#include <boost/property_map/property_map.h>

using namespace boost;
typedef adjacency_matrix<undirectedS> UGraph;


void main()
{
  static_property_map<UGraph, int>;   // im not sure about UGraph

  G = buildGraph();    // this function works fine

  parity_map = stoer_wagner_min_cut(G, ..?..);
}

how should I define this static property map to return int value of 1? im bit struggling with that. also I saw that the return value of stoer_wagner_min_cut is parity_map (ParityMap must be a model of a Writable Property Map and its value type should be a bool type)

Im bit struggling with the building and using those maps, I will be happy for some guidance and example for that..

thanks.

Answer 1

1. what does the first section means? is adjacency_matrix some type of "Vertex List Graph and Incidence Graph"? is there an example for that?

   It means the graph type must model the named concepts. The concepts are documented here:

   • http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_concepts.html

   ---

2. The second question is about property maps. They're also a concept

   And in this case it would be easiest to supply a static property map:

   • http://www.boost.org/doc/libs/1_58_0/libs/property_map/doc/static_property_map.html

   Live On Coliru

   #include <boost/functional/hash.hpp>
   #include <boost/graph/adjacency_matrix.hpp>
   #include <boost/graph/stoer_wagner_min_cut.hpp>
   #include <boost/property_map/property_map.hpp>
   
   using namespace boost;
   
   typedef adjacency_matrix<undirectedS> UGraph;
   
   UGraph buildGraph() {
       UGraph g(10);
   
       // todo
   
       return g;
   }
   
   #include <iostream>
   
   int main() {
       UGraph g = buildGraph(); // this function works fine
   
       int i = stoer_wagner_min_cut(g, boost::make_static_property_map<UGraph::edge_descriptor>(1));
   
       std::cout << "i: " << i << "\n";
   }