|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
Classes | |
| class | BellmanFord |
| class | ConnectedComponents |
| Template class implementing a Union-Find algorithm with path compression for maintaining the connected components of a graph. More... | |
| class | DijkstraSP |
| namespace More... | |
| class | EbertGraphCore |
| A template for the base class that holds the functionality that exists in common between the EbertGraph<> template and the ForwardEbertGraph<> template. More... | |
| class | EbertGraph |
| Most users should only use StarGraph, which is EbertGraph<int32, int32>, and other type shortcuts; see the bottom of this file. More... | |
| class | ForwardEbertGraph |
| A forward-star-only graph representation for greater efficiency in those algorithms that don't need reverse arcs. More... | |
| struct | graph_traits |
| Traits for EbertGraphCore types, for use in testing and clients that work with both forward-only and forward/reverse graphs. More... | |
| struct | graph_traits< ForwardEbertGraph< NodeIndexType, ArcIndexType > > |
| struct | TailArrayBuilder |
| The TailArrayBuilder for graphs with reverse arcs does nothing. More... | |
| struct | TailArrayBuilder< GraphType, false > |
| The TailArrayBuilder for graphs without reverse arcs calls the appropriate method on the graph from the TailArrayBuilder constructor. More... | |
| struct | TailArrayReleaser |
| The TailArrayReleaser for graphs with reverse arcs does nothing. More... | |
| struct | TailArrayReleaser< GraphType, false > |
| The TailArrayReleaser for graphs without reverse arcs calls the appropriate method on the graph from the TailArrayReleaser constructor. More... | |
| class | TailArrayManager |
| class | HamiltonianPathSolver |
| class | LinearSumAssignment |
| class | CostValueCycleHandler |
| class | ArcIndexOrderingByTailNode |
| Logically this class should be defined inside OptimizeGraphLayout, but compilation fails if we do that because C++98 doesn't allow instantiation of member templates with function-scoped types as template parameters, which in turn is because those function-scoped types lack linkage. More... | |
| class | MaxFlow |
| class | MinCostFlow |
Typedefs | |
| typedef int32 | NodeIndex |
| Standard instantiation of ForwardEbertGraph (named 'ForwardStarGraph') of EbertGraph (named 'StarGraph'); and relevant type shortcuts. | |
| typedef int32 | ArcIndex |
| typedef int64 | FlowQuantity |
| typedef int64 | CostValue |
| typedef EbertGraph< NodeIndex, ArcIndex > | StarGraph |
| typedef ForwardEbertGraph < NodeIndex, ArcIndex > | ForwardStarGraph |
| typedef ZVector< NodeIndex > | NodeIndexArray |
| typedef ZVector< ArcIndex > | ArcIndexArray |
| typedef ZVector< FlowQuantity > | QuantityArray |
| typedef ZVector< CostValue > | CostArray |
| typedef int | PathNodeIndex |
Functions | |
| bool | BellmanFordShortestPath (int node_count, int start_node, int end_node, ResultCallback2< int64, int, int > *const graph, int64 disconnected_distance, std::vector< int > *nodes) |
| Bellman-Ford Shortest path with callback-based description of the graph. | |
| void | Search (ResultCallback2< bool, int, int > *const graph, ResultCallback1< bool, const std::vector< int > & > *const callback, int *input_candidates, int input_size, int input_candidate_size, std::vector< int > *actual, bool *stop) |
| void | FindCliques (ResultCallback2< bool, int, int > *const graph, int node_count, ResultCallback1< bool, const std::vector< int > & > *const callback) |
| namespace | |
| void | CoverArcsByCliques (ResultCallback2< bool, int, int > *const graph, int node_count, ResultCallback1< bool, const std::vector< int > & > *const callback) |
| Covers the maximum number of arcs of the graph with cliques. | |
| bool | DijkstraShortestPath (int node_count, int start_node, int end_node, ResultCallback2< int64, int, int > *const graph, int64 disconnected_distance, std::vector< int > *nodes) |
| Dijsktra Shortest path with callback based description of the graph. | |
| template<typename GraphType> | |
| bool | BuildLineGraph (const GraphType &graph, GraphType *const line_graph) |
| Builds a directed line graph for 'graph' (see "directed line graph" in http://en.wikipedia.org/wiki/Line_graph). | |
Variables | |
| static const int | kHamiltonianPathSolverPadValue = 1557 |
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.
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. Graph connectivity algorithm for undirected graphs. Memory consumption: O(n) where m is the number of arcs and n the number of nodes.
You may obtain a copy of the License athttp://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. Solves the Shortest Hamiltonian Path Problem using a complete algorithm. The algorithm was first described in M. Held, R.M. Karp, A dynamic programming approach to sequencing problems, J. SIAM 10 (1962) 196–210
The Shortest Hamiltonian Path Problem (SHPP) is similar to the Traveling Salesperson Problem (TSP). You have to visit all the cities, starting from a given one and you do not need to return to your starting point. With the TSP, you can start anywhere, but you have to return to your start location.
By complete we mean that the algorithm guarantees to compute the optimal solution. The algorithm uses dynamic programming. Its time complexity is O(n*2^n), where n is the number of nodes to be visited. Its space complexity is also O(n*2^n).
Note that the naive implementation of the SHPP exploring all permutations without memorizing intermediate results would have a complexity of (n-1)! (factorial of (n-1) ), which is much higher than n*2^n. To convince oneself of this, just use Stirling's formula: n! ~ sqrt(2*pi*n)*(n/exp(1))^n . Because of these complexity figures, the algorithm is not practical for problems with more than 20 nodes.
Here is how the algorithm works: Let us denote the nodes to be visited by their indices 0..n-1 Let us pick 0 as the starting node. Let d(i,j) denote the distance (or cost) from i to j. f(S,j) where S is a set of nodes and j is a node is defined as follows: f(S,j) = min(i in S, f(Si}, i) + d(i,j))
The set S can be represented by an integer where bit i corresponds to element i in the set. In the following S denotes the integer corresponding to set S.
The computation of f(S,j) is implemented in the method ComputeShortestPath.
To implement dynamic programming, we store the preceding results of computing f(S,i) in an array M[S][i]. Since there are 2^n subsets of the set {0..n-1}, there are 2^n rows and n columns in this array. This explains the complexity figures.
The array M is initialized as follows: for i in (0..n-1) M[0][i] = d(0,i) The dynamic programming iteration is as follows: for S in (0..2^n-2) for i in (0..n-1) M[S][i]=f(S,i)
The dynamic programming iteration is implemented in the method Solve. The optimal value of the Hamiltonian path from 0 to n-1 is given by f(2^n-1,n-1). The optimal value of the Traveling Salesman tour is given by f(2^n-1,0). (There is actually no need to duplicate the first node.)
There are a few tricks in the efficient implementation of this algorithm which are explained below.
Keywords: Traveling Salesman, Hamiltonian Path, Dynamic Programming, Held, Karp.
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. This file contains various shortest paths utilities.
Keywords: directed graph, cheapest path, shortest path, Dijkstra, spp.
| typedef int32 operations_research::ArcIndex |
Definition at line 139 of file ebert_graph.h.
| typedef ZVector<ArcIndex> operations_research::ArcIndexArray |
Definition at line 145 of file ebert_graph.h.
| typedef ZVector<CostValue> operations_research::CostArray |
Definition at line 147 of file ebert_graph.h.
| typedef int64 operations_research::CostValue |
Definition at line 141 of file ebert_graph.h.
| typedef int64 operations_research::FlowQuantity |
Definition at line 140 of file ebert_graph.h.
Definition at line 143 of file ebert_graph.h.
| typedef int32 operations_research::NodeIndex |
Standard instantiation of ForwardEbertGraph (named 'ForwardStarGraph') of EbertGraph (named 'StarGraph'); and relevant type shortcuts.
Unless their use cases prevent them from doing so, users are encouraged to use StarGraph or ForwardStarGraph according to whether or not they require reverse arcs to be represented explicitly. Along with either graph representation, the other type shortcuts here will often come in handy.
Definition at line 130 of file ebert_graph.h.
| typedef ZVector<NodeIndex> operations_research::NodeIndexArray |
Definition at line 144 of file ebert_graph.h.
| typedef int operations_research::PathNodeIndex |
Definition at line 91 of file hamiltonian_path.h.
| typedef ZVector<FlowQuantity> operations_research::QuantityArray |
Definition at line 146 of file ebert_graph.h.
Definition at line 142 of file ebert_graph.h.
| bool operations_research::BellmanFordShortestPath | ( | int | node_count, | |
| int | start_node, | |||
| int | end_node, | |||
| ResultCallback2< int64, int, int > *const | graph, | |||
| int64 | disconnected_distance, | |||
| std::vector< int > * | nodes | |||
| ) |
Bellman-Ford Shortest path with callback-based description of the graph.
The callback returns the distance between two nodes, a distance of 'disconnected_distance' indicates no arcs between these two nodes. Ownership of the callback is taken by the function that will delete it in the end. This function returns true if 'start_node' and 'end_node' are connected, false otherwise. If true, it will fill the 'nodes' vector with the sequence of nodes on the shortest path between 'start_node' and 'end_node'.
Definition at line 113 of file bellman_ford.cc.
| bool operations_research::BuildLineGraph | ( | const GraphType & | graph, | |
| GraphType *const | line_graph | |||
| ) | [inline] |
Builds a directed line graph for 'graph' (see "directed line graph" in http://en.wikipedia.org/wiki/Line_graph).
Arcs of the original graph become nodes and the new graph contains only nodes created from arcs in the original graph (we use the notation (a->b) for these new nodes); the index of the node (a->b) in the new graph is exactly the same as the index of the arc a->b in the original graph. An arc from node (a->b) to node (c->d) in the new graph is added if and only if b == c in the original graph. This method expects that 'line_graph' is an empty graph (it has no nodes and no arcs). Returns false on an error.
Definition at line 1500 of file ebert_graph.h.
| void operations_research::CoverArcsByCliques | ( | ResultCallback2< bool, int, int > *const | graph, | |
| int | node_count, | |||
| ResultCallback1< bool, const std::vector< int > & > *const | callback | |||
| ) |
Covers the maximum number of arcs of the graph with cliques.
The graph is described by the graph callback. graph->Run(i, j) indicates if there is an arc between i and j. This function takes ownership of 'callback' and deletes it after it has run. It calls 'callback' upon each clique. It ignores cliques of size 1.
Definition at line 199 of file cliques.cc.
| bool operations_research::DijkstraShortestPath | ( | int | node_count, | |
| int | start_node, | |||
| int | end_node, | |||
| ResultCallback2< int64, int, int > *const | graph, | |||
| int64 | disconnected_distance, | |||
| std::vector< int > * | nodes | |||
| ) |
Dijsktra Shortest path with callback based description of the graph.
The callback returns the distance between two nodes, a distance of 'disconnected_distance' indicates no arcs between these two nodes. Ownership of the callback is taken by the function that will delete it in the end. This function returns true if 'start_node' and 'end_node' are connected, false otherwise.
Definition at line 156 of file dijkstra.cc.
| void operations_research::FindCliques | ( | ResultCallback2< bool, int, int > *const | graph, | |
| int | node_count, | |||
| ResultCallback1< bool, const std::vector< int > & > *const | callback | |||
| ) |
namespace
Finds all maximal cliques, even of size 1, in the graph described by the graph callback.
This method implements the 'version2' of the Bron-Kerbosch algorithm to find all maximal cliques in a undirected graph.
graph->Run(i, j) indicates if there is an arc between i and j. This function takes ownership of 'callback' and deletes it after it has run. If 'callback' returns true, then the search for cliques stops.
Definition at line 177 of file cliques.cc.
| void operations_research::@1::Search | ( | ResultCallback2< bool, int, int > *const | graph, | |
| ResultCallback1< bool, const std::vector< int > & > *const | callback, | |||
| int * | input_candidates, | |||
| int | input_size, | |||
| int | input_candidate_size, | |||
| std::vector< int > * | actual, | |||
| bool * | stop | |||
| ) | [static] |
Definition at line 27 of file cliques.cc.
const int operations_research::kHamiltonianPathSolverPadValue = 1557 [static] |
Definition at line 176 of file hamiltonian_path.h.