IndependenceSplitter.cpp
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2007 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/.
*/
#include "stdinc.h"
#include "IndependenceSplitter.h"
#include "Ideal.h"
#include "Term.h"
#include "Projection.h"
void IndependenceSplitter::getBigProjection(Projection& projection) const {
projection.reset(_partition, _bigSet);
}
void IndependenceSplitter::getRestProjection(Projection& projection) const {
projection.reset(_partition, 1 - _bigSet);
}
bool IndependenceSplitter::analyze(const Slice& slice) {
_partition.reset(slice.getVarCount());
Ideal::const_iterator stop = slice.getIdeal().end();
for (Ideal::const_iterator it = slice.getIdeal().begin();
it != stop; ++it) {
size_t first = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
if (first == slice.getVarCount())
return false;
_partition.addToSet(first);
for (size_t var = first + 1; var < slice.getVarCount(); ++var)
if ((*it)[var] > 0)
if (_partition.join(first, var))
if (_partition.getSetCount() == 1)
return false;
}
stop = slice.getSubtract().end();
for (Ideal::const_iterator it = slice.getSubtract().begin();
it != stop; ++it) {
size_t first = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
for (size_t var = first + 1; var < slice.getVarCount(); ++var)
if ((*it)[var] > 0)
_partition.join(first, var);
}
size_t childCount = _partition.getSetCount();
if (childCount == 1)
return false;
size_t hasTwo = 0;
for (size_t i = 0; i < childCount; ++i)
if (_partition.getSetSize(i) >= 2)
++hasTwo;
if (hasTwo < 2)
return false;
if (_partition.getSetCount() > 2) {
size_t maxSet = 0;
for (size_t set = 1; set < _partition.getSize(); ++set)
if (_partition.getSizeOfClassOf(set) >
_partition.getSizeOfClassOf(maxSet))
maxSet = _partition.getRoot(set);
size_t nonMaxSet = 0;
for (size_t set = 0; set < _partition.getSize(); ++set)
if (_partition.getRoot(maxSet) != _partition.getRoot(set))
nonMaxSet = set;
ASSERT(_partition.getRoot(maxSet) != _partition.getRoot(nonMaxSet));
for (size_t set = 0; set < _partition.getSize(); ++set)
if (_partition.getRoot(set) != _partition.getRoot(maxSet))
_partition.join(set, nonMaxSet);
}
ASSERT(_partition.getSetCount() == 2);
if (_partition.getSetSize(0) > _partition.getSetSize(1))
_bigSet = 0;
else
_bigSet = 1;
return true;
}
size_t IndependenceSplitter::getVarCount() const {
return _partition.getSize();
}
Ideal.h
IndependenceSplitter.h
Projection.h
Term.h
Ideal::const_iterator
Cont::const_iterator const_iterator
Definition Ideal.h:43
Ideal::end
const_iterator end() const
Definition Ideal.h:49
Ideal::begin
const_iterator begin() const
Definition Ideal.h:48
IndependenceSplitter::_bigSet
size_t _bigSet
Definition IndependenceSplitter.h:55
IndependenceSplitter::getRestProjection
void getRestProjection(Projection &projection) const
Definition IndependenceSplitter.cpp:28
IndependenceSplitter::getVarCount
size_t getVarCount() const
Definition IndependenceSplitter.cpp:97
IndependenceSplitter::_partition
Partition _partition
Definition IndependenceSplitter.h:49
IndependenceSplitter::getBigProjection
void getBigProjection(Projection &projection) const
Definition IndependenceSplitter.cpp:24
IndependenceSplitter::analyze
bool analyze(const Slice &slice)
Definition IndependenceSplitter.cpp:32
Projection
Definition Projection.h:29
Projection::reset
void reset(const Partition &partition, int set)
Definition Projection.cpp:28
Slice
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
Slice::getIdeal
const Ideal & getIdeal() const
Returns for a slice .
Definition Slice.h:104
Slice::getVarCount
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition Slice.h:96
Slice::getSubtract
Ideal & getSubtract()
Returns for a slice .
Definition Slice.h:107
Term::getFirstNonZeroExponent
size_t getFirstNonZeroExponent() const
Definition Term.h:354
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
ASSERT
#define ASSERT(X)
Definition stdinc.h:86