operations_research::LatticeMemoryManager< Set, CostType > Class Template Reference

#include <hamiltonian_path.h>

Public Member Functions
	LatticeMemoryManager ()
void	Init (int max_card)
	Reserves memory and fills in the data necessary to access memory.
uint64_t	Offset (Set s, int node) const
	Returns the offset in memory for f(s, node), with node contained in s.
uint64_t	BaseOffset (int card, Set s) const
uint64_t	OffsetDelta (int card, int added_node, int removed_node, int rank) const
void	SetValue (Set s, int node, CostType value)
void	SetValueAtOffset (uint64_t offset, CostType value)
CostType	Value (Set s, int node) const
CostType	ValueAtOffset (uint64_t offset) const

Detailed Description

template<typename Set, typename CostType>
class operations_research::LatticeMemoryManager< Set, CostType >

The Dynamic Programming (DP) algorithm memorizes the values f(set, node) for node in set, for all the subsets of cardinality <= max_card_. LatticeMemoryManager manages the storage of f(set, node) so that the DP iteration access memory in increasing addresses.

Definition at line 290 of file hamiltonian_path.h.

Constructor & Destructor Documentation

LatticeMemoryManager()

template<typename Set , typename CostType >

operations_research::LatticeMemoryManager< Set, CostType >::LatticeMemoryManager ( )

inline

Definition at line 292 of file hamiltonian_path.h.

Member Function Documentation

BaseOffset()

template<typename Set , typename CostType >

uint64_t operations_research::LatticeMemoryManager< Set, CostType >::BaseOffset ( int card, Set s ) const

inline

Returns the base offset in memory for f(s, node), with node contained in s. This is useful in the Dynamic Programming iterations. Note(user): inlining this function gains about 5%.

Todo

(user): Investigate how to compute BaseOffset(card - 1, s \ { n }) from BaseOffset(card, n) to speed up the DP iteration.

There are binomial_coefficients_[node][node_rank + 1] sets which have node at node_rank.

Note(user): It is possible to get rid of base_offset_[card] by using a 2-D array. It would also make it possible to free all the memory but the layer being constructed and the preceding one, if another lattice of paths is constructed.

Todo

(user): Evaluate the interest of the above. There are 'card' f(set, j) to store. That is why we need to multiply local_offset by card before adding it to the corresponding base_offset_.

Definition at line 406 of file hamiltonian_path.h.

Init()

template<typename Set , typename CostType >

void operations_research::LatticeMemoryManager< Set, CostType >::Init

(

int

max_card

)

Reserves memory and fills in the data necessary to access memory.

Initialize binomial_coefficients_ using Pascal's triangle recursion.

Extend to (n, n + 1) to minimize branchings in LatticeMemoryManager(). This also makes the recurrence above work for k = n.

There are k * binomial_coefficients_[max_card_][k] f(S,j) values to store for each group of f(S,j), with card(S) = k. Update base_offset[k] accordingly.

Definition at line 356 of file hamiltonian_path.h.

Offset()

template<typename Set , typename CostType >

uint64_t operations_research::LatticeMemoryManager< Set, CostType >::Offset	(	Set	s,
		int	node ) const

Returns the offset in memory for f(s, node), with node contained in s.

Definition at line 430 of file hamiltonian_path.h.

OffsetDelta()

template<typename Set , typename CostType >

uint64_t operations_research::LatticeMemoryManager< Set, CostType >::OffsetDelta ( int card, int added_node, int removed_node, int rank ) const

inline

Returns the offset delta for a set of cardinality 'card', to which node 'removed_node' is replaced by 'added_node' at 'rank'

Definition at line 309 of file hamiltonian_path.h.

SetValue()

template<typename Set , typename CostType >

void operations_research::LatticeMemoryManager< Set, CostType >::SetValue	(	Set	s,
		int	node,
		CostType	value )

Memorizes the value = f(s, node) at the correct offset. This is favored in all other uses than the Dynamic Programming iterations.

Definition at line 442 of file hamiltonian_path.h.

SetValueAtOffset()

template<typename Set , typename CostType >

void operations_research::LatticeMemoryManager< Set, CostType >::SetValueAtOffset ( uint64_t offset, CostType value )

inline

Memorizes 'value' at 'offset'. This is useful in the Dynamic Programming iterations where we want to avoid compute the offset of a pair (set, node).

Definition at line 322 of file hamiltonian_path.h.

Value()

template<typename Set , typename CostType >

CostType operations_research::LatticeMemoryManager< Set, CostType >::Value	(	Set	s,
		int	node ) const

Returns the memorized value f(s, node) with node in s. This is favored in all other uses than the Dynamic Programming iterations.

Definition at line 436 of file hamiltonian_path.h.

ValueAtOffset()

template<typename Set , typename CostType >

CostType operations_research::LatticeMemoryManager< Set, CostType >::ValueAtOffset ( uint64_t offset ) const

inline

Returns the memorized value at 'offset'. This is useful in the Dynamic Programming iterations.

Definition at line 332 of file hamiltonian_path.h.

---

The documentation for this class was generated from the following file:

• ortools/graph/hamiltonian_path.h