SizeMaxIndepSetAlg.h
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2009 Bjarke Hammersholt Roune (www.broune.com)
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
*/
#ifndef SIZE_MAX_INDEP_SET_ALG
#define SIZE_MAX_INDEP_SET_ALG
#include "Ideal.h"
class SizeMaxIndepSetAlg {
public:
void run(Ideal& ideal);
mpz_class getMaxIndepSetSize();
private:
enum VarState {
IsMaybeInSet = 0,
IsNotInSet = 1,
IsInSet = 2
};
bool isIndependentIncludingMaybe(size_t pos);
bool couldBeDependence(size_t pos, size_t nextPos, size_t& maybeCount);
void recurse(size_t pos, size_t excluded);
size_t _varCount;
size_t _minExcluded;
vector<VarState> _state;
vector<vector<size_t> > _undo;
bool _noIndependentSets;
vector<size_t> _edges;
size_t _endPos;
};
#endif
Ideal.h
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
SizeMaxIndepSetAlg
Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph.
Definition SizeMaxIndepSetAlg.h:61
SizeMaxIndepSetAlg::isIndependentIncludingMaybe
bool isIndependentIncludingMaybe(size_t pos)
Returns true if _state is an independent set according to every term in _edges from pos and forward.
Definition SizeMaxIndepSetAlg.cpp:78
SizeMaxIndepSetAlg::_undo
vector< vector< size_t > > _undo
Stores information on how to restore the state of _state after having done backtracking on one possib...
Definition SizeMaxIndepSetAlg.h:129
SizeMaxIndepSetAlg::run
void run(Ideal &ideal)
Run the algorithm on ideal.
Definition SizeMaxIndepSetAlg.cpp:23
SizeMaxIndepSetAlg::_varCount
size_t _varCount
The number of variables in the ideal passed to run.
Definition SizeMaxIndepSetAlg.h:114
SizeMaxIndepSetAlg::_noIndependentSets
bool _noIndependentSets
Is true if there are no independent sets for the argument to run.
Definition SizeMaxIndepSetAlg.h:134
SizeMaxIndepSetAlg::_minExcluded
size_t _minExcluded
The minimal number of excluded elements in any independent set found so far.
Definition SizeMaxIndepSetAlg.h:118
SizeMaxIndepSetAlg::VarState
VarState
Is used for encoding the state of a partially-decided set of nodes/variables in the backtracking algo...
Definition SizeMaxIndepSetAlg.h:84
SizeMaxIndepSetAlg::IsInSet
@ IsInSet
Definition SizeMaxIndepSetAlg.h:87
SizeMaxIndepSetAlg::IsMaybeInSet
@ IsMaybeInSet
Definition SizeMaxIndepSetAlg.h:85
SizeMaxIndepSetAlg::IsNotInSet
@ IsNotInSet
Definition SizeMaxIndepSetAlg.h:86
SizeMaxIndepSetAlg::_state
vector< VarState > _state
The current state of the backtracking algorithm.
Definition SizeMaxIndepSetAlg.h:124
SizeMaxIndepSetAlg::recurse
void recurse(size_t pos, size_t excluded)
The recursive method that implements the algortihm.
Definition SizeMaxIndepSetAlg.cpp:106
SizeMaxIndepSetAlg::_edges
vector< size_t > _edges
Sparse encoding of the parameter to run.
Definition SizeMaxIndepSetAlg.h:143
SizeMaxIndepSetAlg::couldBeDependence
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...
Definition SizeMaxIndepSetAlg.cpp:93
SizeMaxIndepSetAlg::getMaxIndepSetSize
mpz_class getMaxIndepSetSize()
Returns the largest size over all independent sets of the hypergraph passed to run.
Definition SizeMaxIndepSetAlg.cpp:67
SizeMaxIndepSetAlg::_endPos
size_t _endPos
The size of _edges.
Definition SizeMaxIndepSetAlg.h:146