 |
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
|
#include <cliques.h>
Public Types | |
| using | IsArcCallback = std::function<bool(NodeIndex, NodeIndex)> |
| using | CliqueCallback |
Public Member Functions | |
| BronKerboschAlgorithm (IsArcCallback is_arc, NodeIndex num_nodes, CliqueCallback clique_callback) | |
| BronKerboschAlgorithmStatus | Run () |
| BronKerboschAlgorithmStatus | RunIterations (int64_t max_num_iterations) |
| BronKerboschAlgorithmStatus | RunWithTimeLimit (int64_t max_num_iterations, TimeLimit *time_limit) |
| BronKerboschAlgorithmStatus | RunWithTimeLimit (TimeLimit *time_limit) |
Implements the Bron-Kerbosch algorithm for finding maximal cliques. The graph is represented as a callback that gets two nodes as its arguments and it returns true if and only if there is an arc between the two nodes. The cliques are reported back to the user using a second callback.
Typical usage: auto graph = [](int node1, int node2) { return true; }; auto on_clique = [](const std::vector<int>& clique) { LOG(INFO) << "Clique!"; };
BronKerboschAlgorithm<int> bron_kerbosch(graph, num_nodes, on_clique); bron_kerbosch.Run();
or:
BronKerboschAlgorithm bron_kerbosch(graph, num_nodes, clique); bron_kerbosch.RunIterations(kMaxNumIterations);
This is a non-recursive implementation of the Bron-Kerbosch algorithm with pivots as described in the paper by Bron and Kerbosch (1973) (the version 2 algorithm in the paper). The basic idea of the algorithm is to incrementally build the cliques using depth-first search. During the search, the algorithm maintains two sets of candidates (nodes that are connected to all nodes in the current clique):
To avoid unnecessary steps, the algorithm selects a pivot at each level of the recursion to guide the selection of candidates added to the current clique. The pivot can be either in the "not" set and among the actual candidates. The algorithm tries to move the pivot and all actual candidates connected to it to the set "not" as quickly as possible. This will fulfill the conditions of step A, and the search algorithm will be able to leave the current branch. Selecting a pivot that has the lowest number of disconnected nodes among the candidates can reduce the running time significantly.
The worst-case maximal depth of the recursion is equal to the number of nodes in the graph, which makes the natural recursive implementation impractical for nodes with more than a few thousands of nodes. To avoid the limitation, this class simulates the recursion by maintaining a stack with the state at each level of the recursion. The algorithm then runs in a loop. In each iteration, the algorithm can do one or both of:
The worst-case time complexity of the algorithm is O(3^(N/3)), and the memory complexity is O(N^2), where N is the number of nodes in the graph.
| using operations_research::BronKerboschAlgorithm< NodeIndex >::CliqueCallback |
A callback called by the algorithm to report a maximal clique to the user. The clique is returned as a list of nodes in the clique, in no particular order. The caller must make a copy of the vector if they want to keep the nodes.
The return value of the callback controls how the algorithm continues after this clique. See the description of the values of 'CliqueResponse' for more details.
| using operations_research::BronKerboschAlgorithm< NodeIndex >::IsArcCallback = std::function<bool(NodeIndex, NodeIndex)> |
|
inline |
| BronKerboschAlgorithmStatus operations_research::BronKerboschAlgorithm< NodeIndex >::Run | ( | ) |
Runs the Bron-Kerbosch algorithm for kint64max iterations. In practice, this is equivalent to running until completion or until the clique callback returns BronKerboschAlgorithmStatus::STOP. If the method returned because the search is finished, it will return COMPLETED; otherwise, it will return INTERRUPTED and it can be resumed by calling this method again.
| BronKerboschAlgorithmStatus operations_research::BronKerboschAlgorithm< NodeIndex >::RunIterations | ( | int64_t | max_num_iterations | ) |
Runs at most 'max_num_iterations' iterations of the Bron-Kerbosch algorithm. When this function returns INTERRUPTED, there is still work to be done to process all the cliques in the graph. In such case the method can be called again and it will resume the work where the previous call had stopped. When it returns COMPLETED any subsequent call to the method will resume the search from the beginning.
| BronKerboschAlgorithmStatus operations_research::BronKerboschAlgorithm< NodeIndex >::RunWithTimeLimit | ( | int64_t | max_num_iterations, |
| TimeLimit * | time_limit ) |
Runs at most 'max_num_iterations' iterations of the Bron-Kerbosch algorithm, until the time limit is exceeded or until all cliques are enumerated. When this function returns INTERRUPTED, there is still work to be done to process all the cliques in the graph. In such case the method can be called again and it will resume the work where the previous call had stopped. When it returns COMPLETED any subsequent call to the method will resume the search from the beginning.
|
inline |
Runs the Bron-Kerbosch algorithm for at most kint64max iterations, until the time limit is excceded or until all cliques are enumerated. In practice, running the algorithm for kint64max iterations is equivalent to running until completion or until the other stopping conditions apply. When this function returns INTERRUPTED, there is still work to be done to process all the cliques in the graph. In such case the method can be called again and it will resume the work where the previous call had stopped. When it returns COMPLETED any subsequent call to the method will resume the search from the beginning.
1.12.0