Re: [xml-dev] Large class of problems: constrain a bunch of pieces to fo

[Michael Kay <mike@saxonica.com>]

On 20 Feb 2017, at 15:17, Costello, Roger L. <costello@mitre.org> wrote:

Hi Folks,

 

There are a large class of problems that may be characterized this way: Given a bunch of pieces, constrain them so they form a single, connected chain.

 

The following is a beautiful example from this class of problems.

 

Problem: Constrain the segments in an aircraft’s route so that they form a single, connected chain.

 

Explanation: An aircraft flies a route. A route consists of segments. A route has a starting fix and an ending fix. A “fix” is a position. Each segment also has a starting fix and an ending fix. One segment’s starting fix must match the route’s starting fix. One segment’s ending fix must match the route’s ending fix. For the other segments, they must be connected: the ending fix of one segment must be the starting fix of another segment.

 

<image001.png>

 

Example: Here is a trivial route with just one segment:

 

<Route>
    <start-Fix>
        <Airport id="BOS"/>
    </start-Fix>
    <end-Fix>
        <Airport id="JFK"/>
    </end-Fix>
    <Segment>
        <start-Fix>
            <Airport id="BOS"/>
        </start-Fix>
        <end-Fix>
            <Airport id="JFK"/>
        </end-Fix>
    </Segment>
</Route>

 

Here is a route with three segments. Notice the segments are connected:
                BOS -> MARSHFIELD -> FITCHBURG -> JFK

 

<image002.png>

Declarative description of the connected-segments constraint:

 

Every segment in a route must satisfy these three constraints:

1.       The segment is the route’s first segment, or the segment follows another segment.

2.       The segment is the route’s last segment, or the segment precedes another segment.

3.       The segment does not follow the route and the segment does not precede the route.

 

Here is a more detailed description:

 

For every segment s in route r:

1.       The starting fix of s matches the starting fix of r, or there is a segment s₂ whose ending fix matches the starting fix of s.

2.       The ending fix of s matches the ending fix of r, or there is a segment s₂ whose starting fix matches the ending fix of s.

3.       The starting fix of s does not match the ending fix of r and the ending fix of s does not match the starting fix of r.

I think those conditions are satisfied by

r.start = A

r.end = C

s1.start = A

s1.end = B

s2.start = B

s2.end = C

s3.start = A

s3.end = C

and I don't think you had that in mind as a valid route (a "single connected chain"). Perhaps your "or" in rules (1) and (2) should be an "exclusive or".

I don't know whether you consider something like A -> B -> C -> B -> D as a valid route. I don't know whether any planes fly such routes but I've certainly been on country bus journeys that followed that pattern. If such routes are legal you may need to revise your rules.

 

Schematron implementation of the connected-segments constraint:

 

        <sch:assert test="

             every $s in Segment satisfies
             ($s/start-Fix/*/@id = $r/start-Fix/*/@id) or
            (some $s2 in Segment satisfies $s2/end-Fix/*/@id = $s/start-Fix/*/@id)
            and

($s/end-Fix/*/@id = $r/end-Fix/*/@id) or
            (some $s2 in Segment satisfies $s2/start-Fix/*/@id = $s/end-Fix/*/@id)
             and

(not($s/start-Fix/*/@id = $r/end-Fix/*/@id) and not($s/end-Fix/*/@id = $r/start-Fix/*/@id))

">
           The segments in the route must be connected.
        </sch:assert>

 

That is so neat. It is a beautiful, declarative expression of the constraints on the segments in a route.

 

Beauty is in the eye of the beholder, but to me, it would be much more elegant to model a flight route using a list of points rather than a list of segments, in which case no additional constraints are necessary:

<route>

  <start>LHR</start>

  <via>GLA</via>

  <via>BOS</via>

  <end>LAX</end>

</route>

Michael Kay

Saxonica