Topology.h

// Copyright (C) 2006-2026 Anders Logg, Garth N. Wells and Jørgen S. Dokken
//
// This file is part of DOLFINx (https://www.fenicsproject.org)
//
// SPDX-License-Identifier:    LGPL-3.0-or-later
 
#pragma once
 
#include <array>
#include <basix/mdspan.hpp>
#include <cstddef>
#include <cstdint>
#include <dolfinx/common/MPI.h>
#include <dolfinx/common/types.h>
#include <dolfinx/graph/AdjacencyList.h>
#include <map>
#include <memory>
#include <optional>
#include <ranges>
#include <span>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace dolfinx::common
{
class IndexMap;
}
 
namespace dolfinx::mesh
{
template <typename R>
concept CellRange = std::ranges::input_range<R> and std::ranges::sized_range<R>
                    and std::is_integral_v<
                        std::remove_const_t<std::ranges::range_value_t<R>>>;
 
enum class CellType : std::int8_t;

class Topology
{
public:
  Topology(
      std::vector<CellType> cell_types,
      std::shared_ptr<const common::IndexMap> vertex_map,
      std::vector<std::shared_ptr<const common::IndexMap>> cell_maps,
      std::vector<std::shared_ptr<graph::AdjacencyList<std::int32_t>>> cells,
      const std::optional<std::vector<std::vector<std::int64_t>>>&
          original_cell_index = std::nullopt,
      int num_threads = 1);

  Topology(const Topology& topology) = default;

#ifdef _MSC_VER
  Topology(Topology&& topology) noexcept = default;
#else
  Topology(Topology&& topology) = default;
#endif

  ~Topology() = default;
 
  // Copy assignment (deleted)
  Topology& operator=(const Topology& topology) = delete;

  Topology& operator=(Topology&& topology) = default;

  int dim() const noexcept;

  const std::vector<CellType>& entity_types(int dim) const;

  CellType cell_type() const;

  std::vector<std::shared_ptr<const common::IndexMap>>
  index_maps(int dim) const;

  std::shared_ptr<const common::IndexMap> index_map(int dim) const;

  std::shared_ptr<const graph::AdjacencyList<std::int32_t>>
  connectivity(std::array<int, 2> d0, std::array<int, 2> d1) const;

  std::shared_ptr<const graph::AdjacencyList<std::int32_t>>
  connectivity(int d0, int d1) const;

  const std::vector<std::uint32_t>& get_cell_permutation_info() const;

  void create_facet_orientations();

  std::vector<std::int8_t> facet_orientations() const;

  bool has_facet_orientations() const noexcept;

  const std::vector<std::uint8_t>& get_entity_permutations(int dim) const;

  std::vector<CellType> cell_types() const;

  const std::vector<std::int32_t>& interprocess_facets(int index) const;

  const std::vector<std::int32_t>& interprocess_facets() const;

  bool create_entities(int dim, int num_threads = 1);

  void create_connectivity(int d0, int d1);

  void create_entity_permutations(int dim, int num_threads = 1);

  void create_cell_permutations(int num_threads = 1);

  std::vector<std::vector<std::int64_t>> original_cell_index;

  MPI_Comm comm() const;
 
private:
  // Cell types for entities in Topology, where _entity_types[d][i]
  // is the ith entity type of dimension d
  std::vector<std::vector<CellType>> _entity_types;
 
  // _index_maps[(d, i)] is the index map for the ith entity type of
  // dimension d
  std::map<std::array<int, 2>, std::shared_ptr<const common::IndexMap>>
      _index_maps;
 
  // Connectivity between cell types: _connectivity[(dim0, i0),
  // (dim1, i1)] is the connection from (dim0, i0) -> (dim1, i1),
  // where dim0 and dim1 are topological dimensions and i0 and i1
  // are the indices of cell types (following the order in _entity_types).
  std::map<std::pair<std::array<int, 2>, std::array<int, 2>>,
           std::shared_ptr<graph::AdjacencyList<std::int32_t>>>
      _connectivity;
 
  // Entity permutations by entity dimension, each (local entity, cell)
  // [cell0_0, cell0_1, cell0_2, cell1_0, cell1_1, cell1_2, ...,
  // celln_0, celln_1, celln_2]. Only sub-entities of a cell are stored,
  // so the dimension is at most 2. Unset until computed, which an empty
  // permutation vector (vertices, or a rank with no cells) does not
  // indicate.
  std::array<std::optional<std::vector<std::uint8_t>>, 3> _entity_permutations;
 
  // Cell permutation info. See the documentation for
  // get_cell_permutation_info for documentation of how this is encoded.
  // Unset until computed; empty is valid (no cells).
  std::optional<std::vector<std::uint32_t>> _cell_permutations;
 
  // Whether the facet signs have been computed. Not encoded in
  // _cell_permutations, where unsigned facets read as all 1.
  bool _has_facet_orientations = false;
 
  // List of facets that are on the inter-process boundary for each
  // facet type. _interprocess_facets[i] is the inter-process facets of
  // facet type i.
  std::vector<std::vector<std::int32_t>> _interprocess_facets;
};

namespace impl
{
std::pair<Topology, std::vector<std::int64_t>>
create_topology(MPI_Comm comm, const std::vector<CellType>& cell_types,
                std::vector<std::span<const std::int64_t>> cells,
                std::vector<std::span<const std::int64_t>> original_cell_index,
                std::vector<std::span<const int>> ghost_owners,
                std::span<const std::int64_t> boundary_vertices,
                int num_threads);
} // namespace impl

Topology
create_topology(MPI_Comm comm, const std::vector<CellType>& cell_types,
                std::vector<std::span<const std::int64_t>> cells,
                std::vector<std::span<const std::int64_t>> original_cell_index,
                std::vector<std::span<const int>> ghost_owners,
                std::span<const std::int64_t> boundary_vertices,
                int num_threads);

Topology create_topology(MPI_Comm comm, std::span<const std::int64_t> cells,
                         std::span<const std::int64_t> original_cell_index,
                         std::span<const int> ghost_owners, CellType cell_type,
                         std::span<const std::int64_t> boundary_vertices,
                         int num_threads);

std::tuple<Topology, std::vector<std::int32_t>, std::vector<std::int32_t>>
create_subtopology(const Topology& topology, int dim,
                   std::span<const std::int32_t> entities);

std::vector<std::int32_t>
entities_to_index(const Topology& topology, int dim,
                  std::span<const std::int32_t> entities);

std::vector<std::vector<std::int32_t>>
compute_mixed_cell_pairs(const Topology& topology, mesh::CellType facet_type);

md::mdspan<const std::uint8_t, md::dextents<std::size_t, 2>>
entity_permutations(Topology& topology, int dim, int cell_type_idx);
 
} // namespace dolfinx::mesh