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 296 of file hamiltonian_path.h.

#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

Constructor & Destructor Documentation

◆ LatticeMemoryManager()

template<typename Set, typename CostType>

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

inline

Definition at line 298 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 412 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 recurrence

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 362 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 436 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 315 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 448 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 328 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 442 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 338 of file hamiltonian_path.h.

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

ortools/graph/hamiltonian_path.h

Detailed Description

Public Member Functions

Constructor & Destructor Documentation

◆ LatticeMemoryManager()

Member Function Documentation

◆ BaseOffset()

◆ Init()

◆ Offset()

◆ OffsetDelta()

◆ SetValue()

◆ SetValueAtOffset()

◆ Value()

◆ ValueAtOffset()