24 #ifndef OR_TOOLS_ALGORITHMS_FIND_GRAPH_SYMMETRIES_H_
25 #define OR_TOOLS_ALGORITHMS_FIND_GRAPH_SYMMETRIES_H_
30 #include "absl/status/status.h"
31 #include "absl/time/time.h"
34 #include "ortools/graph/graph.h"
35 #include "ortools/graph/iterators.h"
36 #include "ortools/util/stats.h"
37 #include "ortools/util/time_limit.h"
41 class SparsePermutation;
45 typedef ::util::StaticGraph<>
Graph;
104 double time_limit_seconds, std::vector<int>* node_equivalence_classes_io,
105 std::vector<std::unique_ptr<SparsePermutation> >* generators,
106 std::vector<int>* factorized_automorphism_group_size);
129 std::vector<int>* new_singletons_or_null);
134 inline int NumNodes()
const {
return graph_.num_nodes(); }
146 std::vector<int> flattened_reverse_adj_lists_;
147 std::vector<int> reverse_adj_list_index_;
148 util::BeginEndWrapper<std::vector<int>::const_iterator> TailsOfIncomingArcsTo(
152 mutable std::unique_ptr<TimeLimit> time_limit_;
164 std::unique_ptr<SparsePermutation> FindOneSuitablePermutation(
167 const std::vector<std::unique_ptr<SparsePermutation> >&
168 generators_found_so_far,
169 const std::vector<std::vector<int> >& permutations_displacing_node);
180 int first_image_node;
181 std::vector<int> remaining_pruned_image_nodes;
183 int num_parts_before_trying_to_map_base_node;
187 int min_potential_mismatching_part_index;
189 SearchState(
int bn,
int in,
int np,
int mi)
191 first_image_node(in),
192 num_parts_before_trying_to_map_base_node(np),
193 min_potential_mismatching_part_index(mi) {}
195 std::string DebugString()
const;
197 std::vector<SearchState> search_states_;
213 bool ConfirmFullMatchOrFindNextMappingDecision(
214 const DynamicPartition& base_partition,
215 const DynamicPartition& image_partition,
216 const DynamicPermutation& current_permutation_candidate,
217 int* min_potential_mismatching_part_index_io,
int* next_base_node,
218 int* next_image_node)
const;
225 void PruneOrbitsUnderPermutationsCompatibleWithPartition(
226 const DynamicPartition& partition,
227 const std::vector<std::unique_ptr<SparsePermutation> >& all_permutations,
228 const std::vector<int>& permutation_indices, std::vector<int>* nodes);
233 DynamicPermutation tmp_dynamic_permutation_;
234 mutable std::vector<bool> tmp_node_mask_;
235 std::vector<int> tmp_degree_;
236 std::vector<int> tmp_stack_;
237 std::vector<std::vector<int> > tmp_nodes_with_degree_;
238 MergingPartition tmp_partition_;
239 std::vector<const SparsePermutation*> tmp_compatible_permutations_;
242 struct Stats :
public StatsGroup {
244 : StatsGroup(
"GraphSymmetryFinder"),
245 initialization_time(
"a Initialization", this),
246 initialization_refine_time(
"b ┗╸Refine", this),
247 invariant_dive_time(
"c Invariant Dive", this),
248 main_search_time(
"d Main Search", this),
249 invariant_unroll_time(
"e ┣╸Dive unroll", this),
250 permutation_output_time(
"f ┣╸Permutation output", this),
251 search_time(
"g ┗╸FindOneSuitablePermutation()", this),
252 search_time_fail(
"h ┣╸Fail", this),
253 search_time_success(
"i ┣╸Success", this),
254 initial_search_refine_time(
"j ┣╸Initial refine", this),
255 search_refine_time(
"k ┣╸Further refines", this),
256 quick_compatibility_time(
"l ┣╸Compatibility checks", this),
257 quick_compatibility_fail_time(
"m ┃ ┣╸Fail", this),
258 quick_compatibility_success_time(
"n ┃ ┗╸Success", this),
259 dynamic_permutation_refinement_time(
260 "o ┣╸Dynamic permutation refinement", this),
261 map_election_std_time(
262 "p ┣╸Mapping election / full match detection", this),
263 map_election_std_mapping_time(
"q ┃ ┣╸Mapping elected", this),
264 map_election_std_full_match_time(
"r ┃ ┗╸Full Match", this),
265 automorphism_test_time(
"s ┣╸[Upon full match] Automorphism check",
267 automorphism_test_fail_time(
"t ┃ ┣╸Fail", this),
268 automorphism_test_success_time(
"u ┃ ┗╸Success", this),
269 search_finalize_time(
"v ┣╸[Upon auto success] Finalization", this),
270 dynamic_permutation_undo_time(
271 "w ┣╸[Upon auto fail, full] Dynamic permutation undo", this),
273 "x ┣╸[Upon auto fail, partial] Mapping re-election", this),
274 non_singleton_search_time(
"y ┃ ┗╸Non-singleton search", this),
275 backtracking_time(
"z ┗╸Backtracking", this),
276 pruning_time(
"{ ┗╸Pruning", this),
277 search_depth(
"~ Search Stats: search_depth", this) {}
279 TimeDistribution initialization_time;
280 TimeDistribution initialization_refine_time;
281 TimeDistribution invariant_dive_time;
282 TimeDistribution main_search_time;
283 TimeDistribution invariant_unroll_time;
284 TimeDistribution permutation_output_time;
285 TimeDistribution search_time;
286 TimeDistribution search_time_fail;
287 TimeDistribution search_time_success;
288 TimeDistribution initial_search_refine_time;
289 TimeDistribution search_refine_time;
290 TimeDistribution quick_compatibility_time;
291 TimeDistribution quick_compatibility_fail_time;
292 TimeDistribution quick_compatibility_success_time;
293 TimeDistribution dynamic_permutation_refinement_time;
294 TimeDistribution map_election_std_time;
295 TimeDistribution map_election_std_mapping_time;
296 TimeDistribution map_election_std_full_match_time;
297 TimeDistribution automorphism_test_time;
298 TimeDistribution automorphism_test_fail_time;
299 TimeDistribution automorphism_test_success_time;
300 TimeDistribution search_finalize_time;
301 TimeDistribution dynamic_permutation_undo_time;
302 TimeDistribution map_reelection_time;
303 TimeDistribution non_singleton_search_time;
304 TimeDistribution backtracking_time;
305 TimeDistribution pruning_time;
307 IntegerDistribution search_depth;
309 mutable Stats stats_;
314 #endif // OR_TOOLS_ALGORITHMS_FIND_GRAPH_SYMMETRIES_H_