Changeset 83410
 Timestamp:
 Mar 12, 2013, 12:35:48 AM (5 years ago)
 Location:
 trunk
 Files:

 3 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

trunk/boost/graph/stoer_wagner_min_cut.hpp
r78329 r83410 16 16 #include <boost/graph/exception.hpp> 17 17 #include <boost/graph/graph_traits.hpp> 18 #include <boost/graph/ iteration_macros.hpp>18 #include <boost/graph/maximum_adjacency_search.hpp> 19 19 #include <boost/graph/named_function_params.hpp> 20 #include <boost/graph/one_bit_color_map.hpp> 20 21 #include <boost/graph/detail/d_ary_heap.hpp> 21 22 #include <boost/property_map/property_map.hpp> 22 23 #include <boost/tuple/tuple.hpp> 23 24 #include <boost/utility/result_of.hpp> 25 #include <boost/graph/iteration_macros.hpp> 24 26 25 27 namespace boost { 26 28 27 29 namespace detail { 28 29 /** 30 * \brief Performs a phase of the StoerWagner mincut algorithm 31 * 32 * Performs a phase of the StoerWagner mincut algorithm. 33 * 34 * As described by Stoer & Wagner (1997), a phase is simply a maximum adjacency search 35 * (also called a maximum cardinality search), which results in the selection of two vertices 36 * \em s and \em t, and, as a side product, a minimum <em>s</em><em>t</em> cut of 37 * the input graph. Here, the input graph is basically \p g, but some vertices are virtually 38 * assigned to others as a way of viewing \p g as a graph with some sets of 39 * vertices merged together. 40 * 41 * This implementation is a translation of pseudocode by Professor Uri Zwick, 42 * School of Computer Science, Tel Aviv University. 43 * 44 * \pre \p g is a connected, undirected graph 45 * \param[in] g the input graph 46 * \param[in] assignments a read/write property map from each vertex to the vertex that it is assigned to 47 * \param[in] assignedVertices a list of vertices that are assigned to others 48 * \param[in] weights a readable property map from each edge to its weight (a nonnegative value) 49 * \param[out] pq a keyed, updatable maxpriority queue 50 * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and "<em>t</em>" 51 * of the minimum <em>s</em><em>t</em> cut and the cut weight \em w 52 * of the minimum <em>s</em><em>t</em> cut. 53 * \see http://www.cs.tau.ac.il/~zwick/gradalgo08/gmc.pdf 54 * 55 * \author Daniel Trebbien 56 * \date 20100911 57 */ 58 template <class UndirectedGraph, class VertexAssignmentMap, class WeightMap, class KeyedUpdatablePriorityQueue> 59 boost::tuple<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::property_traits<WeightMap>::value_type> 60 stoer_wagner_phase(const UndirectedGraph& g, VertexAssignmentMap assignments, const std::set<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor>& assignedVertices, WeightMap weights, KeyedUpdatablePriorityQueue& pq) { 61 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor; 30 template < typename ParityMap, typename WeightMap, typename IndexMap > 31 class mas_min_cut_visitor : public boost::default_mas_visitor { 32 typedef one_bit_color_map <IndexMap> InternalParityMap; 62 33 typedef typename boost::property_traits<WeightMap>::value_type weight_type; 63 64 BOOST_ASSERT(pq.empty()); 65 typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys(); 66 67 BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { 68 if (v == get(assignments, v)) { // foreach u \in V do 69 put(keys, v, weight_type(0)); 70 71 pq.push(v); 34 public: 35 template < typename Graph > 36 mas_min_cut_visitor(const Graph& g, 37 ParityMap parity, 38 weight_type& cutweight, 39 WeightMap weight_map, 40 IndexMap index_map) 41 : m_bestParity(parity), 42 m_parity(make_one_bit_color_map(num_vertices(g), index_map)), 43 m_bestWeight(cutweight), 44 m_cutweight(0), 45 m_visited(0), 46 m_weightMap(weight_map) 47 { 48 // set here since the init list sets the reference 49 m_bestWeight = (std::numeric_limits<weight_type>::max)(); 50 } 51 52 template < typename Vertex, typename Graph > 53 void initialize_vertex(Vertex u, const Graph & g) 54 { 55 typedef typename boost::property_traits<ParityMap>::value_type parity_type; 56 typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type; 57 58 put(m_parity, u, internal_parity_type(0)); 59 put(m_bestParity, u, parity_type(0)); 60 } 61 62 template < typename Edge, typename Graph > 63 void examine_edge(Edge e, const Graph & g) 64 { 65 weight_type w = get(m_weightMap, e); 66 67 // if the target of e is already marked then decrease cutweight 68 // otherwise, increase it 69 if (get(m_parity, boost::target(e, g))) { 70 m_cutweight = w; 71 } else { 72 m_cutweight += w; 72 73 } 73 74 } 74 75 BOOST_ASSERT(pq.size() >= 2); 76 77 vertex_descriptor s = boost::graph_traits<UndirectedGraph>::null_vertex(); 78 vertex_descriptor t = boost::graph_traits<UndirectedGraph>::null_vertex(); 79 weight_type w; 80 while (!pq.empty()) { // while PQ \neq {} do 81 const vertex_descriptor u = pq.top(); // u = extractmax(PQ) 82 w = get(keys, u); 83 pq.pop(); 84 85 s = t; t = u; 86 87 BGL_FORALL_OUTEDGES_T(u, e, g, UndirectedGraph) { // foreach (u, v) \in E do 88 const vertex_descriptor v = get(assignments, target(e, g)); 89 90 if (pq.contains(v)) { // if v \in PQ then 91 put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v)) 92 pq.update(v); 75 76 template < typename Vertex, typename Graph > 77 void finish_vertex(Vertex u, const Graph & g) 78 { 79 typedef typename boost::property_traits<ParityMap>::value_type parity_type; 80 typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type; 81 82 ++m_visited; 83 put(m_parity, u, internal_parity_type(1)); 84 85 if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) { 86 m_bestWeight = m_cutweight; 87 BGL_FORALL_VERTICES_T(i, g, Graph) { 88 put(m_bestParity,i, get(m_parity,i)); 93 89 } 94 90 } 95 96 typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end(); 97 for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) { 98 const vertex_descriptor uPrime = *assignedVertexIt; 99 100 if (get(assignments, uPrime) == u) { 101 BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph) { // foreach (u, v) \in E do 102 const vertex_descriptor v = get(assignments, target(e, g)); 103 104 if (pq.contains(v)) { // if v \in PQ then 105 put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v)) 106 pq.update(v); 107 } 108 } 109 } 110 } 111 } 112 113 return boost::make_tuple(s, t, w); 114 } 115 91 } 92 93 inline void clear() { 94 m_bestWeight = (std::numeric_limits<weight_type>::max)(); 95 m_visited = 0; 96 m_cutweight = 0; 97 } 98 99 private: 100 ParityMap m_bestParity; 101 InternalParityMap m_parity; 102 weight_type& m_bestWeight; 103 weight_type m_cutweight; 104 unsigned m_visited; 105 const WeightMap& m_weightMap; 106 }; 107 116 108 /** 117 109 * \brief Computes a mincut of the input graph … … 136 128 * \date 20100911 137 129 */ 138 template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue >130 template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap> 139 131 typename boost::property_traits<WeightMap>::value_type 140 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) { 132 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) { 133 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor; 134 typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type; 135 typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor; 136 typedef typename boost::property_traits<WeightMap>::value_type weight_type; 137 typedef typename boost::property_traits<ParityMap>::value_type parity_type; 138 139 typename graph_traits<UndirectedGraph>::vertex_iterator u_iter, u_end; 140 141 weight_type bestW = (std::numeric_limits<weight_type>::max)(); 142 weight_type bestThisTime = (std::numeric_limits<weight_type>::max)(); 143 vertex_descriptor bestStart; 144 145 detail::mas_min_cut_visitor<ParityMap, WeightMap, IndexMap> 146 vis(g, parities, bestThisTime, weights, index_map); 147 148 // for each node in the graph, 149 for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { 150 // run the MAS and find the min cut 151 vis.clear(); 152 boost::maximum_adjacency_search(g, 153 boost::weight_map(weights). 154 visitor(vis). 155 root_vertex(*u_iter). 156 vertex_assignment_map(assignments). 157 max_priority_queue(pq)); 158 if (bestThisTime < bestW) { 159 bestW = bestThisTime; 160 bestStart = *u_iter; 161 } 162 } 163 164 // Run one more time, starting from the best start location, to 165 // ensure the visitor has the best values. 166 vis.clear(); 167 boost::maximum_adjacency_search(g, 168 boost::vertex_assignment_map(assignments). 169 weight_map(weights). 170 visitor(vis). 171 root_vertex(bestStart). 172 max_priority_queue(pq)); 173 174 return bestW; 175 } 176 } // end `namespace detail` within `namespace boost` 177 178 template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap> 179 typename boost::property_traits<WeightMap>::value_type 180 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) { 141 181 BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<UndirectedGraph>)); 142 182 BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<UndirectedGraph>)); … … 152 192 BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>)); 153 193 BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>)); 154 194 155 195 vertices_size_type n = num_vertices(g); 156 196 if (n < 2) … … 158 198 else if (!pq.empty()) 159 199 throw std::invalid_argument("the maxpriority queue must be empty initially."); 160 161 std::set<vertex_descriptor> assignedVertices; 162 163 // initialize `assignments` (all vertices are initially assigned to themselves) 164 BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { 165 put(assignments, v, v); 166 } 167 168 vertex_descriptor s, t; 169 weight_type bestW; 170 171 boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq); 172 BOOST_ASSERT(s != t); 173 BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { 174 put(parities, v, parity_type(v == t ? 1 : 0)); 175 } 176 put(assignments, t, s); 177 assignedVertices.insert(t); 178 n; 179 180 for (; n >= 2; n) { 181 weight_type w; 182 boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq); 183 BOOST_ASSERT(s != t); 184 185 if (w < bestW) { 186 BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { 187 put(parities, v, parity_type(get(assignments, v) == t ? 1 : 0)); 188 189 if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s 190 put(assignments, v, s); 191 } 192 193 bestW = w; 194 } else { 195 BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { 196 if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s 197 put(assignments, v, s); 198 } 199 } 200 put(assignments, t, s); 201 assignedVertices.insert(t); 202 } 203 204 BOOST_ASSERT(pq.empty()); 205 206 return bestW; 200 201 return detail::stoer_wagner_min_cut(g, weights, 202 parities, assignments, pq, index_map); 207 203 } 208 209 } // end `namespace detail` within `namespace boost` 210 211 template <class UndirectedGraph, class WeightMap, class P, class T, class R> 212 inline typename boost::property_traits<WeightMap>::value_type 213 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, const boost::bgl_named_params<P, T, R>& params) { 214 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor; 215 typedef typename std::vector<vertex_descriptor>::size_type heap_container_size_type; 216 typedef typename boost::property_traits<WeightMap>::value_type weight_type; 217 218 typedef boost::bgl_named_params<P, T, R> params_type; 219 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) 220 221 typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type; 222 gen_type gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0))); 223 typename boost::result_of<gen_type(const UndirectedGraph&, const arg_pack_type&)>::type pq = gen(g, arg_pack); 224 225 return boost::detail::stoer_wagner_min_cut(g, 226 weights, 227 choose_param(get_param(params, boost::parity_map_t()), boost::dummy_property_map()), 228 boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack), 229 pq 230 ); 204 205 namespace graph { 206 namespace detail { 207 template <class UndirectedGraph, class WeightMap> 208 struct stoer_wagner_min_cut_impl { 209 typedef typename boost::property_traits<WeightMap>::value_type result_type; 210 template <typename ArgPack> 211 result_type operator() (const UndirectedGraph& g, WeightMap weights, const ArgPack& arg_pack) const { 212 using namespace boost::graph::keywords; 213 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor; 214 typedef typename boost::property_traits<WeightMap>::value_type weight_type; 215 216 typedef typename boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type; 217 218 gen_type gen(choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0))); 219 220 typename boost::result_of<gen_type(const UndirectedGraph&, const ArgPack&)>::type pq = gen(g, arg_pack); 221 222 return boost::stoer_wagner_min_cut(g, 223 weights, 224 arg_pack [_parity_map  boost::dummy_property_map()], 225 boost::detail::make_property_map_from_arg_pack_gen<tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack), 226 pq, 227 boost::detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index) 228 ); 229 } 230 }; 231 231 } 232 233 template <class UndirectedGraph, class WeightMap> 234 inline typename boost::property_traits<WeightMap>::value_type 235 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights) { 236 return boost::stoer_wagner_min_cut(g, weights, boost::vertex_index_map(get(boost::vertex_index, g))); 237 } 238 232 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut,2,4) 233 } 234 235 // Named parameter interface 236 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2) 237 namespace graph { 238 // version without IndexMap kept for backwards compatibility 239 // (but requires vertex_index_t to be defined in the graph) 240 // Place after the macro to avoid compilation errors 241 template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue> 242 typename boost::property_traits<WeightMap>::value_type 243 stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) { 244 245 return stoer_wagner_min_cut(g, weights, 246 parities, assignments, pq, 247 get(vertex_index, g)); 248 } 249 } // end `namespace graph` 239 250 } // end `namespace boost` 240 251 
trunk/libs/graph/doc/table_of_contents.html
r81725 r83410 288 288 <LI><A href="is_bipartite.html"><tt>is_bipartite</tt></A> (including twocoloring of bipartite graphs) 289 289 <LI><A href="find_odd_cycle.html"><tt>find_odd_cycle</tt></A> 290 <LI><A href="maximum_adjacency_search.html"><tt>maximum_adjacency_search</tt></A> 290 291 </ol> 291 292 </li> 
trunk/libs/graph/test/Jamfile.v2
r82007 r83410 124 124 [ run random_spanning_tree_test.cpp ../build//boost_graph ] 125 125 [ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ] 126 [ run mas_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ] 126 127 [ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ] 127 128 [ compile filtered_graph_properties_dijkstra.cpp ]
Note: See TracChangeset
for help on using the changeset viewer.