Frobby 0.10.0
Loading...
Searching...
No Matches
SizeMaxIndepSetAlg.h
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#ifndef SIZE_MAX_INDEP_SET_ALG
18#define SIZE_MAX_INDEP_SET_ALG
19
20#include "Ideal.h"
21
62 public:
69 void run(Ideal& ideal);
70
78 mpz_class getMaxIndepSetSize();
79
80 private:
84 enum VarState {
85 IsMaybeInSet = 0,
86 IsNotInSet = 1,
87 IsInSet = 2
88 };
89
93 bool isIndependentIncludingMaybe(size_t pos);
94
100 bool couldBeDependence(size_t pos, size_t nextPos, size_t& maybeCount);
101
109 void recurse(size_t pos, size_t excluded);
110
114 size_t _varCount;
115
118 size_t _minExcluded;
119
124 vector<VarState> _state;
125
129 vector<vector<size_t> > _undo;
130
134 bool _noIndependentSets;
135
143 vector<size_t> _edges;
144
146 size_t _endPos;
147};
148
149#endif
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Definition SizeMaxIndepSetAlg.h:61
void run(Ideal &ideal)
Definition SizeMaxIndepSetAlg.cpp:23
mpz_class getMaxIndepSetSize()
Definition SizeMaxIndepSetAlg.cpp:67