|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r65590 - in trunk: boost/graph boost/graph/detail libs/graph/doc libs/graph/doc/stoer_wagner_imgs libs/graph/example libs/graph/test libs/graph/test/prgen_input_graphs
From: jewillco_at_[hidden]
Date: 2010-09-25 14:52:45
Author: jewillco
Date: 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
New Revision: 65590
URL: http://svn.boost.org/trac/boost/changeset/65590
Log:
Added Stoer-Wagner min-cut algorithm submitted by Daniel Trebbien
Added:
trunk/boost/graph/buffer_concepts.hpp (contents, props changed)
trunk/boost/graph/stoer_wagner_min_cut.hpp (contents, props changed)
trunk/libs/graph/doc/KeyedUpdatableQueue.html (contents, props changed)
trunk/libs/graph/doc/UpdatableQueue.html (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/
trunk/libs/graph/doc/stoer_wagner_imgs/6e4.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/8b7.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/digraph1-min-cut.dot (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/digraph1-min-cut.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/digraph1.dot (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/digraph1.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/f79.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-c1.dot (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-c1.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-min-cut.dot (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-min-cut.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example.dot (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner.cpp.dot (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner.cpp.gif (contents, props changed)
trunk/libs/graph/doc/stoer_wagner_min_cut.html (contents, props changed)
trunk/libs/graph/example/stoer_wagner.cpp (contents, props changed)
trunk/libs/graph/test/prgen_input_graphs/
trunk/libs/graph/test/prgen_input_graphs/prgen_20_70_2.net (contents, props changed)
trunk/libs/graph/test/prgen_input_graphs/prgen_50_40_2.net (contents, props changed)
trunk/libs/graph/test/prgen_input_graphs/prgen_50_70_2.net (contents, props changed)
trunk/libs/graph/test/stoer_wagner_test.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/detail/d_ary_heap.hpp | 6 +++
trunk/boost/graph/graph_concepts.hpp | 24 -----------
trunk/boost/graph/named_function_params.hpp | 79 +++++++++++++++++++++++++++++++++++++--
trunk/libs/graph/doc/BUILD_DOCS.sh | 11 +++++
trunk/libs/graph/doc/graph_theory_review.html | 36 ++++++++++++++++++
trunk/libs/graph/doc/table_of_contents.html | 1
trunk/libs/graph/example/Jamfile.v2 | 1
trunk/libs/graph/test/Jamfile.v2 | 3 +
8 files changed, 133 insertions(+), 28 deletions(-)
Added: trunk/boost/graph/buffer_concepts.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/buffer_concepts.hpp 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,91 @@
+// Copyright Daniel Trebbien 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or the copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_BUFFER_CONCEPTS_HPP
+#define BOOST_GRAPH_BUFFER_CONCEPTS_HPP 1
+#include <boost/concept_check.hpp>
+#include <boost/concept/detail/concept_def.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/typeof/typeof.hpp>
+#include <boost/type_traits/add_const.hpp>
+#include <boost/type_traits/add_reference.hpp>
+#include <boost/type_traits/remove_reference.hpp>
+
+namespace boost {
+
+ BOOST_concept(Buffer, (B))
+ {
+ typedef typename B::value_type value_type;
+ typedef typename B::size_type size_type;
+
+ BOOST_CONCEPT_USAGE(Buffer) {
+ typedef typename boost::add_reference<value_type>::type reference;
+
+ BOOST_CONCEPT_ASSERT((Assignable<value_type>));
+
+ buf.push(g_ct);
+ buf.pop();
+ reference t = buf.top();
+ boost::ignore_unused_variable_warning(t);
+ }
+
+ void const_constraints(const B& cbuf) {
+ typedef typename boost::add_const<typename boost::remove_reference<value_type>::type>::type& const_reference;
+
+ const_reference ct = cbuf.top();
+ s = cbuf.size();
+ if (cbuf.empty())
+ dummy = __LINE__;
+ }
+
+ int dummy;
+
+ static const value_type g_ct;
+ size_type s;
+ B buf;
+ };
+
+ BOOST_concept(UpdatableQueue, (Q))
+ : Buffer<Q>
+ {
+ BOOST_CONCEPT_USAGE(UpdatableQueue) {
+ q.update(g_ct);
+ }
+
+ void const_constraints(const Q& cq) {
+ if (cq.contains(g_ct))
+ dummy = __LINE__;
+ }
+
+ int dummy;
+
+ static const typename Buffer<Q>::value_type g_ct;
+ Q q;
+ };
+
+ BOOST_concept(KeyedUpdatableQueue, (Q))
+ : UpdatableQueue<Q>
+ {
+ typedef typename Q::key_type key_type;
+ typedef typename Q::key_map key_map;
+
+ BOOST_CONCEPT_USAGE(KeyedUpdatableQueue) {
+ BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<key_map, typename Buffer<Q>::value_type>));
+ }
+
+ void const_constraints(const Q& cq) {
+ km = cq.keys();
+ k = get(km, g_ct);
+ }
+
+ static const typename Buffer<Q>::value_type g_ct;
+ key_type k;
+ key_map km;
+ Q q;
+ };
+
+} // end `namespace boost`
+
+#endif // !BOOST_GRAPH_BUFFER_CONCEPTS_HPP
Modified: trunk/boost/graph/detail/d_ary_heap.hpp
==============================================================================
--- trunk/boost/graph/detail/d_ary_heap.hpp (original)
+++ trunk/boost/graph/detail/d_ary_heap.hpp 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -92,6 +92,8 @@
public:
typedef typename Container::size_type size_type;
typedef Value value_type;
+ typedef typename boost::property_traits<DistanceMap>::value_type key_type;
+ typedef DistanceMap key_map;
d_ary_heap_indirect(DistanceMap distance,
IndexInHeapPropertyMap index_in_heap,
@@ -164,6 +166,10 @@
verify_heap();
}
+ DistanceMap keys() const {
+ return distance;
+ }
+
private:
Compare compare;
Container data;
Modified: trunk/boost/graph/graph_concepts.hpp
==============================================================================
--- trunk/boost/graph/graph_concepts.hpp (original)
+++ trunk/boost/graph/graph_concepts.hpp 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -18,6 +18,7 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/numeric_values.hpp>
+#include <boost/graph/buffer_concepts.hpp>
#include <boost/concept_check.hpp>
#include <boost/detail/workaround.hpp>
@@ -493,28 +494,6 @@
Graph g;
};
- // This needs to move out of the graph library
- BOOST_concept(Buffer,(B))
- {
- BOOST_CONCEPT_USAGE(Buffer) {
- b.push(t);
- b.pop();
- typename B::value_type& v = b.top();
- const_constraints(b);
- ignore_unused_variable_warning(v);
- }
- void const_constraints(const B& cb) {
- const typename B::value_type& v = cb.top();
- n = cb.size();
- bool e = cb.empty();
- ignore_unused_variable_warning(v);
- ignore_unused_variable_warning(e);
- }
- typename B::size_type n;
- typename B::value_type t;
- B b;
- };
-
BOOST_concept(ColorValue,(C))
: EqualityComparable<C>
, DefaultConstructible<C>
@@ -614,7 +593,6 @@
using boost::concepts::EdgeIndexGraphConcept;
// Utility concepts
-using boost::concepts::BufferConcept;
using boost::concepts::ColorValueConcept;
using boost::concepts::BasicMatrixConcept;
using boost::concepts::NumericValueConcept;
Modified: trunk/boost/graph/named_function_params.hpp
==============================================================================
--- trunk/boost/graph/named_function_params.hpp (original)
+++ trunk/boost/graph/named_function_params.hpp 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -10,19 +10,23 @@
#ifndef BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP
#define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP
-#include <boost/graph/properties.hpp>
+#include <functional>
+#include <vector>
#include <boost/ref.hpp>
#include <boost/parameter/name.hpp>
#include <boost/parameter/binding.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/not.hpp>
#include <boost/type_traits/add_reference.hpp>
-#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
namespace boost {
+ struct parity_map_t { };
+ struct vertex_assignment_map_t { };
struct distance_compare_t { };
struct distance_combine_t { };
struct distance_inf_t { };
@@ -51,6 +55,8 @@
struct learning_constant_range_t { };
struct vertices_equivalent_t { };
struct edges_equivalent_t { };
+ struct index_in_heap_map_t { };
+ struct max_priority_queue_t { };
#define BOOST_BGL_DECLARE_NAMED_PARAMS \
BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \
@@ -62,6 +68,7 @@
BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex) \
BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality) \
BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality) \
+ BOOST_BGL_ONE_PARAM_CREF(parity_map, parity_map) \
BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color) \
BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color) \
BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity) \
@@ -72,6 +79,7 @@
BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index) \
BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1) \
BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2) \
+ BOOST_BGL_ONE_PARAM_CREF(vertex_assignment_map, vertex_assignment_map) \
BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor) \
BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare) \
BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine) \
@@ -98,7 +106,9 @@
BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range) \
BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \
BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent) \
- BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent)
+ BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent) \
+ BOOST_BGL_ONE_PARAM_CREF(index_in_heap_map, index_in_heap_map) \
+ BOOST_BGL_ONE_PARAM_REF(max_priority_queue, max_priority_queue)
template <typename T, typename Tag, typename Base = no_property>
struct bgl_named_params : public Base
@@ -541,7 +551,68 @@
boost::graph::keywords::tag::color_map,
default_color_type>
make_color_map_from_arg_pack(white_color);
- }
+
+ template <bool Exists, class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q>
+ struct priority_queue_maker_helper {
+ typedef Q priority_queue_type;
+
+ static priority_queue_type
+ make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q& q) {
+ return q;
+ }
+ };
+
+ template <class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q>
+ struct priority_queue_maker_helper<false, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, Q> {
+ typedef typename std::vector<ValueT>::size_type default_index_in_heap_type;
+ typedef typename map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::helper::map_type index_in_heap_map;
+ typedef boost::d_ary_heap_indirect<ValueT, 4, index_in_heap_map, typename map_maker<Graph, ArgPack, KeyMapTag, KeyT>::helper::map_type, Compare> priority_queue_type;
+
+ static priority_queue_type
+ make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q& q) {
+ return priority_queue_type(
+ map_maker<Graph, ArgPack, KeyMapTag, KeyT>::make_map(g, ap, defaultKey),
+ map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::make_map(g, ap, typename boost::property_traits<index_in_heap_map>::value_type(-1))
+ );
+ }
+ };
+
+ template <class Graph, class ArgPack, class KeyT, class ValueT, class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag, class Compare>
+ struct priority_queue_maker {
+ BOOST_STATIC_CONSTANT(
+ bool,
+ g_hasQ =
+ (parameter_exists<ArgPack, PriorityQueueTag>
+ ::value));
+ typedef priority_queue_maker_helper<g_hasQ, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare,
+ typename boost::remove_const<
+ typename boost::parameter::value_type<
+ ArgPack,
+ PriorityQueueTag,
+ boost::reference_wrapper<int>
+ >::type::type
+ >::type> helper;
+ typedef typename helper::priority_queue_type priority_queue_type;
+
+ static priority_queue_type make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey) {
+ return helper::make_queue(g, ap, defaultKey, ap[::boost::parameter::keyword<PriorityQueueTag>::instance | 0]);
+ }
+ };
+
+ template <class PriorityQueueTag, class KeyT, class ValueT, class Compare = std::less<KeyT>, class KeyMapTag = boost::graph::keywords::tag::distance_map, class IndexInHeapMapTag = boost::graph::keywords::tag::index_in_heap_map>
+ struct make_priority_queue_from_arg_pack_gen {
+ KeyT defaultKey;
+
+ make_priority_queue_from_arg_pack_gen(KeyT defaultKey_) : defaultKey(defaultKey_) { }
+
+ template <class Graph, class ArgPack>
+ typename priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type
+ operator()(const Graph& g, const ArgPack& ap) const {
+ return priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::make_queue(g, ap, defaultKey);
+ }
+ };
+
+ } // namespace detail
} // namespace boost
Added: trunk/boost/graph/stoer_wagner_min_cut.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/stoer_wagner_min_cut.hpp 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,240 @@
+// Copyright Daniel Trebbien 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or the copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
+#define BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP 1
+
+#include <cassert>
+#include <set>
+#include <vector>
+#include <boost/concept_check.hpp>
+#include <boost/concept/assert.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/buffer_concepts.hpp>
+#include <boost/graph/exception.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/detail/d_ary_heap.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/typeof/typeof.hpp>
+
+namespace boost {
+
+ namespace detail {
+
+ /**
+ * \brief Performs a phase of the Stoer-Wagner min-cut algorithm
+ *
+ * Performs a phase of the Stoer-Wagner min-cut algorithm.
+ *
+ * As described by Stoer & Wagner (1997), a phase is simply a maximum adjacency search
+ * (also called a maximum cardinality search), which results in the selection of two vertices
+ * \em s and \em t, and, as a side product, a minimum <em>s</em>-<em>t</em> cut of
+ * the input graph. Here, the input graph is basically \p g, but some vertices are virtually
+ * assigned to others as a way of viewing \p g as a graph with some sets of
+ * vertices merged together.
+ *
+ * This implementation is a translation of pseudocode by Professor Uri Zwick,
+ * School of Computer Science, Tel Aviv University.
+ *
+ * \pre \p g is a connected, undirected graph
+ * \param[in] g the input graph
+ * \param[in] assignments a read/write property map from each vertex to the vertex that it is assigned to
+ * \param[in] assignedVertices a list of vertices that are assigned to others
+ * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
+ * \param[out] pq a keyed, updatable max-priority queue
+ * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and "<em>t</em>"
+ * of the minimum <em>s</em>-<em>t</em> cut and the cut weight \em w
+ * of the minimum <em>s</em>-<em>t</em> cut.
+ * \see http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf
+ *
+ * \author Daniel Trebbien
+ * \date 2010-09-11
+ */
+ template <class UndirectedGraph, class VertexAssignmentMap, class WeightMap, class KeyedUpdatablePriorityQueue>
+ boost::tuple<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::property_traits<WeightMap>::value_type>
+ stoer_wagner_phase(const UndirectedGraph& g, VertexAssignmentMap assignments, const std::set<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor>& assignedVertices, WeightMap weights, KeyedUpdatablePriorityQueue& pq) {
+ typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+ typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+
+ assert(pq.empty());
+ typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
+
+ BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
+ if (v == get(assignments, v)) { // foreach u \in V do
+ put(keys, v, weight_type(0));
+
+ pq.push(v);
+ }
+ }
+
+ assert(pq.size() >= 2);
+
+ vertex_descriptor s, t;
+ weight_type w;
+ while (!pq.empty()) { // while PQ \neq {} do
+ const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
+ w = get(keys, u);
+ pq.pop();
+
+ s = t; t = u;
+
+ BGL_FORALL_OUTEDGES_T(u, e, g, UndirectedGraph) { // foreach (u, v) \in E do
+ const vertex_descriptor v = get(assignments, target(e, g));
+
+ if (pq.contains(v)) { // if v \in PQ then
+ put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
+ pq.update(v);
+ }
+ }
+
+ typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
+ for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
+ const vertex_descriptor uPrime = *assignedVertexIt;
+
+ if (get(assignments, uPrime) == u) {
+ BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph) { // foreach (u, v) \in E do
+ const vertex_descriptor v = get(assignments, target(e, g));
+
+ if (pq.contains(v)) { // if v \in PQ then
+ put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
+ pq.update(v);
+ }
+ }
+ }
+ }
+ }
+
+ return boost::make_tuple(s, t, w);
+ }
+
+ /**
+ * \brief Computes a min-cut of the input graph
+ *
+ * Computes a min-cut of the input graph using the Stoer-Wagner algorithm.
+ *
+ * \pre \p g is a connected, undirected graph
+ * \pre <code>pq.empty()</code>
+ * \param[in] g the input graph
+ * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
+ * \param[out] parities a writable property map from each vertex to a bool type object for
+ * distinguishing the two vertex sets of the min-cut
+ * \param[out] assignments a read/write property map from each vertex to a \c vertex_descriptor object. This
+ * map serves as work space, and no particular meaning should be derived from property values
+ * after completion of the algorithm.
+ * \param[out] pq a keyed, updatable max-priority queue
+ * \returns the cut weight of the min-cut
+ * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf
+ * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf
+ *
+ * \author Daniel Trebbien
+ * \date 2010-09-11
+ */
+ template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
+ typename boost::property_traits<WeightMap>::value_type
+ stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
+ BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<UndirectedGraph>));
+ BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<UndirectedGraph>));
+ typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+ typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
+ typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
+ BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<UndirectedGraph>::directed_category, boost::undirected_tag>));
+ BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
+ typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+ BOOST_CONCEPT_ASSERT((boost::WritablePropertyMapConcept<ParityMap, vertex_descriptor>));
+ typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+ BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
+ BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
+ BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
+
+ vertices_size_type n = num_vertices(g);
+ if (n < 2)
+ throw boost::bad_graph("the input graph must have at least two vertices.");
+ else if (!pq.empty())
+ throw std::invalid_argument("the max-priority queue must be empty initially.");
+
+ std::set<vertex_descriptor> assignedVertices;
+
+ // initialize `assignments` (all vertices are initially assigned to themselves)
+ BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
+ put(assignments, v, v);
+ }
+
+ vertex_descriptor s, t;
+ weight_type bestW;
+
+ boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
+ assert(s != t);
+ BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
+ put(parities, v, parity_type(v == t ? 1 : 0));
+ }
+ put(assignments, t, s);
+ assignedVertices.insert(t);
+ --n;
+
+ for (; n >= 2; --n) {
+ weight_type w;
+ boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
+ assert(s != t);
+
+ if (w < bestW) {
+ BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
+ put(parities, v, parity_type(get(assignments, v) == t ? 1 : 0));
+
+ if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
+ put(assignments, v, s);
+ }
+
+ bestW = w;
+ } else {
+ BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
+ if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
+ put(assignments, v, s);
+ }
+ }
+ put(assignments, t, s);
+ assignedVertices.insert(t);
+ }
+
+ assert(pq.empty());
+
+ return bestW;
+ }
+
+ } // end `namespace detail` within `namespace boost`
+
+ template <class UndirectedGraph, class WeightMap, class P, class T, class R>
+ inline typename boost::property_traits<WeightMap>::value_type
+ stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, const boost::bgl_named_params<P, T, R>& params) {
+ typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+ typedef typename std::vector<vertex_descriptor>::size_type heap_container_size_type;
+ typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+
+ typedef boost::bgl_named_params<P, T, R> params_type;
+ BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
+
+ BOOST_AUTO(pq, (boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> >(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)))(g, arg_pack)));
+
+ return boost::detail::stoer_wagner_min_cut(g,
+ weights,
+ choose_param(get_param(params, boost::parity_map_t()), boost::dummy_property_map()),
+ boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
+ pq
+ );
+ }
+
+ template <class UndirectedGraph, class WeightMap>
+ inline typename boost::property_traits<WeightMap>::value_type
+ stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights) {
+ return boost::stoer_wagner_min_cut(g, weights, boost::vertex_index_map(get(boost::vertex_index, g)));
+ }
+
+} // end `namespace boost`
+
+#include <boost/graph/iteration_macros_undef.hpp>
+
+#endif // !BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
Modified: trunk/libs/graph/doc/BUILD_DOCS.sh
==============================================================================
--- trunk/libs/graph/doc/BUILD_DOCS.sh (original)
+++ trunk/libs/graph/doc/BUILD_DOCS.sh 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -1,13 +1,22 @@
#!/bin/sh
# Copyright (C) 2009 The Trustees of Indiana University.
+# Copyright (C) 2010 Daniel Trebbien.
# Use, modification and distribution is subject to the Boost Software
# License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
# http://www.boost.org/LICENSE_1_0.txt)
-# Authors: Jeremiah Willcock, Andrew Lumsdaine
+# Authors: Jeremiah Willcock, Daniel Trebbien, Andrew Lumsdaine
for i in read_graphml read_graphviz write_graphml; do
rst2html.py -gdt --link-stylesheet --traceback --trim-footnote-reference-space --footnote-references=superscript --stylesheet=../../../rst.css $i.rst > $i.html
done
# Also see grid_graph_export_png.sh for figure conversions
+
+# Stoer-Wagner images from Daniel Trebbien
+fdp -s -n -Tgif -ostoer_wagner_imgs/digraph1.gif stoer_wagner_imgs/digraph1.dot
+fdp -s -n -Tgif -ostoer_wagner_imgs/digraph1-min-cut.gif stoer_wagner_imgs/digraph1-min-cut.dot
+fdp -s -n -Tgif -ostoer_wagner_imgs/stoer_wagner-example.gif stoer_wagner_imgs/stoer_wagner-example.dot
+fdp -s -n -Tgif -ostoer_wagner_imgs/stoer_wagner-example-c1.gif stoer_wagner_imgs/stoer_wagner-example-c1.dot
+fdp -s -n -Tgif -ostoer_wagner_imgs/stoer_wagner-example-min-cut.gif stoer_wagner_imgs/stoer_wagner-example-min-cut.dot
+dot -Tgif -ostoer_wagner_imgs/stoer_wagner.cpp.gif stoer_wagner_imgs/stoer_wagner.cpp.dot
Added: trunk/libs/graph/doc/KeyedUpdatableQueue.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/KeyedUpdatableQueue.html 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,99 @@
+<!DOCTYPE html>
+<!--
+ Copyright Daniel Trebbien 2010.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or the copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+-->
+<html>
+<head>
+<title>KeyedUpdatableQueue</title>
+</head>
+<body>
+<img src="../../../boost.png" alt="C++ Boost">
+
+<h2><a name="concept:KeyedUpdatableQueue">KeyedUpdatableQueue</a></h2>
+
+<p>A <i>KeyedUpdatableQueue</i> is a refinement of the UpdatableQueue concept.
+It requires that models order the contained values by their <i>keys</i>, to which
+values are mapped via a read/write key map.
+
+<h3>Notation</h3>
+
+<table>
+<tr> <td> <tt>Q</tt> </td> <td> is a type that models KeyedUpdatableQueue. </td></tr>
+<tr> <td> <tt>T</tt> </td> <td> is the value type of <tt>Q</tt>. </td></tr>
+</table>
+
+
+<h3>Members</h3>
+
+For a type to model the KeyedUpdatableQueue concept it must have the following members
+in addition to the members that are required of types that model UpdatableQueue:
+
+<p>
+
+<table border="1">
+
+<tr> <td><b>Member</b></td> <td><b>Description</b></td> </tr>
+
+<tr> <td> <tt>key_type</tt> </td>
+ <td> The type of keys that are associated with values </td>
+ </tr>
+
+<tr> <td> <tt>key_map</tt> </td>
+ <td> The key property map type. This type must model Read/Write Property Map. </td>
+ </tr>
+
+<tr> <td> <tt>key_map keys() const</tt> </td>
+ <td> Returns the key map </td>
+ </tr>
+
+</table>
+
+<h3>Concept Checking Class</h3>
+
+<p>boost/graph/buffer_concepts.hpp
+
+<pre>
+ template <class Q>
+ struct KeyedUpdatableQueueConcept
+ {
+ typedef typename Q::key_type key_type;
+ typedef typename Q::key_map key_map;
+
+ void constraints() {
+ function_requires< UpdatableQueue<Q> >();
+ function_requires< ReadWritePropertyMap< key_map, typename Buffer<Q>::value_type > >();
+ }
+
+ void const_constraints(const Q& cq) {
+ km = cq.keys();
+ k = get(km, g_ct);
+ }
+
+ static const typename Buffer<Q>::value_type g_ct;
+ key_type k;
+ key_map km;
+ Q q;
+ };
+</pre>
+
+<h3>Models</h3>
+
+<ul>
+<li><tt>boost::d_ary_heap_indirect</tt></a>
+</ul>
+
+<br>
+<hr>
+<table>
+<tr>
+<td>Copyright © 2010</td>
+<td>Daniel Trebbien (<a href="mailto:dtrebbien_at_[hidden]">dtrebbien_at_[hidden]</a>)
+</td>
+</tr>
+</table>
+
+</body>
+</html>
\ No newline at end of file
Added: trunk/libs/graph/doc/UpdatableQueue.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/UpdatableQueue.html 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,100 @@
+<!DOCTYPE html>
+<!--
+ Copyright Daniel Trebbien 2010.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or the copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+-->
+<html>
+<head>
+<title>UpdatableQueue</title>
+</head>
+<body>
+<img src="../../../boost.png" alt="C++ Boost">
+
+<h2><a name="concept:UpdatableQueue">UpdatableQueue</a></h2>
+
+<p>An <i>UpdatableQueue</i> is a refinement of the Buffer concept that additionally requires that the Buffer be updatable.
+
+<p>Implicit in the definition is an ordering of values. Though access to the order is not required, types that model UpdatableQueue must document how an object of the type orders values so that a program may change the position of a given value in the ordering. For example, an UpdatableQueue may choose to order values by using a property map, and a value <tt>v1</tt> is considered less than a value <tt>v2</tt> if <tt><nobr>get(pm, v1) < get(pm, v2)</nobr></tt>. A program can update the properties of values, thus changing the order of values in the UpdatableQueue, and notify the UpdatableQueue of the specific values that have a different position in the ordering by calling the <tt>update</tt> member of the UpdatableQueue on each.
+
+<p>A program that modifies the order must notify the UpdatableQueue of values that may have different positions in the ordering since they were inserted or last updated.
+
+<h3>Notation</h3>
+
+<table>
+<tr> <td> <tt>Q</tt> </td> <td> is a type that models UpdatableQueue. </td></tr>
+<tr> <td> <tt>T</tt> </td> <td> is the value type of <tt>Q</tt>. </td></tr>
+</table>
+
+
+<h3>Members</h3>
+
+For a type to model the UpdatableQueue concept it must have the following members
+in addition to the members that are required of types that model Buffer:
+
+<p>
+
+<table border="1">
+
+<tr> <td><b>Member</b></td> <td><b>Description</b></td> </tr>
+
+<tr> <td> <a name="concept:UpdatableQueue:update"><tt>void update(const T& t)</tt></a> </td>
+ <td> Informs the UpdatableQueue that the program has modified the position of <tt>t</tt> in the ordering </td>
+ </tr>
+
+<tr> <td> <tt><i>unspecified-bool-type</i> contains(const T& t) const</tt> </td>
+ <td> Returns whether the queue contains <tt>t</tt> </td>
+ </tr>
+
+</table>
+
+<h3>Concept Checking Class</h3>
+
+<p>boost/graph/buffer_concepts.hpp
+
+<pre>
+ template <class Q>
+ struct UpdatableQueueConcept
+ {
+ void constraints() {
+ function_requires< Buffer<Q> >();
+
+ q.update(g_ct);
+ }
+
+ void const_constraints(const Q& cq) {
+ if (cq.contains(g_ct));
+ }
+
+ static const typename Buffer<Q>::value_type g_ct;
+ Q q;
+ };
+</pre>
+
+<h3>Futher Refinements</h3>
+
+<ul>
+<li>UpdatablePriorityQueue
+<li>KeyedUpdatableQueue
+</ul>
+
+<h2><a name="concept:UpdatablePriorityQueue">UpdatablePriorityQueue</a></h2>
+<p>An <i>UpdatablePriorityQueue</i> is a slight refinement of UpdatableQueue
+that imposes the requirement that a program may not increase the position of a value that is held in the queue. That is,
+if a value <tt>v</tt> had position <i>n</i> in the ordering, a program may update the position of <tt>v</tt> only to 0, 1, ..., <i>n</i> - 1, or <i>n</i>, where 0 is the top of the queue.
+
+<p>The behavior when a program attempts to increase a value's position in the ordering is undefined.
+
+<br>
+<hr>
+<table>
+<tr>
+<td>Copyright © 2010</td>
+<td>Daniel Trebbien (<a href="mailto:dtrebbien_at_[hidden]">dtrebbien_at_[hidden]</a>)
+</td>
+</tr>
+</table>
+
+</body>
+</html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/graph_theory_review.html
==============================================================================
--- trunk/libs/graph/doc/graph_theory_review.html (original)
+++ trunk/libs/graph/doc/graph_theory_review.html 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -1,6 +1,7 @@
<HTML>
<!--
Copyright (c) Jeremy Siek 2000
+ Copyright (c) Daniel Trebbien 2010
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
@@ -578,6 +579,41 @@
<a href="./bibliography.html#karzanov74:_deter">Karzanov</a>.
+<h2><a name="sec:min-cut-algorithms">Minimum Cut Algorithms</a></h2>
+
+<h3>Undirected Graphs</h3>
+<p>Given an undirected graph <i>G</i> = (<i>V</i>, <i>E</i>), a <em>cut</em> of <i>G</i> is a partition of the vertices into two, non-empty sets <i>X</i> and <img src="stoer_wagner_imgs/6e4.gif" alt="\overline{X} = V - X" style="vertical-align: middle; padding-bottom: 2px">. The <i>weight</i> of a cut is defined as the number of edges between sets <i>X</i> and <img src="stoer_wagner_imgs/f79.gif" alt="\overline{X}" style="vertical-align: middle; padding-bottom: 3px"> if <i>G</i> is unweighted, or the sum of the weights of all edges between sets <i>X</i> and <img src="stoer_wagner_imgs/f79.gif" alt="\overline{X}" style="vertical-align: middle; padding-bottom: 3px"> if <i>G</i> is weighted (each edge has an associated, non-negative weight).
+
+<p>When the weight of a cut <img src="stoer_wagner_imgs/8b7.gif" alt="C = \{X, \overline{X}\}" style="vertical-align: middle"> is minimal for a graph <i>G</i> (that is, no other cut of <i>G</i> has a lesser weight), then the cut is known as a <em>minimum cut</em> or a <em>min-cut</em>. For example, given this weighted graph:
+
+<p>
+
+<p>The cut {{0, 6}, {3, 2, 7, 1, 5, 4}} has weight 13:
+
+<p>
+
+<p>And the min-cut is {{0, 1, 4, 5}, {2, 3, 6, 7}} (weight 4):
+
+<p>
+
+<p>Unlike this example, a graph will sometimes have multiple min-cuts, all of equal weight. A minimum cut algorithm determines one of them as well as the min-cut weight.
+
+<h3>Directed Graphs</h3>
+
+<p>Given a directed graph <i>G</i> = (<i>V</i>, <i>E</i>), a <em>cut</em> of <i>G</i> is a partition of the vertices into two, non-empty sets <i>S</i> and <i>T</i> where <i>S</i> is known as the set of <em>source vertices</em> and <i>T</i> is known as the set of <em>sink vertices</em>. The <em>capacity</em> of a cut <i>C</i> = (<i>S</i>, <i>T</i>) is the number of edges from a vertex in <i>S</i> to a vertex in <i>T</i> if <i>G</i> is unweighted, or the sum of weights of edges from a vertex in <i>S</i> to a vertex in <i>T</i> if <i>G</i> is weighted.
+
+<p>When the capacity of a cut <i>C</i> = (<i>S</i>, <i>T</i>) of a directed graph is minimal (that is, no other cut of <i>G</i> has lesser capacity), then <i>C</i> is known as a <em>minimum cut</em> or <em>min-cut</em>.
+
+<p>For example, given this directed graph:
+
+<p>
+
+<p>A min-cut is:
+
+<p>
+
+<p>where <i>S</i> = {0}, <i>T</i> = {1, 2, 3}, and the min-cut capacity is 1.
+
<br>
<HR>
<TABLE>
Added: trunk/libs/graph/doc/stoer_wagner_imgs/6e4.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/8b7.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/digraph1-min-cut.dot
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/stoer_wagner_imgs/digraph1-min-cut.dot 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,13 @@
+digraph {
+ edge [ len=1.8 ];
+ 0 [ pos="148,246z" ];
+ 1 [ pos="255,30", style="filled", fillcolor=gray ];
+ 2 [ pos="148,138", style="filled", fillcolor=gray ];
+ 3 [ pos="41,138", style="filled", fillcolor=gray ];
+ 1 -> 0 [ label="5" ];
+ 1 -> 2 [ label="3" ];
+ 2 -> 3 [ label="8" ];
+ 3 -> 0 [ headlabel="3", labeldistance=4.5, labelangle=0.2854 ];
+ 0 -> 3 [ headlabel="1", labeldistance=4.5, labelangle=-0.2854, color=red, fontcolor=red, style=dotted ];
+ 3 -> 1 [ label="2", len=2.8 ];
+}
\ No newline at end of file
Added: trunk/libs/graph/doc/stoer_wagner_imgs/digraph1-min-cut.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/digraph1.dot
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/stoer_wagner_imgs/digraph1.dot 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,13 @@
+digraph {
+ edge [ len=1.8 ];
+ 0 [ pos="148,246z" ];
+ 1 [ pos="255,30" ];
+ 2 [ pos="148,138" ];
+ 3 [ pos="41,138" ];
+ 1 -> 0 [ label="5" ];
+ 1 -> 2 [ label="3" ];
+ 2 -> 3 [ label="8" ];
+ 3 -> 0 [ headlabel="3", labeldistance=4.5, labelangle=0.2854 ];
+ 0 -> 3 [ headlabel="1", labeldistance=4.5, labelangle=-0.2854 ];
+ 3 -> 1 [ label="2", len=2.8 ];
+}
\ No newline at end of file
Added: trunk/libs/graph/doc/stoer_wagner_imgs/digraph1.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/f79.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-c1.dot
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-c1.dot 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,23 @@
+graph {
+ edge [ len=1.2 ];
+ 0 [ pos="42,73", style="filled", fillcolor="#333399", fontcolor=white ];
+ 1 [ pos="96,139", style="filled", fillcolor="#9999ff" ];
+ 2 [ pos="113,209", style="filled", fillcolor="#9999ff" ];
+ 3 [ pos="179,279", style="filled", fillcolor="#9999ff" ];
+ 4 [ pos="143,30", style="filled", fillcolor="#9999ff" ];
+ 5 [ pos="211,100", style="filled", fillcolor="#9999ff" ];
+ 6 [ pos="228,175", style="filled", fillcolor="#333399", fontcolor=white ];
+ 7 [ pos="282,241", style="filled", fillcolor="#9999ff" ];
+ 0 -- 1 [ label="2", color=red, fontcolor=red, style=dotted ];
+ 1 -- 2 [ label="3", len=1 ];
+ 2 -- 3 [ label="4" ];
+ 0 -- 4 [ label="3", color=red, fontcolor=red, style=dotted ];
+ 1 -- 4 [ label="2", len=1.3 ];
+ 1 -- 5 [ label="2" ];
+ 2 -- 6 [ label="2", color=red, fontcolor=red, style=dotted ];
+ 3 -- 6 [ label="2", len=1.3, color=red, fontcolor=red, style=dotted ];
+ 3 -- 7 [ label="2" ];
+ 4 -- 5 [ label="3" ];
+ 5 -- 6 [ label="1", len=1.1, color=red, fontcolor=red, style=dotted ];
+ 6 -- 7 [ label="3", color=red, fontcolor=red, style=dotted ];
+}
\ No newline at end of file
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-c1.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-min-cut.dot
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-min-cut.dot 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,23 @@
+graph {
+ edge [ len=1.2 ];
+ 0 [ pos="42,73", style="filled", fillcolor="#333399", fontcolor=white ];
+ 1 [ pos="96,139", style="filled", fillcolor="#333399", fontcolor=white ];
+ 2 [ pos="113,209", style="filled", fillcolor="#9999ff" ];
+ 3 [ pos="179,279", style="filled", fillcolor="#9999ff" ];
+ 4 [ pos="143,30", style="filled", fillcolor="#333399", fontcolor=white ];
+ 5 [ pos="211,100", style="filled", fillcolor="#333399", fontcolor=white ];
+ 6 [ pos="228,175", style="filled", fillcolor="#9999ff" ];
+ 7 [ pos="282,241", style="filled", fillcolor="#9999ff" ];
+ 0 -- 1 [ label="2" ];
+ 1 -- 2 [ label="3", len=1, color=red, fontcolor=red, style=dotted ];
+ 2 -- 3 [ label="4" ];
+ 0 -- 4 [ label="3" ];
+ 1 -- 4 [ label="2", len=1.3 ];
+ 1 -- 5 [ label="2" ];
+ 2 -- 6 [ label="2" ];
+ 3 -- 6 [ label="2", len=1.3 ];
+ 3 -- 7 [ label="2" ];
+ 4 -- 5 [ label="3" ];
+ 5 -- 6 [ label="1", len=1.1, color=red, fontcolor=red, style=dotted ];
+ 6 -- 7 [ label="3" ];
+}
\ No newline at end of file
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example-min-cut.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example.dot
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example.dot 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,23 @@
+graph {
+ edge [ len=1.2 ];
+ 0 [ pos="42,73" ];
+ 1 [ pos="96,139" ];
+ 2 [ pos="113,209" ];
+ 3 [ pos="179,279" ];
+ 4 [ pos="143,30" ];
+ 5 [ pos="211,100" ];
+ 6 [ pos="228,175" ];
+ 7 [ pos="282,241" ];
+ 0 -- 1 [ label="2" ];
+ 1 -- 2 [ label="3", len=1 ];
+ 2 -- 3 [ label="4" ];
+ 0 -- 4 [ label="3" ];
+ 1 -- 4 [ label="2", len=1.3 ];
+ 1 -- 5 [ label="2" ];
+ 2 -- 6 [ label="2" ];
+ 3 -- 6 [ label="2", len=1.3 ];
+ 3 -- 7 [ label="2" ];
+ 4 -- 5 [ label="3" ];
+ 5 -- 6 [ label="1", len=1.1 ];
+ 6 -- 7 [ label="3" ];
+}
\ No newline at end of file
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner-example.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner.cpp.dot
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner.cpp.dot 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,25 @@
+graph {
+ 0 [ style="filled", fillcolor="#9999ff" ];
+ 1 [ style="filled", fillcolor="#333399", fontcolor=white ];
+ 2 [ style="filled", fillcolor="#9999ff" ];
+ 3 [ style="filled", fillcolor="#9999ff" ];
+ 4 [ style="filled", fillcolor="#9999ff" ];
+ 5 [ style="filled", fillcolor="#333399", fontcolor=white ];
+ 6 [ style="filled", fillcolor="#9999ff" ];
+ 7 [ style="filled", fillcolor="#9999ff" ];
+ 3 -- 4 [ taillabel="4" ];
+ 3 -- 6 [ taillabel="3" ];
+ 3 -- 5 [ taillabel="1" ];
+ 0 -- 4 [ taillabel="3" ];
+ 0 -- 1 [ taillabel="1" ];
+ 0 -- 6 [ taillabel="2" ];
+ 0 -- 7 [ taillabel="6" ];
+ 0 -- 5 [ taillabel="1" ];
+ 0 -- 2 [ taillabel="8" ];
+ 4 -- 1 [ label="1" ];
+ 1 -- 6 [ label="1" ];
+ 1 -- 5 [ label="80", len=4 ];
+ 6 -- 7 [ label="2" ];
+ 7 -- 5 [ label="1" ];
+ 5 -- 2 [ label="1" ];
+}
\ No newline at end of file
Added: trunk/libs/graph/doc/stoer_wagner_imgs/stoer_wagner.cpp.gif
==============================================================================
Binary file. No diff available.
Added: trunk/libs/graph/doc/stoer_wagner_min_cut.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/stoer_wagner_min_cut.html 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,166 @@
+<!DOCTYPE html>
+<!--
+ Copyright Daniel Trebbien 2010.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or the copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+-->
+<html>
+<head>
+<title>Boost Graph Library: Stoer–Wagner Min-Cut</title>
+</head>
+<body>
+<img src="../../../boost.png" alt="C++ Boost">
+
+<h1><a name="sec:stoer_wagner"><tt>stoer_wagner_min_cut</tt></a></h1>
+<table border="0" cellspacing="0" style="float: right">
+<caption align="bottom">A min-cut of a weighted graph<br>having min-cut weight 4</caption>
+<tr><td style="border: #666 1px solid"><img src="stoer_wagner_imgs/stoer_wagner-example-min-cut.gif" width="376"></td></tr>
+</table>
+<pre>
+template <class UndirectedGraph, class WeightMap, class P, class T, class R>
+weight_type
+stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights,
+ const bgl_named_params<P, T, R>& params = <i>all defaults</i>);
+</pre>
+
+<p>The <tt>stoer_wagner_min_cut</tt> function determines a min-cut and the min-cut weight of a connected, undirected graph.
+
+<p>A <em>cut</em> of a graph <i>G</i> is a partition of the vertices into two, non-empty sets. The <em>weight</em> of such a partition is the number of edges between the two sets if <i>G</i> is unweighted, or the sum of the weights of all edges between the two sets if <i>G</i> is weighted. A <em>min-cut</em> is a cut having the least weight.
+
+<p>Sometimes a graph has multiple min-cuts, but all have the same weight. The <tt>stoer_wagner_min_cut</tt> function determines exactly one of the min-cuts as well as its weight.
+
+<h3>Where Defined</h3>
+<p>boost/graph/stoer_wagner_min_cut.hpp
+
+<h3>Parameters</h3>
+
+<p>IN: <tt>const UndirectedGraph& g</tt>
+<blockquote>
+ A connected, undirected graph. The graph type must be a model of
+ Vertex List Graph
+ and Incidence Graph.
+</blockquote>
+
+<p>IN: <tt>WeightMap weights</tt>
+<blockquote>
+ The weight or length of each edge in the graph. The <tt>WeightMap</tt> type must be a model
+ of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
+ Property Map</a> and its value type must be <a class="external" href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than
+ Comparable</a> and summable. The key type of this map needs to be the graph's
+ edge descriptor type.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+<p>OUT: <tt>parity_map(ParityMap parities)</tt>
+<blockquote>
+ The algorithm computes a min-cut, which divides the set of vertices into two,
+ non-empty sets. The <tt>stoer_wagner_min_cut</tt> function records which of
+ the two sets that each vertex belongs to by setting the parity to <tt>true</tt>
+ (representing one set) or <tt>false</tt> (for the other). <tt>ParityMap</tt>
+ must be a model of a <a href="../../property_map/doc/WritablePropertyMap.html">Writable
+ Property Map</a> and its value type should be a bool type. The
+ key type must be the graph's vertex descriptor type.<br>
+ <b>Default:</b> <tt>boost::dummy_property_map</tt>
+</blockquote>
+
+<h4>Expert Parameters</h4>
+
+<p>IN: <tt>vertex_index_map(VertexIndexMap vertexIndices)</tt>
+<blockquote>
+ This maps each vertex to an integer in the range [0, <tt>num_vertices(g)</tt>). This
+ is only necessary if the default is used for the assignment, index-in-heap, or distance maps.
+ <tt>VertexIndexMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+ Map</a>. The value type of the map must be an integer type. The
+ key type must be the graph's vertex descriptor type.<br>
+ <b>Default:</b> <tt>get(boost::vertex_index, g)</tt>
+</blockquote>
+
+<p>UTIL: <tt>assignment_map(AssignmentMap assignments)</tt>
+<blockquote>
+ <tt>AssignmentMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
+ Map</a>. The key and value types must be the graph's vertex descriptor type.<br>
+ <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a <tt>std::vector</tt>
+ of <tt>num_vertices(g)</tt> vertex descriptors and <tt>vertexIndices</tt> for
+ the index map.
+</blockquote>
+
+<p>UTIL: <tt>max_priority_queue(MaxPriorityQueue& pq)</tt>
+<blockquote>
+ <tt>MaxPriorityQueue</tt> must be a model of Keyed Updatable Queue
+ and a max-Updatable Priority Queue.
+ The value type must be the graph's vertex descriptor and the key type must be
+ the weight type.
+ <b>Default:</b> A <tt>boost::d_ary_heap_indirect</tt> using a default index-in-heap
+ and distance map.
+</blockquote>
+
+<p>UTIL: <tt>index_in_heap_map(IndexInHeapMap indicesInHeap)</tt>
+<blockquote>
+ This parameter only has an effect when the default max-priority queue is used.<br>
+ <tt>IndexInHeapMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
+ Map</a>. The key type must be the graph's vertex descriptor type. The value type
+ must be a size type (<tt>typename std::vector<vertex_descriptor>::size_type</tt>).<br>
+ <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a <tt>std::vector</tt>
+ of <tt>num_vertices(g)</tt> size type objects and <tt>vertexIndices</tt> for
+ the index map.
+</blockquote>
+
+<p>UTIL: <tt>distance_map(DistanceMap wAs)</tt>
+<blockquote>
+ This parameter only has an effect when the default max-priority queue is used.<br>
+ <tt>DistanceMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
+ Map</a>. The key type must be the graph's vertex descriptor type. The value type
+ must be the weight type (<tt>typename boost::property_traits<WeightMap>::value_type</tt>).<br>
+ <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a <tt>std::vector</tt>
+ of <tt>num_vertices(g)</tt> weight type objects and <tt>vertexIndices</tt> for
+ the index map.
+</blockquote>
+
+<h3>Returns</h3>
+<p>The weight of the min-cut
+
+<h3>Throws</h3>
+
+<p><tt>bad_graph</tt>
+<blockquote>
+ If <tt>num_vertices(g)</tt> is less than 2
+</blockquote>
+
+<p><tt>std::invalid_argument</tt>
+<blockquote>
+ If a max-priority queue is given as an argument and it is not empty
+</blockquote>
+
+<h3>Complexity</h3>
+
+<p>The time complexity is <i>O</i>(<i>V</i>·<i>E</i> + <i>V</i><sup>2</sup> log <i>V</i>).
+
+<h3>Example</h3>
+
+<p>The file examples/stoer_wagner.cpp contains an example of calculating a min-cut of a weighted, undirected graph and its min-cut weight.
+
+<h3>References</h3>
+<ul>
+<li>Mehlhorn, Kurt and Christian Uhrig (1995). <q>The minimum cut algorithm of Stoer and Wagner</q>.
+<li>Stoer, Mechthild and Frank Wagner (1997). <q>A simple min-cut algorithm</q>. <i>Journal of the ACM</i> <b>44</b> (4), 585–591.
+<li>Zwick, Uri (2008). <q>Global minimum cuts</q>.
+</ul>
+
+<br>
+<hr>
+<table>
+<tr>
+<td>Copyright © 2010</td>
+<td>Daniel Trebbien (<a href="mailto:dtrebbien_at_[hidden]">dtrebbien_at_[hidden]</a>)
+</td>
+</tr>
+</table>
+
+</body>
+</html>
Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -208,6 +208,7 @@
</li>
<li>boykov_kolmogorov_max_flow</li>
<LI>edmonds_maximum_cardinality_matching
+ <LI>stoer_wagner_min_cut
</OL>
<li>Sparse Matrix Ordering Algorithms
Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 (original)
+++ trunk/libs/graph/example/Jamfile.v2 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -29,3 +29,4 @@
# exe cc-internet : cc-internet.cpp ../build//boost_graph ;
exe implicit_graph : implicit_graph.cpp ;
exe astar_maze : astar_maze.cpp ;
+exe stoer_wagner : stoer_wagner.cpp ;
Added: trunk/libs/graph/example/stoer_wagner.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/stoer_wagner.cpp 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,71 @@
+// Copyright Daniel Trebbien 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or the copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cassert>
+#include <cstddef>
+#include <iostream>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/one_bit_color_map.hpp>
+#include <boost/graph/stoer_wagner_min_cut.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/typeof/typeof.hpp>
+
+struct edge_t
+{
+ unsigned long first;
+ unsigned long second;
+};
+
+// A graphic of the min-cut is available at <http://www.boost.org/doc/libs/release/libs/graph/doc/stoer_wagner.cpp.gif>
+int main()
+{
+ using namespace std;
+
+ typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
+ boost::no_property, boost::property<boost::edge_weight_t, int> > undirected_graph;
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::property_map<undirected_graph, boost::edge_weight_t>::type weight_map_type;
+ typedef boost::property_traits<weight_map_type>::value_type weight_type;
+
+ // define the 16 edges of the graph. {3, 4} means an undirected edge between vertices 3 and 4.
+ edge_t edges[] = {{3, 4}, {3, 6}, {3, 5}, {0, 4}, {0, 1}, {0, 6}, {0, 7},
+ {0, 5}, {0, 2}, {4, 1}, {1, 6}, {1, 5}, {6, 7}, {7, 5}, {5, 2}, {3, 4}};
+
+ // for each of the 16 edges, define the associated edge weight. ws[i] is the weight for the edge
+ // that is described by edges[i].
+ weight_type ws[] = {0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4};
+
+ // construct the graph object. 8 is the number of vertices, which are numbered from 0
+ // through 7, and 16 is the number of edges.
+ undirected_graph g(edges, edges + 16, ws, 8, 16);
+
+ // define a property map, `parities`, that will store a boolean value for each vertex.
+ // Vertices that have the same parity after `stoer_wagner_min_cut` runs are on the same side of the min-cut.
+ BOOST_AUTO(parities, boost::make_one_bit_color_map(num_vertices(g), get(boost::vertex_index, g)));
+
+ // run the Stoer-Wagner algorithm to obtain the min-cut weight. `parities` is also filled in.
+ int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g), boost::parity_map(parities));
+
+ cout << "The min-cut weight of G is " << w << ".\n" << endl;
+ assert(w == 7);
+
+ cout << "One set of vertices consists of:" << endl;
+ size_t i;
+ for (i = 0; i < num_vertices(g); ++i) {
+ if (get(parities, i))
+ cout << i << endl;
+ }
+ cout << endl;
+
+ cout << "The other set of vertices consists of:" << endl;
+ for (i = 0; i < num_vertices(g); ++i) {
+ if (!get(parities, i))
+ cout << i << endl;
+ }
+ cout << endl;
+
+ return EXIT_SUCCESS;
+}
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -9,6 +9,8 @@
import modules ;
+path-constant TEST_DIR : . ;
+
path-constant PLANAR_INPUT_FILES : ./planar_input_graphs ;
path-constant CYCLE_RATIO_INPUT_FILE : ./cycle_ratio_s382.90.dot ;
@@ -118,6 +120,7 @@
[ run incremental_components_test.cpp ]
[ run random_spanning_tree_test.cpp ../build//boost_graph ]
[ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
+ [ run stoer_wagner_test.cpp ../../test/build : $(TEST_DIR) ]
;
# Run SDB tests only when -sSDB= is set.
Added: trunk/libs/graph/test/prgen_input_graphs/prgen_20_70_2.net
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/prgen_input_graphs/prgen_20_70_2.net 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,137 @@
+c NOIGEN min-cut problem
+p cut 20 135
+a 1 2 180
+a 1 6 880
+a 1 7 1640
+a 1 9 1620
+a 1 10 80
+a 1 11 98
+a 1 12 31
+a 1 13 60
+a 1 16 91
+a 1 17 9
+a 1 18 48
+a 1 19 91
+a 1 20 41
+a 2 3 1300
+a 2 4 620
+a 2 5 1540
+a 2 8 1000
+a 2 9 1100
+a 2 10 620
+a 2 11 68
+a 2 15 64
+a 2 16 55
+a 2 17 31
+a 2 19 29
+a 2 20 98
+a 3 4 1540
+a 3 6 1100
+a 3 8 1340
+a 3 9 1840
+a 3 10 840
+a 3 14 48
+a 3 15 88
+a 3 17 81
+a 3 18 42
+a 3 19 98
+a 3 20 70
+a 4 5 200
+a 4 6 560
+a 4 7 1800
+a 4 9 1220
+a 4 10 1640
+a 4 11 62
+a 4 12 75
+a 4 14 31
+a 4 16 44
+a 4 17 54
+a 4 19 39
+a 5 6 1460
+a 5 8 1020
+a 5 10 1340
+a 5 11 12
+a 5 12 21
+a 5 13 72
+a 5 14 68
+a 5 15 2
+a 5 16 12
+a 5 17 28
+a 5 18 87
+a 6 7 640
+a 6 8 380
+a 6 9 940
+a 6 10 1140
+a 6 12 21
+a 6 13 17
+a 6 15 54
+a 6 17 92
+a 6 18 5
+a 6 19 34
+a 6 20 47
+a 7 8 1980
+a 7 9 1340
+a 7 10 820
+a 7 12 68
+a 7 13 54
+a 7 14 4
+a 7 15 32
+a 7 17 54
+a 7 20 18
+a 8 9 500
+a 8 11 55
+a 8 12 100
+a 8 13 35
+a 8 14 65
+a 8 15 78
+a 8 17 48
+a 8 18 11
+a 8 19 14
+a 8 20 2
+a 9 10 180
+a 9 13 92
+a 9 14 39
+a 9 15 17
+a 9 16 2
+a 9 17 57
+a 9 19 72
+a 10 11 8
+a 10 12 65
+a 10 14 97
+a 10 15 1
+a 10 16 78
+a 10 17 94
+a 10 19 28
+a 10 20 1
+a 11 12 1520
+a 11 13 1300
+a 11 15 940
+a 11 16 1400
+a 11 17 1600
+a 11 18 100
+a 11 20 100
+a 12 13 1320
+a 12 15 780
+a 12 17 160
+a 12 18 1680
+a 12 19 560
+a 12 20 540
+a 13 14 1220
+a 13 18 580
+a 13 19 180
+a 14 15 1580
+a 14 16 1220
+a 14 17 940
+a 14 18 840
+a 15 16 920
+a 15 17 300
+a 15 19 1820
+a 16 17 1020
+a 16 19 1200
+a 16 20 280
+a 17 18 520
+a 17 19 20
+a 17 20 540
+a 18 19 1980
+a 18 20 1420
+a 19 20 300
Added: trunk/libs/graph/test/prgen_input_graphs/prgen_50_40_2.net
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/prgen_input_graphs/prgen_50_40_2.net 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,517 @@
+c NOIGEN min-cut problem
+p cut 50 515
+a 1 2 450
+a 1 6 3850
+a 1 10 350
+a 1 12 2750
+a 1 17 850
+a 1 18 4200
+a 1 20 3600
+a 1 21 4350
+a 1 22 2750
+a 1 26 87
+a 1 27 97
+a 1 28 55
+a 1 34 97
+a 1 35 55
+a 1 37 52
+a 1 39 57
+a 1 41 97
+a 1 45 75
+a 1 49 84
+a 2 3 450
+a 2 5 3750
+a 2 9 2450
+a 2 17 2750
+a 2 19 3850
+a 2 20 4750
+a 2 22 3450
+a 2 24 3350
+a 2 26 90
+a 2 29 22
+a 2 30 37
+a 2 33 4
+a 2 34 22
+a 2 35 49
+a 2 40 34
+a 2 41 82
+a 2 42 99
+a 2 44 37
+a 2 45 30
+a 2 47 95
+a 2 50 10
+a 3 4 3800
+a 3 5 4100
+a 3 6 100
+a 3 8 3600
+a 3 11 4750
+a 3 12 350
+a 3 13 2850
+a 3 15 4750
+a 3 18 1600
+a 3 21 4850
+a 3 23 3100
+a 3 27 84
+a 3 28 19
+a 3 29 25
+a 3 30 4
+a 3 35 69
+a 3 36 30
+a 3 37 4
+a 3 38 99
+a 3 46 2
+a 3 50 49
+a 4 5 4950
+a 4 6 3000
+a 4 9 4100
+a 4 12 500
+a 4 14 500
+a 4 15 4200
+a 4 17 3450
+a 4 19 750
+a 4 21 2450
+a 4 22 2350
+a 4 23 4850
+a 4 27 52
+a 4 28 17
+a 4 30 52
+a 4 32 82
+a 4 33 75
+a 4 37 27
+a 4 44 25
+a 4 46 2
+a 4 47 47
+a 4 48 2
+a 5 6 1350
+a 5 12 200
+a 5 13 2850
+a 5 16 1250
+a 5 17 4950
+a 5 19 3750
+a 5 21 2100
+a 5 22 2350
+a 5 23 3250
+a 5 26 57
+a 5 30 4
+a 5 33 65
+a 5 36 55
+a 5 41 69
+a 5 43 32
+a 5 47 87
+a 5 48 75
+a 5 49 62
+a 5 50 25
+a 6 7 1900
+a 6 8 4750
+a 6 15 950
+a 6 16 2850
+a 6 22 950
+a 6 26 60
+a 6 27 72
+a 6 29 49
+a 6 32 32
+a 6 33 97
+a 6 36 97
+a 6 37 75
+a 6 41 60
+a 6 42 42
+a 6 43 34
+a 6 45 72
+a 6 46 27
+a 7 8 150
+a 7 11 3600
+a 7 12 3850
+a 7 16 3750
+a 7 18 2000
+a 7 19 500
+a 7 24 4100
+a 7 25 600
+a 7 26 90
+a 7 27 67
+a 7 29 10
+a 7 30 67
+a 7 31 90
+a 7 32 10
+a 7 33 12
+a 7 34 77
+a 7 38 17
+a 7 39 49
+a 7 40 19
+a 7 41 67
+a 7 42 67
+a 7 43 62
+a 7 44 52
+a 7 46 10
+a 7 47 52
+a 7 49 22
+a 8 9 2050
+a 8 15 1250
+a 8 16 600
+a 8 18 1850
+a 8 21 4200
+a 8 22 4750
+a 8 27 69
+a 8 28 40
+a 8 32 40
+a 8 37 82
+a 8 38 65
+a 8 39 99
+a 8 41 65
+a 8 43 22
+a 8 50 19
+a 9 10 2600
+a 9 16 4000
+a 9 19 3100
+a 9 31 2
+a 9 32 62
+a 9 34 62
+a 9 36 40
+a 9 39 80
+a 9 40 69
+a 9 41 25
+a 9 42 22
+a 9 48 82
+a 9 50 97
+a 10 11 4400
+a 10 12 4100
+a 10 17 4200
+a 10 18 4850
+a 10 19 2000
+a 10 20 4750
+a 10 23 1600
+a 10 28 30
+a 10 29 82
+a 10 34 97
+a 10 38 34
+a 10 40 47
+a 10 46 90
+a 10 49 65
+a 11 12 4200
+a 11 13 3750
+a 11 19 850
+a 11 20 3000
+a 11 21 2250
+a 11 23 1700
+a 11 26 82
+a 11 27 67
+a 11 30 4
+a 11 31 19
+a 11 32 27
+a 11 35 62
+a 11 36 19
+a 11 37 75
+a 11 38 95
+a 11 39 49
+a 11 40 7
+a 11 41 77
+a 11 42 77
+a 11 43 40
+a 11 44 82
+a 11 47 12
+a 11 49 45
+a 12 13 4500
+a 12 18 4500
+a 12 19 1600
+a 12 20 3750
+a 12 21 350
+a 12 22 4200
+a 12 24 1100
+a 12 27 57
+a 12 30 55
+a 12 33 82
+a 12 34 67
+a 12 36 90
+a 12 39 75
+a 12 41 52
+a 12 45 84
+a 12 46 55
+a 12 48 34
+a 12 49 34
+a 12 50 19
+a 13 14 600
+a 13 15 3600
+a 13 19 2450
+a 13 22 350
+a 13 25 3350
+a 13 27 37
+a 13 29 37
+a 13 31 15
+a 13 33 19
+a 13 36 57
+a 13 37 15
+a 13 38 80
+a 13 40 52
+a 13 45 25
+a 13 50 37
+a 14 15 2100
+a 14 16 2350
+a 14 21 3000
+a 14 22 2100
+a 14 25 1500
+a 14 26 65
+a 14 28 34
+a 14 32 87
+a 14 33 22
+a 14 34 52
+a 14 35 32
+a 14 37 2
+a 14 40 60
+a 14 41 62
+a 14 42 62
+a 14 43 62
+a 14 44 55
+a 14 46 32
+a 14 50 84
+a 15 16 1850
+a 15 17 3750
+a 15 18 4600
+a 15 20 4100
+a 15 21 4600
+a 15 22 4600
+a 15 23 1100
+a 15 24 2600
+a 15 28 60
+a 15 31 30
+a 15 32 84
+a 15 37 65
+a 15 39 12
+a 15 41 87
+a 15 42 72
+a 15 44 97
+a 15 45 25
+a 15 46 82
+a 15 47 4
+a 16 17 3900
+a 16 18 350
+a 16 19 4600
+a 16 24 4000
+a 16 25 4100
+a 16 30 67
+a 16 31 57
+a 16 36 49
+a 16 37 47
+a 16 43 40
+a 16 45 57
+a 16 47 82
+a 16 48 92
+a 16 50 22
+a 17 18 1100
+a 17 19 4000
+a 17 23 4350
+a 17 24 3600
+a 17 31 17
+a 17 33 10
+a 17 34 4
+a 17 37 7
+a 17 38 57
+a 17 40 95
+a 17 43 45
+a 17 45 45
+a 17 49 92
+a 18 19 1850
+a 18 20 3250
+a 18 32 30
+a 18 34 17
+a 18 39 95
+a 18 40 95
+a 18 41 10
+a 18 45 69
+a 18 47 2
+a 18 48 77
+a 18 49 25
+a 18 50 37
+a 19 20 2550
+a 19 21 600
+a 19 28 69
+a 19 30 19
+a 19 31 99
+a 19 36 90
+a 19 37 97
+a 19 38 60
+a 19 40 52
+a 19 41 95
+a 19 42 2
+a 19 44 55
+a 19 45 45
+a 19 47 4
+a 20 21 4250
+a 20 23 2000
+a 20 25 2600
+a 20 27 72
+a 20 31 84
+a 20 32 60
+a 20 34 84
+a 20 36 52
+a 20 37 95
+a 20 38 25
+a 20 40 84
+a 20 45 42
+a 20 46 42
+a 20 48 67
+a 20 49 52
+a 21 22 400
+a 21 30 77
+a 21 31 40
+a 21 32 69
+a 21 33 4
+a 21 35 40
+a 21 37 19
+a 21 39 40
+a 21 41 72
+a 21 48 10
+a 22 23 2050
+a 22 24 4950
+a 22 25 2750
+a 22 30 60
+a 22 34 62
+a 22 36 84
+a 22 40 99
+a 22 45 82
+a 22 47 55
+a 22 49 75
+a 23 24 4150
+a 23 27 15
+a 23 29 84
+a 23 30 84
+a 23 33 87
+a 23 38 99
+a 23 44 12
+a 24 25 3050
+a 24 26 10
+a 24 28 12
+a 24 31 84
+a 24 32 82
+a 24 36 4
+a 24 40 69
+a 24 41 37
+a 24 42 97
+a 25 26 6
+a 25 30 57
+a 25 32 34
+a 25 35 65
+a 25 36 69
+a 25 38 82
+a 25 40 92
+a 25 42 34
+a 25 43 55
+a 25 44 10
+a 26 27 2450
+a 26 29 200
+a 26 30 2350
+a 26 33 950
+a 26 39 3000
+a 26 42 1250
+a 26 46 4000
+a 26 47 3100
+a 26 48 950
+a 27 28 2300
+a 27 30 3100
+a 27 31 1500
+a 27 32 4750
+a 27 34 3850
+a 27 44 3350
+a 27 46 3350
+a 27 47 2600
+a 27 50 3750
+a 28 29 4150
+a 28 38 1850
+a 28 47 4100
+a 29 30 3150
+a 29 31 4200
+a 29 34 3850
+a 29 37 750
+a 29 39 2850
+a 29 46 2450
+a 29 48 4850
+a 30 31 1350
+a 30 34 950
+a 30 35 200
+a 30 36 3350
+a 30 39 4600
+a 30 40 2100
+a 30 41 100
+a 30 42 100
+a 30 43 3750
+a 30 45 3100
+a 30 46 4950
+a 30 48 1850
+a 31 32 4950
+a 31 33 850
+a 31 37 2000
+a 31 41 4350
+a 31 44 850
+a 31 50 3000
+a 32 33 350
+a 32 37 2450
+a 32 40 4750
+a 32 44 750
+a 32 46 3000
+a 32 50 2600
+a 33 34 2600
+a 33 36 2350
+a 33 42 1100
+a 33 43 1850
+a 33 46 3850
+a 33 48 3600
+a 34 35 3250
+a 34 36 1500
+a 34 38 1600
+a 34 42 2750
+a 34 43 3600
+a 34 44 3350
+a 35 36 750
+a 35 37 1700
+a 35 42 2100
+a 35 43 4350
+a 35 46 200
+a 35 47 1700
+a 35 48 3750
+a 36 37 2150
+a 36 39 4000
+a 36 42 3100
+a 36 45 4350
+a 37 38 4800
+a 37 42 1850
+a 37 43 1350
+a 37 48 2750
+a 37 50 2850
+a 38 39 750
+a 38 41 1600
+a 38 43 500
+a 38 46 3100
+a 38 47 3250
+a 38 49 2100
+a 39 40 4250
+a 39 42 3450
+a 39 43 1700
+a 39 44 4600
+a 39 50 3250
+a 40 41 300
+a 40 42 2600
+a 40 44 1350
+a 40 45 500
+a 40 49 2100
+a 41 42 800
+a 41 43 3100
+a 41 46 3850
+a 41 47 100
+a 41 48 1500
+a 41 49 1700
+a 42 43 4700
+a 42 47 4950
+a 43 44 3450
+a 43 49 1600
+a 43 50 1100
+a 44 45 1600
+a 44 46 750
+a 44 48 1600
+a 44 50 200
+a 45 46 1450
+a 45 50 200
+a 46 47 3550
+a 46 50 750
+a 47 48 4350
+a 47 50 1500
+a 48 49 1350
+a 48 50 4850
+a 49 50 650
Added: trunk/libs/graph/test/prgen_input_graphs/prgen_50_70_2.net
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/prgen_input_graphs/prgen_50_70_2.net 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,858 @@
+c NOIGEN min-cut problem
+p cut 50 856
+a 1 2 450
+a 1 6 2200
+a 1 7 4100
+a 1 9 4050
+a 1 10 200
+a 1 11 4900
+a 1 12 1550
+a 1 13 3000
+a 1 16 4550
+a 1 17 450
+a 1 18 2400
+a 1 19 4550
+a 1 20 2050
+a 1 21 2500
+a 1 22 1550
+a 1 23 3850
+a 1 26 50
+a 1 27 55
+a 1 28 31
+a 1 29 68
+a 1 33 64
+a 1 34 55
+a 1 35 31
+a 1 37 29
+a 1 38 98
+a 1 39 32
+a 1 41 55
+a 1 43 67
+a 1 44 92
+a 1 45 42
+a 1 49 48
+a 1 50 88
+a 2 3 450
+a 2 4 4050
+a 2 5 2100
+a 2 6 4900
+a 2 7 3500
+a 2 9 1400
+a 2 10 4500
+a 2 12 3050
+a 2 13 4100
+a 2 14 3100
+a 2 15 3750
+a 2 17 1550
+a 2 19 2200
+a 2 20 2700
+a 2 22 1950
+a 2 24 1900
+a 2 26 51
+a 2 28 67
+a 2 29 12
+a 2 30 21
+a 2 31 72
+a 2 32 68
+a 2 33 2
+a 2 34 12
+a 2 35 28
+a 2 36 87
+a 2 39 97
+a 2 40 19
+a 2 41 47
+a 2 42 57
+a 2 44 21
+a 2 45 17
+a 2 47 54
+a 2 49 92
+a 2 50 5
+a 3 4 3800
+a 3 5 2350
+a 3 6 50
+a 3 7 3350
+a 3 8 2050
+a 3 10 3400
+a 3 11 2700
+a 3 12 200
+a 3 13 1600
+a 3 15 2700
+a 3 18 900
+a 3 21 2750
+a 3 22 5000
+a 3 23 1750
+a 3 24 3250
+a 3 25 3900
+a 3 27 48
+a 3 28 11
+a 3 29 14
+a 3 30 2
+a 3 34 92
+a 3 35 39
+a 3 36 17
+a 3 37 2
+a 3 38 57
+a 3 40 72
+a 3 43 65
+a 3 45 97
+a 3 46 1
+a 3 47 78
+a 3 48 94
+a 3 50 28
+a 4 5 4950
+a 4 6 1700
+a 4 7 3250
+a 4 9 2350
+a 4 10 3500
+a 4 11 4000
+a 4 12 250
+a 4 14 250
+a 4 15 2400
+a 4 17 1950
+a 4 19 400
+a 4 20 4200
+a 4 21 1400
+a 4 22 1350
+a 4 23 2750
+a 4 27 29
+a 4 28 9
+a 4 30 29
+a 4 31 61
+a 4 32 47
+a 4 33 42
+a 4 36 77
+a 4 37 15
+a 4 39 91
+a 4 41 70
+a 4 43 60
+a 4 44 14
+a 4 46 1
+a 4 47 27
+a 4 48 1
+a 4 49 71
+a 5 6 1350
+a 5 7 3700
+a 5 8 4600
+a 5 9 4000
+a 5 12 100
+a 5 13 1600
+a 5 15 4350
+a 5 16 700
+a 5 17 2850
+a 5 18 3700
+a 5 19 2100
+a 5 21 1200
+a 5 22 1350
+a 5 23 1850
+a 5 26 32
+a 5 29 75
+a 5 30 2
+a 5 31 85
+a 5 32 58
+a 5 33 37
+a 5 36 31
+a 5 37 92
+a 5 38 91
+a 5 40 68
+a 5 41 39
+a 5 42 82
+a 5 43 18
+a 5 45 74
+a 5 47 50
+a 5 48 42
+a 5 49 35
+a 5 50 14
+a 6 7 1900
+a 6 8 2700
+a 6 9 2900
+a 6 10 4350
+a 6 11 3000
+a 6 12 4250
+a 6 14 4100
+a 6 15 550
+a 6 16 1600
+a 6 17 3050
+a 6 19 3400
+a 6 20 3700
+a 6 21 4600
+a 6 22 550
+a 6 23 4600
+a 6 26 34
+a 6 27 41
+a 6 29 28
+a 6 31 60
+a 6 32 18
+a 6 33 55
+a 6 34 90
+a 6 36 55
+a 6 37 42
+a 6 38 90
+a 6 40 94
+a 6 41 34
+a 6 42 24
+a 6 43 19
+a 6 45 41
+a 6 46 15
+a 6 50 98
+a 7 8 150
+a 7 11 2050
+a 7 12 2200
+a 7 16 2100
+a 7 18 1100
+a 7 19 250
+a 7 21 4750
+a 7 23 4900
+a 7 24 2350
+a 7 25 350
+a 7 26 51
+a 7 27 38
+a 7 28 70
+a 7 29 5
+a 7 30 38
+a 7 31 51
+a 7 32 5
+a 7 33 7
+a 7 34 44
+a 7 35 90
+a 7 38 9
+a 7 39 28
+a 7 40 11
+a 7 41 38
+a 7 42 38
+a 7 43 35
+a 7 44 29
+a 7 45 78
+a 7 46 5
+a 7 47 29
+a 7 49 12
+a 8 9 2050
+a 8 10 4550
+a 8 11 4900
+a 8 12 4500
+a 8 15 700
+a 8 16 350
+a 8 17 4000
+a 8 18 1050
+a 8 20 4500
+a 8 21 2400
+a 8 22 2700
+a 8 26 68
+a 8 27 39
+a 8 28 22
+a 8 29 95
+a 8 30 64
+a 8 32 22
+a 8 37 47
+a 8 38 37
+a 8 39 57
+a 8 40 97
+a 8 41 37
+a 8 42 88
+a 8 43 12
+a 8 44 97
+a 8 46 87
+a 8 48 81
+a 8 49 77
+a 8 50 11
+a 9 10 2600
+a 9 13 4100
+a 9 14 3850
+a 9 15 3550
+a 9 16 2250
+a 9 17 4500
+a 9 18 4100
+a 9 19 1750
+a 9 20 3900
+a 9 22 4250
+a 9 23 3500
+a 9 26 81
+a 9 27 95
+a 9 29 65
+a 9 30 95
+a 9 31 1
+a 9 32 35
+a 9 33 87
+a 9 34 35
+a 9 36 22
+a 9 38 60
+a 9 39 45
+a 9 40 39
+a 9 41 14
+a 9 42 12
+a 9 43 81
+a 9 45 62
+a 9 48 47
+a 9 50 55
+a 10 11 4400
+a 10 12 2350
+a 10 17 2400
+a 10 18 2750
+a 10 19 1100
+a 10 20 2700
+a 10 21 4750
+a 10 23 900
+a 10 24 4400
+a 10 26 68
+a 10 27 81
+a 10 28 17
+a 10 29 47
+a 10 30 80
+a 10 32 58
+a 10 33 68
+a 10 34 55
+a 10 35 60
+a 10 37 82
+a 10 38 19
+a 10 40 27
+a 10 42 75
+a 10 44 71
+a 10 46 51
+a 10 48 77
+a 10 49 37
+a 11 12 4200
+a 11 13 2100
+a 11 15 4550
+a 11 19 450
+a 11 20 1700
+a 11 21 1250
+a 11 22 3350
+a 11 23 950
+a 11 24 3550
+a 11 25 3550
+a 11 26 47
+a 11 27 38
+a 11 28 58
+a 11 29 84
+a 11 30 2
+a 11 31 11
+a 11 32 15
+a 11 33 77
+a 11 34 91
+a 11 35 35
+a 11 36 11
+a 11 37 42
+a 11 38 54
+a 11 39 28
+a 11 40 4
+a 11 41 44
+a 11 42 44
+a 11 43 22
+a 11 44 47
+a 11 47 7
+a 11 49 25
+a 11 50 60
+a 12 13 4500
+a 12 17 3200
+a 12 18 2550
+a 12 19 900
+a 12 20 2100
+a 12 21 200
+a 12 22 2400
+a 12 24 600
+a 12 25 2900
+a 12 26 90
+a 12 27 32
+a 12 30 31
+a 12 31 95
+a 12 32 70
+a 12 33 47
+a 12 34 38
+a 12 35 81
+a 12 36 51
+a 12 37 90
+a 12 39 42
+a 12 40 80
+a 12 41 29
+a 12 42 84
+a 12 44 94
+a 12 45 48
+a 12 46 31
+a 12 47 67
+a 12 48 19
+a 12 49 19
+a 12 50 11
+a 13 14 600
+a 13 15 2050
+a 13 16 3900
+a 13 17 3900
+a 13 19 1400
+a 13 22 200
+a 13 24 4550
+a 13 25 1900
+a 13 26 62
+a 13 27 21
+a 13 28 97
+a 13 29 21
+a 13 31 8
+a 13 33 11
+a 13 36 32
+a 13 37 8
+a 13 38 45
+a 13 39 84
+a 13 40 29
+a 13 41 94
+a 13 44 84
+a 13 45 14
+a 13 46 74
+a 13 47 78
+a 13 50 21
+a 14 15 2100
+a 14 16 1350
+a 14 17 4700
+a 14 18 3600
+a 14 19 3100
+a 14 21 1700
+a 14 22 1200
+a 14 25 850
+a 14 26 37
+a 14 28 19
+a 14 32 50
+a 14 33 12
+a 14 34 29
+a 14 35 18
+a 14 36 87
+a 14 37 1
+a 14 39 85
+a 14 40 34
+a 14 41 35
+a 14 42 35
+a 14 43 35
+a 14 44 31
+a 14 46 18
+a 14 47 77
+a 14 50 48
+a 15 16 1850
+a 15 17 2100
+a 15 18 2600
+a 15 20 2350
+a 15 21 2600
+a 15 22 2600
+a 15 23 600
+a 15 24 1450
+a 15 25 4600
+a 15 28 34
+a 15 31 17
+a 15 32 48
+a 15 33 80
+a 15 34 94
+a 15 36 100
+a 15 37 37
+a 15 38 61
+a 15 39 7
+a 15 41 50
+a 15 42 41
+a 15 43 67
+a 15 44 55
+a 15 45 14
+a 15 46 47
+a 15 47 2
+a 15 48 70
+a 16 17 3900
+a 16 18 200
+a 16 19 2600
+a 16 20 3550
+a 16 23 3200
+a 16 24 2250
+a 16 25 2350
+a 16 28 72
+a 16 29 71
+a 16 30 38
+a 16 31 32
+a 16 32 67
+a 16 34 67
+a 16 35 70
+a 16 36 28
+a 16 37 27
+a 16 40 100
+a 16 43 22
+a 16 45 32
+a 16 47 47
+a 16 48 52
+a 16 49 67
+a 16 50 12
+a 17 18 1100
+a 17 19 2250
+a 17 23 2500
+a 17 24 2050
+a 17 26 92
+a 17 28 87
+a 17 29 58
+a 17 30 85
+a 17 31 9
+a 17 32 58
+a 17 33 5
+a 17 34 2
+a 17 35 84
+a 17 36 74
+a 17 37 4
+a 17 38 32
+a 17 39 82
+a 17 40 54
+a 17 41 70
+a 17 43 25
+a 17 45 25
+a 17 46 70
+a 17 47 75
+a 17 49 52
+a 18 19 1850
+a 18 20 1850
+a 18 22 4200
+a 18 26 80
+a 18 28 98
+a 18 32 17
+a 18 34 9
+a 18 35 98
+a 18 36 74
+a 18 38 98
+a 18 39 54
+a 18 40 54
+a 18 41 5
+a 18 44 94
+a 18 45 39
+a 18 47 1
+a 18 48 44
+a 18 49 14
+a 18 50 21
+a 19 20 2550
+a 19 21 350
+a 19 23 4350
+a 19 24 4400
+a 19 25 4850
+a 19 26 71
+a 19 28 39
+a 19 29 100
+a 19 30 11
+a 19 31 57
+a 19 34 58
+a 19 36 51
+a 19 37 55
+a 19 38 34
+a 19 39 72
+a 19 40 29
+a 19 41 54
+a 19 42 1
+a 19 44 31
+a 19 45 25
+a 19 47 2
+a 19 48 94
+a 19 50 91
+a 20 21 4250
+a 20 23 1100
+a 20 25 1450
+a 20 26 70
+a 20 27 41
+a 20 31 48
+a 20 32 34
+a 20 34 48
+a 20 36 29
+a 20 37 54
+a 20 38 14
+a 20 40 48
+a 20 41 98
+a 20 42 92
+a 20 43 100
+a 20 44 67
+a 20 45 24
+a 20 46 24
+a 20 47 98
+a 20 48 38
+a 20 49 29
+a 21 22 400
+a 21 23 4100
+a 21 24 3400
+a 21 26 87
+a 21 27 81
+a 21 29 82
+a 21 30 44
+a 21 31 22
+a 21 32 39
+a 21 33 2
+a 21 35 22
+a 21 37 11
+a 21 39 22
+a 21 41 41
+a 21 42 58
+a 21 43 61
+a 21 44 77
+a 21 45 67
+a 21 46 100
+a 21 48 5
+a 21 49 65
+a 22 23 2050
+a 22 24 2850
+a 22 25 1550
+a 22 27 94
+a 22 28 60
+a 22 29 58
+a 22 30 34
+a 22 31 77
+a 22 32 67
+a 22 34 35
+a 22 35 100
+a 22 36 48
+a 22 40 57
+a 22 42 77
+a 22 45 47
+a 22 46 64
+a 22 47 31
+a 22 49 42
+a 23 24 4150
+a 23 25 3500
+a 23 26 62
+a 23 27 8
+a 23 28 91
+a 23 29 48
+a 23 30 48
+a 23 32 71
+a 23 33 50
+a 23 35 65
+a 23 36 95
+a 23 38 57
+a 23 39 70
+a 23 41 95
+a 23 43 67
+a 23 44 7
+a 23 47 61
+a 23 49 87
+a 24 25 3050
+a 24 26 5
+a 24 28 7
+a 24 31 48
+a 24 32 47
+a 24 33 92
+a 24 34 60
+a 24 36 2
+a 24 37 72
+a 24 39 98
+a 24 40 39
+a 24 41 21
+a 24 42 55
+a 24 46 84
+a 24 47 71
+a 24 49 92
+a 24 50 82
+a 25 26 6
+a 25 29 62
+a 25 30 32
+a 25 32 19
+a 25 33 91
+a 25 34 88
+a 25 35 37
+a 25 36 39
+a 25 38 47
+a 25 40 52
+a 25 41 98
+a 25 42 19
+a 25 43 31
+a 25 44 5
+a 25 46 88
+a 25 48 87
+a 25 49 78
+a 26 27 2450
+a 26 28 3250
+a 26 29 100
+a 26 30 1350
+a 26 32 4700
+a 26 33 550
+a 26 35 3250
+a 26 37 4200
+a 26 39 1700
+a 26 40 3750
+a 26 41 4200
+a 26 42 700
+a 26 44 3000
+a 26 45 4550
+a 26 46 2250
+a 26 47 1750
+a 26 48 550
+a 26 50 4200
+a 27 28 2300
+a 27 30 1750
+a 27 31 850
+a 27 32 2700
+a 27 34 2200
+a 27 39 2900
+a 27 40 3900
+a 27 41 3550
+a 27 44 1900
+a 27 45 3900
+a 27 46 1900
+a 27 47 1450
+a 27 48 3050
+a 27 50 2100
+a 28 29 4150
+a 28 30 3550
+a 28 32 2900
+a 28 33 4250
+a 28 38 1050
+a 28 39 4750
+a 28 40 2900
+a 28 46 3600
+a 28 47 2350
+a 29 30 3150
+a 29 31 2400
+a 29 32 3550
+a 29 34 2200
+a 29 36 4050
+a 29 37 400
+a 29 39 1600
+a 29 40 3750
+a 29 41 3900
+a 29 46 1400
+a 29 48 2750
+a 29 49 3400
+a 29 50 3600
+a 30 31 1350
+a 30 33 4400
+a 30 34 550
+a 30 35 100
+a 30 36 1900
+a 30 37 4100
+a 30 38 3600
+a 30 39 2600
+a 30 40 1200
+a 30 41 50
+a 30 42 50
+a 30 43 2100
+a 30 44 3750
+a 30 45 1750
+a 30 46 2850
+a 30 47 5000
+a 30 48 1050
+a 30 50 3100
+a 31 32 4950
+a 31 33 450
+a 31 35 3250
+a 31 36 2900
+a 31 37 1100
+a 31 38 3050
+a 31 39 4900
+a 31 40 4550
+a 31 41 2500
+a 31 44 450
+a 31 47 3900
+a 31 49 3350
+a 31 50 1700
+a 32 33 350
+a 32 35 3050
+a 32 37 1400
+a 32 39 3550
+a 32 40 2700
+a 32 41 3600
+a 32 42 4400
+a 32 44 400
+a 32 45 4600
+a 32 46 1700
+a 32 47 3550
+a 32 48 4750
+a 32 50 1450
+a 33 34 2600
+a 33 36 1350
+a 33 37 4500
+a 33 39 4750
+a 33 41 3100
+a 33 42 600
+a 33 43 1050
+a 33 46 2200
+a 33 48 2050
+a 34 35 3250
+a 34 36 850
+a 34 38 900
+a 34 40 4100
+a 34 42 1550
+a 34 43 2050
+a 34 44 1900
+a 34 45 4250
+a 34 47 5000
+a 34 49 4600
+a 35 36 750
+a 35 37 950
+a 35 40 3500
+a 35 41 3700
+a 35 42 1200
+a 35 43 2500
+a 35 44 4850
+a 35 45 3600
+a 35 46 100
+a 35 47 950
+a 35 48 2100
+a 35 49 2900
+a 35 50 4100
+a 36 37 2150
+a 36 38 3000
+a 36 39 2250
+a 36 41 4200
+a 36 42 1750
+a 36 45 2500
+a 36 47 4850
+a 36 48 3500
+a 37 38 4800
+a 37 39 3750
+a 37 40 4000
+a 37 41 4500
+a 37 42 1050
+a 37 43 750
+a 37 48 1550
+a 37 49 4100
+a 37 50 1600
+a 38 39 750
+a 38 41 900
+a 38 43 250
+a 38 44 4250
+a 38 45 5000
+a 38 46 1750
+a 38 47 1850
+a 38 49 1200
+a 38 50 3000
+a 39 40 4250
+a 39 42 1950
+a 39 43 950
+a 39 44 2600
+a 39 45 3000
+a 39 47 3900
+a 39 50 1850
+a 40 41 300
+a 40 42 1450
+a 40 43 2900
+a 40 44 750
+a 40 45 250
+a 40 46 3900
+a 40 47 3250
+a 40 49 1200
+a 41 42 800
+a 41 43 1750
+a 41 44 4400
+a 41 45 4350
+a 41 46 2200
+a 41 47 50
+a 41 48 850
+a 41 49 950
+a 42 43 4700
+a 42 45 4750
+a 42 46 3200
+a 42 47 2850
+a 43 44 3450
+a 43 45 4850
+a 43 46 3550
+a 43 47 3900
+a 43 49 900
+a 43 50 600
+a 44 45 1600
+a 44 46 400
+a 44 47 3900
+a 44 48 900
+a 44 49 2900
+a 44 50 100
+a 45 46 1450
+a 45 47 4200
+a 45 49 2900
+a 45 50 100
+a 46 47 3550
+a 46 49 3850
+a 46 50 400
+a 47 48 4350
+a 47 49 3000
+a 47 50 850
+a 48 49 1350
+a 48 50 2750
+a 49 50 650
Added: trunk/libs/graph/test/stoer_wagner_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/stoer_wagner_test.cpp 2010-09-25 14:52:41 EDT (Sat, 25 Sep 2010)
@@ -0,0 +1,253 @@
+// Copyright Daniel Trebbien 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or the copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <vector>
+#include <string>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/connected_components.hpp>
+#include <boost/graph/exception.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/read_dimacs.hpp>
+#include <boost/graph/stoer_wagner_min_cut.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
+#include <boost/property_map/property_map.hpp>
+#define BOOST_TEST_DYN_LINK 1
+#include <boost/test/unit_test.hpp>
+#include <boost/tuple/tuple.hpp>
+
+typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int> > undirected_graph;
+typedef boost::property_map<undirected_graph, boost::edge_weight_t>::type weight_map_type;
+typedef boost::property_traits<weight_map_type>::value_type weight_type;
+
+typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> undirected_unweighted_graph;
+
+std::string test_dir;
+
+boost::unit_test::test_suite* init_unit_test_suite( int argc, char* argv[] ) {
+ if (argc != 2) {
+ std::cerr << "Usage: " << argv[0] << " path-to-libs-graph-test" << std::endl;
+ throw boost::unit_test::framework::setup_error("Invalid command line arguments");
+ }
+ test_dir = argv[1];
+ return 0;
+}
+
+struct edge_t
+{
+ unsigned long first;
+ unsigned long second;
+};
+
+// the example from Stoer & Wagner (1997)
+BOOST_AUTO_TEST_CASE(test0)
+{
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
+ {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
+ weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
+ undirected_graph g(edges, edges + 12, ws, 8, 12);
+
+ weight_map_type weights = get(boost::edge_weight, g);
+ std::map<int, bool> parity;
+ boost::associative_property_map<std::map<int, bool> > parities(parity);
+ int w = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
+ BOOST_CHECK_EQUAL(w, 4);
+ const bool parity0 = get(parities, 0);
+ BOOST_CHECK_EQUAL(parity0, get(parities, 1));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 4));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 5));
+ const bool parity2 = get(parities, 2);
+ BOOST_CHECK_NE(parity0, parity2);
+ BOOST_CHECK_EQUAL(parity2, get(parities, 3));
+ BOOST_CHECK_EQUAL(parity2, get(parities, 6));
+ BOOST_CHECK_EQUAL(parity2, get(parities, 7));
+}
+
+BOOST_AUTO_TEST_CASE(test1)
+{
+ { // if only one vertex, can't run `boost::stoer_wagner_min_cut`
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ undirected_graph g;
+ add_vertex(g);
+
+ BOOST_CHECK_THROW(boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g)), boost::bad_graph);
+ }{ // three vertices with one multi-edge
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ edge_t edges[] = {{0, 1}, {1, 2}, {1, 2}, {2, 0}};
+ weight_type ws[] = {3, 1, 1, 1};
+ undirected_graph g(edges, edges + 4, ws, 3, 4);
+
+ weight_map_type weights = get(boost::edge_weight, g);
+ std::map<int, bool> parity;
+ boost::associative_property_map<std::map<int, bool> > parities(parity);
+ std::map<vertex_descriptor, vertex_descriptor> assignment;
+ boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
+ int w = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities).vertex_assignment_map(assignments));
+ BOOST_CHECK_EQUAL(w, 3);
+ const bool parity2 = get(parities, 2),
+ parity0 = get(parities, 0);
+ BOOST_CHECK_NE(parity2, parity0);
+ BOOST_CHECK_EQUAL(parity0, get(parities, 1));
+ }
+}
+
+// example by Daniel Trebbien
+BOOST_AUTO_TEST_CASE(test2)
+{
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ edge_t edges[] = {{5, 2}, {0, 6}, {5, 6},
+ {3, 1}, {0, 1}, {6, 3}, {4, 6}, {2, 4}, {5, 3}};
+ weight_type ws[] = {1, 3, 4, 6, 4, 1, 2, 5, 2};
+ undirected_graph g(edges, edges + 9, ws, 7, 9);
+
+ std::map<int, bool> parity;
+ boost::associative_property_map<std::map<int, bool> > parities(parity);
+ int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g), boost::parity_map(parities));
+ BOOST_CHECK_EQUAL(w, 3);
+ const bool parity2 = get(parities, 2);
+ BOOST_CHECK_EQUAL(parity2, get(parities, 4));
+ const bool parity5 = get(parities, 5);
+ BOOST_CHECK_NE(parity2, parity5);
+ BOOST_CHECK_EQUAL(parity5, get(parities, 3));
+ BOOST_CHECK_EQUAL(parity5, get(parities, 6));
+ BOOST_CHECK_EQUAL(parity5, get(parities, 1));
+ BOOST_CHECK_EQUAL(parity5, get(parities, 0));
+}
+
+// example by Daniel Trebbien
+BOOST_AUTO_TEST_CASE(test3)
+{
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ edge_t edges[] = {{3, 4}, {3, 6}, {3, 5}, {0, 4}, {0, 1}, {0, 6}, {0, 7},
+ {0, 5}, {0, 2}, {4, 1}, {1, 6}, {1, 5}, {6, 7}, {7, 5}, {5, 2}, {3, 4}};
+ weight_type ws[] = {0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4};
+ undirected_graph g(edges, edges + 16, ws, 8, 16);
+
+ weight_map_type weights = get(boost::edge_weight, g);
+ std::map<int, bool> parity;
+ boost::associative_property_map<std::map<int, bool> > parities(parity);
+ int w = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
+ BOOST_CHECK_EQUAL(w, 7);
+ const bool parity1 = get(parities, 1);
+ BOOST_CHECK_EQUAL(parity1, get(parities, 5));
+ const bool parity0 = get(parities, 0);
+ BOOST_CHECK_NE(parity1, parity0);
+ BOOST_CHECK_EQUAL(parity0, get(parities, 2));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 3));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 4));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 6));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 7));
+}
+
+BOOST_AUTO_TEST_CASE(test4)
+{
+ typedef boost::graph_traits<undirected_unweighted_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_unweighted_graph>::edge_descriptor edge_descriptor;
+
+ edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
+ {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7},
+ {0, 4}, {6, 7}};
+ undirected_unweighted_graph g(edges, edges + 14, 8);
+
+ std::map<vertex_descriptor, bool> parity;
+ boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
+ std::map<vertex_descriptor, vertex_descriptor> assignment;
+ boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
+ int w = boost::stoer_wagner_min_cut(g, boost::make_constant_property<edge_descriptor>(weight_type(1)), boost::vertex_assignment_map(assignments).parity_map(parities));
+ BOOST_CHECK_EQUAL(w, 2);
+ const bool parity0 = get(parities, 0);
+ BOOST_CHECK_EQUAL(parity0, get(parities, 1));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 4));
+ BOOST_CHECK_EQUAL(parity0, get(parities, 5));
+ const bool parity2 = get(parities, 2);
+ BOOST_CHECK_NE(parity0, parity2);
+ BOOST_CHECK_EQUAL(parity2, get(parities, 3));
+ BOOST_CHECK_EQUAL(parity2, get(parities, 6));
+ BOOST_CHECK_EQUAL(parity2, get(parities, 7));
+}
+
+// The input for the `test_prgen` family of tests comes from a program, named
+// `prgen`, that comes with a package of min-cut solvers by Chandra Chekuri,
+// Andrew Goldberg, David Karger, Matthew Levine, and Cliff Stein. `prgen` was
+// used to generate input graphs and the solvers were used to verify the return
+// value of `boost::stoer_wagner_min_cut` on the input graphs.
+//
+// http://www.columbia.edu/~cs2035/code.html
+//
+// Note that it is somewhat more difficult to verify the parities because
+// "`prgen` graphs" often have several min-cuts. This is why only the cut
+// weight of the min-cut is verified.
+
+// 3 min-cuts
+BOOST_AUTO_TEST_CASE(test_prgen_20_70_2)
+{
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ std::ifstream ifs((test_dir + "/prgen_input_graphs/prgen_20_70_2.net").c_str());
+ undirected_graph g;
+ boost::read_dimacs_min_cut(g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
+
+ std::map<vertex_descriptor, std::size_t> component;
+ boost::associative_property_map<std::map<vertex_descriptor, std::size_t> > components(component);
+ BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1U); // verify the connectedness assumption
+
+ BOOST_AUTO(distances, (boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g))));
+ typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
+ BOOST_AUTO(indicesInHeap, (boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g))));
+ boost::d_ary_heap_indirect<vertex_descriptor, 22, BOOST_TYPEOF(indicesInHeap), BOOST_TYPEOF(distances), std::greater<weight_type> > pq(distances, indicesInHeap);
+
+ int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g), boost::max_priority_queue(pq));
+ BOOST_CHECK_EQUAL(w, 3407);
+}
+
+// 7 min-cuts
+BOOST_AUTO_TEST_CASE(test_prgen_50_40_2)
+{
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ std::ifstream ifs((test_dir + "/prgen_input_graphs/prgen_50_40_2.net").c_str());
+ undirected_graph g;
+ boost::read_dimacs_min_cut(g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
+
+ std::map<vertex_descriptor, std::size_t> component;
+ boost::associative_property_map<std::map<vertex_descriptor, std::size_t> > components(component);
+ BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1U); // verify the connectedness assumption
+
+ int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g));
+ BOOST_CHECK_EQUAL(w, 10056);
+}
+
+// 6 min-cuts
+BOOST_AUTO_TEST_CASE(test_prgen_50_70_2)
+{
+ typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+ std::ifstream ifs((test_dir + "/prgen_input_graphs/prgen_50_70_2.net").c_str());
+ undirected_graph g;
+ boost::read_dimacs_min_cut(g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
+
+ std::map<vertex_descriptor, std::size_t> component;
+ boost::associative_property_map<std::map<vertex_descriptor, std::size_t> > components(component);
+ BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1U); // verify the connectedness assumption
+
+ int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g));
+ BOOST_CHECK_EQUAL(w, 21755);
+}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
