ExplicitGraph.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*-------------------------- File ExplicitGraph.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_ExplicitGraph
 #define __PBeFS_ExplicitGraph
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <cstddef>
 
#include <cstdint>
 
#include <stdexcept>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/astar/Domain.h"
 
#include "PBeFS/astar/Structures.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
#if defined( PBEFS_STRUCTURES_STD )
 
/*--------------------------------------------------------------------------*/
/*------------------------ CLASS ExplicitAdjacency -------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class Cost >
class ExplicitAdjacency {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:

 
 explicit ExplicitAdjacency( std::size_t n ) : v_adj( n ) {}

 
 void add( std::uint32_t u , std::uint32_t v , Cost c ) {
  v_adj[ u ].emplace_back( v , c );
  }

 
 template< class F >
 void for_each( std::uint32_t u , F && f ) const {
  for( const auto & [ v , c ] : v_adj[ u ] )
   f( v , c );
  }

 
 [[nodiscard]] std::size_t size( void ) const noexcept {
  return( v_adj.size() );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 std::vector< std::vector< std::pair< std::uint32_t , Cost > > > v_adj;
 
 };  // end( class( ExplicitAdjacency ) )
 
#endif  /* PBEFS_STRUCTURES_STD */
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
/*------------------ THE ADJACENCY OF THE OTHER STRUCTURES -----------------*/
/*--------------------------------------------------------------------------*/
 
#if defined( PBEFS_STRUCTURES_BOOST )
 #include "PBeFS/astar/structures/boost/ExplicitAdjacency.h"
#elif defined( PBEFS_STRUCTURES_ADS )
 #include "PBeFS/astar/structures/ads/ExplicitAdjacency.h"
#endif
 
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS ExplicitGraph ---------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class Cost = int >
class ExplicitGraph {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using state_type = std::uint32_t;          
 using cost_type = Cost;                    
 
/*--------------------- CONSTRUCTOR AND INITIALIZATION ---------------------*/

 
 ExplicitGraph( std::size_t n , state_type s , state_type t )
  : f_source( s ) , f_target( t ) , f_adj( n ) , v_h( n , Cost( 0 ) ) {
  if( ( s >= n ) || ( t >= n ) )
   throw( std::invalid_argument( "ExplicitGraph::ExplicitGraph: source or "
                                 "target out of range" ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void add_edge( state_type u , state_type v , Cost c ,
                bool directed = false ) {
  if( ( u >= f_adj.size() ) || ( v >= f_adj.size() ) || ( c < 0 ) )
   throw( std::invalid_argument( "ExplicitGraph::add_edge: bad arc" ) );
  f_adj.add( u , v , c );
  if( ! directed )
   f_adj.add( v , u , c );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void set_heuristic( state_type u , Cost h ) { v_h.at( u ) = h; }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void set_source( state_type s ) {
  if( s >= f_adj.size() )
   throw( std::invalid_argument( "ExplicitGraph::set_source: bad node" ) );
  f_source = s;
  }
 
/*------------------------- METHODS OF THE DOMAIN --------------------------*/
 
 [[nodiscard]] state_type initial_state( void ) const noexcept {
  return( f_source );
  }
 
 [[nodiscard]] bool is_goal( state_type s ) const noexcept {
  return( s == f_target );
  }
 
 [[nodiscard]] std::uint64_t hash( state_type s ) const noexcept {
  return( ADS::splitmix64( s ) );
  }
 
 [[nodiscard]] Cost heuristic( state_type s ) const noexcept {
  return( v_h[ s ] );
  }
 
 template< class F >
 void for_each_successor( state_type s , Cost , F && f ) const {
  f_adj.for_each( s , [ & ]( state_type v , Cost c ) {
   f( v , c , v_h[ v ] );
   } );
  }
 
/*---------------------- FEATURES FOR ZOBRIST HASHING ----------------------*/
 
 [[nodiscard]] std::size_t num_features( void ) const noexcept {
  return( f_adj.size() );
  }
 
 template< class F >
 void for_each_feature( state_type s , F && f ) const {
  f( std::size_t( s ) );
  }
 
/*------------------------------ OTHER HASHES ------------------------------*/
 
 [[nodiscard]] std::uint64_t perfect_hash( state_type s ) const noexcept {
  return( s );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::size_t size( void ) const noexcept {
  return( f_adj.size() );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 state_type f_source;                                  
 state_type f_target;                                  
 ExplicitAdjacency< Cost > f_adj;                     
 std::vector< Cost > v_h;                     
 
 };  // end( class( ExplicitGraph ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_ExplicitGraph */
 
/*--------------------------------------------------------------------------*/
/*------------------------ End File ExplicitGraph.h ------------------------*/
/*--------------------------------------------------------------------------*/