Program Listing for File Problems.h

↰ Return to documentation for file (ADS/complexity/Problems.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File Problems.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdlib>
#include <numeric>
#include <optional>
#include <vector>

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

namespace ADS {

using Adjacency = std::vector< std::vector< bool > >;
using Clause = std::vector< int >;
using Cnf = std::vector< Clause >;
using Nodes = std::vector< int >;

/*--------------------------------------------------------------------------*/
/*------------------------------ GRAPHS ------------------------------------*/
/*--------------------------------------------------------------------------*/

inline bool cliqueCertificate( const Adjacency & G , const Nodes & S , int k );

namespace detail {

template< class Ok , class Done >
bool chooseK( int n , int k , Ok && ok , Done && done );

}  // end( namespace detail )

inline std::optional< Nodes > clique( const Adjacency & G , int k );

inline std::optional< Nodes > independentSet( const Adjacency & G , int k );

inline std::optional< Nodes > vertexCover( const Adjacency & G , int k );

inline std::optional< std::vector< int > > coloring( const Adjacency & G ,
                                                     int k );

inline std::optional< Nodes > bisection( const Adjacency & G , int k );

template< class T >
bool tspCertificate( const std::vector< std::vector< T > > & D , T k ,
                     const Nodes & P );

template< class T >
std::optional< Nodes > tsp( const std::vector< std::vector< T > > & D , T k );

namespace detail {

inline std::optional< Nodes > hamilton( const Adjacency & G ,
                                        const Nodes & starts , bool cycle ,
                                        int end = -1 );

inline Nodes all( int n );

}  // end( namespace detail )

inline std::optional< Nodes > hamiltonianCircuit( const Adjacency & G );

inline std::optional< Nodes > hamiltonianCycle( const Adjacency & G );

inline std::optional< Nodes > hamiltonianPath( const Adjacency & G ,
                                               int r = -1 , int t = -1 );

inline std::optional< Nodes > hamiltonianChain( const Adjacency & G );

inline std::optional< Nodes > longestPath( const Adjacency & G , int r ,
                                           int t , int k );

inline int longestPathDag( const Adjacency & G , int r , int t );

inline std::optional< std::vector< std::pair< int , int > > >
boundedSpanningTree( const Adjacency & G , int k );

/*--------------------------------------------------------------------------*/
/*---------------------- LOGIC AND LINEAR PROGRAMMING ----------------------*/
/*--------------------------------------------------------------------------*/

inline bool satCertificate( const Cnf & F , const std::vector< bool > & x );

inline std::optional< std::vector< bool > > satisfiable( const Cnf & F ,
                                                         int n );

inline std::optional< std::vector< int > > lp01(
                              const std::vector< std::vector< long > > & A ,
                              const std::vector< long > & b , int n );

/*--------------------------------------------------------------------------*/
/*------------------------------- NUMBERS ----------------------------------*/
/*--------------------------------------------------------------------------*/

inline std::optional< Nodes > subsetSumExists( const std::vector< long > & A ,
                                               long k );

inline std::optional< Nodes > partition( const std::vector< long > & A );

inline std::optional< Nodes > knapsackDecision( const std::vector< long > & p ,
                                                const std::vector< long > & v ,
                                                long C , long k );

inline std::optional< std::vector< int > > multiprocessorScheduling(
                        const std::vector< long > & t , int m , long d );

inline std::optional< Nodes > exactCover3(
                      const std::vector< std::array< int , 3 > > & Y , int m );

inline std::optional< Nodes > threeDimensionalMatching(
                     const std::vector< std::array< int , 3 > > & M , int q );

inline std::optional< std::vector< long > > bribes(
                      std::vector< long > M , const std::vector< bool > & ps );

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

}  // end( namespace ADS )

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

#include "ADS/complexity/impl/Problems.tpp"

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

#endif  /* Problems.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File Problems.h ---------------------------*/
/*--------------------------------------------------------------------------*/