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;
105 std::vector<int>* node_equivalence_classes_io,
106 std::vector<std::unique_ptr<SparsePermutation> >* generators,
107 std::vector<int>* factorized_automorphism_group_size,
108 TimeLimit* time_limit =
nullptr);
131 std::vector<int>* new_singletons_or_null);
136 inline int NumNodes()
const {
return graph_.num_nodes(); }
148 std::vector<int> flattened_reverse_adj_lists_;
149 std::vector<int> reverse_adj_list_index_;
150 util::BeginEndWrapper<std::vector<int>::const_iterator> TailsOfIncomingArcsTo(
156 TimeLimit dummy_time_limit_;
157 TimeLimit* time_limit_;
169 std::unique_ptr<SparsePermutation> FindOneSuitablePermutation(
172 const std::vector<std::unique_ptr<SparsePermutation> >&
173 generators_found_so_far,
174 const std::vector<std::vector<int> >& permutations_displacing_node);
185 int first_image_node;
186 std::vector<int> remaining_pruned_image_nodes;
188 int num_parts_before_trying_to_map_base_node;
192 int min_potential_mismatching_part_index;
194 SearchState(
int bn,
int in,
int np,
int mi)
196 first_image_node(in),
197 num_parts_before_trying_to_map_base_node(np),
198 min_potential_mismatching_part_index(mi) {}
200 std::string DebugString()
const;
202 std::vector<SearchState> search_states_;
218 bool ConfirmFullMatchOrFindNextMappingDecision(
219 const DynamicPartition& base_partition,
220 const DynamicPartition& image_partition,
221 const DynamicPermutation& current_permutation_candidate,
222 int* min_potential_mismatching_part_index_io,
int* next_base_node,
223 int* next_image_node)
const;
230 void PruneOrbitsUnderPermutationsCompatibleWithPartition(
231 const DynamicPartition& partition,
232 const std::vector<std::unique_ptr<SparsePermutation> >& all_permutations,
233 const std::vector<int>& permutation_indices, std::vector<int>* nodes);
238 DynamicPermutation tmp_dynamic_permutation_;
239 mutable std::vector<bool> tmp_node_mask_;
240 std::vector<int> tmp_degree_;
241 std::vector<int> tmp_stack_;
242 std::vector<std::vector<int> > tmp_nodes_with_degree_;
243 MergingPartition tmp_partition_;
244 std::vector<const SparsePermutation*> tmp_compatible_permutations_;
247 struct Stats :
public StatsGroup {
249 : StatsGroup(
"GraphSymmetryFinder"),
250 initialization_time(
"a Initialization", this),
251 initialization_refine_time(
"b ┗╸Refine", this),
252 invariant_dive_time(
"c Invariant Dive", this),
253 main_search_time(
"d Main Search", this),
254 invariant_unroll_time(
"e ┣╸Dive unroll", this),
255 permutation_output_time(
"f ┣╸Permutation output", this),
256 search_time(
"g ┗╸FindOneSuitablePermutation()", this),
257 search_time_fail(
"h ┣╸Fail", this),
258 search_time_success(
"i ┣╸Success", this),
259 initial_search_refine_time(
"j ┣╸Initial refine", this),
260 search_refine_time(
"k ┣╸Further refines", this),
261 quick_compatibility_time(
"l ┣╸Compatibility checks", this),
262 quick_compatibility_fail_time(
"m ┃ ┣╸Fail", this),
263 quick_compatibility_success_time(
"n ┃ ┗╸Success", this),
264 dynamic_permutation_refinement_time(
265 "o ┣╸Dynamic permutation refinement", this),
266 map_election_std_time(
267 "p ┣╸Mapping election / full match detection", this),
268 map_election_std_mapping_time(
"q ┃ ┣╸Mapping elected", this),
269 map_election_std_full_match_time(
"r ┃ ┗╸Full Match", this),
270 automorphism_test_time(
"s ┣╸[Upon full match] Automorphism check",
272 automorphism_test_fail_time(
"t ┃ ┣╸Fail", this),
273 automorphism_test_success_time(
"u ┃ ┗╸Success", this),
274 search_finalize_time(
"v ┣╸[Upon auto success] Finalization", this),
275 dynamic_permutation_undo_time(
276 "w ┣╸[Upon auto fail, full] Dynamic permutation undo", this),
278 "x ┣╸[Upon auto fail, partial] Mapping re-election", this),
279 non_singleton_search_time(
"y ┃ ┗╸Non-singleton search", this),
280 backtracking_time(
"z ┗╸Backtracking", this),
281 pruning_time(
"{ ┗╸Pruning", this),
282 search_depth(
"~ Search Stats: search_depth", this) {}
284 TimeDistribution initialization_time;
285 TimeDistribution initialization_refine_time;
286 TimeDistribution invariant_dive_time;
287 TimeDistribution main_search_time;
288 TimeDistribution invariant_unroll_time;
289 TimeDistribution permutation_output_time;
290 TimeDistribution search_time;
291 TimeDistribution search_time_fail;
292 TimeDistribution search_time_success;
293 TimeDistribution initial_search_refine_time;
294 TimeDistribution search_refine_time;
295 TimeDistribution quick_compatibility_time;
296 TimeDistribution quick_compatibility_fail_time;
297 TimeDistribution quick_compatibility_success_time;
298 TimeDistribution dynamic_permutation_refinement_time;
299 TimeDistribution map_election_std_time;
300 TimeDistribution map_election_std_mapping_time;
301 TimeDistribution map_election_std_full_match_time;
302 TimeDistribution automorphism_test_time;
303 TimeDistribution automorphism_test_fail_time;
304 TimeDistribution automorphism_test_success_time;
305 TimeDistribution search_finalize_time;
306 TimeDistribution dynamic_permutation_undo_time;
307 TimeDistribution map_reelection_time;
308 TimeDistribution non_singleton_search_time;
309 TimeDistribution backtracking_time;
310 TimeDistribution pruning_time;
312 IntegerDistribution search_depth;
314 mutable Stats stats_;
void RecursivelyRefinePartitionByAdjacency(int first_unrefined_part_index, DynamicPartition *partition)
::util::StaticGraph Graph
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)