MUSE arc consistency is enforced by removing those labels in each
which violate the conditions of Definition
8. MUSE AC-1 builds and maintains
several data structures, described in Figure 19, to allow
it to efficiently perform this operation. Many of these data
structures are borrowed from AC-4, while others exploit the DAG
representation of the MUSE CSP to determine when values are
incompatible in all of the segments. Figure 22 shows the
code for initializing the data structures, and Figures
23 and 24 contain
the algorithm for eliminating inconsistent labels from the domains.
Figure 19: Data structures and notation for MUSE AC-1.
In MUSE AC-1 as in AC-4, if label a at node i is compatible with label b at node
j, then a supports b. To keep track of how much
support each label a has, the number of labels in 
which are
compatible with a in are counted, and the total is stored in
Counter[(i,j), a]. For CSP arc consistency, if Counter[(i,j),
a] is zero, a would be immediately removed from ,
because that would mean that a could never appear in any solution.
However, in MUSE arc consistency, this may not be the case, because
even though a does not participate in a solution for any of the
segments which contain i and j, there could be another segment for which
a would be perfectly legal. A label cannot become globally
inadmissible until it is incompatible with every segment.
Hence, in MUSE CSP, if Counter[(i,j), a] is zero, the algorithm
simply places [(i,j),a] on List and records that fact by setting
M[(i,j),a] to 1. By placing [(i,j),a] on List, the
algorithm is indicating that the segments containing i and j do
not support the label a.
MUSE AC-1 must also keep track of those labels in j that label a
in supports by using
S[(i,j), a], a set of node-label pairs.
For example, S 
means that a in
supports b and c in . If a is ever invalid for
, then b and c will loose some of their support.
Because 
is a DAG, MUSE AC-1 is able to use the
properties of the DAG to identify local (and hence efficiently
computable) conditions under which labels become globally
inadmissible. Segments are defined as paths through the
MUSE CSP from start to end. If a value associated
with a variable is not supported by any of the variables which precede it
or follow it, then there is no way that the value can be used by
any segment, so it can be deleted by the arc consistency algorithm.
In addition, if a value in a variable's domain is supported by the constraints for
values associated with a second variable, but the second variable is preceded or
followed by variables that have no values supporting the value, then because a solution
involves a path of variables in the MUSE DAG, the value cannot be supported for any segment
involving the two variables. These two ideas provide the
basis for the remaining data structures used by MUSE AC-1.
Consider Figure 20, which shows the nodes
which are adjacent to node i in the DAG. Because
every segment in the DAG which contains node i is
represented as a directed path in the DAG going through node i,
either node j or node k must be in every segment containing i.
Hence, if the
label a is to remain in , it must be compatible with at least
one label in either or 
.
Also, because either n or m must be contained in every segment
containing i, if label a is to remain in , it must also be
compatible with at least one label in either 
or 
.
In order to track this
dependency, two sets are maintained for each label a at node i,
Local-Next-Support(i,a) and Local-Prev-Support(i,a).
Local-Next-Support(i,a) is a set of ordered node pairs (i,j) such
that 
Next-Edge 
, and if 
, there is at least one label 
which is compatible with a. Local-Prev-Support(i,a) is
a set of ordered pairs (i,j) such that 
Prev-Edge ,
and if ,
there is at least one label which is compatible with
a. Dummy ordered pairs are also created to
handle cases where a node is at the beginning or end of a network:
when 
Prev-Edge , 
is added to
Local-Prev-Support(i,a), and when 
Next-Edge ,
is added to Local-Next-Support(i,a). This is to
prevent a label from being ruled out because no nodes precede or
follow it in the DAG. Whenever one of i's adjacent nodes, j, no
longer has any labels b in its domain which are compatible with a,
then (i,j) should be removed from Local-Prev-Support(i,a) or
Local-Next-Support(i,a), depending on whether the edge is from j
to i or from i to j, respectively. If either
Local-Prev-Support(i,a) or Local-Next-Support(i,a) becomes
empty, then a is no longer a part of any MUSE arc consistent instance, and should be
eliminated from . In Figure 20, the label
a is admissible for the segments containing both i and j, but not for
the segments containing i and k. If because of constraints, the labels in j become
inconsistent with a on i, (i,j) would
be eliminated from Local-Next-Support(a,i), leaving an empty set.
In that case, a would no longer be supported by any segment.
Figure 20: Local-Prev-Support and Local-Next-Support for an example DAG. The
sets indicate that the label a is allowed for every segment which contains
n, m, and j, but is disallowed for every segment which contains
k. The solid directed lines are members of G, and the solid
undirected lines represent members of E.
The algorithm can utilize similar conditions for nodes which are not
directly connected to i by Next-Edge or Prev-Edge .
Consider Figure 21. Suppose that the label
a at node i is compatible with a label in , but it is incompatible
with the labels in 
and 
, then
it is reasonable to eliminate a for all segments containing
both i and j, because those segments would have to
include either node x or y. To determine whether a
label is admissible for a set of segments containing i and j,
we calculate Prev-Support[(i,j),a] and Next-Support[(i,j),a]
sets. Next-Support[(i,j),a] includes all (i,k) arcs which support a in
i given that there is a directed edge from j to k, and
(i,j) supports a. Prev-Support[(i,j),a] includes all (i,k) arcs which support a in
i given that there is a directed edge from k to j, and
(i,j) supports a.
Note that Prev-Support[(i,j),a] will contain an
ordered pair (i,j) if Prev-Edge 
, and
Next-Support[(i,j),a] will contain an
ordered pair (i,j) if Next-Edge . These elements
are included because the edge between nodes i and j
is sufficient to allow j's labels to support a in the segment
containing i and j. Dummy ordered pairs are also created to
handle cases where a node is at the beginning or end of a network:
when 
Prev-Edge , is added to
Prev-Support[(i,j),a], and when 
Next-Edge ,
is added to Next-Support[(i,j),a]. This is to
prevent a label from being ruled out because no nodes precede or follow it in the
DAG.
Figure 22 shows the Prev-Support, Next-Support,
Local-Next-Support, and Local-Prev-Support sets that the initialization
algorithm creates for a simple example DAG.
After the initialization step, these sets contain all node pairs that are allowed based
on the connectivity of G. Later, during the consistency step those
node pairs which do not support the associated label are eliminated from each set.
Figure 21: If 
, and 
, then a is inadmissible for every segment containing both i and j. The solid directed lines are members of G, and the solid undirected lines represent members of E.
Figure 22: Initialization of the data structures for MUSE AC-1
along with a simple example.
Figure 23: Eliminating inconsistent labels from the domains in MUSE AC-1.
Figure 24: The function UPDATE-SUPPORT-SETS([(i,j),a]) for MUSE AC-1.
To illustrate how these data structures are used by the second
step of MUSE AC-1 shown in Figure 23,
consider what happens if initially 
for the MUSE
CSP depicted in Figure 22. [(1,3),a] is placed on
List to indicate that the label a in 
is not supported by
any of the labels associated with node 3. When that value is popped
off List, it is necessary for each 
S[(1,3),a] to
decrement Counter[(3,1), x] by one. If any Counter[(3,1), x]
becomes 0, and [(3,1),x] has not already been placed on the List,
then it is added for future processing. Once this is done, it is
necessary to remove [(1,3),a]'s influence on the MUSE DAG. To
handle this, we examine the two sets Prev-Support 
and Next-Support 
. Note that
the value 
in Next-Support[(1,3),a] and the value
(1,3) in Prev-Support[(1,3),a], require no further action because
they are dummy values. However, the value (1,2) in
Prev-Support[(1,3),a] indicates that (1,3) is a member of
Next-Support[(1,2), a], and since a is not admissible for (1,3),
(1,3) should be removed from Next-Support[(1,2), a], leaving an
empty set. Note that because Next-Support[(1,2),a] is empty, and
assuming that M[(1,2),a] = 0, [(1,2),a] is added to List for
further processing. Next, (1,3) is removed from
Local-Next-Support(1,a), leaving a set of 
. During the
next iteration of the while loop [(1,2),a] is popped from List.
When Prev-Support[(1,2),a] and Next-Support[(1,2),a] are
processed, Next-Support 
and Prev-Support[(1,2),a]
contains only a dummy, requiring no action. Finally, when (1,2) is
removed from Local-Next-Support(1,a), the set becomes empty, so a
is no longer compatible with any segment containing node 1 and can
be eliminated from further consideration as a possible label for node
1. Once a is eliminated from node 1, it is also necessary to
remove the support of 
from all labels on nodes that
precede node 1, that is for all nodes x such that 
Local-Prev-Support(1,a). Since Local-Prev-Support 
, and start is a dummy node, there is no more work
to be done.
In contrast, consider what happens if initially
for the MUSE CSP in Figure 22.
In this case, Prev-Support[(1,2), a] contains (1,2) which requires
no additional work; whereas, Next-Support[(1,2),a] contains (1,3),
indicating that (1,2) must be removed from
Prev-Support[(1,3),a]'s set. After the removal,
Prev-Support[(1,3),a] is non-empty, so the segment containing
nodes 1 and 3 still supports the label a in .
The reason that these two cases provide different results is that the
constraint arc between nodes 1 and 3 is contained in every segment; whereas,
the constraint arc between nodes 1 and 2 is found in only one of them.