#include <PartialOrdering.h>

Public Types
typedef std::list< T >	C_ValList

Public Member Functions
template<class T1 , class T2 >
bool	addOrder (T1 a, T2 b)

template<class T2 >
bool	anyLeft (const T2 &R) const

template<class T2 >
bool	anyRight (const T2 &L) const

void	clear ()

std::size_t	depthToLeft (T t) const

bool	empty () const

template<class T2 , class F > requires std::constructible_from<T,T2> && std::invocable<F,T>
void	getRelated (T2 L, F R, std::size_t maxDepth=0) const

template<class F > requires std::invocable<F,T>
void	getRelated (C_ValList L, F R, std::size_t maxDepth=0) const

template<class F , class T2 > requires std::constructible_from<T,T2> && std::invocable<F,T>
void	getRelated (F L, T2 R, std::size_t maxDepth=0) const

template<class F > requires std::invocable<F,T>
void	getRelated (F L, C_ValList R, std::size_t maxDepth=0) const

template<class F > requires std::invocable<F,T>
void	makeLinear (F apply, E_MakeLinearPolicy policy=MLP_BREADTH_FIRST) const

bool	related (const T &a, const T &b) const

Detailed Description

template<std::equality_comparable T>
class bux::C_PartialOrdering< T >

DEFINITIONs: Let R be a partial ordering and aRb. Then a is said to be "left-related" to b, and similarly b is "right-related" to a. If no x in fld R satisfies xRa, a is said to be a "leftmost" in R. "Rightmost" is defined similarly.

Examples: test/test_PO.cpp.

Definition at line 18 of file PartialOrdering.h.

Member Typedef Documentation

◆ C_ValList

template<std::equality_comparable T>

std::list<T> bux::C_PartialOrdering< T >::C_ValList

Definition at line 28 of file PartialOrdering.h.

Member Function Documentation

◆ addOrder()

template<std::equality_comparable T>

template<class T1 , class T2 >

bool bux::C_PartialOrdering< T >::addOrder	(	T1	a,
		T2	b )

nodiscard

Examples: test/test_PO.cpp.

Definition at line 82 of file PartialOrdering.h.

References bux::C_PartialOrdering< T >::related().

◆ anyLeft()

template<std::equality_comparable T>

template<class T2 >

bool bux::C_PartialOrdering< T >::anyLeft ( const T2 & R ) const

Examples: test/test_PO.cpp.

Definition at line 126 of file PartialOrdering.h.

◆ anyRight()

template<std::equality_comparable T>

template<class T2 >

bool bux::C_PartialOrdering< T >::anyRight ( const T2 & L ) const

Examples: test/test_PO.cpp.

Definition at line 137 of file PartialOrdering.h.

◆ clear()

template<std::equality_comparable T>

void bux::C_PartialOrdering< T >::clear ( )

inline

Examples: test/test_PO.cpp.

Definition at line 38 of file PartialOrdering.h.

◆ depthToLeft()

template<std::equality_comparable T>

std::size_t bux::C_PartialOrdering< T >::depthToLeft ( T t ) const

Examples: test/test_PO.cpp.

Definition at line 101 of file PartialOrdering.h.

References bux::C_PartialOrdering< T >::depthToLeft().

Referenced by bux::C_PartialOrdering< T >::depthToLeft().

Here is the caller graph for this function:

◆ empty()

template<std::equality_comparable T>

bool bux::C_PartialOrdering< T >::empty ( ) const

inline

Examples: test/test_PO.cpp.

Definition at line 41 of file PartialOrdering.h.

◆ getRelated() [1/4]

template<std::equality_comparable T>
requires std::invocable<F,T>

template<class F >
requires std::invocable<F,T>

void bux::C_PartialOrdering< T >::getRelated	(	C_ValList	L,
		F	R,
		std::size_t	maxDepth = 0 ) const

Definition at line 162 of file PartialOrdering.h.

References bux::addUnique().

◆ getRelated() [2/4]

template<std::equality_comparable T>
requires std::invocable<F,T>

template<class F >
requires std::invocable<F,T>

void bux::C_PartialOrdering< T >::getRelated	(	F	L,
		C_ValList	R,
		std::size_t	maxDepth = 0 ) const

Definition at line 187 of file PartialOrdering.h.

References bux::addUnique().

◆ getRelated() [3/4]

template<std::equality_comparable T>
requires std::constructible_from<T,T2> && std::invocable<F,T>

template<class F , class T2 >
requires std::constructible_from<T,T2> && std::invocable<F,T>

void bux::C_PartialOrdering< T >::getRelated	(	F	L,
		T2	R,
		std::size_t	maxDepth = 0 ) const

Definition at line 155 of file PartialOrdering.h.

References bux::C_PartialOrdering< T >::getRelated().

◆ getRelated() [4/4]

template<std::equality_comparable T>
requires std::constructible_from<T,T2> && std::invocable<F,T>

template<class T2 , class F >
requires std::constructible_from<T,T2> && std::invocable<F,T>

void bux::C_PartialOrdering< T >::getRelated	(	T2	L,
		F	R,
		std::size_t	maxDepth = 0 ) const

Examples: test/test_PO.cpp.

Definition at line 148 of file PartialOrdering.h.

References bux::C_PartialOrdering< T >::getRelated().

Referenced by bux::C_PartialOrdering< T >::getRelated(), and bux::C_PartialOrdering< T >::getRelated().

Here is the caller graph for this function:

◆ makeLinear()

template<std::equality_comparable T>
requires std::invocable<F,T>

template<class F >
requires std::invocable<F,T>

void bux::C_PartialOrdering< T >::makeLinear	(	F	apply,
		E_MakeLinearPolicy	policy = MLP_BREADTH_FIRST ) const

Parameters

[in]	apply	Node visitor.
[in]	policy	How to serialize the lattice ? Breadth first or depth first.

[Excerpt from here] The usual algorithm for topological sorting has running time linear in the number of nodes plus the number of edges (O(|V|+|E|)). It uses depth-first search. First, find a list of "start nodes" which have no incoming edges and insert them into a queue Q. Then,

while Q is nonempty do
    remove a node n from Q
    output n
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q 

If this algorithm terminates without outputting all the nodes of the graph, it means the graph has at least one cycle and therefore is not a DAG, so the algorithm can report an error.