Scine::Molassembler::OrderDiscoveryHelper< T > Class Template Reference

Container aiding in gradual discovery of order. More...

#include <OrderDiscoveryHelper.h>

Inheritance diagram for Scine::Molassembler::OrderDiscoveryHelper< T >:

Data Structures
class	GraphvizWriter
struct	VertexData

Public Types
using	DependencyGraphType = boost::adjacency_list< boost::setS, boost::vecS, boost::directedS, VertexData >
using	VertexIndexType = typename DependencyGraphType::vertex_descriptor

Public Member Functions
template<typename Container >
	OrderDiscoveryHelper (const Container &container)
	Arbitrary container constructor. More...
void	addRelationshipsFromOther (const OrderDiscoveryHelper &other)
	Transfer relationships from another OrderDiscoveryHelper. More...
void	addAllFromOther (const OrderDiscoveryHelper &other)
	Adds vertices and edges from another instance, then adds transferability edges. More...
void	addTransferabilityEdges ()
	Adds missing transferability edges. More...
template<typename It >
void	setUnorderedValues (It iter, const It end)
	Range-abstracted. More...
template<typename Container >
void	setUnorderedValues (Container &&container)
	Container-abstracted. More...
std::vector< std::vector< T > >	getSets () const
	Get a list of sets (in descending order) as currently discovered. More...
std::vector< std::vector< T > >	getUndecidedSets () const
	Returns grouped data (in descending order) whose internal order is undecided. More...
bool	isTotallyOrdered () const
	Returns whether the total order has been discovered or not. More...
void	addLessThanRelationship (const T &a, const T &b)
	Add a less-than relationship to the graph. More...
std::string	dumpGraphviz () const
	Dumps a graphviz string for visualization of relationships. More...
bool	isSmaller (const T &a, const T &b) const
	Check if a value is smaller than another. More...

Private Member Functions
std::vector< std::vector< T > >	getSetsByDegree_ () const
	Get a grouped list of the ordered data sorted by out_degree ascending. More...
VertexIndexType	addItem_ (const T &item)

Private Attributes
std::map< T, VertexIndexType >	sourceMap_
DependencyGraphType	graph_

Detailed Description

template<typename T>
class Scine::Molassembler::OrderDiscoveryHelper< T >

Container aiding in gradual discovery of order.

Template Parameters

T	The type whose order is to be discovered

Constructor & Destructor Documentation

template<typename T>

template<typename Container >

Scine::Molassembler::OrderDiscoveryHelper< T >::OrderDiscoveryHelper ( const Container &  container )

inlineexplicit

Arbitrary container constructor.

Template Parameters

Container

Container type

Parameters

container

Container instance

Complexity \(\Theta(N)\)

Member Function Documentation

template<typename T>

void Scine::Molassembler::OrderDiscoveryHelper< T >::addAllFromOther ( const OrderDiscoveryHelper< T > &  other )

inline

Adds vertices and edges from another instance, then adds transferability edges.

Adds all information present in another OrderDiscoveryHelper that are not yet present in this one. Any vertices not present in this graph are added, plus any missing relationship edges. If any contradictory information is present, this function throws. Missing transferability edges are added too (if a < b && b < c, then a < c).

Complexity \(O(N^2)\)

template<typename T>

void Scine::Molassembler::OrderDiscoveryHelper< T >::addLessThanRelationship ( const T &  a, const T &  b  )

inline

Add a less-than relationship to the graph.

Complexity \(\Theta(1)\)

template<typename T>

void Scine::Molassembler::OrderDiscoveryHelper< T >::addRelationshipsFromOther ( const OrderDiscoveryHelper< T > &  other )

inline

Transfer relationships from another OrderDiscoveryHelper.

Adds any relationships from another OrderDiscoveryHelper that are not yet present in this instance. No new vertices are added. Missing transferability edges are added (if a < b && b < c, then a < c) If any contradictory information is present, this function throws.

Complexity \(\Theta(N^2)\)

template<typename T>

void Scine::Molassembler::OrderDiscoveryHelper< T >::addTransferabilityEdges ( )

inline

Adds missing transferability edges.

Adds any missing transferability edges (if a < b && b < c, then a < c).

Complexity \(O(N^2)\)

This function is awful in terms of complexity, it's worst case of O(N²). There must be better ways of doing this.

template<typename T>

std::string Scine::Molassembler::OrderDiscoveryHelper< T >::dumpGraphviz ( ) const

inline

Dumps a graphviz string for visualization of relationships.

Complexity \(\Theta(N)\)

template<typename T>

std::vector< std::vector<T> > Scine::Molassembler::OrderDiscoveryHelper< T >::getSets ( ) const

inline

Get a list of sets (in descending order) as currently discovered.

Complexity \(\Theta(N)\)

template<typename T>

std::vector< std::vector<T> > Scine::Molassembler::OrderDiscoveryHelper< T >::getSetsByDegree_ ( ) const

inlineprivate

Get a grouped list of the ordered data sorted by out_degree ascending.

Complexity \(\Theta(N)\)

template<typename T>

std::vector< std::vector<T> > Scine::Molassembler::OrderDiscoveryHelper< T >::getUndecidedSets ( ) const

inline

Returns grouped data (in descending order) whose internal order is undecided.

Complexity \(\Theta(N)\)

template<typename T>

bool Scine::Molassembler::OrderDiscoveryHelper< T >::isSmaller ( const T &  a, const T &  b  ) const

inline

Check if a value is smaller than another.

This returns true if and only if both values are part of the graph and if the less-than relationship is present in the order given, i.e. a < b.

In all other cases (either of the values isn't in the graph, there is no ordering relationship or the ordering relationship is the other way around), this function returns false.

Complexity \(\Theta(1)\)

template<typename T>

bool Scine::Molassembler::OrderDiscoveryHelper< T >::isTotallyOrdered ( ) const

inline

Returns whether the total order has been discovered or not.

Complexity \(\Theta(1)\)

template<typename T>

template<typename It >

void Scine::Molassembler::OrderDiscoveryHelper< T >::setUnorderedValues ( It  iter, const It  end  )

inline

Range-abstracted.

See Also

setUnorderedValues

Complexity \(\Theta(N)\)

template<typename T>

template<typename Container >

void Scine::Molassembler::OrderDiscoveryHelper< T >::setUnorderedValues ( Container &&  container )

inline

Container-abstracted.

See Also

setUnorderedValues

Complexity \(\Theta(N)\)

---

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

• Molassembler/Molecule/OrderDiscoveryHelper.h