num::concepts::incidence_structure

Defined in header <structures/concepts.hpp>

template <typename G, typename Index = num::idx>
concept incidence_structure = requires(const G g, Index u) {
  { g.n_vertices() } -> std::same_as<Index>;
  { g.n_edges() } -> std::same_as<Index>;
  { g.degree(u) } -> std::same_as<Index>;
  { g.neighbors(u) };
};

Finite incidence structure \(G = (V, E)\) with \(E \subseteq V \times V\).

neighbors(u) enumerates \(\{v : (u,v) \in E\}\) and degree(u) is that set's cardinality. The two must agree, and for an undirected graph the handshake lemma \(\sum_u \deg(u) = 2|E|\) must hold.