如果我们想检查三个时间集 I、J、K 是否满足 (I u J)&K 为空，我们可以通过以下操作符进行

if ((I | J) & K).is_empty() { ... }

但是使用迭代器特性可能更高效，因为不需要构建中间时间集

I.into_iter().union(J).intersection(K).is_none()

graph 模块处理时间约束图，主要提供两种结构

• graph::TimeGraph：时间约束图，时间约束定义为两个瞬间之间的持续时间间隔，可以将图视为时间约束的集合
• graph::TimeScheduler：调度器根据其时间图维护一个槽位集合（每个瞬间一个槽位）

时间约束管理

图表示为一个 (Max,+) 正方形矩阵。

此矩阵用于实现时间约束图，如下所示：单元格（i,j）表示从这一刻i到这一刻j的时间约束的下限。请注意，在这种情况下，对角线填充了0元素。

全局传播算法

我们使用Floyd-Warshall路径一致性算法[3]：我们通过探索它们之间的每条路径来计算两个节点之间的最小距离。换句话说，我们提取出约束更多的路径。

实际上，由于图的完备性，这项任务并不困难：在这种情况下，我们知道局部一致性保证了全局一致性。因此，我们只需研究三个节点的所有路径（约束的端点和任何中间节点）[2]。

一个可能的算法是迭代此计算，直到约束保持稳定。另一个算法提议传播的时间复杂度为O(n³)，其中n是图的大小[1]。

增量传播算法

为了向用户提供有用的反馈，我们使用一个派生算法，该算法逐个传播约束，每一步的复杂度为O(n²)。因此，在最坏的情况下，我们达到的复杂度为O(n⁴)（因为最坏的情况是对于每个节点对都有一个约束，所以n²个约束）。

参考文献

1. C. Dousson. 《进化监控与编年史识别》博士论文（法语），计算机科学，人工智能，保罗·萨巴蒂埃大学，图卢兹（1994）
2. U. Montanari. 《约束网络：基本性质及其在图像处理中的应用》信息科学7，1974，第95-132页。
3. C.H. Papadimitriou和K. Steiglitz. 《组合优化：算法与复杂性》普伦蒂斯-霍尔，恩格尔伍德克利夫斯，新泽西州1982。