gabow.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2023-2025 James D. Mitchell
//
// 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/>.
//
 
// This file contains the declaration of a class implementing Gabow's algorithm
// for WordGraphs.
 
#ifndef LIBSEMIGROUPS_GABOW_HPP_
#define LIBSEMIGROUPS_GABOW_HPP_
 
#include <cstddef>   // for size_t
#include <iterator>  // for pair
#include <queue>     // for queue
#include <stack>     // for stack
#include <string>    // for string
#include <vector>    // for vector
 
#include "constants.hpp"   // for UNDEFINED, operator!=, Undefined
#include "debug.hpp"       // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"   // for LIBSEMIGROUPS_EXCEPTION
#include "forest.hpp"      // for Forest
#include "ranges.hpp"      // for iterator_range, transform
#include "word-graph.hpp"  // for WordGraph
 
namespace libsemigroups {

  template <typename Node>
  class Gabow {
   public:
    using node_type = Node;

    using label_type = typename WordGraph<node_type>::label_type;

    using size_type = size_t;
 
   private:
    WordGraph<node_type> const*                 _graph;
    mutable std::vector<std::vector<node_type>> _comps;
    mutable bool                                _finished;
    mutable std::vector<size_type>              _id;
    mutable Forest                              _bckwd_forest;
    mutable bool                                _bckwd_forest_defined;
    mutable Forest                              _forwd_forest;
    mutable bool                                _forwd_forest_defined;
 
   public:
    Gabow() = delete;

    Gabow(Gabow const&) = default;

    Gabow(Gabow&&) = default;

    Gabow& operator=(Gabow const&) = default;

    Gabow& operator=(Gabow&&) = default;
 
    ~Gabow();

    explicit Gabow(WordGraph<node_type> const& wg) {
      init(wg);
    }

    Gabow& init(WordGraph<node_type> const& wg);

    [[nodiscard]] size_type id_no_checks(node_type n) const {
      run();
      return _id[n];
    }

    // Not noexcept because throw_if_node_out_of_range isn't
    [[nodiscard]] size_type id(node_type n) const {
      run();
      throw_if_node_out_of_range(n);
      return id_no_checks(n);
    }

    [[nodiscard]] std::vector<std::vector<node_type>> const&
    components() const {
      run();
      return _comps;
    }

    [[nodiscard]] std::vector<node_type> const& component(size_type i) const {
      run();
      throw_if_scc_index_out_of_range(i);
      return _comps[i];
    }

    [[nodiscard]] std::vector<node_type>
    component_no_checks(size_type i) const {
      run();
      return _comps[i];
    }

    [[nodiscard]] size_t number_of_components() const {
      run();
      return _comps.size();
    }

    [[nodiscard]] auto roots() const {
      run();
      return (rx::iterator_range(_comps.cbegin(), _comps.cend())
              | rx::transform([](auto const& comp) { return comp[0]; }));
    }

    // Not noexcept because scc_id isn't
    [[nodiscard]] node_type root_of(node_type n) const {
      return component_of(n)[0];
    }

    [[nodiscard]] node_type root_of_no_checks(node_type n) const {
      return component_of_no_checks(n)[0];
    }

    [[nodiscard]] std::vector<node_type> const&
    component_of(node_type n) const {
      run();
      throw_if_node_out_of_range(n);
      return _comps[_id[n]];
    }

    [[nodiscard]] std::vector<node_type> const&
    component_of_no_checks(node_type n) const {
      run();
      return _comps[_id[n]];
    }

    Forest const& spanning_forest() const;

    Forest const& reverse_spanning_forest() const;

    WordGraph<Node> const& word_graph() const noexcept {
      return *_graph;
    }

    [[nodiscard]] bool has_components() const noexcept {
      return _finished;
    }
 
   private:
    void reset() const noexcept;
    void run() const;
    void throw_if_node_out_of_range(node_type n) const;
    void throw_if_scc_index_out_of_range(size_t i) const;
  };

  template <typename Node>
  Gabow(WordGraph<Node> const&) -> Gabow<Node>;

  template <typename Node>
  std::string to_human_readable_repr(Gabow<Node> const& g);
 
}  // namespace libsemigroups
 
#include "gabow.tpp"
#endif  // LIBSEMIGROUPS_GABOW_HPP_