OR-Tools  8.2
sparse_permutation.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 #ifndef OR_TOOLS_ALGORITHMS_SPARSE_PERMUTATION_H_
15 #define OR_TOOLS_ALGORITHMS_SPARSE_PERMUTATION_H_
16 
17 #include <string>
18 #include <vector>
19 
20 #include "ortools/base/logging.h"
21 
22 namespace operations_research {
23 
24 // A compact representation for permutations of {0..N-1} that displaces few
25 // elements: it needs only O(K) memory for a permutation that displaces
26 // K elements.
28  public:
29  explicit SparsePermutation(int size) : size_(size) {} // Identity.
30 
31  // TODO(user,user): complete the reader API.
32  int Size() const { return size_; }
33  int NumCycles() const { return cycle_ends_.size(); }
34 
35  // Returns the "support" of this permutation; that is, the set of elements
36  // displaced by it.
37  const std::vector<int>& Support() const { return cycles_; }
38 
39  // The permutation has NumCycles() cycles numbered 0 .. NumCycles()-1.
40  // To iterate over cycle #i of the permutation, do this:
41  // for (const int e : permutation.Cycle(i)) { ...
42  struct Iterator;
43  Iterator Cycle(int i) const;
44 
45  // This is useful for iterating over the pair {element, image}
46  // of a permutation:
47  //
48  // for (int c = 0; c < perm.NumCycles(); ++c) {
49  // int element = LastElementInCycle(c);
50  // for (int image : perm.Cycle(c)) {
51  // // The pair is (element, image).
52  // ...
53  // element = image;
54  // }
55  // }
56  //
57  // TODO(user): Provide a full iterator for this? Note that we have more
58  // information with the loop above. Not sure it is needed though.
59  int LastElementInCycle(int i) const;
60 
61  // To add a cycle to the permutation, repeatedly call AddToCurrentCycle()
62  // with the cycle's orbit, then call CloseCurrentCycle();
63  // This shouldn't be called on trivial cycles (of length 1).
64  void AddToCurrentCycle(int x);
65  void CloseCurrentCycle();
66 
67  // Removes the cycles with given indices from the permutation. This
68  // works in O(K) for a permutation displacing K elements.
69  void RemoveCycles(const std::vector<int>& cycle_indices);
70 
71  // Output all non-identity cycles of the permutation, sorted
72  // lexicographically (each cycle is described starting by its smallest
73  // element; and all cycles are sorted lexicographically against each other).
74  // This isn't efficient; use for debugging only.
75  // Example: "(1 4 3) (5 9) (6 8 7)".
76  std::string DebugString() const;
77 
78  private:
79  const int size_;
80  std::vector<int> cycles_;
81  std::vector<int> cycle_ends_;
82 };
83 
85  DCHECK_GE(x, 0);
86  DCHECK_LT(x, size_);
87  cycles_.push_back(x);
88 }
89 
91  if (cycle_ends_.empty()) {
92  DCHECK_GE(cycles_.size(), 2);
93  } else {
94  DCHECK_GE(cycles_.size(), cycle_ends_.back() + 2);
95  }
96  cycle_ends_.push_back(cycles_.size());
97 }
98 
100  // These typedefs allow this iterator to be used within testing::ElementsAre.
101  typedef int value_type;
102  typedef std::vector<int>::const_iterator const_iterator;
103 
104  Iterator() {}
105  Iterator(const std::vector<int>::const_iterator& b,
106  const std::vector<int>::const_iterator& e)
107  : begin_(b), end_(e) {}
108 
109  std::vector<int>::const_iterator begin() const { return begin_; }
110  std::vector<int>::const_iterator end() const { return end_; }
111  const std::vector<int>::const_iterator begin_;
112  const std::vector<int>::const_iterator end_;
113 
114  int size() const { return end_ - begin_; }
115 };
116 
118  DCHECK_GE(i, 0);
119  DCHECK_LT(i, NumCycles());
120  return Iterator(cycles_.begin() + (i == 0 ? 0 : cycle_ends_[i - 1]),
121  cycles_.begin() + cycle_ends_[i]);
122 }
123 
124 inline int SparsePermutation::LastElementInCycle(int i) const {
125  DCHECK_GE(i, 0);
126  DCHECK_LT(i, cycle_ends_.size());
127  DCHECK_GT(cycle_ends_[i], i == 0 ? 0 : cycle_ends_[i - 1]);
128  return cycles_[cycle_ends_[i] - 1];
129 }
130 
131 } // namespace operations_research
132 
133 #endif // OR_TOOLS_ALGORITHMS_SPARSE_PERMUTATION_H_
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
void RemoveCycles(const std::vector< int > &cycle_indices)
const std::vector< int > & Support() const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< int >::const_iterator end() const
Iterator(const std::vector< int >::const_iterator &b, const std::vector< int >::const_iterator &e)
const std::vector< int >::const_iterator end_
std::vector< int >::const_iterator const_iterator
std::vector< int >::const_iterator begin() const
const std::vector< int >::const_iterator begin_