An incidence structure encodes a binary function (x,y) ⇒ boolean with discrete, limited value
sets of both operands x and y. Examples are vertex-facet incidence relation in a polyhedron,
simplicial complex, etc. In Polymake Template Library, the objects of the incidence relation (vertices, facets, etc.)
are always enumerated, so that the data structures have to deal with closed intervals of non-negative integers:
[0..n-1].
An incidence structure can also be interpreted as a sparse matrix with boolean values,
where an element (i,j) is true iff the ith element of the first set
is incident to the jth element of the second set. The implementation of incidence matrices
allows seamless switching back and forth between these views.
the simplest form of encoding of an incident structure. Obviously, you can take std::list or
std::vector instead of Array, or substitute Set<int> by
Bitset, if needed. The only disadvantage is the asymmetry between the
relation operands: you can't query for all first-operand objects incident to a given second-operand object,
without performing an exhaustive search over the whole structure.
two-dimensional grid of sets. The rows and columns (encoding the first and second operands respectively)
have identical functionality, allowing for efficient iteration, search, insertion, and deletion of elements.
The main disadvantage are rather high reallocation costs in the case of dynamical growth of an operand range
(they are linear in the number of rows/columns.)
two-dimensional grid of sets, optimized for queries of the following kind: "For a given element set, find all
incidence sets that are included in or including it." These queries, however, are possible only for the rows
(first-operand incidence sets.) The columns have restricted functionality.