FordFulkerson.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 <unordered_set>
 
#include <graph/GraphClasses.hpp>
#include <node/NodeClasses.hpp>
#include <edge/EdgeClasses.hpp>
 
namespace std {
template<>
struct hash<std::pair<node::Node, node::Node> > {
  std::size_t operator()(const std::pair<node::Node, node::Node> &p) const {
    return std::hash<std::string>()(ext::to_string(p.first) + ext::to_string(p.second));
  }
};
}
 
// =====================================================================================================================
 
namespace graph {
 
namespace minimum_cut {
 
typedef std::unordered_set<std::pair<node::Node, node::Node> > Cut;
 
// Old implementation without templates
using UndirectedGraph = graph::UndirectedGraph<node::Node, edge::CapacityEdge<node::Node, int>>;
using DirectedGraph = graph::DirectedGraph<node::Node, edge::CapacityEdge<node::Node, int>>;
 
class FordFulkerson {
 public:
// ---------------------------------------------------------------------------------------------------------------------
 
  static Cut findMinimumCut(const DirectedGraph &graph,
                            const node::Node &source,
                            const node::Node &sink);
 
  static Cut findMinimumCut(const UndirectedGraph &graph,
                            const node::Node &source,
                            const node::Node &sink);
 
// ---------------------------------------------------------------------------------------------------------------------
 
};
 
// =====================================================================================================================
 
 
// ---------------------------------------------------------------------------------------------------------------------
 
} // namespace minimum_cut
 
} // namespace graph