shortest_paths.h File Reference

#include <cstdint>
#include <limits>
#include <memory>
#include <utility>
#include <vector>
#include "absl/base/attributes.h"
#include "absl/container/flat_hash_map.h"
#include "absl/functional/bind_front.h"
#include "absl/log/check.h"
#include "absl/types/span.h"
#include "ortools/base/adjustable_priority_queue-inl.h"
#include "ortools/base/adjustable_priority_queue.h"
#include "ortools/base/logging.h"
#include "ortools/base/map_util.h"
#include "ortools/base/stl_util.h"
#include "ortools/base/threadpool.h"
#include "ortools/base/timer.h"

Go to the source code of this file.

Classes
class	operations_research::GenericPathContainer< GraphType >
class	operations_research::PathTree< NodeIndex, kNilNode >
class	operations_research::DistanceContainer< NodeIndex, kNilNode >
	Path container which only stores distances between path nodes. More...
class	operations_research::InMemoryCompactPathContainer< NodeIndex, kNilNode >
	Path container which stores explicit paths and distances between path nodes. More...
class	operations_research::NodeEntry< NodeIndex, kNilNode >
	Priority queue node entry in the boundary of the Dijkstra algorithm. More...

Namespaces
namespace	operations_research
	In SWIG mode, we don't want anything besides these top-level includes.
namespace	operations_research::internal
	End of the interface. Below is the implementation.

Typedefs
typedef uint32_t	operations_research::PathDistance

Functions
template<class NodeIndex, NodeIndex kNilNode>
bool	operations_research::InsertOrUpdateEntry (PathDistance distance, NodeEntry< NodeIndex, kNilNode > *entry, AdjustablePriorityQueue< NodeEntry< NodeIndex, kNilNode > > *priority_queue)
template<class GraphType>
void	operations_research::ComputeOneToManyOnGraph (const GraphType *const graph, const std::vector< PathDistance > *const arc_lengths, typename GraphType::NodeIndex source, const std::vector< typename GraphType::NodeIndex > *const destinations, typename GenericPathContainer< GraphType >::Impl *const paths)
template<class GraphType>
void	ComputeManyToManyShortestPathsWithMultipleThreads (const GraphType &graph, const std::vector< PathDistance > &arc_lengths, const std::vector< typename GraphType::NodeIndex > &sources, const std::vector< typename GraphType::NodeIndex > &destinations, int num_threads, GenericPathContainer< GraphType > *const paths)

Variables
const PathDistance	operations_research::kDisconnectedPathDistance

Function Documentation

ComputeManyToManyShortestPathsWithMultipleThreads()

template<class GraphType>

void ComputeManyToManyShortestPathsWithMultipleThreads	(	const GraphType &	graph,
		const std::vector< PathDistance > &	arc_lengths,
		const std::vector< typename GraphType::NodeIndex > &	sources,
		const std::vector< typename GraphType::NodeIndex > &	destinations,
		int	num_threads,
		GenericPathContainer< GraphType > *const	paths )

Removing duplicate sources to allow mutex-free implementation (and it's more efficient); same with destinations for efficiency reasons.

Definition at line 746 of file shortest_paths.h.