Ich habe viel Mühe gehabt, um herauszufinden, wie das geht. Ich bin daran interessiert, den Schnittsatz eines Graphen schnell zu finden. Ich weiß, dass BGL das Finden des durch Iteration festgelegten Schnitts über die colorMap-Argumente unterstützt, die beispielsweise von edmonds_karp_max_flow unterstützt werden. Der Gomory-Hu-Algorithmus muss mehrere Aufrufe an einen Minimum-Cut-Algorithmus senden.

Das Ergebnis, auf das ich gehofft hatte, war eine Multimap mit: (color, vertex)

Der folgende Code ist ein Versuch, das Beispiel aus der Boost-Diagrammbibliothek so umzuschreiben, dass eine Multimap für die Associative-Property-Map verwendet wird. Das Kompilieren des Codes kann erfolgen mit: clang -lboost_graph -o edmonds_karp edmonds_karp.cpp oder g ++ anstelle von clang. Ich bekomme nicht die Fehler, die rauskommen.

#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;
}

Hints wird sehr geschätzt. Vielen Dank