Clarification:

the role of the ordering graph described below is to 
restrict the set of class graphs with which the strategy
graph can be used.

Boaz just came up with an efficient algorithm for the problem:

Given a strategy graph SG with source s, 
an ordering graph OG and a class graph G,
decide whether all paths in the 
path set defined by SG and s satisfy all OG ordering constraints.

The algorithm checks each constraint P < Q in turn on the
traversal graph. Remember, the traversal graph is the "modern"
form of the propagation graph (Boaz).

-- Karl

==================
Thoughts about the Demeter Seminar discussion June 9, 1997:

Executive summary:
Doug questions the role of targets.
We need an ordering graph on top of the strategy graph.

Traversal strategies started out as 
"from A bypassing edges through K to Z"
specifications with a clear source (A) and target (Z).
Such strategies are called line strategies since the underlying
structure is a graph consisting of a sequence of consecutive edges.
Strategies evolved to series-parallel graph specifications of the form
"(merge from A through B to D, from A through C to D)" which
also have a clear source (A) and target (D). 
Such strategies are called series-parallel strategies.
Both for line graphs and series-parallel graphs the generalization
to multiple sources and targets is straightforward.
Later, Boaz evolved
traversal strategies to general graphs and in a graph it
is less clear what the sources of a general graph are.

Doug was pointing out that in his adaptive programs inside Demeter/Java
targets have sometimes an artificial role. He wants to go
from a source to a bunch of "targets" but the target nodes
serve often the role of requiring a visitor method.

A general graph has a "natural" set of sources: the vertex base
of the graph. It is a minimal set of nodes from which all other
nodes can be reached. Both line graphs and series-parallel
graphs have a unique vertex basis consisting of one node.
By analogy, a general graph has a "natural" set of targets:
A minimal set of vertices which are reachable from the graph nodes.
Often there are multiple vertex basis for the same graph and therefore,
the concept of sources and targets is not unique for general graphs
(as opposed to line and series parallel graphs).

The question now is: should a strategy have a set of sources
and targets associated with it? I think a strategy needs
an interface which says what the entry nodes are (where
traversals may begin) and what the additional code glue nodes are.
The glue nodes are all nodes mentioned in the strategy
plus the ones given additionally.
Syntax:

strategy a1#A.(B . C + D . C).a2#A
entry: a1#A,D
glue: P,Q
  constraints: P < C, Q < C

The strategy defines an abstraction of a class graph and we want
to start traversals at a1#A and D. The path set must contain
paths going through P and Q and both P and Q must appear
before C in all those path sets.

Notice that this is more adaptive than:
strategy a1#A.(B . P . C + D . Q . C).a2#A
entry: a1#A,D

and

strategy a1#A. P . Q .(B . C + D . C).a2#A
entry: a1#A,D

To summarize, in the world of strategies as general graphs
it is necessary to specify "sources" explicitly to indicate
where a traversal starts. The set of specified sources
may not be a vertex basis since it can contain additional entry nodes.
The concept of targets should be replaced by the concept of glue nodes
so that a strategy mentions all the classes which may get
visitor methods.

There is one situation where the concept of sources and targets
is still important: composition of strategies. For the expression:
do s1 . do s2 we need to know what the source and what the target is.
Maybe they are unique based on the vertex basis definition. If not,
the sources and targets need to be specified explicitly:

This could be specified as part of the join:

do s1 . do s2 where targets s1 = ... and sources s2 = ...

The need for constraints seems to indicate that strategy graphs
by themselves are not expressive enough. We need to add
ordering constraints of the form A < B.
A < B has the meaning that on all paths starting at an entry point,
B is never encountered before A. The need for such constraints
arises from the code in the visitors. It might be that in A we initialize
something used in B and therefore we must encounter an A before
we get to a B.

examples:
strategy: A . B . C
ordering: B < C

The strategy allows a traversal : A C B C
but the ordering disallows this and allows a traversal like: A X B Y C

It is interesting to notice that the ordering constraints also
correspond to a graph: A < B is an edge from A to B.

So in this version of AP, adaptive programs are specified in terms
of strategies consisting of a 

strategy graph SG as a sketch of the shape of the collaborting classes
for the current task.

set of nodes S which define the allowed entry nodes

set of additional nodes A which play a role in the traversal

ordering graph OG in terms of node labels of SG and A  which indicates 
ordering constraints.

So a strategy is a tuple (SG,S,A,OG). How does this look like?
I think that ordering graphs are important to specify correct reuse
of adaptive programs at a high level of abstraction.

Good-by targets, except for composition.

-- Karl