End of the interface. Below is the implementation. More...

Detailed Description

End of the interface. Below is the implementation.

Implementation details, here and below.

Implementation.

Todo: (user): Support the user providing already-allocated memory buffers for the radix counts and/or for the temporary vector<T> copy.

The rest of this .h is the implementation of the above templates.

Todo: (user): introduce an enum to choose the algorithm. It's useless as long as this file only provides Yen.

Template implementations

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Clearly not the fastest radix sort, but its complexity is the right one. Furthermore:

it is as memory-safe as std::vectors can be (no pointers),
no multiplication is performed,
it is stable
it handles the cases of signed and unsigned integers automatically,
bounds on the keys are optional, or they can be computed automatically,
based on those bounds, the number of passes is automatically computed,
a payload is associated to each key, and it is sorted in the same way as the keys. This payload can be a vector of integers or a vector of pointers to larger objects.
Todo
(user): Make it an independent library.

Classes
struct	AlignedBlock
struct	AllocatorWithAlignment
class	ElementGetter
struct	is_strong_int
struct	is_strong_int<::util_intops::StrongInt< Tag, Native, Validator > >
class	PathContainerImpl
class	PathWithPriority
struct	ReleaseSCIPMessageHandler
class	ScipCallbackRunner
class	ScipCallbackRunnerImpl
class	ScopedSCIPMessageHandlerDisabler
struct	ToUInt
struct	ToUInt< double >
struct	ToUInt< float >
class	UnderlyingContainerAdapter
class	UntypedGScipConstraintHandler
class	UntypedGScipConstraintHandlerImpl

Typedefs
template<typename T>
using	to_uint = typename ToUInt<T>::type
template<typename IndexType, typename ValueType>
using	IndexedVector
using	MessageHandlerPtr

Functions
template<class T>
bool	IsNanGeneric (const T &)
template<>
bool	IsNanGeneric (const float &x)
template<>
bool	IsNanGeneric (const double &x)
template<>
bool	IsNanGeneric (const long double &x)
template<typename T>
bool	AreNumbersOfSameSign (const T &x, const T &y)
template<typename IntT>
constexpr bool	UsesTwosComplement ()
uint64_t	OneBit64 (int pos)
uint64_t	BitPos64 (uint64_t pos)
uint64_t	BitOffset64 (uint64_t pos)
uint64_t	BitLength64 (uint64_t size)
bool	IsBitSet64 (const uint64_t *const bitset, uint64_t pos)
void	SetBit64 (uint64_t *const bitset, uint64_t pos)
void	ClearBit64 (uint64_t *const bitset, uint64_t pos)
template<typename T>
std::vector< T >	GetInversePermutation (const std::vector< T > &permutation)
template<typename Graph>
bool	GraphIsConnected (const Graph &graph)
template<class GraphType>
GraphType::ArcIndex	FindArcIndex (const GraphType &graph, const typename GraphType::NodeIndex source, const typename GraphType::NodeIndex destination)
template<class GraphType>
std::tuple< std::vector< typename GraphType::NodeIndex >, PathDistance >	ComputeShortestPath (const GraphType &graph, const std::vector< PathDistance > &arc_lengths, const typename GraphType::NodeIndex source, const typename GraphType::NodeIndex destination)
template<class GraphType>
PathDistance	ComputePathLength (const GraphType &graph, const absl::Span< const PathDistance > arc_lengths, const absl::Span< const typename GraphType::NodeIndex > path)
	Computes the total length of a path.
template<typename NodeType>
bool	IsValidParent (const NodeType node, const NodeType num_tree_nodes)
template<typename NodeType>
absl::Status	IsValidNode (const NodeType node, const NodeType num_tree_nodes)
template<typename NodeType>
std::vector< NodeType >	ExtractCycle (absl::Span< const NodeType > parents, const NodeType node_in_cycle)
template<typename NodeType>
std::string	CycleErrorMessage (absl::Span< const NodeType > cycle)
template<typename NodeType>
std::vector< NodeType >	CheckForCycle (absl::Span< const NodeType > parents, std::vector< NodeType > *topological_order)
absl::Status	RegisterConstraintHandler (GScip *gscip, std::unique_ptr< UntypedGScipConstraintHandler > constraint_handler)
absl::StatusOr< SCIP_CONS * >	AddCallbackConstraint (GScip gscip, const std::string &handler_name, const std::string &constraint_name, void constraint_data, const GScipConstraintOptions &options)
MessageHandlerPtr	CaptureMessageHandlerPtr (SCIP_MESSAGEHDLR *const handler)
absl::StatusOr< MessageHandlerPtr >	MakeSCIPMessageHandler (GScipMessageHandler gscip_message_handler)
	Make a message handler for SCIP that calls the input function.
void	AddConstraintHandlerImpl (const ScipConstraintHandlerDescription &description, std::unique_ptr< ScipCallbackRunner > runner, SCIP *scip)
void	AddCallbackConstraintImpl (SCIP scip, const std::string &handler_name, const std::string &constraint_name, void constraint_data, const ScipCallbackConstraintOptions &options)
absl::Status	ScipCodeToUtilStatus (int retcode, const char source_file, int source_line, const char scip_statement)
	Our own version of SCIP_CALL to do error management.
template<typename Proto>
std::vector< Proto >	ReadNumRecords (File *file, int expected_num_records)
template<typename Proto>
std::vector< Proto >	ReadNumRecords (absl::string_view filename, int expected_num_records)
	Ditto, taking a filename as argument.
template<typename Value, size_t size>
void	AddInPlace (AlignedBlock< Value, size > &out, const AlignedBlock< Value, size > &in)
template<size_t block_size, size_t num_blocks_per_iteration, typename Value>
AlignedBlock< Value, block_size > ABSL_ATTRIBUTE_NOINLINE	AlignedBlockSum (const AlignedBlock< Value, block_size > *blocks, size_t num_blocks)
template<size_t block_size = 4, size_t num_blocks_per_iteration = 4, bool assume_aligned_at_start = false, typename Value>
Value	VectorSum (absl::Span< const Value > values)

Variables
const PathDistance	kMaxDistance = std::numeric_limits<PathDistance>::max() - 1
const PathDistance	kDisconnectedDistance

Typedef Documentation

◆ IndexedVector

template<typename IndexType, typename ValueType>

using operations_research::internal::IndexedVector

Initial value:

 
    std::conditional_t<is_strong_int<IndexType>::value,
                       ::util_intops::StrongVector<IndexType, ValueType>,
                       std::vector<ValueType>>

Definition at line 78 of file bounded_dijkstra.h.

◆ MessageHandlerPtr

using operations_research::internal::MessageHandlerPtr

Initial value:

std::unique_ptr<SCIP_MESSAGEHDLR, ReleaseSCIPMessageHandler>

A unique_ptr that releases a SCIP message handler when destroyed.

Use CaptureMessageHandlerPtr() to create to capture an existing message handler and creates this automatic pointer that will released it on destruction.

Definition at line 54 of file gscip_message_handler.h.

◆ to_uint

template<typename T>

using operations_research::internal::to_uint = typename ToUInt<T>::type

Definition at line 96 of file radix_sort.h.

Function Documentation

◆ AddCallbackConstraint()

absl::StatusOr< SCIP_CONS * > operations_research::internal::AddCallbackConstraint	(	GScip *	gscip,
		const std::string &	handler_name,
		const std::string &	constraint_name,
		void *	constraint_data,
		const GScipConstraintOptions &	options )

Definition at line 615 of file gscip_constraint_handler.cc.

◆ AddCallbackConstraintImpl()

void operations_research::internal::AddCallbackConstraintImpl	(	SCIP *	scip,
		const std::string &	handler_name,
		const std::string &	constraint_name,
		void *	constraint_data,
		const ScipCallbackConstraintOptions &	options )

Definition at line 440 of file scip_callback.cc.

◆ AddConstraintHandlerImpl()

void operations_research::internal::AddConstraintHandlerImpl	(	const ScipConstraintHandlerDescription &	description,
		std::unique_ptr< ScipCallbackRunner >	runner,
		SCIP *	scip )

Definition at line 416 of file scip_callback.cc.

◆ AddInPlace()

template<typename Value, size_t size>

void operations_research::internal::AddInPlace	(	AlignedBlock< Value, size > &	out,
		const AlignedBlock< Value, size > &	in )

In-place addition for two AlignedBlock values. Adds in to out, storing the value in out. Unless something steps in, this compiles into a single *addp* instruction.

Definition at line 54 of file vector_sum_internal.h.

◆ AlignedBlockSum()

template<size_t block_size, size_t num_blocks_per_iteration, typename Value>

AlignedBlock< Value, block_size > ABSL_ATTRIBUTE_NOINLINE operations_research::internal::AlignedBlockSum	(	const AlignedBlock< Value, block_size > *	blocks,
		size_t	num_blocks )

Computes the sum of num_blocks aligned blocks. Proceeds in three phases:

Parallel sum with N = num_blocks_per_iteration independent block-sized accumulators. At the end, accumulator i contains partial sums at indices i, i + N, i + 2*N, ..., i + M*N, where M is the largest number of blocks such that i+M*N < num_blocks for all i.
Parallel addition of remaining blocks. All remaining blocks are added to accumulators 0, ..., num_remaining_blocks - 1.
Sum of accumulators: all accumulators are added together. The result is a single block-sized accumulator that is returned to the caller.

The code of the function was specifically tuned for 32-bit floating point values, and works best with block_size = 4 and num_blocks_per_iteration = 4. It will likely work with other types, but may require extra care and possibly different parameters.

NOTE(user): As of 2023-04-28, Clang's auto-vectorizer is very brittle and most attempts to reduce the last accumulator from step 3 into a single value prevents the rest of the function from being vectorized. To mitigate this behavior we return the whole block (which should normally fit into a single vector register). We also mark the function with ABSL_ATTRIBUTE_NOINLINE to make prevent the inliner from merging this function with any additional code that would prevent vectorization.

Phase 1: Parallel sum of the bulk of the data.

Phase 2: Semi-parallel sum of the remaining up to num_blocks_per_iteration - 1 blocks.

Phase 3: Reduce the accumulator blocks to a single block. NOTE(user): When this code is auto-vectorized correctly, the initial copy is a no-op, and the for loop below translates to num_blocks_per_iteration - 1 vector add instructions. In 2023-05, I experimented with other versions (e.g. using sum[0] as the target or making res a const reference to sum[0], but in most cases they broke vectorization of the whole function).

Definition at line 84 of file vector_sum_internal.h.

◆ AreNumbersOfSameSign()

template<typename T>

bool operations_research::internal::AreNumbersOfSameSign	(	const T &	x,
		const T &	y )

Definition at line 161 of file binary_search.h.

◆ BitLength64()

uint64_t operations_research::internal::BitLength64 ( uint64_t size )

inline

Definition at line 26 of file bitmap.h.

◆ BitOffset64()

uint64_t operations_research::internal::BitOffset64 ( uint64_t pos )

inline

Definition at line 25 of file bitmap.h.

◆ BitPos64()

uint64_t operations_research::internal::BitPos64 ( uint64_t pos )

inline

Definition at line 24 of file bitmap.h.

◆ CaptureMessageHandlerPtr()

MessageHandlerPtr operations_research::internal::CaptureMessageHandlerPtr ( SCIP_MESSAGEHDLR * handler )

Captures the input handler and returns a unique pointer that will release it when destroyed.

Definition at line 115 of file gscip_message_handler.cc.

◆ CheckForCycle()

template<typename NodeType>

std::vector< NodeType > operations_research::internal::CheckForCycle	(	absl::Span< const NodeType >	parents,
		std::vector< NodeType > *	topological_order )

Every element of parents must be in {kNullParent} union [0..parents.size()), otherwise UB.

Definition at line 390 of file rooted_tree.h.

◆ ClearBit64()

void operations_research::internal::ClearBit64	(	uint64_t *const	bitset,
		uint64_t	pos )

inline

Definition at line 33 of file bitmap.h.

◆ ComputePathLength()

template<class GraphType>

PathDistance operations_research::internal::ComputePathLength	(	const GraphType &	graph,
		const absl::Span< const PathDistance >	arc_lengths,
		const absl::Span< const typename GraphType::NodeIndex >	path )

Computes the total length of a path.

Definition at line 199 of file k_shortest_paths.h.

◆ ComputeShortestPath()

template<class GraphType>

std::tuple< std::vector< typename GraphType::NodeIndex >, PathDistance > operations_research::internal::ComputeShortestPath	(	const GraphType &	graph,
		const std::vector< PathDistance > &	arc_lengths,
		const typename GraphType::NodeIndex	source,
		const typename GraphType::NodeIndex	destination )

Determines the shortest path from the given source and destination, returns a tuple with the path (as a vector of node indices) and its cost.

There are shortest paths in this graph, just not from the source to this destination. This case only happens when some arcs have an infinite length (i.e. larger than kMaxDistance): BoundedDijkstraWrapper::NodePathTo fails to return a path, even empty.

Definition at line 168 of file k_shortest_paths.h.

◆ CycleErrorMessage()

template<typename NodeType>

std::string operations_research::internal::CycleErrorMessage ( absl::Span< const NodeType > cycle )

Definition at line 372 of file rooted_tree.h.

◆ ExtractCycle()

template<typename NodeType>

std::vector< NodeType > operations_research::internal::ExtractCycle	(	absl::Span< const NodeType >	parents,
		const NodeType	node_in_cycle )

Definition at line 352 of file rooted_tree.h.

◆ FindArcIndex()

template<class GraphType>

GraphType::ArcIndex operations_research::internal::FindArcIndex	(	const GraphType &	graph,
		const typename GraphType::NodeIndex	source,
		const typename GraphType::NodeIndex	destination )

Determines the arc index from a source to a destination.

This operation requires iterating through the set of outgoing arcs from the source node, which might be expensive.

In a multigraph, this function returns an index for one of the edges between the source and the destination.

Definition at line 152 of file k_shortest_paths.h.

◆ GetInversePermutation()

template<typename T>

std::vector< T > operations_research::internal::GetInversePermutation ( const std::vector< T > & permutation )

Definition at line 907 of file dag_constrained_shortest_path.h.

◆ GraphIsConnected()

template<typename Graph>

bool operations_research::internal::GraphIsConnected ( const Graph & graph )

We use iterative DFS, which is probably the fastest.

Definition at line 155 of file eulerian_path.h.

◆ IsBitSet64()

bool operations_research::internal::IsBitSet64	(	const uint64_t *const	bitset,
		uint64_t	pos )

inline

Definition at line 27 of file bitmap.h.

◆ IsNanGeneric() [1/4]

template<>

bool operations_research::internal::IsNanGeneric ( const double & x )

inline

Definition at line 152 of file binary_search.h.

◆ IsNanGeneric() [2/4]

template<>

bool operations_research::internal::IsNanGeneric ( const float & x )

inline

Definition at line 148 of file binary_search.h.

◆ IsNanGeneric() [3/4]

template<>

bool operations_research::internal::IsNanGeneric ( const long double & x )

inline

Definition at line 156 of file binary_search.h.

◆ IsNanGeneric() [4/4]

template<class T>

bool operations_research::internal::IsNanGeneric ( const T & )

Definition at line 143 of file binary_search.h.

◆ IsValidNode()

template<typename NodeType>

absl::Status operations_research::internal::IsValidNode	(	const NodeType	node,
		const NodeType	num_tree_nodes )

Definition at line 342 of file rooted_tree.h.

◆ IsValidParent()

template<typename NodeType>

bool operations_research::internal::IsValidParent	(	const NodeType	node,
		const NodeType	num_tree_nodes )

Definition at line 336 of file rooted_tree.h.

◆ MakeSCIPMessageHandler()

absl::StatusOr< MessageHandlerPtr > operations_research::internal::MakeSCIPMessageHandler ( const GScipMessageHandler gscip_message_handler )

Make a message handler for SCIP that calls the input function.

We use a unique_ptr here to make sure we delete the data if SCIPmessagehdlrCreate() fails.

SCIPmessagehdlrCreate() succeeded, we disable the deletion of the data by the unique_ptr since the ownership has been transferred to SCIP.

Definition at line 122 of file gscip_message_handler.cc.

◆ OneBit64()

uint64_t operations_research::internal::OneBit64 ( int pos )

inline

Definition at line 23 of file bitmap.h.

◆ ReadNumRecords() [1/2]

template<typename Proto>

std::vector< Proto > operations_research::internal::ReadNumRecords	(	absl::string_view	filename,
		int	expected_num_records )

Ditto, taking a filename as argument.

Definition at line 106 of file file_util.h.

◆ ReadNumRecords() [2/2]

template<typename Proto>

std::vector< Proto > operations_research::internal::ReadNumRecords	(	File *	file,
		int	expected_num_records )

General method to read expected_num_records from a file. If expected_num_records is -1, then reads all records from the file. If not, dies if the file doesn't contain exactly expected_num_records.

Definition at line 79 of file file_util.h.

◆ RegisterConstraintHandler()

absl::Status operations_research::internal::RegisterConstraintHandler	(	GScip *	gscip,
		std::unique_ptr< UntypedGScipConstraintHandler >	constraint_handler )

Definition at line 583 of file gscip_constraint_handler.cc.

◆ ScipCodeToUtilStatus()

absl::Status operations_research::internal::ScipCodeToUtilStatus	(	int	retcode,
		const char *	source_file,
		int	source_line,
		const char *	scip_statement )

inline

Our own version of SCIP_CALL to do error management.

Definition at line 24 of file scip_helper_macros.h.

◆ SetBit64()

void operations_research::internal::SetBit64	(	uint64_t *const	bitset,
		uint64_t	pos )

inline

Definition at line 30 of file bitmap.h.

◆ UsesTwosComplement()

template<typename IntT>

bool operations_research::internal::UsesTwosComplement ( )

constexpr

Definition at line 174 of file binary_search.h.

◆ VectorSum()

template<size_t block_size = 4, size_t num_blocks_per_iteration = 4, bool assume_aligned_at_start = false, typename Value>

Value operations_research::internal::VectorSum ( absl::Span< const Value > values )

Computes the sum of values in values, by adding num_blocks_per_iteration blocks of block_size values. By default, the sum does not make any assumptions about the size or alignment of values. When the first item of values is known to be aligned to block_size * sizeof(Value) bytes, assume_aligned_at_start can be used to save a small amount of time.

With less than two blocks, there's not a lot to vectorize, and a simple sequential sum is usually faster.

Definition at line 138 of file vector_sum_internal.h.

Variable Documentation

◆ kDisconnectedDistance

const PathDistance operations_research::internal::kDisconnectedDistance

Initial value:

=

std::numeric_limits<PathDistance>::max()

Definition at line 141 of file k_shortest_paths.h.

◆ kMaxDistance

const PathDistance operations_research::internal::kMaxDistance = std::numeric_limits<PathDistance>::max() - 1

Definition at line 140 of file k_shortest_paths.h.

Detailed Description

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ IndexedVector

◆ MessageHandlerPtr

◆ to_uint

Function Documentation

◆ AddCallbackConstraint()

◆ AddCallbackConstraintImpl()

◆ AddConstraintHandlerImpl()

◆ AddInPlace()

◆ AlignedBlockSum()

◆ AreNumbersOfSameSign()

◆ BitLength64()

◆ BitOffset64()

◆ BitPos64()

◆ CaptureMessageHandlerPtr()

◆ CheckForCycle()

◆ ClearBit64()

◆ ComputePathLength()

◆ ComputeShortestPath()

◆ CycleErrorMessage()

◆ ExtractCycle()

◆ FindArcIndex()

◆ GetInversePermutation()

◆ GraphIsConnected()

◆ IsBitSet64()

◆ IsNanGeneric() [1/4]

◆ IsNanGeneric() [2/4]

◆ IsNanGeneric() [3/4]

◆ IsNanGeneric() [4/4]

◆ IsValidNode()

◆ IsValidParent()

◆ MakeSCIPMessageHandler()

◆ OneBit64()

◆ ReadNumRecords() [1/2]

◆ ReadNumRecords() [2/2]

◆ RegisterConstraintHandler()

◆ ScipCodeToUtilStatus()

◆ SetBit64()

◆ UsesTwosComplement()

◆ VectorSum()

Variable Documentation

◆ kDisconnectedDistance

◆ kMaxDistance