Program Listing for File MaxFlow.h

↰ Return to documentation for file (ADS/graph/MaxFlow.h)

/*--------------------------------------------------------------------------*/
/*----------------------------- File MaxFlow.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_MaxFlow
 #define __ADS_MaxFlow
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"

#include <algorithm>
#include <cstddef>
#include <limits>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

enum class Augment { FORD_FULKERSON , EDMONDS_KARP , DINIC };

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS FlowNetwork ----------------------------*/
/*--------------------------------------------------------------------------*/

class FlowNetwork {

/*--------------------------------------------------------------------------*/
 public:

 explicit FlowNetwork( int n );

 [[nodiscard]] int n( void ) const { return( int( f_adj.size() ) ); }

 int addEdge( int u , int v , long long c );

 [[nodiscard]] long long flow( int e ) const;

 [[nodiscard]] long long capacity( int e ) const;

 long long maxFlow( int s , int t , Augment how = Augment::DINIC ,
                    long long * paths = nullptr );

 [[nodiscard]] std::vector< bool > minCut( int s ) const;

/*--------------------------------------------------------------------------*/
 private:

 struct Edge { int to; long long cap , flow; };

 static constexpr long long INF = std::numeric_limits< long long >::max();

 long long residual( int e ) const;

 void push( int e , long long d );

 long long bfsAugment( int s , int t );

 long long dfsAugment( int s , int t );

 bool levels( int s , int t );

 long long blocking( int u , int t , long long d );

 [[nodiscard]] bool skewSymmetric( void ) const;

 std::vector< std::vector< int > > f_adj;
 std::vector< Edge > f_e;
 std::vector< int > f_level;
 std::vector< std::size_t > f_next;

 };  // end( class FlowNetwork )

struct BoundedEdge { int u , v; long long low , high; };

inline bool feasibleCirculation( int n , const std::vector< BoundedEdge > & E ,
                                 std::vector< long long > * flows = nullptr );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/graph/impl/MaxFlow.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* MaxFlow.h included */

/*--------------------------------------------------------------------------*/
/*--------------------------- End File MaxFlow.h ---------------------------*/
/*--------------------------------------------------------------------------*/