FloydWarshall.hpp

Go to the documentation of this file.

 
// Copyright (c) 2017 Czech Technical University in Prague | Faculty of Information Technology. All rights reserved.
 
#pragma once
 
#include <functional>
#include <alib/map>
#include <alib/set>
#include <limits>
#include <stdexcept>
 
#include <common/SupportFunction.hpp>
 
namespace graph {
 
namespace shortest_path {
 
class FloydWarshall {
// ---------------------------------------------------------------------------------------------------------------------
 
 public:
  template<typename TGraph>
  static
  ext::map<typename TGraph::node_type, ext::map<typename TGraph::node_type, typename TGraph::edge_type::weight_type>>
  run(const TGraph &graph);
 
// =====================================================================================================================
 
};
 
// =====================================================================================================================
 
template<typename TGraph>
ext::map<typename TGraph::node_type, ext::map<typename TGraph::node_type, typename TGraph::edge_type::weight_type>>
FloydWarshall::run(const TGraph &graph) {
  using weight_type = typename TGraph::edge_type::weight_type;
  using node_type = typename TGraph::node_type;
 
  ext::map<node_type, ext::map<node_type, weight_type>> dist;
 
  ext::set<node_type> nodes = graph.getNodes();
 
  // Init distances matrix
  for (auto &first : nodes) {
    dist.insert(ext::make_pair(first, ext::map<node_type, weight_type>()));
    for (auto &second: nodes) {
      if (first == second) {
        dist[first].insert(ext::make_pair(second, 0));
      } else {
        dist[first].insert(ext::make_pair(second, std::numeric_limits<weight_type>::max()));
      }
    }
  }
 
  for (auto &first : nodes) {
    for (auto &s_edge : graph.successorEdges(first)) {
      const node_type &s = common::SupportFunction::other(s_edge, first); // successor
      dist[first][s] = std::min(dist[s_edge.first][s_edge.second], s_edge.weight());
    }
  }
 
  // Run FloydWarshall
  for (auto &k : nodes) {
    for (auto &i : nodes) {
      if (dist[i][k] != std::numeric_limits<weight_type>::max()) { // Optimization
        for (auto &j : nodes) {
          if (dist[k][j] != std::numeric_limits<weight_type>::max()) { // Optimization
            dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
          }
        }
      }
    }
  }
 
  // Check for negative cycle
  for (auto &n : nodes)
    if (dist[n][n] < 0)
      throw std::out_of_range("FloydWarshall: Detected negative weight cycle.");
 
  return dist;
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
} // namespace shortest_path
 
} // namespace graph