// 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/core/lightweight_test.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 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_TEST(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_TEST(acceptance_test(matrix_graph, 100, 2000));

    return boost::report_errors();
}