C++ Reference

C++ Reference: Algorithms

find_graph_symmetries.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // This class solves the graph automorphism problem
15 // (https://en.wikipedia.org/wiki/Graph_automorphism), a variant of the famous
16 // graph isomorphism problem (https://en.wikipedia.org/wiki/Graph_isomorphism).
17 //
18 // The algorithm is largely based on the following article, published in 2008:
19 // "Faster Symmetry Discovery using Sparsity of Symmetries" by Darga, Sakallah
20 // and Markov. http://web.eecs.umich.edu/~imarkov/pubs/conf/dac08-sym.pdf.
21 //
22 // See the comments on the class below for more details.
23 
24 #ifndef OR_TOOLS_ALGORITHMS_FIND_GRAPH_SYMMETRIES_H_
25 #define OR_TOOLS_ALGORITHMS_FIND_GRAPH_SYMMETRIES_H_
26 
27 #include <memory>
28 #include <vector>
29 
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"
38 
39 namespace operations_research {
40 
41 class SparsePermutation;
42 
44  public:
45  typedef ::util::StaticGraph<> Graph;
46 
47  // If the Graph passed to the GraphSymmetryFinder is undirected, i.e.
48  // for every arc a->b, b->a is also present, then you should set
49  // "is_undirected" to true.
50  // This will, in effect, DCHECK() that the graph is indeed undirected,
51  // and bypass the need for reverse adjacency lists.
52  //
53  // If you don't know this in advance, you may use GraphIsSymmetric() from
54  // ortools/graph/util.h.
55  //
56  // "graph" must not have multi-arcs.
57  // TODO(user): support multi-arcs.
58  GraphSymmetryFinder(const Graph& graph, bool is_undirected);
59 
60  // Whether the given permutation is an automorphism of the graph given at
61  // construction. This costs O(sum(degree(x))) (the sum is over all nodes x
62  // that are displaced by the permutation).
63  bool IsGraphAutomorphism(const DynamicPermutation& permutation) const;
64 
65  // Find a set of generators of the automorphism subgroup of the graph that
66  // respects the given node equivalence classes. The generators are themselves
67  // permutations of the nodes: see http://en.wikipedia.org/wiki/Automorphism.
68  // These permutations may only map a node onto a node of its equivalence
69  // class: two nodes i and j are in the same equivalence class iff
70  // node_equivalence_classes_io[i] == node_equivalence_classes_io[j];
71  //
72  // This set of generators is not necessarily the smallest possible (neither in
73  // the number of generators, nor in the size of these generators), but it is
74  // minimal in that no generator can be removed while keeping the generated
75  // group intact.
76  // TODO(user): verify the minimality in unit tests.
77  //
78  // Note that if "generators" is empty, then the graph has no symmetry: the
79  // only automorphism is the identity.
80  //
81  // The equivalence classes are actually an input/output: they are refined
82  // according to all asymmetries found. In the end, n1 and n2 will be
83  // considered equivalent (i.e. node_equivalence_classes_io[n1] ==
84  // node_equivalence_classes_io[n2]) if and only if there exists a
85  // permutation of nodes that:
86  // - keeps the graph invariant
87  // - maps n1 onto n2
88  // - maps each node to a node of its original equivalence class.
89  //
90  // This method also outputs the size of the automorphism group, expressed as
91  // a factorized product of integers (note that the size itself may be as
92  // large as N!).
93  //
94  // DEADLINE AND PARTIAL COMPLETION:
95  // If the deadline passed as argument (via TimeLimit) is reached, this method
96  // will return quickly (within a few milliseconds of the limit). The outputs
97  // may be partially filled:
98  // - Each element of "generators", if non-empty, will be a valid permutation.
99  // - "node_equivalence_classes_io" will contain the equivalence classes
100  // corresponding to the orbits under all the generators in "generators".
101  // - "factorized_automorphism_group_size" will also be incomplete, and
102  // partially valid: its last element may be undervalued. But all prior
103  // elements are valid factors of the automorphism group size.
104  absl::Status FindSymmetries(
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);
109 
110  // Fully refine the partition of nodes, using the graph as symmetry breaker.
111  // This means applying the following steps on each part P of the partition:
112  // - Compute the aggregated in-degree of all nodes of the graph, only looking
113  // at arcs originating from nodes in P.
114  // - For each in-degree d=1...max_in_degree, refine the partition by the set
115  // of nodes with in-degree d.
116  // And recursively applying it on all new or modified parts.
117  //
118  // In our use cases, we may call this in a scenario where the partition was
119  // already partially refined on all parts #0...#K, then you should set
120  // "first_unrefined_part_index" to K+1.
121  void RecursivelyRefinePartitionByAdjacency(int first_unrefined_part_index,
122  DynamicPartition* partition);
123 
124  // **** Methods below are public FOR TESTING ONLY. ****
125 
126  // Special wrapper of the above method: assuming that partition is already
127  // fully refined, further refine it by {node}, and propagate by adjacency.
128  // Also, optionally collect all the new singletons of the partition in
129  // "new_singletons", sorted by their part number in the partition.
130  void DistinguishNodeInPartition(int node, DynamicPartition* partition,
131  std::vector<int>* new_singletons_or_null);
132 
133  private:
134  const Graph& graph_;
135 
136  inline int NumNodes() const { return graph_.num_nodes(); }
137 
138  // If the graph isn't symmetric, then we store the reverse adjacency lists
139  // here: for each i in 0..NumNodes()-1, the list of nodes that have an
140  // outgoing arc to i is stored (sorted by node) in:
141  // flattened_reverse_adj_lists_[reverse_adj_list_index_[i] ...
142  // reverse_adj_list_index_[i + 1]]
143  // and can be iterated on easily with:
144  // for (const int tail : TailsOfIncomingArcsTo(node)) ...
145  //
146  // If the graph was specified as symmetric upon construction, both these
147  // vectors are empty, and TailsOfIncomingArcsTo() crashes.
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(
151  int node) const;
152 
153  // Deadline management. Populated upon FindSymmetries(). If the passed
154  // time limit is nullptr, time_limit_ will point to dummy_time_limit_ which
155  // is an object with infinite limits by default.
156  TimeLimit dummy_time_limit_;
157  TimeLimit* time_limit_;
158 
159  // Internal search code used in FindSymmetries(), split out for readability:
160  // find one permutation (if it exists) that maps root_node to root_image_node
161  // and such that the image of "base_partition" by that permutation is equal to
162  // the "image_partition". If no such permutation exists, returns nullptr.
163  //
164  // "generators_found_so_far" and "permutations_displacing_node" are used for
165  // pruning in the search. The former is just the "generators" vector of
166  // FindGraphSymmetries(), with the permutations found so far; and the latter
167  // is an inverted index from each node to all permutations (that we found)
168  // that displace it.
169  std::unique_ptr<SparsePermutation> FindOneSuitablePermutation(
170  int root_node, int root_image_node, DynamicPartition* base_partition,
171  DynamicPartition* image_partition,
172  const std::vector<std::unique_ptr<SparsePermutation> >&
173  generators_found_so_far,
174  const std::vector<std::vector<int> >& permutations_displacing_node);
175 
176  // Data structure used by FindOneSuitablePermutation(). See the .cc
177  struct SearchState {
178  int base_node;
179 
180  // We're tentatively mapping "base_node" to some image node. At first, we
181  // just pick a single candidate: we fill "first_image_node". If this
182  // candidate doesn't work out, we'll select all other candidates in the same
183  // image part, prune them by the symmetries we found already, and put them
184  // in "remaining_pruned_image_nodes" (and set "first_image_node" to -1).
185  int first_image_node;
186  std::vector<int> remaining_pruned_image_nodes;
187 
188  int num_parts_before_trying_to_map_base_node;
189 
190  // Only parts that are at or beyond this index, or their parent parts, may
191  // be mismatching between the base and the image partitions.
192  int min_potential_mismatching_part_index;
193 
194  SearchState(int bn, int in, int np, int mi)
195  : base_node(bn),
196  first_image_node(in),
197  num_parts_before_trying_to_map_base_node(np),
198  min_potential_mismatching_part_index(mi) {}
199 
200  std::string DebugString() const;
201  };
202  std::vector<SearchState> search_states_;
203 
204  // Subroutine of FindOneSuitablePermutation(), split out for modularity:
205  // With the partial candidate mapping given by "base_partition",
206  // "image_partition" and "current_permutation_candidate", determine whether
207  // we have a full match (eg. the permutation is a valid candidate).
208  // If so, simply return true. If not, return false but also fill
209  // "next_base_node" and "next_image_node" with what should be the next mapping
210  // decision.
211  //
212  // This also uses and updates "min_potential_mismatching_part_index_io"
213  // to incrementally search for mismatching parts along the partitions.
214  //
215  // Note(user): there may be false positives, i.e. this method may return true
216  // even if the partitions aren't actually a full match, because it uses
217  // fingerprints to compare part. This should almost never happen.
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;
224 
225  // Subroutine of FindOneSuitablePermutation(), split out for modularity:
226  // Keep only one node of "nodes" per orbit, where the orbits are described
227  // by a subset of "all_permutations": the ones with indices in
228  // "permutation_indices" and that are compatible with "partition".
229  // For each orbit, keep the first node that appears in "nodes".
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);
234 
235  // Temporary objects used by some of the class methods, and owned by the
236  // class to avoid (costly) re-allocation. Their resting states are described
237  // in the side comments; with N = NumNodes().
238  DynamicPermutation tmp_dynamic_permutation_; // Identity(N)
239  mutable std::vector<bool> tmp_node_mask_; // [0..N-1] = false
240  std::vector<int> tmp_degree_; // [0..N-1] = 0.
241  std::vector<int> tmp_stack_; // Empty.
242  std::vector<std::vector<int> > tmp_nodes_with_degree_; // [0..N-1] = [].
243  MergingPartition tmp_partition_; // Reset(N).
244  std::vector<const SparsePermutation*> tmp_compatible_permutations_; // Empty.
245 
246  // Internal statistics, used for performance tuning and debugging.
247  struct Stats : public StatsGroup {
248  Stats()
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",
271  this),
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),
277  map_reelection_time(
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) {}
283 
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;
311 
312  IntegerDistribution search_depth;
313  };
314  mutable Stats stats_;
315 };
316 
317 } // namespace operations_research
318 
319 #endif // OR_TOOLS_ALGORITHMS_FIND_GRAPH_SYMMETRIES_H_
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)