Frobby 0.9.5
IndependenceSplitter.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 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"
19
20#include "Ideal.h"
21#include "Term.h"
22#include "Projection.h"
23
25 projection.reset(_partition, _bigSet);
26}
27
29 projection.reset(_partition, 1 - _bigSet);
30}
31
34
35 Ideal::const_iterator stop = slice.getIdeal().end();
36 for (Ideal::const_iterator it = slice.getIdeal().begin();
37 it != stop; ++it) {
38 size_t first = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
39 if (first == slice.getVarCount())
40 return false;
41 _partition.addToSet(first);
42 for (size_t var = first + 1; var < slice.getVarCount(); ++var)
43 if ((*it)[var] > 0)
44 if (_partition.join(first, var))
45 if (_partition.getSetCount() == 1)
46 return false;
47 }
48
49 stop = slice.getSubtract().end();
50 for (Ideal::const_iterator it = slice.getSubtract().begin();
51 it != stop; ++it) {
52 size_t first = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
53 for (size_t var = first + 1; var < slice.getVarCount(); ++var)
54 if ((*it)[var] > 0)
55 _partition.join(first, var);
56 }
57
58 size_t childCount = _partition.getSetCount();
59
60 if (childCount == 1)
61 return false;
62
63 size_t hasTwo = 0;
64 for (size_t i = 0; i < childCount; ++i)
65 if (_partition.getSetSize(i) >= 2)
66 ++hasTwo;
67 if (hasTwo < 2)
68 return false;
69
70 if (_partition.getSetCount() > 2) {
71 size_t maxSet = 0;
72 for (size_t set = 1; set < _partition.getSize(); ++set)
75 maxSet = _partition.getRoot(set);
76
77 size_t nonMaxSet = 0;
78 for (size_t set = 0; set < _partition.getSize(); ++set)
79 if (_partition.getRoot(maxSet) != _partition.getRoot(set))
80 nonMaxSet = set;
81 ASSERT(_partition.getRoot(maxSet) != _partition.getRoot(nonMaxSet));
82
83 for (size_t set = 0; set < _partition.getSize(); ++set)
84 if (_partition.getRoot(set) != _partition.getRoot(maxSet))
85 _partition.join(set, nonMaxSet);
86 }
88
90 _bigSet = 0;
91 else
92 _bigSet = 1;
93
94 return true;
95}
96
98 return _partition.getSize();
99}
const_iterator end() const
Definition Ideal.h:49
const_iterator begin() const
Definition Ideal.h:48
Cont::const_iterator const_iterator
Definition Ideal.h:43
void getRestProjection(Projection &projection) const
void getBigProjection(Projection &projection) const
bool analyze(const Slice &slice)
size_t getSetCount() const
Definition Partition.cpp:72
size_t getSetSize(size_t set) const
Definition Partition.cpp:88
size_t getSizeOfClassOf(size_t i) const
Definition Partition.cpp:84
bool join(size_t i, size_t j)
Definition Partition.cpp:51
void reset(size_t size)
Definition Partition.cpp:39
size_t getSize() const
void addToSet(size_t i)
size_t getRoot(size_t i) const
void reset(const Partition &partition, int set)
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
const Ideal & getIdeal() const
Returns for a slice .
Definition Slice.h:104
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition Slice.h:96
Ideal & getSubtract()
Returns for a slice .
Definition Slice.h:107
size_t getFirstNonZeroExponent() const
Definition Term.h:354
This header file includes common definitions and is included as the first line of code in every imple...
#define ASSERT(X)
Definition stdinc.h:86