5.316. path_from_to
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Usual name
- Arguments
- Restrictions
- Purpose
Select some arcs of a digraph so that there is still a path between two given vertices of .
- Example
-
The constraint holds since within the digraph corresponding to the item of the collection there is a path from vertex to vertex : this path starts from vertex 4, enters vertex 5, and ends up in vertex 3.
- Typical
- Symmetry
Items of are permutable.
- See also
common keyword: Β (path),
Β (constraint involving set variables),
, Β (path).
- Keywords
-
constraint arguments: constraint involving set variables.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
Within the context of the Example slot, partΒ (A) of FigureΒ 5.316.1 shows the initial graph from which we choose to start. It is derived from the set associated with each vertex. Each set describes the potential values of the attribute of a given vertex. PartΒ (B) of FigureΒ 5.316.1 gives the final graph associated with the Example slot. Since we use the graph property we show on the final graph the following information:
The vertices that respectively correspond to the start and the end of the required path are stressed in bold.
The arcs on the required path are also stressed in bold.
The constraint holds since there is a path from vertex 4 to vertex 3 (4 and 3 refer to the attribute of a vertex).
Figure 5.316.1. Initial and final graph of the set constraint
(a) (b) - Signature
Since the maximum value returned by the graph property is equal to 1 we can rewrite to . Therefore we simplify to .