 |
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
#include <shortest_paths.h>
Public Types | |
| using | NodeIndex = typename GraphType::NodeIndex |
| using | Impl = internal::PathContainerImpl<NodeIndex, GraphType::kNilNode> |
Public Member Functions | |
| GenericPathContainer (const GenericPathContainer &)=delete | |
| This type is neither copyable nor movable. | |
| GenericPathContainer & | operator= (const GenericPathContainer &)=delete |
| ~GenericPathContainer () | |
| PathDistance | GetDistance (NodeIndex from, NodeIndex to) const |
| virtual NodeIndex | GetPenultimateNodeInPath (NodeIndex from, NodeIndex to) const =0 |
| virtual void | GetPath (NodeIndex from, NodeIndex to, std::vector< NodeIndex > *path) const =0 |
Returns path nodes from node from to node to in a ordered vector. | |
| virtual void | StoreSingleSourcePaths (NodeIndex from, const std::vector< NodeIndex > &predecessor_in_path_tree, const std::vector< PathDistance > &distance_to_destination)=0 |
Container class storing paths and distances along the paths. It is used in shortest path computation functions to store resulting shortest paths. Usage example iterating on the path between nodes from and to: GenericPathContainer<StaticGraph<>> container = GenericPathContainer< StaticGraph<>>::BuildInMemoryCompactPathContainer(); ///< ... fill up container ... const GenericPathContainer::NodeIndex from =...; GenericPathContainer::NodeIndex to =...; while (to != from) { LOG(INFO) << to; to = container.GetPenultimateNodeInPath(from, to); }
Definition at line 114 of file shortest_paths.h.
| using operations_research::GenericPathContainer< GraphType >::Impl = internal::PathContainerImpl<NodeIndex, GraphType::kNilNode> |
Definition at line 117 of file shortest_paths.h.
| using operations_research::GenericPathContainer< GraphType >::NodeIndex = typename GraphType::NodeIndex |
Definition at line 116 of file shortest_paths.h.
|
delete |
This type is neither copyable nor movable.
|
default |
| PathDistance GenericPathContainer::GetDistance | ( | NodeIndex | from, |
| NodeIndex | to ) const |
Returns the distance between node from and node to following the path out of from and into to. Note that if from == to, the distance is not necessarily 0 if the path out of to and back into to has a distance greater than 0. If you do require the distance to be 0 in this case, add to the graph an arc from to to itself with a length of 0. If nodes are not connected, returns kDisconnectedPathDistance.
Definition at line 707 of file shortest_paths.h.
|
pure virtual |
Returns path nodes from node from to node to in a ordered vector.
Definition at line 722 of file shortest_paths.h.
|
pure virtual |
Returns the penultimate node on the path out of node from into node to (the direct predecessor of node to on the path). If from == to, the penultimate node is to only if the shortest path from to to itself is composed of the arc (to,to), which might not be / the case if either this arc doesn't exist or if the length of this arc is / greater than the distance of an alternate path. / If nodes are not connected, returnsGraphType::kNilNode`. NodeIndex GetPenultimateNodeInPath(NodeIndex from, NodeIndex to) const;
/ Returns path nodes from node from to node to in the order in which they / appear along the path. / The vector starts with from and ends with to, if both nodes are / connected (otherwise an empty vector is returned). void GetPath(NodeIndex from, NodeIndex to,
std::vector<NodeIndex>* path) const;
/ Builds a path container which only stores distances between path nodes. static GenericPathContainer BuildPathDistanceContainer();
/ Builds a path container which stores explicit paths and distances between / path nodes in a memory-compact representation. / In this case GetPenultimateNodeInPath() is O(log(path_tree_size)), / path_tree_size being the size of a tree of paths from a source node (in / practice it is equal to the number of nodes in the graph if all nodes / are strongly connected). / GetPath is O(log(path_tree_size) + path_size), where path_size is the / size of the resulting path; note this is faster than successive calls / to GetPenultimateNodeInPath() which would result in / O(log(path_tree_size) * path_size). static GenericPathContainer BuildInMemoryCompactPathContainer();
/
(user): Add save-to-disk container. /
(user): Add BuildInMemoryFastPathContainer(), which does / GetPenultimateNodeInPath() in O(1).
/ For internal use only. Returns the internal container implementation. Impl* GetImplementation() const { return container_.get(); }
private: explicit GenericPathContainer(std::unique_ptr<Impl> impl) : container_(std::move(impl)) {}
std::unique_ptr<Impl> container_; };
/ Utility function which returns a vector containing all nodes of a graph. template <class GraphType> void GetGraphNodes(const GraphType& graph, std::vector<typename GraphType::NodeIndex>* nodes) { CHECK(nodes != nullptr); nodes->clear(); nodes->reserve(graph.num_nodes()); for (typename GraphType::NodeIterator iterator(graph); iterator.Ok(); iterator.Next()) { nodes->push_back(iterator.Index()); } }
template <class GraphType> void GetGraphNodesFromGraph(const GraphType& graph, std::vector<typename GraphType::NodeIndex>* nodes) { CHECK(nodes != nullptr); nodes->clear(); nodes->reserve(graph.num_nodes()); for (const typename GraphType::NodeIndex node : graph.AllNodes()) { nodes->push_back(node); } }
/ In all the functions below the arc_lengths vector represents the lengths of / the arcs of the graph (arc_lengths[arc] is the length of arc). / Resulting shortest paths are stored in a path container path_container.
/ Computes shortest paths from the node source to all nodes in the graph. template <class GraphType> void ComputeOneToAllShortestPaths(
const GraphType& graph, const std::vector<PathDistance>& arc_lengths,
typename GraphType::NodeIndex source,
GenericPathContainer<GraphType>* const path_container) { std::vector<typename GraphType::NodeIndex> all_nodes; GetGraphNodesFromGraph<GraphType>(graph, &all_nodes); ComputeOneToManyShortestPaths(graph, arc_lengths, source, all_nodes,
path_container); }
/ Computes shortest paths from the node source to nodes in destinations. /
/ Computes the shortest path from the node source to the node destination / and returns that path as a vector of nodes. If there is no path from source / to destination, the returned vector is empty. / / To get distance information, use ComputeOneToManyShortestPaths with a / single destination and a PathContainer built with / BuildPathDistanceContainer (if you just need the distance) or / BuildInMemoryCompactPathContainer (otherwise). template <class GraphType> std::vector<typename GraphType::NodeIndex> ComputeOneToOneShortestPath(
const GraphType& graph, const std::vector<PathDistance>& arc_lengths,
typename GraphType::NodeIndex source,
typename GraphType::NodeIndex destination) { std::vector<typename GraphType::NodeIndex> sources(1, source); std::vector<typename GraphType::NodeIndex> destinations(1, destination);
auto path_container = GenericPathContainer<GraphType>::BuildInMemoryCompactPathContainer();
ComputeManyToManyShortestPathsWithMultipleThreads( graph, arc_lengths, sources, destinations, 1, &path_container);
std::vector<typename GraphType::NodeIndex> path; path_container.GetPath(source, destination, &path); return path; }
/ Computes shortest paths from the nodes in sources to all nodes in the / graph. template <class GraphType> void ComputeManyToAllShortestPathsWithMultipleThreads(
const GraphType& graph, const std::vector<PathDistance>& arc_lengths,
const std::vector<typename GraphType::NodeIndex>& sources, int num_threads,
GenericPathContainer<GraphType>* const path_container) { std::vector<typename GraphType::NodeIndex> all_nodes; GetGraphNodesFromGraph<GraphType>(graph, &all_nodes); ComputeManyToManyShortestPathsWithMultipleThreads(
graph, arc_lengths, sources, all_nodes, num_threads, path_container); }
/ Computes shortest paths between all nodes of the graph. template <class GraphType> void ComputeAllToAllShortestPathsWithMultipleThreads( const GraphType& graph, const std::vector<PathDistance>& arc_lengths, int num_threads, GenericPathContainer<GraphType>* const path_container) { std::vector<typename GraphType::NodeIndex> all_nodes; GetGraphNodesFromGraph<GraphType>(graph, &all_nodes); ComputeManyToManyShortestPathsWithMultipleThreads( graph, arc_lengths, all_nodes, all_nodes, num_threads, path_container); }
/
/ Implementation. /
namespace internal {
/ Base path container implementation class. Defines virtual functions used to / fill the container (in particular from the shortest path computation / function). template <class NodeIndex, NodeIndex kNilNode> class PathContainerImpl { public: PathContainerImpl() = default; virtual ~PathContainerImpl() = default;
/ Initializes the container on source and destination node vectors / (num_nodes is the total number of nodes in the graph containing source / and destination nodes). / Called before adding any paths to the container. virtual void Initialize(const std::vector<NodeIndex>& sources,
const std::vector<NodeIndex>& destinations,
NodeIndex num_nodes) = 0;
/ Called when no more path will be added to the container. virtual void Finalize() {}
/ Returns the distance between node from and node to following the path / out of from and into to. Note that if from == to, the distance is / not necessarily 0 if the path out of to and back into to has a distance / greater than 0. If you do require the distance to be 0 in this case, add to / the graph an arc from to to itself with a length of 0. / If nodes are not connected, returns kDisconnectedPathDistance. virtual PathDistance GetDistance(NodeIndex from, NodeIndex to) const = 0;
/ Returns the penultimate node on the path out of node from into node to / (the direct predecessor of node to on the path). / If from == to, the penultimate node is to only if the shortest path / from to to itself is composed of the arc (to,to), which might not be the case if either this arc doesn't exist or if the length of this arc is greater than the distance of an alternate path. If nodes are not connected, returnskNilNode`.
Definition at line 715 of file shortest_paths.h.
|
delete |
|
pure virtual |
Adds a path tree rooted at node from, and to a set of implicit destinations:
predecessor_in_path_tree[node] is the predecessor of node node in the path from from to node, or kNilNode if there is no predecessor (i.e. if node is not in the path tree);distance_to_destination[i] is the distance from from to the i-th destination (see Initialize()). 
1.13.2