Program Listing for File Heuristics.h

↰ Return to documentation for file (ADS/intractable/Heuristics.h)

/*--------------------------------------------------------------------------*/
/*--------------------------- File Heuristics.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/complexity/Problems.h"
#include "ADS/graph/MinimumSpanningTree.h"
#include "ADS/intractable/Approximation.h"
#include "ADS/mfset/MFSet.h"
#include "ADS/string/Alignment.h"

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <numeric>
#include <set>
#include <string>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------------ GREEDY TSP --------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
std::pair< std::vector< std::pair< int , int > > , Nodes > greedyTsp(
                        const std::vector< std::vector< T > > & D );

/*--------------------------------------------------------------------------*/
/*---------------------------- LOCAL SEARCH --------------------------------*/
/*--------------------------------------------------------------------------*/

inline Nodes twoOptMove( Nodes pi , int i , int j );

template< class T >
Nodes twoOpt( const std::vector< std::vector< T > > & D , Nodes pi ,
              std::vector< T > * trace = nullptr );

inline long kOptNeighbours( int n , int k );

inline std::vector< int > partitionLocalSearch( const std::vector< long > & A ,
                                                std::vector< int > side );

/*--------------------------------------------------------------------------*/
/*---------------------------- BISECTION -----------------------------------*/
/*--------------------------------------------------------------------------*/

class Buckets {

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

 explicit Buckets( int n );

 void insert( int u );

 void remove( int u );

 void inc( int k , int u );

 [[nodiscard]] bool contains( int u ) const;

 [[nodiscard]] int count( int k , int u ) const;

 [[nodiscard]] const Nodes & bucket( int k , int h ) const;

 [[nodiscard]] int dim( int k , int h ) const;

 [[nodiscard]] int min( int k ) const;

 [[nodiscard]] int max( int k ) const;

 [[nodiscard]] int choose( int k ) const;

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

 void put( int k , int u );

 void take( int k , int u );

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

 int f_n;
 std::vector< Nodes > f_bucket[ 2 ];
 std::vector< int > f_h[ 2 ] , f_place[ 2 ];
 int f_min[ 2 ] , f_max[ 2 ];

 };  // end( class Buckets )

inline std::vector< int > minMaxGreedy( const Adjacency & G , int a , int b );

inline int cutSize( const Adjacency & G , const std::vector< int > & side );

/*--------------------------------------------------------------------------*/
/*----------------------------- STRINGS ------------------------------------*/
/*--------------------------------------------------------------------------*/

inline int overlap( const std::string & a , const std::string & b );

inline std::string greedySuperstring( const std::vector< std::string > & P );

inline std::pair< int , std::vector< std::pair< std::string , std::string > > >
starAlignment( const std::vector< std::string > & P );

/*--------------------------------------------------------------------------*/
/*----------------------------- COLORING -----------------------------------*/
/*--------------------------------------------------------------------------*/

inline std::vector< int > dsatur( const Adjacency & G );

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

}  // end( namespace ADS )

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

#include "ADS/intractable/impl/Heuristics.tpp"

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

#endif  /* Heuristics.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File Heuristics.h --------------------------*/
/*--------------------------------------------------------------------------*/