Struct TimeGraph

pub struct TimeGraph { /* private fields */ }

A graph of non disjunctive time constraints.

Each node of the graph corresponds to an instant and the time constraints between two nodes are defined as a TimeInterval. Each added constraint is automatically propagated (through a path-consistency algorithm) and so, the global consistency is always ensured.

Minimize the complete graph

A time graph is always a complete graph since one can alwys define a time constraint between each couple of nodes, the default used constraint is ]-∞, +∞[. The minimal complete graph is the least constrained complete graph which is in respect with all the user defined constraints. We can prove that this graph is unique. For instance, the following figure shows a user defined constraints graph on the left side and the corresponding minimal graph on the right hand.

Global Propagation Algorithm

We use a Floyd-Warshall path consistency algorithm [3]: we compute the smallest distance between two nodes by exploring every path between them. In other words, we extract the more constrained path.

Actually, the task is not so hard because of the completeness of the graph: in this case, we know that a local consistency ensures the global consistency. So we only study all the paths of three nodes (the ends of the constraints and any intermediate one) [2].

Any edge is updated by intersecting the current constraint and the computed one through a third node (see the following figure).

A first algorithm can be to iterate this calculus untill the constraints remain stable. Another one is proposed to do the propagation is O(n³) where n is the size of the graph [1].

Incremental Propagation Algorithm

In order to provide a useful feedback to the user, we use a derivated algorithm which propagate the constraints one by one, with a complexity of O(n²) at each step (each added constraint by calling [Self::add_time_constraint]). So, in the worst case, we reach a complexity of O(n⁴) (since the worst case is when we have a constraint for each couple of nodes, so n² constraints).

Implementation: (Max,+) square matrix.

This matrix is used to implement a time constraint graph as follows: the cell (i,j) represents the lower bound of the time constraint from this instant i to the instant j. Notice that, in this particular case, the diagonal is filled with 0 element.

As an illustration, the following figure show a time graph with the associated time matrix:

References

1. C. Dousson. “Evolution Monitoring and Chronicle Recognition.” PhD thesis (in french), computer sciences, A.I., Université Paul Sabatier, Toulouse (1994)
2. U. Montanari. “Networks of constraints: fundamental properties and applications to picture processing”, Information sciences 7, 1974, pp 95-132.
3. C.H. Papadimitriou and K. Steiglitz. “Combinatorial optimization: algorithms and complexity.” Prentice-Hall, Englewood Cliffs, N.J. 1982.

Implementations

impl TimeGraph

pub fn constraint( &self, from: Instant, to: Instant, ) -> Option<TimeGraphConstraint<'_>>

Gets the constraint between two instants, if it exists

If one instant is out of the graph or if the instants are not constrained each other (i.e. ]-oo,+oo[), then there is no constraint and None is returned.

pub fn constraints_from( &self, from: Instant, ) -> impl Iterator<Item = TimeGraphConstraint<'_>>

Gets an iterator over all the propagated constraints starting from i

pub fn constraints_to( &self, to: Instant, ) -> impl Iterator<Item = TimeGraphConstraint<'_>>

Gets an iterator over all the propagated constraints ending to i

pub fn iter(&self) -> impl Iterator<Item = TimeGraphConstraint<'_>>

Gets an iterator over all the propagated constraints of the graph.

Only relevant constraints are iterated.

impl TimeGraph

pub fn propagate<K: TimeConstraint>( &mut self, k: K, ) -> Result<TimePropagation, TimeInconsistencyError>

pub fn merge( &mut self, graph: TimeGraph, ) -> Result<TimePropagation, TimeInconsistencyError>

Merge two timegraphs

pub fn extend<I, K>( &mut self, iter: I, ) -> Result<TimePropagation, TimeInconsistencyError>

where K: TimeConstraint, I: IntoIterator<Item = K>,

Add several constraints in one shot

If this set of constraints are inconsistent with the graph, there is no possible recovery and the graph is definitively corrupted

impl TimeGraph

pub fn reset(&mut self)

Clears all the constraints

The size remains the same

pub fn with_size(size: u32) -> TimeGraph

Create a new unconstrained graph

The graph contains the specified number of instants (nodes) and all the constraints are set to ]-oo,+oo[.

pub fn size(&self) -> u32

Number of instants (nodes) of the graph

pub fn resize(&mut self, n: Instant)

Resize the graph

If the new size is smaller than the current one, they the related constraint are also removed buth the impact of their propagation remains.

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the graph as much as possible.

The latest unconstrained instants are also removed so the size of the graph could change.

It will drop down as close as possible to the length but the allocator may still inform the graph that there is space for a few more elements.

pub fn shrink_to(&mut self, n: Instant)

Shrinks the capacity of the graph with a lower bound.

The capacity will remain at least as large as both the length and the supplied value.

If the current capacity is less than the lower limit, this is a no-op.

pub fn timespan(&self, i: Instant, j: Instant) -> TimeSpan

pub fn instant_cmp(&self, i: Instant, j: Instant) -> Option<Ordering>

pub fn are_distinct_instants(&self, i: Instant, j: Instant) -> bool

Trait Implementations

impl Clone for TimeGraph

fn clone(&self) -> TimeGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for TimeGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for TimeGraph

fn default() -> TimeGraph

Returns the “default value” for a type.

impl Display for TimeGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K: TimeConstraint> Extend<K> for TimeGraph

fn extend<T: IntoIterator<Item = K>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K: TimeConstraint> FromIterator<K> for TimeGraph

fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self

Creates a value from an iterator.