Prerequisits

#include <HasseDiagram.h>
using namespace polymake; 

Introduction

template <typename VertexSet=Set<int>, typename EdgeAttr=nothing> class HasseDiagram : public Graph<VertexSet, EdgeAttr, directed>

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. An edge (n1, n2) exists if and only if the face n1 is a subset of n2, and dim(n1) = dim(n2)-1.

Node attributes usually contain the sets of vertices comprising the corresponding faces. For example, the bottom node dim==-1 has an empty set, and the nodes of dim==0 have single-element sets. The nodes of dim==0 always appear in the same order as the vertices of the polyhedron (or complex), as well as the nodes of codim==1 always appear in the same order as the facets of the polyhedron.

Edge attributes has no special meaning for the lattice, they can be used to store arbitrary data.

Notes

  1. 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.
  2. 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.

Construction

HasseDiagram();
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.

int add_node (const GenericSet& vertex_set);
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.

int add_node (const GenericSet& vertex_set, const GenericSet& facet_set);
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.
template <typename Iterator1, typename Iterator2> void add_nodes (int n, Iterator1 vertex_sets, Iterator2 facet_sets);
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.
void clear();
Make the graph empty.

Data access

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.

The edge method can be safely used to access the edge attributes, provided that it does not create new edges which would be inconsistent with the face lattice structrure (it is not checked by the class itself!)

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.
sequence nodes_of_dim (int d) const; sequence nodes_of_dim (int d1, int d2) const;
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.

Input/output

As a special case of Graph, HasseDiagram inherits the masquerading functions which allow to read and store graphs with node attributes different from VertexSet.