MUSE path consistency is enforced by setting 
to false when it violates the conditions of Definition
9. MUSE PC-1 builds and maintains
several data structures comparable to the data structures defined for
MUSE AC-1, described in Figure 29, to allow it to efficiently perform this operation.
Figure 32 shows the code for initializing the data
structures, and
Figures 33 and 34 contain the
algorithm for eliminating MUSE path inconsistent binary constraints.
Figure 29: Data structures and notation for MUSE PC-1.
MUSE PC-1 must keep track of which labels in 
support . To keep
track of how much path support each
has, the number of labels in which satisfy
and 
are counted using
Counter[(i,j),k,a,b]. Additionally, the algorithm
must keep track of the set S[(i,j),k,a,b], which contains members
of the form (k,c) where and
are supported by . If ever becomes false in the segment containing i, j,
and k, then and will loose
some of their support. MUSE PC-1 also uses the
Local-Next-Support, Local-Prev-Support, Prev-Support, and Next-Support
sets similar to those in MUSE AC-1.
MUSE PC-1 is able to use the
properties of the DAG to identify local (and hence efficiently
computable) conditions under which binary constraints fail because
of lack of path support. Consider Figure 30, which shows the nodes
which are adjacent to node i and j in the DAG. Because
every segment in the DAG which contains node i and j is
represented as a directed path in the DAG going through both node i and node j, some
node must precede and follow nodes i and j for
to hold. In order to track this
dependency, two sets are maintained for each [(i,j), a, b] tuple:
Local-Prev-Support[(i,j), a, b] and Local-Next-Support[(i,j), a,
b]. Note that we distinguish Local-Prev-Support[(i,j), a, b] from
Local-Prev-Support[(j,i), b, a] to separately keep track of those elements
directly preceding i and those directly preceding j.
We also distinguish Local-Next-Support[(i,j), a, b] from
Local-Next-Support[(j,i), b, a]. If any of these sets become empty, then
the (i,j) arc can no longer support .
Local-Prev-Support[(i,j), a, b] is a set of ordered node pairs
(i,x) such that 
Prev-Edge 
, and if 
, there is at least
one label 
which is compatible with .
Local-Next-Support[(i,j), a, b] is a set of ordered node pairs
(i,x) such that 
Next-Edge , and if , there is at least
one label which is compatible with .
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,j),a,b], and when 
Next-Edge ,
is added to Local-Next-support[(i,j),a,b].
Figure 30: Local-Prev-Support and Local-Next-Support for the path
consistency of an example DAG. The solid directed lines are members of G, and
the solid undirected line represents the (i,j) and (j,i) members of E.
The algorithm can utilize similar conditions for nodes which may not be
directly connected to i and j.
Consider Figure 31. Suppose that
is compatible with a label in
, but is incompatible with
the labels in 
and 
, then
and 
are false for all segments containing
i, j, and k because those segments would have to
include either node x or y. To determine whether a
constraint is admissible for a set of segments containing i, j, and k,
we calculate Prev-Support[(i,j), k, a, b], Prev-Support[(j,i), k,
b,a], Next-Support[(i,j), k, a, b], and Next-Support[(j,i),k,b,a]
sets. Next-Support[(i,j),k,a,b] includes all (i,x) arcs which
support given that there is a directed edge from k to
x, 
, 
, and 
(Next-Support[(j,i),k,b,a]
is defined similarly). Prev-Support[(i,j),k,a,b]
includes all (i,x) arcs which support
given that there is a directed edge from x to k,
, , and (Prev-Support[(j,i),k,b,a] is defined similarly).
Note that Prev-Support[(i,j),k,a,b] will contain an
ordered pair (i,k) if (i,k) 
Prev-Edge 
, and
(i,j) if (j,k) Prev-Edge . Next-Support[(i,j),k,a,b]
will contain an ordered pair (i,k) if (k,i) Next-Edge
and (i,j) if 
Next-Edge . These elements
are included because the edge between those nodes
is sufficient to allow the support. 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),k,a,b], and when 
Next-Edge ,
is added to Next-Support[(i,j),k,a,b].
Figure 31: If it is found that 
, then is ruled out for every segment containing i, j, and k. The solid directed lines are members of G, and the solid undirected lines represent members of E.
Figure 32: Initialization of the data structures for MUSE PC-1.
Figure 33: Eliminating inconsistent binary constraints in MUSE PC-1.
Figure 34: The function UPDATE-SUPPORT-SETS([(i,j),k, a, b]) for MUSE PC-1.