22 const std::vector<std::unique_ptr<SparsePermutation>>& generators) {
25 std::vector<std::vector<int>> num_cycles_to_2cyclers;
26 for (
int g = 0; g < generators.size(); ++g) {
27 const std::unique_ptr<SparsePermutation>& perm = generators[g];
28 bool contain_only_2cycles =
true;
29 const int num_cycles = perm->NumCycles();
30 for (
int i = 0; i < num_cycles; ++i) {
31 if (perm->Cycle(i).size() != 2) {
32 contain_only_2cycles =
false;
36 if (!contain_only_2cycles)
continue;
37 if (num_cycles >= num_cycles_to_2cyclers.size()) {
38 num_cycles_to_2cyclers.resize(num_cycles + 1);
40 num_cycles_to_2cyclers[num_cycles].push_back(g);
49 for (
int i = 0; i < num_cycles_to_2cyclers.size(); ++i) {
50 if (num_cycles_to_2cyclers[i].size() > 1) {
51 const int num_perms = num_cycles_to_2cyclers[i].size() + 1;
52 VLOG(1) <<
"Potential orbitope: " << i <<
" x " << num_perms;
54 if (score > best_score) {
61 std::vector<std::vector<int>> orbitope;
62 if (best == -1)
return orbitope;
65 std::vector<bool> in_matrix;
68 orbitope.resize(best);
69 for (
const int g : num_cycles_to_2cyclers[best]) {
71 if (orbitope[0].empty()) {
72 const std::unique_ptr<SparsePermutation>& perm = generators[g];
73 const int num_cycles = perm->NumCycles();
74 for (
int i = 0; i < num_cycles; ++i) {
75 for (
const int x : perm->Cycle(i)) {
76 orbitope[i].push_back(x);
77 if (x >= in_matrix.size()) in_matrix.resize(x + 1,
false);
92 std::vector<int> grow;
93 int matching_column_index = -1;
94 const std::unique_ptr<SparsePermutation>& perm = generators[g];
95 const int num_cycles = perm->NumCycles();
96 for (
int i = 0; i < num_cycles; ++i) {
99 for (
const int x : perm->Cycle(i)) tmp.push_back(x);
100 const int a = tmp[0];
101 const int b = tmp[1];
105 int num_matches_a = 0;
106 int num_matches_b = 0;
107 int last_match_index = -1;
108 for (
int j = 0; j < orbitope[i].size(); ++j) {
109 if (orbitope[i][j] ==
a) {
111 last_match_index = j;
112 }
else if (orbitope[i][j] ==
b) {
114 last_match_index = j;
117 if (last_match_index == -1)
break;
118 if (matching_column_index == -1) {
119 matching_column_index = last_match_index;
121 if (matching_column_index != last_match_index)
break;
122 if (num_matches_a == 0 && num_matches_b == 1) {
123 if (
a >= in_matrix.size() || !in_matrix[
a]) grow.push_back(
a);
124 }
else if (num_matches_a == 1 && num_matches_b == 0) {
125 if (
b >= in_matrix.size() || !in_matrix[
b]) grow.push_back(
b);
132 if (grow.size() == num_cycles) {
133 for (
int i = 0; i < orbitope.size(); ++i) {
134 orbitope[i].push_back(grow[i]);
135 if (grow[i] >= in_matrix.size()) in_matrix.resize(grow[i] + 1,
false);
136 in_matrix[grow[i]] =
true;
145 int n,
const std::vector<std::unique_ptr<SparsePermutation>>& generators) {
148 for (
const std::unique_ptr<SparsePermutation>& perm : generators) {
149 const int num_cycles = perm->NumCycles();
150 for (
int i = 0; i < num_cycles; ++i) {
153 bool is_first =
true;
154 for (
const int x : perm->Cycle(i)) {
166 std::vector<int> orbits(n, -1);
167 for (
int i = 0; i < n; ++i) {
170 if (orbits[root] == -1) orbits[root] = num_parts++;
171 orbits[i] = orbits[root];
177 int n,
const std::vector<std::vector<int>>& orbitope) {
178 std::vector<int> orbits(n, -1);
179 for (
int i = 0; i < orbitope.size(); ++i) {
180 for (
int j = 0; j < orbitope[i].size(); ++j) {
181 CHECK_EQ(orbits[orbitope[i][j]], -1);
182 orbits[orbitope[i][j]] = i;
#define CHECK_EQ(val1, val2)
#define VLOG(verboselevel)
int NumNodesInSamePartAs(int node)
void Reset(int num_nodes)
int MergePartsOf(int node1, int node2)
int GetRootAndCompressPath(int node)
std::vector< int > GetOrbitopeOrbits(int n, const std::vector< std::vector< int > > &orbitope)
std::vector< int > GetOrbits(int n, const std::vector< std::unique_ptr< SparsePermutation > > &generators)
std::vector< std::vector< int > > BasicOrbitopeExtraction(const std::vector< std::unique_ptr< SparsePermutation > > &generators)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...