5.134. dom_reachability
| DESCRIPTION | LINKS |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
Let , and be three directed graphs respectively called the flow graph, the dominance graph and the transitive closure graph which all have the same vertices. In addition let denote a vertex of the flow graph called the source node (not necessarily a vertex with no incoming arcs). The constraint holds if and only if the flow graph (and its source node) verifies:
The dominance relation expressed by the dominance graph (i.e.,Β if there is an arc in the dominance graph then, within the flow graph, all the paths from the source node to contain ; note that when there is no path from the source node to then any node dominates ).
The transitive relation expressed by the transitive closure graph (i.e.,Β if there is an arc in the transitive closure graph then there is also a path from to in the flow graph).
- Example
-
The flow graph, the dominance graph and the transitive closure graph corresponding to the second, third and fourth arguments of the constraint are respectively depicted by parts (A), (B) and (C) of FigureΒ 5.134.1. The holds since the following conditions hold.
The dominance relation expressed by the dominance graph is verified:
Since belongs to the dominance graph all the paths from 1 to 2 in the flow graph pass through 1.
Since belongs to the dominance graph all the paths from 1 to 3 in the flow graph pass through 1.
Since belongs to the dominance graph all the paths from 1 to 4 in the flow graph pass through 1.
Since belongs to the dominance graph all the paths from 1 to 3 in the flow graph pass through 2.
Since belongs to the dominance graph all the paths from 1 to 4 in the flow graph pass through 2.
The graph depicted by the fourth argument of the constraint (i.e.,Β ) is the transitive closure of the graph depicted by the second argument (i.e.,Β ).
Figure 5.134.1. (A)Β Flow graph, (B)Β dominance graph and (C)Β transitive closure graph of the Example slot (taken fromΒ [Quesada06])
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
Items of are permutable.
- Usage
The constraint was introduced in order to solve reachability problems (e.g., disjoint paths, simple path with mandatory nodes).
- Remark
Within the name , stands for domination. In the context of path problems refers to the start of the path we want to build.
- Algorithm
It was shown inΒ [Quesada06] that, finding out wether a constraint has a solution or not is NP-hard. This was achieved by reduction to disjoint paths problemΒ [GareyJohnson79].
The first implementationΒ [QuesadaVanRoyDeville05] of the constraint was done in MozartΒ [Mozart06]. Later on, a second implementionΒ [Quesada06] was done in GecodeΒ [Gecode06]. Both implementations consist of the following two parts:
AlgorithmsΒ [Roditty03] for maintaining the lower bound of the transitive closure graph.
Algorithms for maintaining the upper bound of the transitive closure graph, while respecting the dominance constraintsΒ [Georgiadis05].
- See also
common keyword: , Β (path).
- Keywords