A special kind of a directed graph, a so called layered graph. This means, its node set can be partitioned
in non-intersecting subsets (layers) numbered from -1 to d so that all edges connect some node from layer k
with another node from layer k+1.
In Polymake Template Library this class is used for representantion of face lattices of polyhedra, or, more commonly, of complexes.
The bottommost (-1) and topmost (d) layers contain exactly one node each, corresponding to the empty face and to the whole
polyhedron. The nodes from the layer k correspond to the k-dimensional faces of the polyhedron. The node attribute
is the set of vertices comprising the face. An edge (n1, n2) exists if and only if the face n1 is a subset
of n2, and dim(n1) = dim(n2)-1.
Notes
There is nothing in the implementation of the class itself that guarantees for a proper face lattice
in the above sense. It is still a plain directed graph with associated node dimension dictionary.
This class is suitable for successive building and traversing the face lattice. But it has no facilities for a random
search for a given face. If a sequential search among all its nodes is too expensive for you, you should introduce some
auxiliary dictionary structure for the facets, such as std::hash_map or FaceMap.
Create an empty graph. It can be populated with nodes and edges either directly, using the inherited
Graph interface, or via one of the filler classes:
class HasseDiagram::_filler;
HasseDiagram::_filler filler (HasseDiagram&);
A little proxy class encapsulating the graph modification operations. Creating a filler object
automatically makes the graph empty. The first node to be added should be either the "empty face" or the
"full polyhedron" node.
There can be always only one filler object active for a given HasseDiagram object.
If copied, the new copy become the active filler, and the old one become void. This behavior is similar to
std::auto_ptr.
Create a new node (face) in the current layer, return its index. vertex_set should list the
vertices comprising the face, its copy is stored as the attribute of the created node.
template <typename Iterator>
void add_nodes (int n, Iterator vertex_sets);
Create n new nodes (faces) in the current layer, return the index of the first of them.
vertex_sets should be an input iterator supplying the sets of vertices contained in the faces.
They are stored as the attributes of the created nodes.
void add_edge (int n_from, int n_to);
Create an edge between the given nodes. One of the nodes should belong to the current layer
and another one to the previous layer.
void increase_dim();
Finish the filling of the current layer, switch to the next one, one dimension higher or lower.
class HasseDiagram::_flex_filler
: public HasseDiagram::_filler
HasseDiagram::_flex_filler filler (HasseDiagram&, bool primal);
A more elaborated variant of a filler. The graph building direction is controlled dynamically,
by the parameter primal.
If it is true, the graph is build from "full polyhedron" towards "empty face", the false
case chooses the opposite direction.
Create a new node (face) in the current layer, return its index. Store vertex_set in the primal case
or facet_set in the dual case as the node attribute.
Create n new nodes (faces) in the current layer, return the index of the first of them.
vertex_sets and facet_sets should be input iterators supplying the sets of vertices contained in the new faces,
and the sets of facets containing the new facets, correspondingly.
The attributes of the new nodes are taken from vertex_sets in the primal case and from facet_sets in the
dual case.
void add_edge (int n_from, int n_to);
Create an edge between the given nodes. One of the nodes should belong to the current layer
and another one to the previous layer. In the dual case, the actual edge direction is reversed.
void next_layer();
Finish the creation of the current layer. The nodes added after this call will belong to the next layer.
Although the HasseDiagram class inherits all modification methods from the
Graph class, using them will almost always
destroy the face lattice property, as the new nodes cannot be inserted in the proper layer any more.
The only exception are delete_node and delete_nodes methods.
They are overwritten by HasseDiagram, so that they preserve the correct layer description
after node removal. The topmost and bottommost nodes may not be deleted.
int dim() const;
Tell the (combinatorial) dimension of the polyhedron. If the HasseDiagram object represents
a (simplicial) complex, you should subtract 1 from the return value!
int dim_of_node(int n) const;
Tell the dimension of the face corresponding to the given node. This operation takes O(log(dim())) time.
int top_node() const;
int bottom_node() const;
Return the index of the "empty face" and the "whole polyhedron" node correspondingly.
Return the indices of the nodes corresponding to the faces of dimension @ d,
or from dimension range [d1,d2]. Since the nodes of one layer lie in a contiguous range,
and the layer dimensions increase or decrease monotonically, the resulting set can always be represented
as a sequence. Validity checking of dimension arguments can be activated.
If d, d1, or d2 are negative, they are treated as co-dimensions. This way, d==-1
corresponds to the facets of the polyhedron, and not to the "empty face" node! The index of the latter can be obtained
only via bottom_node method.
As a special case of Graph, HasseDiagram inherits the
masquerading functions which allow to read and store graphs
with node attributes different from VertexSet.