Crates.io | chronologic |

lib.rs | chronologic |

version | 0.7.2 |

source | src |

created_at | 2022-06-08 09:12:29.233246 |

updated_at | 2024-04-02 14:03:33.255632 |

description | Time constraint reasoning (scheduling...) |

homepage | |

repository | https://github.com/XopheD/chronologic |

max_upload_size | |

id | 601943 |

size | 248,868 |

https://docs.rs/chronologic

# chronologic
This crate is dedicated to reasoning about time.
It deals with time constraints, propagates them and
maintains an agenda of all the possible dates consistent
with the user constraints.
It is designed to manage efficiently thousands of instants
in order to be used, for instance, for planning or sheduling problems.
## Time structures
Several time structures (interval, sets) are provided
to make easier time manipulation.
This time data defines several operators for union, intersection,
translation in two ways:
* by using standard operators (`&` for intersection, `|` for union, `+/-` for translation)
* by using iterator traits (see module [`iter`]) which allows time manipulation with
saving memory allocation (no intermediate structures needed)
If we want to check that three time sets I, J, K verifies (I u J)&K is empty,
we can do it by using the operators
```rust
if ((I | J) & K).is_empty() { ... }
```
But using the iterator traits could be more efficient since no intermediate time sets need to be built:
```rust
I.into_iter().union(J).intersection(K).is_none()
```
The module [`graph`] deals with time constraints graph and mainly provides two structures:
* [`graph::TimeGraph`]: the time constraints graph, a time constraint is defined as an interval
of duration between two instants, a graph could be considered as a collection of time constraints
* [`graph::TimeScheduler`]: the scheduler maintains a set of slots (one for each instant) according to
its time graph
## Time constraint management
The graph is represented as a (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.
### 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.

Commit count: 51
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].

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^{3}) 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^{2}) at each step.
So, in the worst case, we reach a complexity of O(n^{4}) (since
the worst case is when we have a constraint for each couple of nodes, so n^{2} constraints).
## References
1. C. Dousson. _"Evolution Monitoring and Chronicle Recognition."_
PhD thesis (in french), computer sciences, A.I., Université Paul Sabatier, Toulouse (1994)
1. U. Montanari. _"Networks of constraints: fundamental properties and applications to picture
processing"_, Information sciences 7, 1974, pp 95-132.
1. C.H. Papadimitriou and K. Steiglitz. _"Combinatorial optimization: algorithms and complexity."_
Prentice-Hall, Englewood Cliffs, N.J. 1982.