 |
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
Functions | |
| template<class Graph , class NodeIndex = int> | |
| absl::StatusOr< std::vector< NodeIndex > > | GetBFSRootedTree (const Graph &graph, NodeIndex num_nodes, NodeIndex source) |
| template<class NodeIndex > | |
| absl::StatusOr< std::vector< NodeIndex > > | GetBFSDistances (const std::vector< NodeIndex > &bfs_tree) |
| template<class NodeIndex > | |
| absl::StatusOr< std::vector< NodeIndex > > | GetBFSShortestPath (const std::vector< NodeIndex > &bfs_tree, NodeIndex target) |
| template<class AdjacencyLists > | |
| absl::StatusOr< std::vector< int > > | FastTopologicalSort (const AdjacencyLists &adj) |
| template<class AdjacencyLists > | |
| absl::StatusOr< std::vector< int > > | FindCycleInGraph (const AdjacencyLists &adj) |
| std::vector< int > | DenseIntTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs) |
| std::vector< int > | DenseIntStableTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs) |
| template<typename T > | |
| std::vector< T > | StableTopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs) |
|
inline |
Definition at line 607 of file topologicalsorter.h.
|
inline |
Definition at line 603 of file topologicalsorter.h.
| absl::StatusOr< std::vector< int > > util::graph::FastTopologicalSort | ( | const AdjacencyLists & | adj | ) |
This is the recommended API when performance matters. It's also very simple. AdjacencyList is any type that lets you iterate over the neighbors of node with the [] operator, for example vector<vector<int>> or util::Graph.
If you don't already have an adjacency list representation, build one using StaticGraph<> in ./graph.h: FastTopologicalSort() can take any such graph as input.
ERRORS: returns InvalidArgumentError if the input is broken (negative or out-of-bounds integers) or if the graph is cyclic. In the latter case, the error message will contain "cycle". Note that if cycles may occur in your input, you can probably assume that your input isn't broken, and thus rely on failures to detect that the graph is cyclic.
TIE BREAKING: the returned topological order is deterministic and fixed, and corresponds to iterating on nodes in a LIFO (Breadth-first) order.
Benchmark: gpaste/6147236302946304, 4-10x faster than util_graph::TopoSort().
EXAMPLES: std::vector<std::vector<int>> adj = {{..}, {..}, ..}; ASSIGN_OR_RETURN(std::vector<int> topo_order, FastTopologicalSort(adj));
or std::vector<pair<int, int>> arcs = {{.., ..}, ..., }; ASSIGN_OR_RETURN( std::vector<int> topo_order, FastTopologicalSort(util::StaticGraph<>::FromArcs(num_nodes, arcs)));
We cast to unsigned int to test "head < 0 || head ≥ num_nodes" with a single test. Microbenchmarks showed a ~1% overall performance gain.
NOTE(user): We could detect self-arcs here (head == from) and exit early, but microbenchmarks show a 2 to 4% slow-down if we do it, so we simply rely on self-arcs being detected as cycles in the topo sort.
We cast to unsigned int to test "head < 0 || head ≥ num_nodes" with a single test. Microbenchmarks showed a ~1% overall performance gain.
NOTE(user): We could detect self-arcs here (head == from) and exit early, but microbenchmarks show a 2 to 4% slow-down if we do it, so we simply rely on self-arcs being detected as cycles in the topo sort.
Definition at line 618 of file topologicalsorter.h.
| absl::StatusOr< std::vector< int > > util::graph::FindCycleInGraph | ( | const AdjacencyLists & | adj | ) |
Finds a cycle in the directed graph given as argument: nodes are dense integers in 0..num_nodes-1, and (directed) arcs are pairs of nodes {from, to}. The returned cycle is a list of nodes that form a cycle, eg. {1, 4, 3} if the cycle 1->4->3->1 exists. If the graph is acyclic, returns an empty vector.
To find a cycle, we start a DFS from each yet-unvisited node and try to find a cycle, if we don't find it then we know for sure that no cycle is reachable from any of the explored nodes (so, we don't explore them in later DFSs).
The DFS stack will contain a chain of nodes, from the root of the DFS to the current leaf.
Points at the first child node that we did not yet look at.
Start the DFS.
Look at the current child, and increase the current state's adj_list_index.
We detected a cycle! It corresponds to the tail end of dfs_stack, in reverse order, until we find "child".
Push the child onto the stack.
Verify that its adjacency list seems valid.
If we're here, then all the DFS stopped, and there is no cycle.
To find a cycle, we start a DFS from each yet-unvisited node and try to find a cycle, if we don't find it then we know for sure that no cycle is reachable from any of the explored nodes (so, we don't explore them in later DFSs).
The DFS stack will contain a chain of nodes, from the root of the DFS to the current leaf.
Points at the first child node that we did not yet look at.
Start the DFS.
Look at the current child, and increase the current state's adj_list_index.
We detected a cycle! It corresponds to the tail end of dfs_stack, in reverse order, until we find "child".
Push the child onto the stack.
Verify that its adjacency list seems valid.
If we're here, then all the DFS stopped, and there is no cycle.
Definition at line 659 of file topologicalsorter.h.
| absl::StatusOr< std::vector< NodeIndex > > util::graph::GetBFSDistances | ( | const std::vector< NodeIndex > & | bfs_tree | ) |
Returns the distances of all nodes from the source, in O(num_nodes). bfs_tree must be exactly as returned by GetBFSRootedTree().
Run a few checks on the input first.
The algorithm starts.
Ascend the parent tree until we reach either the root (the BFS source), or an already-marked node (whose distance we already know).
We've reached the root or an already-marked node. Update our distance.
Now ascend the path a second time, to mark the distances of all nodes on the path.
Run a few checks on the input first.
The algorithm starts.
Ascend the parent tree until we reach either the root (the BFS source), or an already-marked node (whose distance we already know).
We've reached the root or an already-marked node. Update our distance.
Now ascend the path a second time, to mark the distances of all nodes on the path.
| absl::StatusOr< std::vector< NodeIndex > > util::graph::GetBFSRootedTree | ( | const Graph & | graph, |
| NodeIndex | num_nodes, | ||
| NodeIndex | source ) |
Runs a BFS (Breadth First Search) in O(num_nodes + num_arcs), and returns the BFS tree rooted at the source: returned element #i is either:
TIE BREAKING: This implementation always breaks tie the same way, by order in the adjacency lists. E.g. if all the adjacency lists are sorted, then the parent of a node in the BFS tree is always the smalled possible parent.
Implementation of the templates.
NOTE(user): -1 works fine for unsigned integers because 'num_nodes' is already an exclusive upper bound for node indices (and -1 unsigned can only be ≥ num_nodes).
NOTE(user): -1 works fine for unsigned integers because 'num_nodes' is already an exclusive upper bound for node indices (and -1 unsigned can only be ≥ num_nodes).
| absl::StatusOr< std::vector< NodeIndex > > util::graph::GetBFSShortestPath | ( | const std::vector< NodeIndex > & | bfs_tree, |
| NodeIndex | target ) |
Returns the shortest path from the source to target, in O(path length). bfs_tree must be exactly as returned by GetBFSRootedTree(). If target wasn't reached in the BFS, returns the empty vector. Else the returned path always starts with the source and ends with the target (if source=target, returns [source]).
| std::vector< T > util::graph::StableTopologicalSortOrDie | ( | const std::vector< T > & | nodes, |
| const std::vector< std::pair< T, T > > & | arcs ) |
Definition at line 612 of file topologicalsorter.h.
1.12.0