Represents a poset by the matrix of order relations. More...

#include <poset.h>

Public Member Functions
	Poset ()

	Poset (size_t n)

template<typename C >
	Poset (const std::vector< C > &hasse)
	Build Poset from its Hasse diagram. More...

	Poset (size_t n, const std::vector< Link > &)
	Build Poset from arbitrary list of links. More...

	Poset (const Poset &p, tags::DualTag)

	~Poset ()

void	swap (Poset &other)

bool	lesseq (set::Elt i, set::Elt j) const
	The order relation itself. More...

bool	operator== (const Poset &other) const

size_t	size () const

const bitmap::BitMap &	below (set::Elt y) const

bitmap::BitMap	above (set::Elt x) const

set::EltList	maxima (const bitmap::BitMap &) const

set::EltList	minima (const bitmap::BitMap &) const

set::EltList	covered_by (set::Elt y) const

set::EltList	covers_of (set::Elt x) const

graph::OrientedGraph	hasseDiagram () const
	Puts in h the Hasse diagram of the poset. More...

graph::OrientedGraph	hasseDiagram (set::Elt max) const

unsigned long	n_comparable () const
	Number of comparable pairs (including those on the diagonal) More...

void	resize (unsigned long)
	Resizes the poset to size n, adding only the diagonal for the new rows. More...

void	extend (const std::vector< Link > &lks)
	Transforms the poset into the weakest ordering containing the relations it previously contained, plus the relations \|first < second\| for all elements listed in \|lks\|. More...

template<typename C >
void	new_max (C container)

Private Member Functions
void	new_cover (unsigned long x, unsigned long y)
	The basic method to add elementary relations. More...

Private Attributes
std::vector< bitmap::BitMap >	d_below
	Matrix of order relations. More...

Detailed Description

Represents a poset by the matrix of order relations.

It is required that the ordering be compatible with the natural ordering on integers.

Constructor & Destructor Documentation

atlas::poset::Poset::Poset ( )

inline

atlas::poset::Poset::Poset ( size_t n )

explicit

Synopsis: constructs the discrete poset of size n.

template<typename C >

atlas::poset::Poset::Poset ( const std::vector< C > & hasse )

explicit

Build Poset from its Hasse diagram.

Constructs a Poset from its Hasse diagram.

Precondition: it is assumed that for each |x|, |hasse(x)| is a container |C| listing elements covered by |x|, which elements must be numbers $<x$.

As a consequence, the closure at |x| can be computed once |hasse(x)| is inspected, for increaing |x|.

atlas::poset::Poset::Poset	(	size_t	n,
		const std::vector< Link > &	lk
	)

Build Poset from arbitrary list of links.

atlas::poset::Poset::Poset	(	const Poset &	p,
		tags::DualTag
	)

atlas::poset::Poset::~Poset ( )

inline

Member Function Documentation

bitmap::BitMap atlas::poset::Poset::above ( set::Elt x ) const

const bitmap::BitMap& atlas::poset::Poset::below ( set::Elt y ) const

inline

set::EltList atlas::poset::Poset::covered_by ( set::Elt y ) const

inline

set::EltList atlas::poset::Poset::covers_of ( set::Elt x ) const

void atlas::poset::Poset::extend ( const std::vector< Link > & lks )

inline

Transforms the poset into the weakest ordering containing the relations it previously contained, plus the relations |first < second| for all elements listed in |lks|.

Precondition: |lks| is sorted in increasing lexicographical order, and is compatible with relations already present in the poset. More precisely the following (weaker, given the compatibility of the order relation with integral ordering) condition is assumed: all occurrences of a value |i| as first (smaller) member in a Link must follow all occurrences of |i| as second (larger) member in another Link, and no element smaller in a pre-existing relation should be the larger element of a link. This guarantees that the calls of |new_cover| generate the transitive closure.

graph::OrientedGraph atlas::poset::Poset::hasseDiagram ( ) const

Puts in h the Hasse diagram of the poset.

Explanation: the Hasse diagram is the oriented graph whose vertices are the elements of the poset, with an edge from each vertex to each vertex immediately below it.

graph::OrientedGraph atlas::poset::Poset::hasseDiagram ( set::Elt max ) const

bool atlas::poset::Poset::lesseq	(	set::Elt	i,
		set::Elt	j
	)		const

inline

The order relation itself.

set::EltList atlas::poset::Poset::maxima ( const bitmap::BitMap & b ) const

Synopsis: writes in a the elements in b that are maximal for the induced order.

Algorithm: the largest element x in b (if any) is maximal; add that to a, remove from b the intersection with the closure of x, and iterate.

set::EltList atlas::poset::Poset::minima ( const bitmap::BitMap & b ) const

unsigned long atlas::poset::Poset::n_comparable ( ) const

Number of comparable pairs (including those on the diagonal)

void atlas::poset::Poset::new_cover	(	unsigned long	x,
		unsigned long	y
	)

inlineprivate

The basic method to add elementary relations.

template<typename C >

void atlas::poset::Poset::new_max ( C container )

inline

bool atlas::poset::Poset::operator== ( const Poset & other ) const

void atlas::poset::Poset::resize ( unsigned long n )

Resizes the poset to size n, adding only the diagonal for the new rows.

size_t atlas::poset::Poset::size ( ) const

inline

void atlas::poset::Poset::swap ( Poset & other )

inline

Member Data Documentation

std::vector<bitmap::BitMap> atlas::poset::Poset::d_below

private

Matrix of order relations.

Bit i of d_below[j] is set if and only if |i| is less than |j| in the poset. In other words, viewed as a set of integers, d_below[j]union{j} represents the downwards closure in the poset of the singleton {j}.

By the assumption on the poset structure, the capacity of |d_below[j]| need only be |j|.

The documentation for this class was generated from the following files:

/home/ran/atlas_project/latest_branch_07182016/sources/utilities/poset.h
/home/ran/atlas_project/latest_branch_07182016/sources/utilities/poset.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation