20 #include "absl/memory/memory.h"
21 #include "absl/status/status.h"
22 #include "absl/strings/str_format.h"
23 #include "absl/strings/str_join.h"
24 #include "absl/time/clock.h"
25 #include "absl/time/time.h"
34 ABSL_FLAG(
bool, minimize_permutation_support_size,
false,
35 "Tweak the algorithm to try and minimize the support size"
36 " of the generators produced. This may negatively impact the"
37 " performance, but works great on the sat_holeXXX benchmarks"
38 " to reduce the support size.");
46 void SwapFrontAndBack(std::vector<int>* v) {
48 std::swap((*v)[0], v->back());
51 bool PartitionsAreCompatibleAfterPartIndex(
const DynamicPartition& p1,
52 const DynamicPartition& p2,
54 const int num_parts = p1.NumParts();
55 if (p2.NumParts() != num_parts)
return false;
56 for (
int p = part_index; p < num_parts; ++p) {
57 if (p1.SizeOfPart(p) != p2.SizeOfPart(p) ||
58 p1.ParentOfPart(p) != p2.ParentOfPart(p)) {
74 bool ListMapsToList(
const List& l1,
const List& l2,
75 const DynamicPermutation& permutation,
76 std::vector<bool>* tmp_node_mask) {
77 int num_elements_delta = 0;
79 for (
const int mapped_x : l2) {
81 (*tmp_node_mask)[mapped_x] =
true;
83 for (
const int x : l1) {
85 const int mapped_x = permutation.ImageOf(x);
86 if (!(*tmp_node_mask)[mapped_x]) {
90 (*tmp_node_mask)[mapped_x] =
false;
92 if (num_elements_delta != 0) match =
false;
95 for (
const int x : l2) (*tmp_node_mask)[x] =
false;
103 tmp_dynamic_permutation_(NumNodes()),
104 tmp_node_mask_(NumNodes(), false),
105 tmp_degree_(NumNodes(), 0),
106 tmp_nodes_with_degree_(NumNodes() + 1) {
108 time_limit_ = &dummy_time_limit_;
109 tmp_partition_.
Reset(NumNodes());
116 reverse_adj_list_index_.assign(graph.
num_nodes() + 2, 0);
117 for (
const int node : graph.
AllNodes()) {
119 ++reverse_adj_list_index_[graph.
Head(arc) + 2];
125 std::partial_sum(reverse_adj_list_index_.begin() + 2,
126 reverse_adj_list_index_.end(),
127 reverse_adj_list_index_.begin() + 2);
131 flattened_reverse_adj_lists_.assign(graph.
num_arcs(), -1);
132 for (
const int node : graph.
AllNodes()) {
134 flattened_reverse_adj_lists_[reverse_adj_list_index_[graph.
Head(arc) +
143 for (
const int i : flattened_reverse_adj_lists_)
DCHECK_NE(i, -1);
151 const int image = permutation.
ImageOf(base);
152 if (image == base)
continue;
153 if (!ListMapsToList(graph_[base], graph_[image], permutation,
158 if (!reverse_adj_list_index_.empty()) {
162 const int image = permutation.
ImageOf(base);
163 if (image == base)
continue;
164 if (!ListMapsToList(TailsOfIncomingArcsTo(base),
165 TailsOfIncomingArcsTo(image), permutation,
178 inline void IncrementCounterForNonSingletons(
const T& nodes,
180 std::vector<int>* node_count,
181 std::vector<int>* nodes_seen,
182 int64* num_operations) {
183 *num_operations += nodes.end() - nodes.begin();
184 for (
const int node : nodes) {
186 const int count = ++(*node_count)[node];
187 if (count == 1) nodes_seen->push_back(node);
195 std::vector<int>& tmp_nodes_with_nonzero_degree = tmp_stack_;
204 int64 num_operations = 0;
217 std::vector<bool> adjacency_directions(1,
true);
218 if (!reverse_adj_list_index_.empty()) {
219 adjacency_directions.push_back(
false);
221 for (
int part_index = first_unrefined_part_index;
224 for (
const bool outgoing_adjacency : adjacency_directions) {
227 if (outgoing_adjacency) {
229 IncrementCounterForNonSingletons(
230 graph_[node], *partition, &tmp_degree_,
231 &tmp_nodes_with_nonzero_degree, &num_operations);
235 IncrementCounterForNonSingletons(
236 TailsOfIncomingArcsTo(node), *partition, &tmp_degree_,
237 &tmp_nodes_with_nonzero_degree, &num_operations);
242 num_operations += 3 + tmp_nodes_with_nonzero_degree.size();
243 for (
const int node : tmp_nodes_with_nonzero_degree) {
244 const int degree = tmp_degree_[node];
245 tmp_degree_[node] = 0;
246 max_degree =
std::max(max_degree, degree);
247 tmp_nodes_with_degree_[degree].push_back(node);
249 tmp_nodes_with_nonzero_degree.clear();
252 for (
int degree = 1; degree <= max_degree; ++degree) {
255 num_operations += 1 + 3 * tmp_nodes_with_degree_[degree].size();
256 partition->
Refine(tmp_nodes_with_degree_[degree]);
257 tmp_nodes_with_degree_[degree].clear();
266 static_cast<double>(num_operations));
271 const int original_num_parts = partition->
NumParts();
272 partition->
Refine(std::vector<int>(1, node));
276 if (new_singletons !=
nullptr) {
277 new_singletons->clear();
278 for (
int p = original_num_parts; p < partition->
NumParts(); ++p) {
282 if (!tmp_node_mask_[parent] && parent < original_num_parts &&
284 tmp_node_mask_[parent] =
true;
292 for (
int p = original_num_parts; p < partition->
NumParts(); ++p) {
299 void MergeNodeEquivalenceClassesAccordingToPermutation(
302 for (
int c = 0; c < perm.
NumCycles(); ++c) {
305 for (
const int e : perm.
Cycle(c)) {
307 const int removed_representative =
309 if (sorted_representatives !=
nullptr && removed_representative != -1) {
310 sorted_representatives->
Remove(removed_representative);
330 void GetAllOtherRepresentativesInSamePartAs(
331 int representative_node,
const DynamicPartition& partition,
332 const DenseDoublyLinkedList& representatives_sorted_by_index_in_partition,
333 MergingPartition* node_equivalence_classes,
334 std::vector<int>* pruned_other_nodes) {
335 pruned_other_nodes->clear();
336 const int part_index = partition.PartOf(representative_node);
338 int repr = representative_node;
340 DCHECK_EQ(repr, node_equivalence_classes->GetRoot(repr));
341 repr = representatives_sorted_by_index_in_partition.Prev(repr);
342 if (repr < 0 || partition.PartOf(repr) != part_index)
break;
343 pruned_other_nodes->push_back(repr);
346 repr = representative_node;
348 DCHECK_EQ(repr, node_equivalence_classes->GetRoot(repr));
349 repr = representatives_sorted_by_index_in_partition.Next(repr);
350 if (repr < 0 || partition.PartOf(repr) != part_index)
break;
351 pruned_other_nodes->push_back(repr);
359 std::vector<int> expected_output;
360 for (
const int e : partition.ElementsInPart(part_index)) {
361 if (node_equivalence_classes->GetRoot(e) != representative_node) {
362 expected_output.push_back(e);
365 node_equivalence_classes->KeepOnlyOneNodePerPart(&expected_output);
366 for (
int& x : expected_output) x = node_equivalence_classes->GetRoot(x);
367 std::sort(expected_output.begin(), expected_output.end());
368 std::vector<int> sorted_output = *pruned_other_nodes;
369 std::sort(sorted_output.begin(), sorted_output.end());
370 DCHECK_EQ(absl::StrJoin(expected_output,
" "),
371 absl::StrJoin(sorted_output,
" "));
377 std::vector<int>* node_equivalence_classes_io,
378 std::vector<std::unique_ptr<SparsePermutation>>* generators,
379 std::vector<int>* factorized_automorphism_group_size,
385 factorized_automorphism_group_size->clear();
386 if (node_equivalence_classes_io->size() != NumNodes()) {
387 return absl::Status(absl::StatusCode::kInvalidArgument,
388 "Invalid 'node_equivalence_classes_io'.");
398 return absl::Status(absl::StatusCode::kDeadlineExceeded,
399 "During the initial refinement.");
401 VLOG(4) <<
"Base partition: "
405 std::vector<std::vector<int>> permutations_displacing_node(NumNodes());
406 std::vector<int> potential_root_image_nodes;
429 struct InvariantDiveState {
431 int num_parts_before_refinement;
433 InvariantDiveState(
int node,
int num_parts)
434 : invariant_node(node), num_parts_before_refinement(num_parts) {}
436 std::vector<InvariantDiveState> invariant_dive_stack;
443 for (
int invariant_node = 0; invariant_node < NumNodes(); ++invariant_node) {
447 invariant_dive_stack.push_back(
448 InvariantDiveState(invariant_node, base_partition.
NumParts()));
450 VLOG(4) <<
"Invariant dive: invariant node = " << invariant_node
451 <<
"; partition after: "
454 return absl::Status(absl::StatusCode::kDeadlineExceeded,
455 "During the invariant dive.");
466 while (!invariant_dive_stack.empty()) {
470 const int root_node = invariant_dive_stack.back().invariant_node;
471 const int base_num_parts =
472 invariant_dive_stack.back().num_parts_before_refinement;
473 invariant_dive_stack.pop_back();
476 VLOG(4) <<
"Backtracking invariant dive: root node = " << root_node
501 GetAllOtherRepresentativesInSamePartAs(
502 root_node, base_partition, representatives_sorted_by_index_in_partition,
503 &node_equivalence_classes, &potential_root_image_nodes);
504 DCHECK(!potential_root_image_nodes.empty());
505 IF_STATS_ENABLED(stats_.invariant_unroll_time.StopTimerAndAddElapsedTime());
509 while (!potential_root_image_nodes.empty()) {
511 VLOG(4) <<
"Potential (pruned) images of root node " << root_node
512 <<
" left: [" << absl::StrJoin(potential_root_image_nodes,
" ")
514 const int root_image_node = potential_root_image_nodes.back();
515 VLOG(4) <<
"Trying image of root node: " << root_image_node;
517 std::unique_ptr<SparsePermutation> permutation =
518 FindOneSuitablePermutation(root_node, root_image_node,
519 &base_partition, &image_partition,
520 *generators, permutations_displacing_node);
522 if (permutation !=
nullptr) {
527 MergeNodeEquivalenceClassesAccordingToPermutation(
528 *permutation, &node_equivalence_classes,
529 &representatives_sorted_by_index_in_partition);
534 SwapFrontAndBack(&potential_root_image_nodes);
536 &potential_root_image_nodes);
537 SwapFrontAndBack(&potential_root_image_nodes);
540 const int permutation_index =
static_cast<int>(generators->size());
541 for (
const int node : permutation->Support()) {
542 permutations_displacing_node[node].push_back(permutation_index);
547 generators->push_back(std::move(permutation));
550 potential_root_image_nodes.pop_back();
556 factorized_automorphism_group_size->push_back(
564 return absl::Status(absl::StatusCode::kDeadlineExceeded,
565 "Some automorphisms were found, but probably not all.");
567 return ::absl::OkStatus();
578 int part_index,
int* base_node,
int* image_node) {
592 if (absl::GetFlag(FLAGS_minimize_permutation_support_size)) {
594 for (
const int node : base_partition.
ElementsInPart(part_index)) {
595 if (image_partition.
PartOf(node) == part_index) {
596 *image_node = *base_node = node;
607 if (image_partition.
PartOf(*base_node) == part_index) {
608 *image_node = *base_node;
618 std::unique_ptr<SparsePermutation>
619 GraphSymmetryFinder::FindOneSuitablePermutation(
620 int root_node,
int root_image_node, DynamicPartition* base_partition,
621 DynamicPartition* image_partition,
622 const std::vector<std::unique_ptr<SparsePermutation>>&
623 generators_found_so_far,
624 const std::vector<std::vector<int>>& permutations_displacing_node) {
630 DCHECK(search_states_.empty());
633 std::vector<int> base_singletons;
634 std::vector<int> image_singletons;
637 int min_potential_mismatching_part_index;
638 std::vector<int> next_potential_image_nodes;
642 search_states_.emplace_back(
644 base_partition->NumParts(),
645 base_partition->NumParts());
647 search_states_.back().remaining_pruned_image_nodes.assign(1, root_image_node);
652 while (!search_states_.empty()) {
664 const SearchState& ss = search_states_.back();
665 const int image_node = ss.first_image_node >= 0
666 ? ss.first_image_node
667 : ss.remaining_pruned_image_nodes.back();
671 DCHECK_EQ(ss.num_parts_before_trying_to_map_base_node,
672 image_partition->NumParts());
681 VLOG(4) << ss.DebugString();
698 bool compatible =
true;
701 compatible = PartitionsAreCompatibleAfterPartIndex(
702 *base_partition, *image_partition,
703 ss.num_parts_before_trying_to_map_base_node);
704 u.AlsoUpdate(compatible ? &stats_.quick_compatibility_success_time
705 : &stats_.quick_compatibility_fail_time);
707 bool partitions_are_full_match =
false;
711 &stats_.dynamic_permutation_refinement_time);
712 tmp_dynamic_permutation_.
AddMappings(base_singletons, image_singletons);
715 min_potential_mismatching_part_index =
716 ss.min_potential_mismatching_part_index;
717 partitions_are_full_match = ConfirmFullMatchOrFindNextMappingDecision(
718 *base_partition, *image_partition, tmp_dynamic_permutation_,
719 &min_potential_mismatching_part_index, &next_base_node,
721 u.AlsoUpdate(partitions_are_full_match
722 ? &stats_.map_election_std_full_match_time
723 : &stats_.map_election_std_mapping_time);
725 if (compatible && partitions_are_full_match) {
726 DCHECK_EQ(min_potential_mismatching_part_index,
727 base_partition->NumParts());
733 bool is_automorphism =
true;
737 u.AlsoUpdate(is_automorphism ? &stats_.automorphism_test_success_time
738 : &stats_.automorphism_test_fail_time);
740 if (is_automorphism) {
744 std::unique_ptr<SparsePermutation> sparse_permutation(
746 VLOG(4) <<
"Automorphism found: " << sparse_permutation->DebugString();
747 const int base_num_parts =
748 search_states_[0].num_parts_before_trying_to_map_base_node;
749 base_partition->UndoRefineUntilNumPartsEqual(base_num_parts);
750 image_partition->UndoRefineUntilNumPartsEqual(base_num_parts);
751 tmp_dynamic_permutation_.
Reset();
752 search_states_.clear();
754 search_time_updater.AlsoUpdate(&stats_.search_time_success);
755 return sparse_permutation;
761 VLOG(4) <<
"Permutation candidate isn't a valid automorphism.";
762 if (base_partition->NumParts() == NumNodes()) {
773 int non_singleton_part = 0;
776 while (base_partition->SizeOfPart(non_singleton_part) == 1) {
777 ++non_singleton_part;
778 DCHECK_LT(non_singleton_part, base_partition->NumParts());
782 1e-9 *
static_cast<double>(non_singleton_part));
786 GetBestMapping(*base_partition, *image_partition, non_singleton_part,
787 &next_base_node, &next_image_node);
802 while (!search_states_.empty()) {
803 SearchState*
const last_ss = &search_states_.back();
804 image_partition->UndoRefineUntilNumPartsEqual(
805 last_ss->num_parts_before_trying_to_map_base_node);
806 if (last_ss->first_image_node >= 0) {
819 const int part = image_partition->PartOf(last_ss->first_image_node);
820 last_ss->remaining_pruned_image_nodes.reserve(
821 image_partition->SizeOfPart(part));
822 last_ss->remaining_pruned_image_nodes.push_back(
823 last_ss->first_image_node);
824 for (
const int e : image_partition->ElementsInPart(part)) {
825 if (e != last_ss->first_image_node) {
826 last_ss->remaining_pruned_image_nodes.push_back(e);
831 PruneOrbitsUnderPermutationsCompatibleWithPartition(
832 *image_partition, generators_found_so_far,
833 permutations_displacing_node[last_ss->first_image_node],
834 &last_ss->remaining_pruned_image_nodes);
836 SwapFrontAndBack(&last_ss->remaining_pruned_image_nodes);
837 DCHECK_EQ(last_ss->remaining_pruned_image_nodes.back(),
838 last_ss->first_image_node);
839 last_ss->first_image_node = -1;
841 last_ss->remaining_pruned_image_nodes.pop_back();
842 if (!last_ss->remaining_pruned_image_nodes.empty())
break;
844 VLOG(4) <<
"Backtracking one level up.";
845 base_partition->UndoRefineUntilNumPartsEqual(
846 last_ss->num_parts_before_trying_to_map_base_node);
851 search_states_.pop_back();
860 VLOG(4) <<
" Deepening the search.";
861 search_states_.emplace_back(
862 next_base_node, next_image_node,
863 base_partition->NumParts(),
864 min_potential_mismatching_part_index);
872 search_time_updater.AlsoUpdate(&stats_.search_time_fail);
877 GraphSymmetryFinder::TailsOfIncomingArcsTo(
int node)
const {
879 flattened_reverse_adj_lists_.begin() + reverse_adj_list_index_[node],
880 flattened_reverse_adj_lists_.begin() + reverse_adj_list_index_[node + 1]);
883 void GraphSymmetryFinder::PruneOrbitsUnderPermutationsCompatibleWithPartition(
884 const DynamicPartition& partition,
885 const std::vector<std::unique_ptr<SparsePermutation>>& permutations,
886 const std::vector<int>& permutation_indices, std::vector<int>* nodes) {
887 VLOG(4) <<
" Pruning [" << absl::StrJoin(*nodes,
", ") <<
"]";
894 if (nodes->size() <= 1)
return;
899 std::vector<int>& tmp_nodes_on_support =
901 DCHECK(tmp_nodes_on_support.empty());
905 for (
const int p : permutation_indices) {
906 const SparsePermutation& permutation = *permutations[p];
909 bool compatible =
true;
910 for (
int c = 0; c < permutation.NumCycles(); ++c) {
911 const SparsePermutation::Iterator cycle = permutation.Cycle(c);
913 partition.SizeOfPart(partition.PartOf(*cycle.begin()))) {
918 if (!compatible)
continue;
921 for (
int c = 0; c < permutation.NumCycles(); ++c) {
923 for (
const int node : permutation.Cycle(c)) {
924 if (partition.PartOf(node) != part) {
929 part = partition.PartOf(node);
933 if (!compatible)
continue;
936 MergeNodeEquivalenceClassesAccordingToPermutation(permutation,
937 &tmp_partition_,
nullptr);
938 for (
const int node : permutation.Support()) {
939 if (!tmp_node_mask_[node]) {
940 tmp_node_mask_[node] =
true;
941 tmp_nodes_on_support.push_back(node);
950 for (
const int node : tmp_nodes_on_support) {
951 tmp_node_mask_[node] =
false;
954 tmp_nodes_on_support.clear();
955 VLOG(4) <<
" Pruned: [" << absl::StrJoin(*nodes,
", ") <<
"]";
958 bool GraphSymmetryFinder::ConfirmFullMatchOrFindNextMappingDecision(
959 const DynamicPartition& base_partition,
960 const DynamicPartition& image_partition,
961 const DynamicPermutation& current_permutation_candidate,
962 int* min_potential_mismatching_part_index_io,
int* next_base_node,
963 int* next_image_node)
const {
964 *next_base_node = -1;
965 *next_image_node = -1;
969 if (!absl::GetFlag(FLAGS_minimize_permutation_support_size)) {
973 for (
const int loose_node : current_permutation_candidate.LooseEnds()) {
974 DCHECK_GT(base_partition.ElementsInSamePartAs(loose_node).size(), 1);
975 *next_base_node = loose_node;
976 const int root = current_permutation_candidate.RootOf(loose_node);
978 if (image_partition.PartOf(root) == base_partition.PartOf(loose_node)) {
981 *next_image_node = root;
985 if (*next_base_node != -1) {
990 .ElementsInPart(base_partition.PartOf(*next_base_node))
1006 const int initial_min_potential_mismatching_part_index =
1007 *min_potential_mismatching_part_index_io;
1008 for (; *min_potential_mismatching_part_index_io < base_partition.NumParts();
1009 ++*min_potential_mismatching_part_index_io) {
1010 const int p = *min_potential_mismatching_part_index_io;
1011 if (base_partition.SizeOfPart(p) != 1 &&
1012 base_partition.FprintOfPart(p) != image_partition.FprintOfPart(p)) {
1013 GetBestMapping(base_partition, image_partition, p, next_base_node,
1018 const int parent = base_partition.ParentOfPart(p);
1019 if (parent < initial_min_potential_mismatching_part_index &&
1020 base_partition.SizeOfPart(parent) != 1 &&
1021 base_partition.FprintOfPart(parent) !=
1022 image_partition.FprintOfPart(parent)) {
1023 GetBestMapping(base_partition, image_partition, parent, next_base_node,
1032 for (
int p = 0; p < base_partition.NumParts(); ++p) {
1033 if (base_partition.SizeOfPart(p) != 1) {
1034 CHECK_EQ(base_partition.FprintOfPart(p),
1035 image_partition.FprintOfPart(p));
1042 std::string GraphSymmetryFinder::SearchState::DebugString()
const {
1043 return absl::StrFormat(
1044 "SearchState{ base_node=%d, first_image_node=%d,"
1045 " remaining_pruned_image_nodes=[%s],"
1046 " num_parts_before_trying_to_map_base_node=%d }",
1047 base_node, first_image_node,
1048 absl::StrJoin(remaining_pruned_image_nodes,
" "),
1049 num_parts_before_trying_to_map_base_node);
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
IterablePart ElementsInPart(int i) const
void Refine(const std::vector< int > &distinguished_subset)
const std::vector< int > & ElementsInHierarchicalOrder() const
int SizeOfPart(int part) const
void UndoRefineUntilNumPartsEqual(int original_num_parts)
IterablePart ElementsInSamePartAs(int i) const
int PartOf(int element) const
int ParentOfPart(int part) const
std::string DebugString(DebugStringSorting sorting) const
const int NumParts() const
std::unique_ptr< SparsePermutation > CreateSparsePermutation() const
std::string DebugString() const
const std::vector< int > & AllMappingsSrc() const
void UndoLastMappings(std::vector< int > *undone_mapping_src)
void AddMappings(const std::vector< int > &src, const std::vector< int > &dst)
void RecursivelyRefinePartitionByAdjacency(int first_unrefined_part_index, DynamicPartition *partition)
bool IsGraphAutomorphism(const DynamicPermutation &permutation) const
void DistinguishNodeInPartition(int node, DynamicPartition *partition, std::vector< int > *new_singletons_or_null)
absl::Status FindSymmetries(std::vector< int > *node_equivalence_classes_io, std::vector< std::unique_ptr< SparsePermutation > > *generators, std::vector< int > *factorized_automorphism_group_size, TimeLimit *time_limit=nullptr)
GraphSymmetryFinder(const Graph &graph, bool is_undirected)
int NumNodesInSamePartAs(int node)
void Reset(int num_nodes)
int MergePartsOf(int node1, int node2)
int FillEquivalenceClasses(std::vector< int > *node_equivalence_classes)
void KeepOnlyOneNodePerPart(std::vector< int > *nodes)
Iterator Cycle(int i) const
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
bool LimitReached()
Returns true when the external limit is true, or the deterministic time is over the deterministic lim...
void AdvanceDeterministicTime(double deterministic_duration)
Advances the deterministic time.
ArcIndexType num_arcs() const
NodeIndexType num_nodes() const
IntegerRange< NodeIndex > AllNodes() const
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
SharedTimeLimit * time_limit
ABSL_FLAG(bool, minimize_permutation_support_size, false, "Tweak the algorithm to try and minimize the support size" " of the generators produced. This may negatively impact the" " performance, but works great on the sat_holeXXX benchmarks" " to reduce the support size.")
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
DisabledScopedTimeDistributionUpdater ScopedTimeDistributionUpdater
bool GraphIsSymmetric(const Graph &graph)
#define IF_STATS_ENABLED(instructions)
std::vector< int >::const_iterator begin() const