Frobby 0.9.5
SizeMaxIndepSetAlg.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2009 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "SizeMaxIndepSetAlg.h"
19
20#include "Ideal.h"
21#include "Term.h"
22
24 ASSERT(ideal.isSquareFree());
26
27 if (ideal.getGeneratorCount() == 1 && // for efficiency
28 ideal.containsIdentity()) {
29 _noIndependentSets = true;
30 return;
31 } else
32 _noIndependentSets = false;
33
34 // Improves efficiency by putting related edges together.
35 ideal.sortReverseLex();
36
37 _varCount = ideal.getVarCount();
38
39 // OK since we now know that ideal does have independent sets.
41
42 // Allocate this now so we don't have to ensure this at every step
43 // in the algorithm.
44 _undo.resize(_varCount + 1);
45
46 // Encode the hypergraph of the ideal into _edges.
47 for (size_t term = 0; term < ideal.getGeneratorCount(); ++term) {
48 _edges.push_back(Term::getSizeOfSupport(ideal[term], _varCount));
49 for (size_t var = 0; var < _varCount; ++var) {
50 if (ideal[term][var] != 0) {
51 ASSERT(ideal[term][var] == 1);
52 _edges.push_back(var);
53 }
54 }
55 }
56
57 _endPos = _edges.size();
58
59 // Make state
60 _state.clear();
61 _state.resize(_varCount);
62
63 // Run the algorithm.
64 recurse(0, 0);
65}
66
68 // We can't just let _minExcluded itself be _varCount + 1, as that
69 // may cause an overflow due to non-infinite precision of size_t.
71 return -1;
72 else {
74 return _varCount - _minExcluded;
75 }
76}
77
79 while (pos != _endPos) {
80 size_t nextPos = pos + _edges[pos] + 1;
81 while (true) {
82 ++pos;
83 if (pos == nextPos)
84 return false;
85 if (_state[_edges[pos]] == IsNotInSet)
86 break;
87 }
88 pos = nextPos;
89 }
90 return true;
91}
92
93inline bool SizeMaxIndepSetAlg::couldBeDependence(size_t pos, size_t nextPos, size_t& maybeCount) {
94 maybeCount = 0;
95 for (size_t p = pos + 1; p != nextPos; ++p) {
97 if (varState == IsNotInSet) {
98 // In this case the term cannot make the set dependent.
99 return false;
100 } else if (varState == IsMaybeInSet)
101 ++maybeCount;
102 }
103 return true;
104}
105
106void SizeMaxIndepSetAlg::recurse(size_t pos, size_t excluded) {
107 ASSERT(_undo[excluded].empty());
108 ASSERT(pos <= _endPos);
110
111 // Branch-and-bound criterion.
112 if (excluded >= _minExcluded)
113 return;
114
115 // An optimization made possible by branch-and-bound. If we are only
116 // 1 node from being excluded by the branch-and-bound criterion
117 // above, then every IsMaybeInSet must be a InSet if we are to make
118 // an improvement. So there is no need for further backtracking - it
119 // only matters if the set we are looking at now is independent
120 // where maybe's are treated as yes.
121 if (excluded + 1 == _minExcluded) {
124 return;
125 }
126
127 // Run through the edges only one becomes undecided (and then
128 // consider cases) or we know that the set is independent according
129 // to all edges.
130 while (true) {
131 // The set is independent according to all edges.
132 if (pos == _endPos) {
133 // The set has not been eliminated by brand-and-bound, so there
134 // must be an improvement.
137 break;
138 }
139
140 // The starting point of the encoding of the next term.
141 size_t nextPos = pos + _edges[pos] + 1;
142
143 // Set to the number of maybe's in the support of the term at pos.
144 size_t maybeCount;
146 // This edge cannot make the set dependent, so move on to the
147 // next one.
148 pos = nextPos;
149 continue;
150 }
151
152 if (maybeCount == 0) {
153 // This edge definitely makes the set dependent, so stop looking
154 // at this further.
155 break;
156 }
157
158 // Now we consider the two cases for each undecided variable.
159
160 vector<size_t>& undo = _undo[excluded]; // for convenience
161 for (size_t p = pos + 1; p != nextPos; ++p) {
162 size_t var = _edges[p];
163 VarState& varState = _state[var];
164
165 if (varState != IsMaybeInSet)
166 continue;
167
168 // The case of var definitely not in the set.
171 // recurse may change temporarily change _state, but it restores
172 // it to the way it was before it returns, so consider it as
173 // though this call did not change _state. This is done because
174 // this way is more efficient than copying since often
175 // maybeCount is much less than _varCount.
176
177 // We have considered the other case, so now let var definitely
178 // be in the set, moving on to the next undecided variable, if
179 // any.
180
181 if (maybeCount == 1) {
182 // There are no more undecided vars, so restore _state to the
183 // way it was when we were called and then return to the
184 // caller.
186 while (!undo.empty()) {
187 _state[undo.back()] = IsMaybeInSet;
188 undo.pop_back();
189 }
190
191 // On gcc 3.4.4 on Cygwin (at least), putting break here
192 // instead of return is on the order of 15% faster. So that is
193 // why it says break, and then break again below, even though
194 // a return would be more natural.
195 break;
196 }
197
199 --maybeCount;
200
201 // Store information needed to restore _state to the way it was
202 // before.
203 undo.push_back(var);
204 }
205 break;
206 }
207}
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
bool isSquareFree() const
Definition Ideal.cpp:98
size_t getGeneratorCount() const
Definition Ideal.h:57
bool containsIdentity() const
Definition Ideal.cpp:65
void sortReverseLex()
Definition Ideal.cpp:510
bool isMinimallyGenerated() const
Definition Ideal.cpp:81
size_t getVarCount() const
Definition Ideal.h:56
bool isIndependentIncludingMaybe(size_t pos)
Returns true if _state is an independent set according to every term in _edges from pos and forward.
vector< vector< size_t > > _undo
Stores information on how to restore the state of _state after having done backtracking on one possib...
void run(Ideal &ideal)
Run the algorithm on ideal.
size_t _varCount
The number of variables in the ideal passed to run.
bool _noIndependentSets
Is true if there are no independent sets for the argument to run.
size_t _minExcluded
The minimal number of excluded elements in any independent set found so far.
VarState
Is used for encoding the state of a partially-decided set of nodes/variables in the backtracking algo...
vector< VarState > _state
The current state of the backtracking algorithm.
void recurse(size_t pos, size_t excluded)
The recursive method that implements the algortihm.
vector< size_t > _edges
Sparse encoding of the parameter to run.
bool couldBeDependence(size_t pos, size_t nextPos, size_t &maybeCount)
Returns true if the term encoded in _edges between pos and nextPos makes or might make the set in _st...
mpz_class getMaxIndepSetSize()
Returns the largest size over all independent sets of the hypergraph passed to run.
size_t _endPos
The size of _edges.
size_t getSizeOfSupport() const
Definition Term.h:411
#define ASSERT(X)
Definition stdinc.h:86