He estado luchando mucho para descubrir cómo hacer esto. Estoy interesado en encontrar rápidamente el conjunto de corte de un gráfico. Sé que BGL admite encontrar el corte establecido por iteración sobre los argumentos de colorMap admitidos por, por ejemplo, edmonds_karp_max_flow. El algoritmo Gomory Hu necesita hacer varias llamadas a un algoritmo de corte mínimo.

El resultado que esperaba era tener un mapa múltiple que contiene: (color, vértice)

El siguiente código es un intento de reescribir el ejemplo de la Boost Graph Library para usar un mapa múltiple para asociative_property_map. La compilación del código se puede hacer con: clang -lboost_graph -o edmonds_karp edmonds_karp.cpp o g ++ en lugar de clang. No obtengo los errores que surgen.

#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/unordered_map.hpp>

int main()
{
  using namespace boost;

  typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
  typedef adjacency_list < listS, vecS, directedS,
    property < vertex_name_t, std::string >,
    property < edge_capacity_t, long,
    property < edge_residual_capacity_t, long,
    property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;

  Graph g;

  property_map < Graph, edge_capacity_t >::type
    capacity = get(edge_capacity, g);
  property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
  property_map < Graph, edge_residual_capacity_t >::type
    residual_capacity = get(edge_residual_capacity, g);

  std::multimap<default_color_type, Traits::vertex_descriptor> colorMap;
  boost::associative_property_map< std::map<default_color_type,
                                            Traits::vertex_descriptor> >
      color_map(colorMap);

  Traits::vertex_descriptor s, t;
  read_dimacs_max_flow(g, capacity, rev, s, t);

  std::vector<Traits::edge_descriptor> pred(num_vertices(g));
  long flow = edmonds_karp_max_flow
      (g, s, t, capacity, residual_capacity, rev,
       make_iterator_property_map(color_map.begin()),
       &pred[0]);

  std::cout << "c  The total flow:" << std::endl;
  std::cout << "s " << flow << std::endl << std::endl;

  std::cout << "c flow values:" << std::endl;
  graph_traits < Graph >::vertex_iterator u_iter, u_end;
  graph_traits < Graph >::out_edge_iterator ei, e_end;
  for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
    for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
      if (capacity[*ei] > 0)
        std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
          << (capacity[*ei] - residual_capacity[*ei]) << std::endl;

  // if using the original example, unedited, this piece of code works
  // BOOST_FOREACH(default_color_type x, color){
  //   std::cout << x << std::endl;
  // }

  return EXIT_SUCCESS;
}

Las sugerencias serán muy apreciadas. Gracias.