123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392 |
- // 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;
- }
|