DilworthDecomposition: dilworthdecomposition.cpp File Reference


Functions
template<class T>
set< T >	list_to_set (const list< T > l)
	This function returns the set of members in a list. I.e, it converts an ordered list to a set.
int	MAXIMAL_ANTI_CHAIN (const graph &G, set< node > &MA)
	This function computes a maximal antichain chain of a DAG (order).
int	MINIMAL_CHAIN (const graph &G, node_array< int > &chain)
	This function computes a minimal chain decomposition of a DAG (an order).
template<class T>
list< T >	set_to_list (const set< T > l)
	This function returns the an ordered from a set.

Function Documentation

template<class T>

template< class T > set< T > list_to_set ( const list< T > l )

This function returns the set of members in a list. I.e, it converts an ordered list to a set.

Parameters:

[in] l The ordered list to convert.

template<class T>

template< class T > list< T > set_to_list ( const set< T > l )

This function returns the an ordered from a set.

Parameters:

[in] l The set to convert.

This function computes a maximal antichain chain of a DAG (order).

Parameters:

`[in]`	G	The DAG.
`[out]`	MA	A Maximal antichain.

Returns:: the width of the DAG. It is equal to the size of a maximal antichain.

Remarks:: A maximal antichain may not be unique. This function returns an arbitrary one.

This function computes a minimal chain decomposition of a DAG (an order).

Parameters:

`[in]`	G	The DAG.
`[out]`	chain	$\forall u \in V, chain[u] \in [0, p(G)-1]$ contains the number of the chain to which belongs.

Returns:: the minimal number of chains of the DAG. Dilworth proved that , that is, it is equal to the size of a maximal antichain.

Remarks:: A minimal chain decomposition may not be unique. This function returns an arbitrary one.

dilworthdecomposition.cpp File Reference