diff options
Diffstat (limited to 'src/boost/libs/graph/test/floyd_warshall_test.cpp')
-rw-r--r-- | src/boost/libs/graph/test/floyd_warshall_test.cpp | 392 |
1 files changed, 392 insertions, 0 deletions
diff --git a/src/boost/libs/graph/test/floyd_warshall_test.cpp b/src/boost/libs/graph/test/floyd_warshall_test.cpp new file mode 100644 index 00000000..fcb60672 --- /dev/null +++ b/src/boost/libs/graph/test/floyd_warshall_test.cpp @@ -0,0 +1,392 @@ +// Copyright 2002 Rensselaer Polytechnic Institute + +// 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: Lauren Foutz +// Scott Hill +#include <boost/graph/floyd_warshall_shortest.hpp> +#include <map> +#include <algorithm> +#include <iostream> +#include <boost/random/linear_congruential.hpp> +#include <boost/graph/graph_utility.hpp> +#include <boost/graph/properties.hpp> +#include <boost/graph/bellman_ford_shortest_paths.hpp> +#include <boost/graph/random.hpp> +#include <boost/graph/adjacency_list.hpp> +#include <boost/graph/adjacency_matrix.hpp> +#include <boost/test/minimal.hpp> +#include <algorithm> +using namespace boost; + +template<typename T> +inline const T& my_min(const T& x, const T& y) +{ return x < y? x : y; } + +template<typename Graph> +bool acceptance_test(Graph& g, int vec, int e) +{ + boost::minstd_rand ran(vec); + + { + typename boost::property_map<Graph, boost::vertex_name_t>::type index = + boost::get(boost::vertex_name, g); + typename boost::graph_traits<Graph>::vertex_iterator firstv, lastv, + firstv2, lastv2; + int x = 0; + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + boost::put(index, *firstv, x); + x++; + } + + + for(int i = 0; i < e; i++){ + boost::add_edge(index[ran() % vec], index[ran() % vec], g); + } + + + typename boost::graph_traits<Graph>::edge_iterator first, last; + typename boost::property_map<Graph, boost::edge_weight_t>::type + local_edge_map = boost::get(boost::edge_weight, g); + for(boost::tie(first, last) = boost::edges(g); first != last; first++){ + if (ran() % vec != 0){ + boost::put(local_edge_map, *first, ran() % 100); + } else { + boost::put(local_edge_map, *first, 0 - (ran() % 100)); + } + } + + int int_inf = + std::numeric_limits<int>::max BOOST_PREVENT_MACRO_SUBSTITUTION(); + typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_des; + std::map<vertex_des,int> matrixRow; + std::map<vertex_des, std::map<vertex_des ,int> > matrix; + typedef typename boost::property_map<Graph, boost::vertex_distance_t>::type + distance_type; + distance_type distance_row = boost::get(boost::vertex_distance, g); + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + boost::put(distance_row, *firstv, int_inf); + matrixRow[*firstv] = int_inf; + } + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + matrix[*firstv] = matrixRow; + } + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + matrix[*firstv][*firstv] = 0; + } + std::map<vertex_des, std::map<vertex_des, int> > matrix3(matrix); + std::map<vertex_des, std::map<vertex_des, int> > matrix4(matrix); + for(boost::tie(first, last) = boost::edges(g); first != last; first++){ + if (matrix[boost::source(*first, g)][boost::target(*first, g)] != int_inf) + { + matrix[boost::source(*first, g)][boost::target(*first, g)] = + my_min + (boost::get(local_edge_map, *first), + matrix[boost::source(*first, g)][boost::target(*first, g)]); + } else { + matrix[boost::source(*first, g)][boost::target(*first, g)] = + boost::get(local_edge_map, *first); + } + } + bool is_undirected = + boost::is_same<typename boost::graph_traits<Graph>::directed_category, + boost::undirected_tag>::value; + if (is_undirected){ + for(boost::tie(first, last) = boost::edges(g); first != last; first++){ + if (matrix[boost::target(*first, g)][boost::source(*first, g)] != int_inf) + { + matrix[boost::target(*first, g)][boost::source(*first, g)] = + my_min + (boost::get(local_edge_map, *first), + matrix[boost::target(*first, g)][boost::source(*first, g)]); + } else { + matrix[boost::target(*first, g)][boost::source(*first, g)] = + boost::get(local_edge_map, *first); + } + } + } + + + bool bellman, floyd1, floyd2, floyd3; + floyd1 = + boost::floyd_warshall_initialized_all_pairs_shortest_paths + (g, + matrix, weight_map(boost::get(boost::edge_weight, g)). + distance_inf(int_inf). distance_zero(0)); + + floyd2 = + boost::floyd_warshall_all_pairs_shortest_paths + (g, matrix3, + weight_map(local_edge_map). + distance_inf(int_inf). distance_zero(0)); + + floyd3 = boost::floyd_warshall_all_pairs_shortest_paths(g, matrix4); + + + boost::dummy_property_map dummy_map; + std::map<vertex_des, std::map<vertex_des, int> > matrix2; + for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++){ + boost::put(distance_row, *firstv, 0); + bellman = + boost::bellman_ford_shortest_paths + (g, vec, + weight_map(boost::get(boost::edge_weight, g)). + distance_map(boost::get(boost::vertex_distance, g)). + predecessor_map(dummy_map)); + distance_row = boost::get(boost::vertex_distance, g); + for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; + firstv2++){ + matrix2[*firstv][*firstv2] = boost::get(distance_row, *firstv2); + boost::put(distance_row, *firstv2, int_inf); + } + if(bellman == false){ + break; + } + } + + + if (bellman != floyd1 || bellman != floyd2 || bellman != floyd3){ + std::cout << + "A negative cycle was detected in one algorithm but not the others. " + << std::endl; + return false; + } + else if (bellman == false && floyd1 == false && floyd2 == false && + floyd3 == false){ + return true; + } + else { + typename boost::graph_traits<Graph>::vertex_iterator first1, first2, + last1, last2; + for (boost::tie(first1, last1) = boost::vertices(g); first1 != last1; + first1++){ + for (boost::tie(first2, last2) = boost::vertices(g); first2 != last2; + first2++){ + if (matrix2[*first1][*first2] != matrix[*first1][*first2]){ + std::cout << "Algorithms do not match at matrix point " + << index[*first1] << " " << index[*first2] + << " Bellman results: " << matrix2[*first1][*first2] + << " floyd 1 results " << matrix[*first1][*first2] + << std::endl; + return false; + } + if (matrix2[*first1][*first2] != matrix3[*first1][*first2]){ + std::cout << "Algorithms do not match at matrix point " + << index[*first1] << " " << index[*first2] + << " Bellman results: " << matrix2[*first1][*first2] + << " floyd 2 results " << matrix3[*first1][*first2] + << std::endl; + return false; + } + if (matrix2[*first1][*first2] != matrix4[*first1][*first2]){ + std::cout << "Algorithms do not match at matrix point " + << index[*first1] << " " << index[*first2] + << " Bellman results: " << matrix2[*first1][*first2] + << " floyd 3 results " << matrix4[*first1][*first2] + << std::endl; + return false; + } + } + } + } + + } + return true; +} + +template<typename Graph> +bool acceptance_test2(Graph& g, int vec, int e) +{ + boost::minstd_rand ran(vec); + + { + + typename boost::property_map<Graph, boost::vertex_name_t>::type index = + boost::get(boost::vertex_name, g); + typename boost::graph_traits<Graph>::vertex_iterator firstv, lastv, + firstv2, lastv2; + int x = 0; + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + boost::put(index, *firstv, x); + x++; + } + + boost::generate_random_graph(g, vec, e, ran, true); + + typename boost::graph_traits<Graph>::edge_iterator first, last; + typename boost::property_map<Graph, boost::edge_weight_t>::type + local_edge_map = boost::get(boost::edge_weight, g); + for(boost::tie(first, last) = boost::edges(g); first != last; first++){ + if (ran() % vec != 0){ + boost::put(local_edge_map, *first, ran() % 100); + } else { + boost::put(local_edge_map, *first, 0 - (ran() % 100)); + } + } + + int int_inf = + std::numeric_limits<int>::max BOOST_PREVENT_MACRO_SUBSTITUTION(); + typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_des; + std::map<vertex_des,int> matrixRow; + std::map<vertex_des, std::map<vertex_des ,int> > matrix; + typedef typename boost::property_map<Graph, boost::vertex_distance_t>::type + distance_type; + distance_type distance_row = boost::get(boost::vertex_distance, g); + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + boost::put(distance_row, *firstv, int_inf); + matrixRow[*firstv] = int_inf; + } + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + matrix[*firstv] = matrixRow; + } + for(boost::tie(firstv, lastv) = boost::vertices(g); firstv != lastv; + firstv++){ + matrix[*firstv][*firstv] = 0; + } + std::map<vertex_des, std::map<vertex_des, int> > matrix3(matrix); + std::map<vertex_des, std::map<vertex_des, int> > matrix4(matrix); + for(boost::tie(first, last) = boost::edges(g); first != last; first++){ + if (matrix[boost::source(*first, g)][boost::target(*first, g)] != int_inf) + { + matrix[boost::source(*first, g)][boost::target(*first, g)] = + my_min + (boost::get(local_edge_map, *first), + matrix[boost::source(*first, g)][boost::target(*first, g)]); + } else { + matrix[boost::source(*first, g)][boost::target(*first, g)] = + boost::get(local_edge_map, *first); + } + } + bool is_undirected = + boost::is_same<typename boost::graph_traits<Graph>::directed_category, + boost::undirected_tag>::value; + if (is_undirected){ + for(boost::tie(first, last) = boost::edges(g); first != last; first++){ + if (matrix[boost::target(*first, g)][boost::source(*first, g)] + != int_inf){ + matrix[boost::target(*first, g)][boost::source(*first, g)] = + my_min + (boost::get(local_edge_map, *first), + matrix[boost::target(*first, g)][boost::source(*first, g)]); + } else { + matrix[boost::target(*first, g)][boost::source(*first, g)] = + boost::get(local_edge_map, *first); + } + } + } + + + bool bellman, floyd1, floyd2, floyd3; + floyd1 = + boost::floyd_warshall_initialized_all_pairs_shortest_paths + (g, + matrix, weight_map(boost::get(boost::edge_weight, g)). + distance_inf(int_inf). distance_zero(0)); + + floyd2 = + boost::floyd_warshall_all_pairs_shortest_paths + (g, matrix3, + weight_map(local_edge_map). + distance_inf(int_inf). distance_zero(0)); + + floyd3 = boost::floyd_warshall_all_pairs_shortest_paths(g, matrix4); + + + boost::dummy_property_map dummy_map; + std::map<vertex_des, std::map<vertex_des, int> > matrix2; + for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++){ + boost::put(distance_row, *firstv, 0); + bellman = + boost::bellman_ford_shortest_paths + (g, vec, + weight_map(boost::get(boost::edge_weight, g)). + distance_map(boost::get(boost::vertex_distance, g)). + predecessor_map(dummy_map)); + distance_row = boost::get(boost::vertex_distance, g); + for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; + firstv2++){ + matrix2[*firstv][*firstv2] = boost::get(distance_row, *firstv2); + boost::put(distance_row, *firstv2, int_inf); + } + if(bellman == false){ + break; + } + } + + + if (bellman != floyd1 || bellman != floyd2 || bellman != floyd3){ + std::cout << + "A negative cycle was detected in one algorithm but not the others. " + << std::endl; + return false; + } + else if (bellman == false && floyd1 == false && floyd2 == false && + floyd3 == false){ + return true; + } + else { + typename boost::graph_traits<Graph>::vertex_iterator first1, first2, + last1, last2; + for (boost::tie(first1, last1) = boost::vertices(g); first1 != last1; + first1++){ + for (boost::tie(first2, last2) = boost::vertices(g); first2 != last2; + first2++){ + if (matrix2[*first1][*first2] != matrix[*first1][*first2]){ + std::cout << "Algorithms do not match at matrix point " + << index[*first1] << " " << index[*first2] + << " Bellman results: " << matrix2[*first1][*first2] + << " floyd 1 results " << matrix[*first1][*first2] + << std::endl; + return false; + } + if (matrix2[*first1][*first2] != matrix3[*first1][*first2]){ + std::cout << "Algorithms do not match at matrix point " + << index[*first1] << " " << index[*first2] + << " Bellman results: " << matrix2[*first1][*first2] + << " floyd 2 results " << matrix3[*first1][*first2] + << std::endl; + return false; + } + if (matrix2[*first1][*first2] != matrix4[*first1][*first2]){ + std::cout << "Algorithms do not match at matrix point " + << index[*first1] << " " << index[*first2] + << " Bellman results: " << matrix2[*first1][*first2] + << " floyd 3 results " << matrix4[*first1][*first2] + << std::endl; + return false; + } + } + } + } + + } + return true; +} + +int test_main(int, char*[]) +{ + typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS, + boost::property<boost::vertex_distance_t, int, + boost::property<boost::vertex_name_t, int> > , + boost::property<boost::edge_weight_t, int> > Digraph; + Digraph adjlist_digraph; + BOOST_CHECK(acceptance_test2(adjlist_digraph, 100, 2000)); + + typedef boost::adjacency_matrix<boost::undirectedS, + boost::property<boost::vertex_distance_t, int, + boost::property<boost::vertex_name_t, int> > , + boost::property<boost::edge_weight_t, int> > Graph; + Graph matrix_graph(100); + BOOST_CHECK(acceptance_test(matrix_graph, 100, 2000)); + + return 0; +} |