OR-Tools  8.2
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"
36#include "ortools/util/stats.h"
38
39namespace operations_research {
40
41class 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_;
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)
StatsGroup(const std::string &name)
Definition: stats.h:138
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...