Frobby 0.9.5
SizeMaxIndepSetAlg.h
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#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
79
80 private:
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
119
124 vector<VarState> _state;
125
130
135
143 vector<size_t> _edges;
144
146 size_t _endPos;
147};
148
149#endif
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
Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph.
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.