Struct ddo::core::implementation::mdd::flat::FlatMDD

pub struct FlatMDD<T, C> where
    T: Hash + Eq + Clone,
    C: Config<T>,  { /* fields omitted */ }

This is the structure implementing flat MDD. This is a kind of bounded width MDD which offers a real guarantee wrt to the maximum amount of used memory. This should be your go-to implementation of a bounded-width MDD, and it is the default type of MDD built by the mdd_builder.

A flat mdd is highly efficient in the sense that it only maintains one 'slice' of the current MDD unrolling. That is, at any time, it only knows the current layer, and the next layer (being developed). All previous layers are irremediably forgotten (but this causes absolutely no harm). Alongside the current and next layers, this structure also knows of a 3rd layer which materializes the last exact layer (exact cutset) of this mdd. Moving from one layer to the next (after the next layer has been expanded) is extremely inexpensive as it only amounts to swapping two integer indices.

Remark

So far, the FlatMDD implementation only supports the last exact layer (LEL) kind of exact cutset. This might change in the future, but it is your only option at the time being since it keeps the code clean and simple.

Note

The behavior of this MDD is heavily dependent on the configuration you provide. Therefore, and although a public constructor exists for this structure, it it recommended that you build this type of mdd using the mdd_builder functionality as shown in the following examples.

Example

let problem    = MockProblem;
let relaxation = MockRelax;
// Following line configure and builds a flat mdd.
let flat_mdd   = mdd_builder(problem, relaxation).build();

// ... or equivalently (where you emphasize the use of a *flat* mdd)
let problem    = MockProblem;
let relaxation = MockRelax;
let flat_mdd   = mdd_builder(problem, relaxation).into_flat();

// Naturally, you can also provide configuration parameters to customize
// the behavior of your MDD. For instance, you can use a custom max width
// heuristic as follows (below, a fixed width)
let problem    = MockProblem;
let relaxation = MockRelax;
let flat_mdd = mdd_builder(problem, relaxation)
                .with_max_width(FixedWidth(100))
                .build();

Methods

impl<T, C> FlatMDD<T, C> where
    T: Hash + Eq + Clone,
    C: Config<T>, 

Private functions

pub fn new(config: C) -> Self

Constructor, uses the given config to parameterize the mdd's behavior

Trait Implementations

impl<T: Clone, C: Clone> Clone for FlatMDD<T, C> where
    T: Hash + Eq + Clone,
    C: Config<T>, 

fn clone(&self) -> FlatMDD<T, C>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, C> MDD<T> for FlatMDD<T, C> where
    T: Hash + Eq + Clone,
    C: Config<T>, 

FlatMDD implements the MDD abstract data type. Check its documentation for further details.

fn mdd_type(&self) -> MDDType

Tells whether this MDD is exact, relaxed, or restricted.

fn root(&self) -> Node<T>

Generates the root node of the problem

fn exact(&mut self, root: &Node<T>, best_lb: i32)

Expands this MDD into an exact MDD

fn restricted(&mut self, root: &Node<T>, best_lb: i32)

Expands this MDD into a restricted (lower bound approximation) version of the exact MDD.

fn relaxed(&mut self, root: &Node<T>, best_lb: i32)

Expands this MDD into a relaxed (upper bound approximation) version of the exact MDD.

fn consume_cutset<F>(&mut self, f: F) where
    F: FnMut(T, NodeInfo), 

Consumes (removes) all nodes from the cutset of this mdd ands applies the given function f to each pair of (state, node_info) present in this mdd.

fn is_exact(&self) -> bool

Return true iff this MDD is exact. That is to say, it returns true if no nodes have been merged (because of relaxation) or suppressed (because of restriction).

fn best_value(&self) -> i32

Returns the length of the longest path between the root and the terminal node of this MDD.

fn best_node(&self) -> &Option<NodeInfo>

Returns the terminal node having the longest associated path in this MDD.

fn longest_path(&self) -> Vec<Decision>

Returns the list of decisions along the longest path between the root node and the best terminal node of this MDD.