Pgr_stoerWagner< G > Class Template Reference

#include "pgr_stoerWagner.hpp"

Public Types
typedef G::E	E
typedef G::E_i	E_i
typedef G::V	V

Public Member Functions
std::vector< pgr_stoerWagner_t >	stoerWagner (G &graph)

Private Member Functions
std::vector< pgr_stoerWagner_t >	generatestoerWagner (const G &graph)

Detailed Description

template<class G>
class Pgr_stoerWagner< G >

Definition at line 50 of file pgr_stoerWagner.hpp.

Member Typedef Documentation

E

template<class G >

typedef G::E Pgr_stoerWagner< G >::E

Definition at line 60 of file pgr_stoerWagner.hpp.

E_i

template<class G >

typedef G::E_i Pgr_stoerWagner< G >::E_i

Definition at line 61 of file pgr_stoerWagner.hpp.

V

template<class G >

typedef G::V Pgr_stoerWagner< G >::V

Definition at line 59 of file pgr_stoerWagner.hpp.

Member Function Documentation

generatestoerWagner()

template<class G >

std::vector< pgr_stoerWagner_t > Pgr_stoerWagner< G >::generatestoerWagner ( const G &  graph )

inlineprivate

Definition at line 68 of file pgr_stoerWagner.hpp.

                         {
       std::vector< pgr_stoerWagner_t > results;
       auto parities = boost::make_one_bit_color_map(
                                        num_vertices(graph.graph),
                                        get(boost::vertex_index, graph.graph));
 
       double w = stoer_wagner_min_cut(
                                   graph.graph,
                                   get(&G::G_T_E::cost, graph.graph),
                                   boost::parity_map(parities));
 
       double totalcost = 0;
       E_i ei, ei_end;
       for (boost::tie(ei, ei_end) = edges(graph.graph); ei != ei_end; ei++) {
          auto s = source(*ei, graph.graph);
          auto t = target(*ei, graph.graph);
 
          if (get(parities, s) != get(parities, t)) {
               pgr_stoerWagner_t tmp;
 
               tmp.cost = graph[*ei].cost;
 
               auto edge_id =
                 graph.get_edge_id(
                         source(*ei, graph.graph),
                         target(*ei, graph.graph),
                         tmp.cost);
 
               tmp.edge = edge_id;
               totalcost += tmp.cost;
               tmp.mincut = totalcost;
               results.push_back(tmp);
             }
       }
 
       pgassert(w == totalcost);
       return results;
     }

References pgr_stoerWagner_t::cost, pgr_stoerWagner_t::edge, pgr_stoerWagner_t::mincut, and pgassert.

stoerWagner()

template<class G >

std::vector< pgr_stoerWagner_t > Pgr_stoerWagner< G >::stoerWagner

(

G &

graph

)

Definition at line 111 of file pgr_stoerWagner.hpp.

                          {
      pgassert(num_vertices(graph.graph) > 1);
      return generatestoerWagner(
                             graph);
}

References pgassert.

Referenced by pgr_stoerWagner().

---

The documentation for this class was generated from the following file:

• pgr_stoerWagner.hpp