// Copyright 2002 Rensselaer Polytechnic Institute

// 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)

//  Authors: Lauren Foutz

//           Scott Hill

/*

  This file implements the functions

  template <class VertexListGraph, class DistanceMatrix, 

    class P, class T, class R>

  bool floyd_warshall_initialized_all_pairs_shortest_paths(

    const VertexListGraph& g, DistanceMatrix& d, 

    const bgl_named_params<P, T, R>& params)

  AND

  template <class VertexAndEdgeListGraph, class DistanceMatrix, 

    class P, class T, class R>

  bool floyd_warshall_all_pairs_shortest_paths(

    const VertexAndEdgeListGraph& g, DistanceMatrix& d, 

    const bgl_named_params<P, T, R>& params)

*/

#ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP

#define BOOST_GRAPH_FLOYD_WARSHALL_HPP

#include <boost/property_map.hpp>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/named_function_params.hpp>

#include <boost/graph/graph_concepts.hpp>

#include <boost/graph/relax.hpp>

namespace boost

{

  namespace detail {

    template<typename T, typename BinaryPredicate>

    T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare)

    {

      if (compare(x, y)) return x; 

      else return y;

    }

    template<typename VertexListGraph, typename DistanceMatrix, 

      typename BinaryPredicate, typename BinaryFunction,

      typename Infinity, typename Zero>

    bool floyd_warshall_dispatch(const VertexListGraph& g, 

      DistanceMatrix& d, const BinaryPredicate &compare, 

      const BinaryFunction &combine, const Infinity& inf, 

      const Zero& zero)

    {

      typename graph_traits<VertexListGraph>::vertex_iterator 

        i, lasti, j, lastj, k, lastk;

      for (tie(k, lastk) = vertices(g); k != lastk; k++)

        for (tie(i, lasti) = vertices(g); i != lasti; i++)

          for (tie(j, lastj) = vertices(g); j != lastj; j++)

          {

            d[*i][*j] = 

              detail::min_with_compare(d[*i][*j], 

                                       combine(d[*i][*k], d[*k][*j]),

                                       compare);

          }

      for (tie(i, lasti) = vertices(g); i != lasti; i++)

        if (compare(d[*i][*i], zero))

          return false;

      return true;

    }

  }

  template <typename VertexListGraph, typename DistanceMatrix, 

    typename BinaryPredicate, typename BinaryFunction,

    typename Infinity, typename Zero>

  bool floyd_warshall_initialized_all_pairs_shortest_paths(

    const VertexListGraph& g, DistanceMatrix& d, 

    const BinaryPredicate& compare, 

    const BinaryFunction& combine, const Infinity& inf, 

    const Zero& zero)

  {

    function_requires<VertexListGraphConcept<VertexListGraph> >();

    return detail::floyd_warshall_dispatch(g, d, compare, combine, 

    inf, zero);

  }

  template <typename VertexAndEdgeListGraph, typename DistanceMatrix, 

    typename WeightMap, typename BinaryPredicate, 

    typename BinaryFunction, typename Infinity, typename Zero>

  bool floyd_warshall_all_pairs_shortest_paths(

    const VertexAndEdgeListGraph& g, 

    DistanceMatrix& d, const WeightMap& w, 

    const BinaryPredicate& compare, const BinaryFunction& combine, 

    const Infinity& inf, const Zero& zero)

  {

    function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();

    function_requires<EdgeListGraphConcept<VertexAndEdgeListGraph> >();

    function_requires<IncidenceGraphConcept<VertexAndEdgeListGraph> >();

    typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator 

      firstv, lastv, firstv2, lastv2;

    typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last;

    for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)

      for(tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++)

        d[*firstv][*firstv2] = inf;

    for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)

      d[*firstv][*firstv] = zero;

    for(tie(first, last) = edges(g); first != last; first++)

    {

      if (d[source(*first, g)][target(*first, g)] != inf) {

        d[source(*first, g)][target(*first, g)] = 

          detail::min_with_compare(

            get(w, *first), 

            d[source(*first, g)][target(*first, g)],

            compare);

      } else 

        d[source(*first, g)][target(*first, g)] = get(w, *first);

    }

    bool is_undirected = is_same<typename 

      graph_traits<VertexAndEdgeListGraph>::directed_category, 

      undirected_tag>::value;

    if (is_undirected)

    {

      for(tie(first, last) = edges(g); first != last; first++)

      {

        if (d[target(*first, g)][source(*first, g)] != inf)

          d[target(*first, g)][source(*first, g)] = 

            detail::min_with_compare(

              get(w, *first), 

              d[target(*first, g)][source(*first, g)],

              compare);

        else 

          d[target(*first, g)][source(*first, g)] = get(w, *first);

      }

    }

    return detail::floyd_warshall_dispatch(g, d, compare, combine, 

      inf, zero);

  }

  namespace detail {        

    template <class VertexListGraph, class DistanceMatrix, 

      class WeightMap, class P, class T, class R>

    bool floyd_warshall_init_dispatch(const VertexListGraph& g, 

      DistanceMatrix& d, WeightMap w, 

      const bgl_named_params<P, T, R>& params)

    {

      typedef typename property_traits<WeightMap>::value_type WM;

      return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,

        choose_param(get_param(params, distance_compare_t()), 

          std::less<WM>()),

        choose_param(get_param(params, distance_combine_t()), 

          closed_plus<WM>()),

        choose_param(get_param(params, distance_inf_t()), 

          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),

        choose_param(get_param(params, distance_zero_t()), 

          WM()));

    }

    template <class VertexAndEdgeListGraph, class DistanceMatrix, 

      class WeightMap, class P, class T, class R>

    bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g, 

      DistanceMatrix& d, WeightMap w, 

      const bgl_named_params<P, T, R>& params)

    {

      typedef typename property_traits<WeightMap>::value_type WM;

      return floyd_warshall_all_pairs_shortest_paths(g, d, w,

        choose_param(get_param(params, distance_compare_t()), 

          std::less<WM>()),

        choose_param(get_param(params, distance_combine_t()), 

          closed_plus<WM>()),

        choose_param(get_param(params, distance_inf_t()), 

          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),

        choose_param(get_param(params, distance_zero_t()), 

          WM()));

    }

  }   // namespace detail

  template <class VertexListGraph, class DistanceMatrix, class P, 

    class T, class R>

  bool floyd_warshall_initialized_all_pairs_shortest_paths(

    const VertexListGraph& g, DistanceMatrix& d, 

    const bgl_named_params<P, T, R>& params)

  {

    return detail::floyd_warshall_init_dispatch(g, d, 

      choose_const_pmap(get_param(params, edge_weight), g, edge_weight), 

      params);

  }

  template <class VertexListGraph, class DistanceMatrix>

  bool floyd_warshall_initialized_all_pairs_shortest_paths(

    const VertexListGraph& g, DistanceMatrix& d)

  {

    bgl_named_params<int,int> params(0);

    return detail::floyd_warshall_init_dispatch(g, d,

      get(edge_weight, g), params);

  }

  template <class VertexAndEdgeListGraph, class DistanceMatrix, 

    class P, class T, class R>

  bool floyd_warshall_all_pairs_shortest_paths(

    const VertexAndEdgeListGraph& g, DistanceMatrix& d, 

    const bgl_named_params<P, T, R>& params)

  {

    return detail::floyd_warshall_noninit_dispatch(g, d, 

      choose_const_pmap(get_param(params, edge_weight), g, edge_weight), 

      params);

  }

  template <class VertexAndEdgeListGraph, class DistanceMatrix>

  bool floyd_warshall_all_pairs_shortest_paths(

    const VertexAndEdgeListGraph& g, DistanceMatrix& d)

  {

    bgl_named_params<int,int> params(0);

    return detail::floyd_warshall_noninit_dispatch(g, d,

      get(edge_weight, g), params);

  }

} // namespace boost

#endif