From 483eb2f56657e8e7f419ab1a4fab8dce9ade8609 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 27 Apr 2024 20:24:20 +0200 Subject: Adding upstream version 14.2.21. Signed-off-by: Daniel Baumann --- src/boost/libs/graph/test/stoer_wagner_test.cpp | 242 ++++++++++++++++++++++++ 1 file changed, 242 insertions(+) create mode 100644 src/boost/libs/graph/test/stoer_wagner_test.cpp (limited to 'src/boost/libs/graph/test/stoer_wagner_test.cpp') diff --git a/src/boost/libs/graph/test/stoer_wagner_test.cpp b/src/boost/libs/graph/test/stoer_wagner_test.cpp new file mode 100644 index 00000000..7cbb017c --- /dev/null +++ b/src/boost/libs/graph/test/stoer_wagner_test.cpp @@ -0,0 +1,242 @@ +// 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) + +#if defined(_MSC_VER) && !defined(_CRT_SECURE_NO_WARNINGS) +# define _CRT_SECURE_NO_WARNINGS +#endif + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +typedef boost::adjacency_list > undirected_graph; +typedef boost::property_map::type weight_map_type; +typedef boost::property_traits::value_type weight_type; + +typedef boost::adjacency_list 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) +{ + 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 parity; + boost::associative_property_map > 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` + 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::vertex_descriptor vertex_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 parity; + boost::associative_property_map > parities(parity); + std::map assignment; + boost::associative_property_map > 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) +{ + 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 parity; + boost::associative_property_map > 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) +{ + 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 parity; + boost::associative_property_map > 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::vertex_descriptor vertex_descriptor; + typedef boost::graph_traits::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 parity; + boost::associative_property_map > parities(parity); + std::map assignment; + boost::associative_property_map > assignments(assignment); + int w = boost::stoer_wagner_min_cut(g, boost::make_constant_property(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::vertex_descriptor vertex_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 component; + boost::associative_property_map > components(component); + BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1U); // verify the connectedness assumption + + typedef boost::shared_array_property_map::const_type> distances_type; + distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g)); + typedef std::vector::size_type index_in_heap_type; + typedef boost::shared_array_property_map::const_type> indicesInHeap_type; + indicesInHeap_type 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 > 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::vertex_descriptor vertex_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 component; + boost::associative_property_map > 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::vertex_descriptor vertex_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 component; + boost::associative_property_map > 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); +} -- cgit v1.2.3