To: dem
Subject: from path set to slice

Hi Mitch:

Following your earlier suggestion, 
we archive all our interesting discussions at:

http://www.ccs.neu.edu/research/demeter/archives/dem/

Thank you for your note. A crucial expression is:
s (=>.(<=.C.=>)*.<=) t to define (s,t) paths in class graphs.

But when we compose two such paths we don't get necessarily a path that 
corresponds to an object path? we may have => after <= in
such a path?

I look forward to your presentation in the Demeter Seminar
on Nov. 16 to discuss the many other points you make.

During the seminar you asked how a 
path set in the class graph guides the traversal
of an object graph. We define how a class graph path set turns
an object graph into an object graph slice (a subgraph of the object graph).
So while the effect of a strategy at the class graph level is a path set
which in general cannot be summarized by a subgraph of the class graph,
at the object graph level, the effect of a strategy is is to
define a subgraph. Doug pointed that out in the seminar.

Given a flat class graph G (wlog)
and an object graph O, a path set P[S,G] in G turns as follows into
an object slice OS of O. 
A node q of O is in OS if in O there is a path from s to q that is also
a path pcg in P[S,G] if we drop all alternation nodes and edges and inheritance
edges from pcg .
An edge e of O is in OS if there is a path from s to
the end point of e through e that is also
a path pcg in P[S,G] if we drop all alternation nodes and edges and inheritance
edges from pcg .

What is a little confusing is that we say that an object graph path becomes
a class graph path. We mean that we just focus on the labels
on the edges and nodes. The paths however are in different graphs.

You regular expression:
s (=>.(<=.C.=>)*.<=) t
is very intuitive. Its main purpose is to disallow: <=.=>.

I claim that our regular expressions are equivalent:
new: EA* (EI* EC EA*)* EI*
old: ((EI* EC) | EA)* EI*

To summarize: The AP programmer needs the following concepts:

class graph

object graph

strategy graph 

A strategy SS with source s and target t defines a path set
in a class graph G by taking all s-t paths in G that are
expansions of s-t paths in SS.

A path set in G determines an object slice OS of O by eliminating
the alternation related edges and nodes from the path set.

-- Karl

From wand@ccs.neu.edu  Thu Nov  2 14:09:51 2000
Return-Path: <wand@ccs.neu.edu>
From: Mitchell Wand <wand@ccs.neu.edu>
MIME-Version: 1.0
Date: Thu, 2 Nov 2000 14:09:19 -0500 (EST)
To: dem@ccs.neu.edu
Subject: Algorithms for finding paths in object graphs

I thought some more about the discussions we had yesterday, and what
came out is a direct method for doing directed search *in the object
graphs*.  This point of view has the advantage that it has very simple
semantics (definition 3 below).  See how you like it.  Perhaps we can
discuss it in seminar in 2 weeks.

--Mitch 

Def.1  A class graph is a directed graph with a partial order on the
      nodes.  We write c1 -> c2  for the edges ("construction edges")
      and c1 <= c2 for the order ("inheritance" -- c1 is a subclass of
      c2).

We write => for the inverse of <= .

We often think of directed graphs as relations (and vice versa), so we
write C(c1,c2) or c1 C c2 when there is an edge from c1 to c2 in C.

We denote composition of relations by "." eg x (R.S) z iff there
exists a y st xRy and ySz.  We also write x R y S z.  Sometimes we'll
even omit the ".", and write RS. And of course we get to take the
reflexive transitive closure of a relation, denoted R*, as usual.

Def.2  If C is a class graph, then an object graph of C is a directed
      graph O equipped with a map  class : O -> C, such that 

      (1) if class(o1) <= c1 and C(c1,c2), then there exists an o2 st
          O(o1,o2) and class(o2) <= c2  {there are enough edges}

      (2) if O(o1,o2), then class(o1) <=.C.=> class(o2)  {all edges
          are images of ones in C}.

Proposition:  Every class graph C has a non-empty object graph.

Proof:  Construct O as follows:  let the nodes of O be the <=-minimal
nodes of C, and for each such node c, let class(c) = c.  For every c'
s.t.  c <=.C c' , choose an arbitrary minimal c'' <= c', and add an
edge O(c, c'').  

We call the object graph constructed in this way a "naive object graph".

We say an object o has type c iff class(o) <= c .  Note that an
object may have many types.

Def.3  Let p = (o1,..,oN) be a path in O, and let R = (c1,..,cK) be a sequence 
      of classes.  Then p is an R-path iff there is a subsequence o_{j_1}
      ,...o_{j_K} such that for each i, o_{j_i} has type c_i.  j_1
      must be 1 and j_K must be N  (ie the first and last elements of
      the path must be part of the subsequence).

We call R a "requirement".   In Demeter terms, (c1,...,cK) is like "to
c1 to c2 .. to cK"  ("from" is not so interesting).

Prop.  Let s and t be classes.  Then there exists an object graph O
with an (s,t)-path iff s (=>.(<=.C.=>)*.<=) t

Proof.  Let O be an object graph of C with an (s,t)-path.  Then the
path must look like (o1,...,on), where class(o1) <= s, and class(on)
<= t.  Since we have O(o_i,o_{i+1}), we have class(o1) .(<=.C.=>)*
class(on), by condition (2) in the defn of an object graph.  Putting
it all together, we have  s (=>.(<=.C.=>)*.<=) t .

Conversely, assume we have s => c1 (<=C=>) c2 (<=C=>) ... (<=C=>) cn
<= t.  Then construct an object graph as follows: start with the
object graph O constructed in the proposition above.  Then add n new
objects, o1,.., on, with class(o_i) an arbitrary minimal class c_i' <=
c_i.  Add an edge O(o_i,o_i+1) for each i.  This is legal, by
condition (2).  For every other c' such that c_i <=C c', choose an
arbitrary minimal c'' <= c',  and add an edge O(o_i,c''), where c''
here denotes the corresponding node of the "naive" object graph that
we started with.

Given a requirement R, and an object o, we would like to find all the
R-paths in O starting with o.  Unfortunately, this is not feasible:
consider lists that may contain even or odd numbers.  And consider the
requirement (List, Even).  Given a list, we cannot tell in a single
step whether it contains an even number.

So the best we can hope for is to define an "R-slice" starting at o:
given o in O, with class(o) = c0, we want to follow all those edges
that *might* (in some O' extending what we know of O) be part of an
R-path starting at o.

When we are at object o, we must choose which edges to traverse based
only on class(o) and {c' | class(o) (<=.C) c'} (the "declared types"
of the parts of o).

This suggests the following rule:

RULE:  For a requirement (t)  {"to t"} -- Given o1 with class(o1) =
c1, follow an edge (c1,c2) in (<=.C) iff c2 (=>.(<=C=>)*.<=) t .

We can condense this as follows:

POSS(c1,t) = {c2 |  c1 <=.C c2  (=>.(<=C=>)*.<=) t }

These are the "declared types" of the first edges of paths leading
from an object of !class! c1 to an object of !type! t .

The next proposition states that you have to look at each of these edges:

Proposition:  For each c2 in POSS(c1,t), there is an object graph O,
an object o1 of class c1, and a (c1,t)-path such that the second
object o2 in the path is of type c2.

Proof.  Consider the the sequence of classes 

c1 <=.C c2 => c2' (<=C=>) c3 (<=C=>) ... (<=C=>) cn <= t

As in the preceding construction, start with a naive object graph O.
Add to O n new objects o1,..., o_n, with class(o1) = c1, class(o2) =
an arbitrary minimal c2'' <= c2', and class(oi) an arbitraray minimal
c_i' <= c_i.  This gives the required (c1,t)-path.  Complete the
object graph as before:   For every other c' such that c_i <=C c', choose an
arbitrary minimal c'' <= c',  and add an edge O(o_i,c''), where c''
here denotes the corresponding node of the "naive" object graph that
we started with.

Note that POSS(c1,t) can be computed easily by doing transitive
closures, etc.

What about more complex requirements R = (s, t1, t2, ..., tn) ?  Since
the concept of an R-path is compositional (yay!), you can do "waypoint
navigation":  follow the edges in POSS(-,t1) until you get to an
object of type t1.  Then follow the edges in POSS(-,t2) until you get
to an object of type t2, etc.

Algorithm:  searching for an R-path. 

Procedure search(o,R):	
Given an R-path (t1, ...,tn) and an object o in an object graph,
search as follows: 

(1) If o does not have type t1, explore all the edges in
    POSS(class(o),t1). 

(2) If o has type t1, and R is just (t1), then visit o.

(3) If o has type t1 and R is (t1, t2, ...), then search(o,(t2,...,))

This could be implemented in a variety of ways, ranging from inserting
methods (probably n methods) in each class for R, to a DJ-like
first-class long-getter.