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/max_flow_test.cpp | 136 ++++++++++++++++++++++++++++ 1 file changed, 136 insertions(+) create mode 100644 src/boost/libs/graph/test/max_flow_test.cpp (limited to 'src/boost/libs/graph/test/max_flow_test.cpp') diff --git a/src/boost/libs/graph/test/max_flow_test.cpp b/src/boost/libs/graph/test/max_flow_test.cpp new file mode 100644 index 00000000..8cd5e4a2 --- /dev/null +++ b/src/boost/libs/graph/test/max_flow_test.cpp @@ -0,0 +1,136 @@ +// Copyright (c) 2006, Stephan Diederich +// +// This code may be used under either of the following two licences: +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following +// conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE. +// +// Or: +// +// Distributed under 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) + +#include +#include +#include +#include +#include + +#include +//three max_flows we test here +#include +#include +#include +//boost utilities we use +#include +#include +#include +#include +#include + +/*************** +* test which compares results of the three different max_flow implementations +* command line parameters: +* number_of_vertices: defaults to 100 +* number_of_edges: defaults to 1000 +* seeed: defaults to 1 +***************/ + +using namespace boost; + +int test_main(int argc, char* argv[]) +{ + + typedef adjacency_list_traits < vecS, vecS, directedS > Traits; + typedef adjacency_list < vecS, vecS, directedS, + property < vertex_index_t, long, + property < vertex_color_t, boost::default_color_type, + property < vertex_distance_t, long, + property < vertex_predecessor_t, Traits::edge_descriptor > > > >, + property < edge_capacity_t, long, + property < edge_residual_capacity_t, long, + property < edge_reverse_t, Traits::edge_descriptor > > > > Graph; + + typedef graph_traits::edge_descriptor tEdge; + typedef graph_traits::vertex_descriptor tVertex; + + graph_traits::vertices_size_type n_verts = 100; + graph_traits::edges_size_type n_edges = 1000; + std::size_t seed = 1; + + if (argc > 1) n_verts = lexical_cast(argv[1]); + if (argc > 2) n_edges = lexical_cast(argv[2]); + if (argc > 3) seed = lexical_cast(argv[3]); + + Graph g; + const int cap_low = 1; + const int cap_high = 1000; + + //init random numer generator + minstd_rand gen(seed); + //generate graph + generate_random_graph(g, n_verts, n_edges, gen); + + //init an uniform distribution int generator + typedef variate_generator > tIntGen; + tIntGen int_gen(gen, uniform_int(cap_low, cap_high)); + //init edge-capacities + randomize_property (g,int_gen); + + //get source and sink node + tVertex source_vertex = random_vertex(g, gen); + tVertex sink_vertex = graph_traits::null_vertex(); + while(sink_vertex == graph_traits::null_vertex() || sink_vertex == source_vertex) + sink_vertex = random_vertex(g, gen); + + //add reverse edges (ugly... how to do better?!) + property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g); + property_map < Graph, edge_capacity_t >::type cap = get(edge_capacity, g); + std::list edges_copy; + graph_traits::edge_iterator ei, e_end; + boost::tie(ei, e_end) = edges(g); + std::copy(ei, e_end, std::back_insert_iterator< std::list >(edges_copy)); + while( ! edges_copy.empty()){ + tEdge old_edge=edges_copy.front(); + edges_copy.pop_front(); + tVertex source_vertex = target(old_edge, g); + tVertex target_vertex = source(old_edge, g); + bool inserted; + tEdge new_edge; + boost::tie(new_edge,inserted) = add_edge(source_vertex, target_vertex, g); + assert(inserted); + rev[old_edge] = new_edge; + rev[new_edge] = old_edge ; + cap[new_edge] = 0; + } + + typedef property_traits< property_map::const_type>::value_type tEdgeVal; + + tEdgeVal bk = boykov_kolmogorov_max_flow(g,source_vertex,sink_vertex); + tEdgeVal push_relabel = push_relabel_max_flow(g,source_vertex,sink_vertex); + tEdgeVal edmonds_karp = edmonds_karp_max_flow(g,source_vertex,sink_vertex); + + BOOST_REQUIRE( bk == push_relabel ); + BOOST_REQUIRE( push_relabel == edmonds_karp ); + + return 0; +} -- cgit v1.2.3