Container aiding in gradual discovery of order.
More...
#include <OrderDiscoveryHelper.h>
|
|
using | DependencyGraphType = boost::adjacency_list< boost::setS, boost::vecS, boost::directedS, VertexData > |
| |
|
using | VertexIndexType = typename DependencyGraphType::vertex_descriptor |
| |
|
| 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) |
| |
|
|
std::map< T, VertexIndexType > | sourceMap_ |
| |
|
DependencyGraphType | graph_ |
| |
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 |
template<typename T>
template<typename Container >
Arbitrary container constructor.
- Template Parameters
-
- Parameters
-
Complexity \(\Theta(N)\)
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)\)
Add a less-than relationship to the graph.
Complexity \(\Theta(1)\)
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)\)
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.
Dumps a graphviz string for visualization of relationships.
Complexity \(\Theta(N)\)
Get a list of sets (in descending order) as currently discovered.
Complexity \(\Theta(N)\)
Get a grouped list of the ordered data sorted by out_degree ascending.
Complexity \(\Theta(N)\)
Returns grouped data (in descending order) whose internal order is undecided.
Complexity \(\Theta(N)\)
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)\)
Returns whether the total order has been discovered or not.
Complexity \(\Theta(1)\)
template<typename T>
template<typename It >
template<typename T>
template<typename Container >
The documentation for this class was generated from the following file:
