24 #ifndef OR_TOOLS_GRAPH_CLIQUES_H_
25 #define OR_TOOLS_GRAPH_CLIQUES_H_
31 #include "absl/strings/str_cat.h"
32 #include "ortools/base/int_type.h"
33 #include "ortools/base/logging.h"
34 #include "ortools/base/strong_vector.h"
35 #include "ortools/util/time_limit.h"
44 void FindCliques(std::function<
bool(
int,
int)> graph,
int node_count,
45 std::function<
bool(
const std::vector<int>&)> callback);
54 std::function<
bool(
const std::vector<int>&)> callback);
143 template <
typename NodeIndex>
166 : is_arc_(std::move(is_arc)),
167 clique_callback_(std::move(clique_callback)),
168 num_nodes_(num_nodes) {}
193 TimeLimit* time_limit);
209 DEFINE_INT_TYPE(CandidateIndex, ptrdiff_t);
221 State(
const State& other)
222 : pivot(other.pivot),
223 num_remaining_candidates(other.num_remaining_candidates),
224 candidates(other.candidates),
225 first_candidate_index(other.first_candidate_index),
226 candidate_for_recursion(other.candidate_for_recursion) {}
228 State& operator=(
const State& other) {
230 num_remaining_candidates = other.num_remaining_candidates;
231 candidates = other.candidates;
232 first_candidate_index = other.first_candidate_index;
233 candidate_for_recursion = other.candidate_for_recursion;
240 inline void MoveFirstCandidateToNotSet() {
241 ++first_candidate_index;
242 --num_remaining_candidates;
246 std::string DebugString() {
248 absl::StrAppend(&buffer,
"pivot = ", pivot,
249 "\nnum_remaining_candidates = ", num_remaining_candidates,
251 for (CandidateIndex i(0); i < candidates.size(); ++i) {
252 if (i > 0) buffer +=
", ";
253 absl::StrAppend(&buffer, candidates[i]);
256 &buffer,
"]\nfirst_candidate_index = ", first_candidate_index.value(),
257 "\ncandidate_for_recursion = ", candidate_for_recursion.value());
266 int num_remaining_candidates;
275 absl::StrongVector<CandidateIndex, NodeIndex> candidates;
279 CandidateIndex first_candidate_index;
283 CandidateIndex candidate_for_recursion;
296 static const double kPushStateDeterministicTimeSecondsPerCandidate;
312 void InitializeState(State* state);
316 return node1 == node2 || is_arc_(node1, node2);
322 CandidateIndex SelectCandidateIndexForRecursion(State* state);
325 std::string CliqueDebugString(
const std::vector<NodeIndex>& clique);
343 std::vector<State> states_;
346 std::vector<NodeIndex> current_clique_;
350 int64 num_remaining_iterations_;
354 TimeLimit* time_limit_;
357 template <
typename NodeIndex>
358 void BronKerboschAlgorithm<NodeIndex>::InitializeState(State* state) {
359 DCHECK(state !=
nullptr);
360 const int num_candidates = state->candidates.size();
361 int num_disconnected_candidates = num_candidates;
363 CandidateIndex pivot_index(-1);
364 for (CandidateIndex pivot_candidate_index(0);
365 pivot_candidate_index < num_candidates &&
366 num_disconnected_candidates > 0;
367 ++pivot_candidate_index) {
368 const NodeIndex pivot_candidate = state->candidates[pivot_candidate_index];
370 for (CandidateIndex i(state->first_candidate_index); i < num_candidates;
372 if (!IsArc(pivot_candidate, state->candidates[i])) {
376 if (count < num_disconnected_candidates) {
377 pivot_index = pivot_candidate_index;
378 state->pivot = pivot_candidate;
379 num_disconnected_candidates = count;
382 state->num_remaining_candidates = num_disconnected_candidates;
383 if (pivot_index >= state->first_candidate_index) {
384 std::swap(state->candidates[pivot_index],
385 state->candidates[state->first_candidate_index]);
386 ++state->num_remaining_candidates;
390 template <
typename NodeIndex>
391 typename BronKerboschAlgorithm<NodeIndex>::CandidateIndex
392 BronKerboschAlgorithm<NodeIndex>::SelectCandidateIndexForRecursion(
394 DCHECK(state !=
nullptr);
395 CandidateIndex disconnected_node_index =
396 std::max(state->first_candidate_index, state->candidate_for_recursion);
397 while (disconnected_node_index < state->candidates.size() &&
398 state->candidates[disconnected_node_index] != state->pivot &&
399 IsArc(state->pivot, state->candidates[disconnected_node_index])) {
400 ++disconnected_node_index;
402 state->candidate_for_recursion = disconnected_node_index;
403 return disconnected_node_index;
406 template <
typename NodeIndex>
407 void BronKerboschAlgorithm<NodeIndex>::Initialize() {
408 DCHECK(states_.empty());
409 states_.reserve(num_nodes_);
410 states_.emplace_back();
412 State*
const root_state = &states_.back();
413 root_state->first_candidate_index = 0;
414 root_state->candidate_for_recursion = 0;
415 root_state->candidates.resize(num_nodes_, 0);
416 std::iota(root_state->candidates.begin(), root_state->candidates.end(), 0);
417 root_state->num_remaining_candidates = num_nodes_;
418 InitializeState(root_state);
420 DVLOG(2) <<
"Initialized";
423 template <
typename NodeIndex>
424 void BronKerboschAlgorithm<NodeIndex>::PopState() {
425 DCHECK(!states_.empty());
427 if (!states_.empty()) {
428 State*
const state = &states_.back();
429 current_clique_.pop_back();
430 state->MoveFirstCandidateToNotSet();
434 template <
typename NodeIndex>
435 std::string BronKerboschAlgorithm<NodeIndex>::CliqueDebugString(
436 const std::vector<NodeIndex>& clique) {
437 std::string message =
"Clique: [ ";
439 absl::StrAppend(&message, node,
" ");
445 template <
typename NodeIndex>
446 void BronKerboschAlgorithm<NodeIndex>::PushState(
NodeIndex selected) {
447 DCHECK(!states_.empty());
448 DCHECK(time_limit_ !=
nullptr);
449 DVLOG(2) <<
"PushState: New depth = " << states_.size() + 1
450 <<
", selected node = " << selected;
451 absl::StrongVector<CandidateIndex, NodeIndex> new_candidates;
453 State*
const previous_state = &states_.back();
454 const double deterministic_time =
455 kPushStateDeterministicTimeSecondsPerCandidate *
456 previous_state->candidates.size();
457 time_limit_->AdvanceDeterministicTime(deterministic_time,
"PushState");
464 new_candidates.reserve(previous_state->candidates.size());
465 for (CandidateIndex i(0); i < previous_state->first_candidate_index; ++i) {
466 const NodeIndex candidate = previous_state->candidates[i];
467 if (IsArc(selected, candidate)) {
468 new_candidates.push_back(candidate);
471 const CandidateIndex new_first_candidate_index(new_candidates.size());
472 for (CandidateIndex i = previous_state->first_candidate_index + 1;
473 i < previous_state->candidates.size(); ++i) {
474 const NodeIndex candidate = previous_state->candidates[i];
475 if (IsArc(selected, candidate)) {
476 new_candidates.push_back(candidate);
480 current_clique_.push_back(selected);
481 if (new_candidates.empty()) {
484 DVLOG(2) << CliqueDebugString(current_clique_);
485 const CliqueResponse response = clique_callback_(current_clique_);
490 num_remaining_iterations_ = 1;
492 current_clique_.pop_back();
493 previous_state->MoveFirstCandidateToNotSet();
500 states_.emplace_back();
501 State*
const new_state = &states_.back();
502 new_state->candidates.swap(new_candidates);
503 new_state->first_candidate_index = new_first_candidate_index;
505 InitializeState(new_state);
508 template <
typename NodeIndex>
510 int64 max_num_iterations, TimeLimit* time_limit) {
511 CHECK(time_limit !=
nullptr);
512 time_limit_ = time_limit;
513 if (states_.empty()) {
516 for (num_remaining_iterations_ = max_num_iterations;
517 !states_.empty() && num_remaining_iterations_ > 0 &&
518 !time_limit->LimitReached();
519 --num_remaining_iterations_) {
520 State*
const state = &states_.back();
521 DVLOG(2) <<
"Loop: " << states_.size() <<
" states, "
522 << state->num_remaining_candidates <<
" candidate to explore\n"
523 << state->DebugString();
524 if (state->num_remaining_candidates == 0) {
529 const CandidateIndex selected_index =
530 SelectCandidateIndexForRecursion(state);
531 DVLOG(2) <<
"selected_index = " << selected_index;
532 const NodeIndex selected = state->candidates[selected_index];
533 DVLOG(2) <<
"Selected candidate = " << selected;
535 NodeIndex& f = state->candidates[state->first_candidate_index];
536 NodeIndex& s = state->candidates[selected_index];
541 time_limit_ =
nullptr;
542 return states_.empty() ? BronKerboschAlgorithmStatus::COMPLETED
546 template <
typename NodeIndex>
548 int64 max_num_iterations) {
549 TimeLimit time_limit(std::numeric_limits<double>::infinity());
550 return RunWithTimeLimit(max_num_iterations, &time_limit);
553 template <
typename NodeIndex>
555 return RunIterations(kint64max);
558 template <
typename NodeIndex>
560 NodeIndex>::kPushStateDeterministicTimeSecondsPerCandidate = 0.54663e-7;
563 #endif // OR_TOOLS_GRAPH_CLIQUES_H_