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 <alib/unordered_map>
 
#include <graph/GraphClasses.hpp>
#include <node/NodeClasses.hpp>
#include <edge/EdgeClasses.hpp>
 
namespace graph {
 
namespace maximum_flow {
 
typedef ext::unordered_map<node::Node, ext::unordered_map<node::Node, int> > Capacity;
typedef ext::unordered_map<node::Node, ext::unordered_map<node::Node, int> > Flow;
 
// 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 Flow findMaximumFlow(const DirectedGraph &graph,
                              const node::Node &source,
                              const node::Node &sink);
 
  static Flow findMaximumFlow(const UndirectedGraph &graph,
                              const node::Node &source,
                              const node::Node &sink);
 
// ---------------------------------------------------------------------------------------------------------------------
 
};
 
// =====================================================================================================================
 
 
// ---------------------------------------------------------------------------------------------------------------------
 
} // namespace maximum_flow
 
} // namespace graph