PBeFS
Parallel Best-First Search
Loading...
Searching...
No Matches
Node.h
Go to the documentation of this file.
1/*--------------------------------------------------------------------------*/
2/*------------------------------ File Node.h -------------------------------*/
3/*--------------------------------------------------------------------------*/
20/*--------------------------------------------------------------------------*/
21/*------------------------------ DEFINITIONS -------------------------------*/
22/*--------------------------------------------------------------------------*/
23
24#ifndef __PBeFS_Node
25 #define __PBeFS_Node
26 /* self-identification: #endif at the end of the file */
27
28/*--------------------------------------------------------------------------*/
29/*-------------------------------- INCLUDES --------------------------------*/
30/*--------------------------------------------------------------------------*/
31
32#include <algorithm>
33
34#include <cstddef>
35
36#include <cstdint>
37
38#include <limits>
39
40#include <memory>
41
42#include <type_traits>
43
44#include <vector>
45
46#include "PBeFS/astar/Domain.h"
47
48#include "PBeFS/astar/Structures.h"
49
50#include "PBeFS/core/SearchUtils.h"
51
52/*--------------------------------------------------------------------------*/
53/*------------------------------- NAMESPACE --------------------------------*/
54/*--------------------------------------------------------------------------*/
55
57namespace PBeFS_di_unipi_it
58{
59
60/*--------------------------------------------------------------------------*/
61/*------------------------------- CLASS Node -------------------------------*/
62/*--------------------------------------------------------------------------*/
64
72
73template< class State , class Cost >
74struct Node {
75
76 State state;
77 Cost g;
78 Cost h;
79 Node * parent;
80 bool closed;
81 bool expanded;
82 std::uint8_t op = no_op;
83 std::uint32_t key = 0;
84
87 [[nodiscard]] Cost f( void ) const noexcept { return( g + h ); }
88
89 }; // end( struct( Node ) )
90
91
92/*--------------------------------------------------------------------------*/
93
94/*--------------------------------------------------------------------------*/
95/*------------------------------- FUNCTIONS --------------------------------*/
96/*--------------------------------------------------------------------------*/
98
99template< class Cost >
100[[nodiscard]] constexpr Cost infinite_cost( void ) noexcept
101{
102 if constexpr( std::numeric_limits< Cost >::has_infinity )
103 return( std::numeric_limits< Cost >::infinity() );
104 else
105 return( std::numeric_limits< Cost >::max() );
106 }
107
108/*--------------------------------------------------------------------------*/
112
113
114template< class Cost >
115 requires std::is_integral_v< Cost >
116[[nodiscard]] constexpr std::uint64_t packed_fg( Cost g , Cost h ) noexcept
117{
118 return( ( std::uint64_t( g + h ) << 32 ) |
119 ( ~std::uint64_t( g ) & 0xFFFFFFFFu ) );
120 }
121
122/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
124
125template< class NodeT >
126[[nodiscard]] auto trace_path( const NodeT * goal )
127{
128 std::vector< decltype( goal->state ) > path;
129 for( const NodeT * n = goal ; n ; n = n->parent )
130 path.push_back( n->state );
131 std::reverse( path.begin() , path.end() );
132 return( path );
133 }
134
135/*--------------------------------------------------------------------------*/
136
137} // end( namespace PBeFS_di_unipi_it )
138
139/*--------------------------------------------------------------------------*/
140
141// the structures of the chosen set [see Structures.h]
142#if defined( PBEFS_STRUCTURES_STD )
143 #include "PBeFS/astar/structures/std/NodePool.h"
144#elif defined( PBEFS_STRUCTURES_BOOST )
145 #include "PBeFS/astar/structures/boost/NodePool.h"
146#elif defined( PBEFS_STRUCTURES_ADS )
147 #include "PBeFS/astar/structures/ads/NodePool.h"
148#endif
149
150/*--------------------------------------------------------------------------*/
151
152#endif /* __PBeFS_Node */
153
154/*--------------------------------------------------------------------------*/
155/*---------------------------- End File Node.h -----------------------------*/
156/*--------------------------------------------------------------------------*/
Domain.h
Header file for the concepts a search problem has to satisfy in order to be searched by the algorithm...
NodePool.h
Header file for the class template NodePool of the set of data structures of ADS [see Structures....
SearchUtils.h
Header file for the small helpers shared by the searches: a stopwatch, the placement of the workers o...
Structures.h
Header file for the choice of the set of data structures of A*: the arena of the nodes (NodePool),...
PBeFS_di_unipi_it
namespace for the Parallel Best-First Search library
Definition AStar.h:83
PBeFS_di_unipi_it::infinite_cost
constexpr Cost infinite_cost(void) noexcept
the largest value of a cost type, used as "no incumbent yet"
Definition Node.h:100
PBeFS_di_unipi_it::packed_fg
constexpr std::uint64_t packed_fg(Cost g, Cost h) noexcept
with integer costs, f = g + h in the high half of a word and the complement of g in the low one,...
Definition Node.h:116
PBeFS_di_unipi_it::no_op
constexpr std::uint8_t no_op
the operator of the root, which no state was generated by
Definition Domain.h:205
PBeFS_di_unipi_it::trace_path
auto trace_path(const NodeT *goal)
the states from the root to goal, following the parent pointers
Definition Node.h:126
PBeFS_di_unipi_it::Node
a node of the search graph
Definition Node.h:74
PBeFS_di_unipi_it::Node::parent
Node * parent
the predecessor on that path (nullptr at the root)
Definition Node.h:79
PBeFS_di_unipi_it::Node::expanded
bool expanded
true if ever expanded
Definition Node.h:81
PBeFS_di_unipi_it::Node::closed
bool closed
true if expanded with the current g
Definition Node.h:80
PBeFS_di_unipi_it::Node::op
std::uint8_t op
the operator that generated the state
Definition Node.h:82
PBeFS_di_unipi_it::Node::state
State state
the state
Definition Node.h:76
PBeFS_di_unipi_it::Node::g
Cost g
the cost of the best path found from the root
Definition Node.h:77
PBeFS_di_unipi_it::Node::h
Cost h
the heuristic estimate of the cost to a goal
Definition Node.h:78
PBeFS_di_unipi_it::Node::f
Cost f(void) const noexcept
the estimate of the cost of a solution through the Node
Definition Node.h:87
PBeFS_di_unipi_it::Node::key
std::uint32_t key
the key of the state for its owner
Definition Node.h:83