Quelle obvinf.cpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2020 James D. Mitchell
// Copyright (C) 2020 Reinis Cirpons
//
// 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 3 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 "libsemigroups/obvinf.hpp"

#include <algorithm>  // for all_of
#include <cstddef>    // for size_t
#include <string>     // for string
#include <utility>    // for pair
#include <vector>     // for vector

// for LIBSEMIGROUPS_EIGEN_ENABLED
#include "libsemigroups/config.hpp"

#include "libsemigroups/constants.hpp"  // for UNDEFINED
#include "libsemigroups/debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "libsemigroups/word.hpp"       // for StringToWord

#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
#include <Eigen/QR>  // for dimensionOfKernel
#endif

namespace libsemigroups {
  namespace detail {

    using const_iterator_word_type =
        typename std::vector<word_type>::const_iterator;
    using const_iterator_pair_string = typename std::vector<
        std::pair<std::string, std::string>>::const_iterator;

    IsObviouslyInfinite::IsObviouslyInfinite(size_t n)
        : _empty_word(false),
          _letter_components(n),
          _nr_gens(n),
          _nr_relations(0),
          _preserve_length(true),
          _preserve(n, false),
          _seen(n, false),
          _unique(n, false),
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
          _matrix(0, n) {
    }
#else
          _matrix(n, 0) {
    }
#endif

    IsObviouslyInfinite::~IsObviouslyInfinite() = default;

    void IsObviouslyInfinite::add_rules(const_iterator_word_type first,
                                        const_iterator_word_type last) {
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
      auto matrix_start = _matrix.rows();
      _matrix.conservativeResize(matrix_start + (last - first) / 2,
                                 Eigen::NoChange);
      _matrix.block(matrix_start, 0, (last - first) / 2, _matrix.cols())
          .setZero();
#else
      auto matrix_start = 0;
      std::fill(_matrix.begin(), _matrix.end(), 0);
#endif
      for (auto it = first; it < last; it += 2) {
        private_add_rule(matrix_start + (it - first) / 2, *it, *(it + 1));
      }
      _nr_letter_components = _letter_components.number_of_blocks();
    }

    void IsObviouslyInfinite::add_rules(std::string const&         lphbt,
                                        const_iterator_pair_string first,
                                        const_iterator_pair_string last) {
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
      auto matrix_start = _matrix.rows();
      _matrix.conservativeResize(matrix_start + (last - first),
                                 Eigen::NoChange);
      _matrix.block(matrix_start, 0, (last - first), _matrix.cols()).setZero();
#else
      auto matrix_start = 0;
      std::fill(_matrix.begin(), _matrix.end(), 0);
#endif

      StringToWord stw(lphbt);
      word_type    lhs;
      word_type    rhs;
      for (auto it = first; it < last; ++it) {
        stw(it->first, lhs);   // lhs changed in-place
        stw(it->second, rhs);  // rhs changed in-place
        private_add_rule(matrix_start + (it - first), lhs, rhs);
      }
      _nr_letter_components = _letter_components.number_of_blocks();
    }

    bool IsObviouslyInfinite::result() const {
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
      LIBSEMIGROUPS_ASSERT(_matrix.rows() >= 0);
      LIBSEMIGROUPS_ASSERT(_matrix.cast<float>().colPivHouseholderQr().rank()
                           >= 0);
#endif
      return (_preserve_length
              || (!_empty_word
                  && !std::all_of(_unique.begin(),
                                  _unique.end(),
                                  [](bool v) -> bool { return v; }))
              || !std::all_of(_preserve.begin(),
                              _preserve.end(),
                              [](bool v) -> bool { return v; })
              || (!_empty_word && _nr_letter_components > 1)
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
              || _nr_relations < _nr_gens
              || size_t(_matrix.cast<float>().colPivHouseholderQr().rank())
                     != _nr_gens);
#else
               || _nr_relations < _nr_gens);
#endif
    }

    void IsObviouslyInfinite::private_add_rule(size_t           row_index,
                                               word_type const& u,
                                               word_type const& v) {
      _nr_relations++;
      if (u.empty() || v.empty()) {
        _empty_word = true;
      }
      std::fill(_seen.begin(), _seen.end(), false);
      plus_letters_in_word(row_index, u);
      if (!_empty_word
          && std::all_of(u.cbegin() + 1, u.cend(), [&u](letter_type i) -> bool {
               return i == u[0];
             })) {
        _unique[u[0]] = true;
      }
      minus_letters_in_word(row_index, v);
      if (!_empty_word && !v.empty()
          && std::all_of(v.cbegin() + 1, v.cend(), [&v](letter_type i) -> bool {
               return i == v[0];
             })) {
        _unique[v[0]] = true;
      }
      for (size_t x = 0; x < _nr_gens; x++) {
        if (matrix(row_index, x) != 0) {
          _preserve[x] = true;
        }
      }
      if (_preserve_length && !matrix_row_sums_to_0(row_index)) {
        _preserve_length = false;
      }
      size_t last_seen = UNDEFINED;
      for (size_t x = 0; x < _nr_gens; ++x) {
        if (_seen[x]) {
          if (last_seen != UNDEFINED) {
            _letter_components.unite(last_seen, x);
          }
          last_seen = x;
        }
      }
    }
  }  // namespace detail
}  // namespace libsemigroups

quality92%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.