A Simple O-Plan Time-Point Net (TPN) Demo

*** Still under construction ***

Contents

The TPN

Demonstration inputs

The input specifies points and constraints, with optional minimum and maximum values, plus default minimum and maximum values.

Ranges

A minimum value is a positive integer. A maximum value is a positive integer or the symbol "inf". A min and max together specify a range with lower and upper bounds. An inf effectively means there is no upper bound. In point and constraint specifications, a range is written like this:
   min max
If only one value is given, it is taken as both the min and the max. If no value is given, the default min and max are used.

Points

A point is specified like this:
   name min max
The min and max give the initial range of the point; the point's range may become narrower when constraints are added to the net.

In the area for entering points, you can write a sequence of point specifications separated by commas. The commas are optional. A reasonable approach is to include the commas only when more than one point is described on the same line. Here's an example:

   a 0 100
   b, c
This gives a an initial range of 0 to 100. The other points, b and c, get the default range.

Constraints

As with points, you can write a sequence of constraint specifications separated by commas, and the commas are optional.

Constraints can be specified in two ways. The first is similar to the notation for points:

   name1 min max name2
This says that the point name1 must be before the point name2 and specifies a minimum and maximum distance between them.

The second notation is more complex, but it makes it easy to specify common combinations of constraints.

Formal syntax

Bounds

bounds ::= value | lower-bound upper-bound
value ::= positive-integer
lower-bound ::= positive-integer
upper-bound ::= positive-integer | inf

Points

point ::= name | name bounds

Constraints

constraint
    ::= sequence-constraint
     |  parallel-constraint
     |  simple-constraint

simple-constraint
    ::= name1 name2
     |  name1 bounds name2

sequence-constraint ::= < seq >

seq ::= constr 
     |  constr, seq
     |  constr bounds seq

parallel-constraint ::= [ par ]

par ::= constr
     |  constr, par

constr 
    ::= sequence-constraint
     |  parallel-constraint
     |  name

Demonstration outputs

A number of different outputs are available: We'll desribe the outputs with the aid of an example. It's the example that's already in the form when you first see it. So if you were to select "Go" without changing the form, the outputs below are what you'd get. If you've forgotten what the form contained, don't worry: the inputs are reproduced in the first section of output.

All output is returned in an HTML document. Some items appear directly in the document; others are reached via links. The output begins with an identification of the O-Plan version:

O-Plan version 2.2+
Release date: 19-Apr-95
Build date:   19-Apr-95
The rest of the output matches the sequence of sections below. Buttons in the input form let you select which parts you wish to receive.

Note that in the output, min and max values are often written with two dots between them:

  min..max.
That is the notation normally used in O-Plan, but the dots are not used (and indeed are not allowed) in the demonstration input. Using spaces instead of dots should make the input easier to type.

Description of the inputs

Defaults:
Points: 0 to inf.
Constraints: 10 to 20.

Point input:
a 0 100

Constraint input:
<a,[b,c,d],e>
<e,[f,g]>

Points as parsed:
  (a 0 100)

Constraints as parsed:
  (:sequence a 10 20 (:parallel b c d) 10 20 e)
  (:sequence e 10 20 (:parallel f g))

Expanded constraints:
  a 10..20 b
  a 10..20 c
  a 10..20 d
  b 10..20 e
  c 10..20 e
  d 10..20 e
  e 10..20 f
  e 10..20 g

Success!

This section shows how the point and constraint descriptions are processed. First, they're converted to lists by a simple recursive-descent parser. The parser also fills in default min and max values when no range has been supplied. Next, the sequential / parallel constraint notation is expanded to produce a list of individual constraints, and any points that are mentioned only in the constraints are given the default min and max values.

The final step is to construct the TPN. This is done by adding all the points and then adding constraints one at a time from the list of expanded constraints. "Success!" indicates that all the constraints could be added. If some constraint could not be added, a "Failure" message is printed instead.

For example, suppose we had the following constraints instead of the ones above:

Constraint input:
<a,b,a,c>

Expanded constraints:
  a 10..20 b
  b 10..20 a
  a 10..20 c
Note that this says a must be before b and that b must be before a, an impossibility; so the second constraint cannot be added to the net:
Failure: cannot add constraint (b a 10 20).

Dropped constraints:
  b 10..20 a
  a 10..20 c
Net constructions stops after the first failure. There's no attempt to add later constructions, even if they could be added consistently. The TPN is managed in a way that would let us continue, if we wanted to, but the results may be easier to understand if we stop. In any case, all of the requested outputs will still be produced, based on the net as built before the failure.

Graph with constraints shown as links

The boxes represent time-points. Each box contains the name of the corresponding point and the final min and max values of that point. If the min and max values are the same, only one number is displayed.

The lines between boxes represent constraints. Constraints "point" to the right, so boxes further to the right are later in time.

Graph with constraints shown as intermediate nodes

As in the previous graph, the boxes represent time-points, and each box contains the name of the corresponding point above the final min and max values of that point. If the min and max values are the same, only one number is listed. Points that are later in time are drawn further to the right.

Constraints are drawn as smaller boxes containing only min and max values. As with points, when the min and max are equal, only one number is shown. The box for a constraint between two points is connected by lines to the two points. For instance, there's a constraint that says a must be before b, with a distance of 10 to 20 units between them. This is drawn as a small "10 20" box between the boxes for a and b.

Initial and final point values

   Alphabetical order     Increasing final min time

   a   0..100   0..100    a   0..100        
   b   0..inf  10..120    b  10..120        
   c   0..inf  10..120    c  10..120        
   d   0..inf  10..120    d  10..120        
   e   0..inf  20..140    e  20..140        
   f   0..inf  30..160    f  30..160        
   g   0..inf  30..160    g  30..160        
This table is pretty much self-explanatory. It shows the initial and final range for each point.

Points in context

                     a= 0..100 10.. 20 b=10..120
                     a= 0..100 10.. 20 c=10..120
                     a= 0..100 10.. 20 d=10..120

   a= 0..100 10.. 20 b=10..120 10.. 20 e=20..140

   a= 0..100 10.. 20 c=10..120 10.. 20 e=20..140

   a= 0..100 10.. 20 d=10..120 10.. 20 e=20..140

   b=10..120 10.. 20 e=20..140 10.. 20 f=30..160
   c=10..120 10.. 20 e=20..140 10.. 20 g=30..160
   d=10..120 10.. 20 e=20..140

   e=20..140 10.. 20 f=30..160

   e=20..140 10.. 20 g=30..160
This table is similar to a KWIC (Key Words In Context) index. Each point is shown together with the constraints that directly affect it, with the aim of making it easy to see that all the constraints are satisfied. In this table, points are always shown together with their range, like this:
   name=min..max
A constraint range is shown as
   min..max
On a given line of the table, the point in bold is the one being shown "in context". Constraints from earlier points are shown to the left, constraints to later points are shown to the right. When both a from and a to constraint appear on the same line, it is not significant. Constraints are listed that way just to make the table more compact.

The remaining details are best explained by an example. The point e will show the most. Remember that the constraints were defined as follows, with a default range of 10 to 20:

   Constraint input:
   <a,[b,c,d],e>
   <e,[f,g]>
The constraints that directly involve e are therefore:
   b 10..20 e
   c 10..20 e
   d 10..20 e
   e 10..20 f
   e 10..20 g
The "points in context" table adds the ranges of all the points and neatly lines things up:
   b=10..120 10.. 20 e=20..140 10.. 20 f=30..160
   c=10..120 10.. 20 e=20..140 10.. 20 g=30..160
   d=10..120 10.. 20 e=20..140
The aim is to make it fairly easy to see that e's range satisfies all of the constraints that involve e. The rest of the table does the same for the other points.

Here's the sort of check we can make. Consider one constraint as it appears in the table:

   b=10..120 10.. 20 e=20..140
The constraint says that point e must be at least 10 and at most 20 after b. The earliest time for b is 10, so the earliest time for e must be at least 10 greater. The actual value for e, 20, is at least 10 greater, so that part of the contraint is satisfied. Now consider latest times and the maximum distance allowed by the constraint. The latest time for b is 120, and the latest time for e can be at most 20 greater. Again the actual value, 140, is ok.
Jeff Dalton