Graph Refinement
This paper explores several graph relationships relevant to AP. Advances the state-of-the-art of formal definitions and properties/algorithms for evolving generic programs of the adaptive style.

The paper is available as Springer Verlag Lecture Notes:

@INPROCEEDINGS{graph-refinement2:patt-shamir,
AUTHOR = "Karl Lieberherr and Boaz Patt-Shamir",
TITLE = "The Refinement Relation of Graph-Based Generic Programs",
BOOKTITLE = "1998 Schloss Dagstuhl Workshop on Generic Programming",
YEAR = "2000",
ADDRESS = "",
PAGES = "40--52",
EDITOR = "M. Jazayeri and R. Loos and David Musser",
PUBLISHER = "Springer",
NOTE =  "LNCS 1766".
}

The paper is available as technical report:


Bibtex entry:

@TECHREPORT{graph-refinement:patt-shamir,
AUTHOR       = "Karl Lieberherr and Boaz Patt-Shamir",
TITLE        = "{The Refinement Relation of Graph-Based Generic Programs}",
INSTITUTION  = "College of Computer Science, Northeastern University",
YEAR         = 1998,
MONTH        = "September",
NUMBER       = "{NU-CCS-98-10}",
ADDRESS      = "Boston, MA"
}                 

An unpublished key reference to understand this paper: Latest paper on Traversal Strategies

Online versions of recent Demeter/AP papers.

Further information about the paper:

Roles played by strategy graph, corresponding class graph and a refined strategy.

roles played | strategy graph | base graph  | refined strategy
--------------------------------------------------------------------
scenario 1   | traversal spec | class graph | subtraversal
--------------------------------------------------------------------
scenario 2   | class graph    | expanded    | disciplined, expanded
                              | class graph |    class graph   
--------------------------------------------------------------------
In scenario 1, we have the typical roles: the strategy graph defines a path set in a class graph which itself defines traversals in object graphs (not shown). A refined strategy defines a subtraversal where only a subset of the paths is in the path set.

In scenario 2, we have the "new" roles: the strategy graph plays the role of a class graph which defines a "view" of a more complex class graph. We also call such a view an interface class graph (ICG). The base graph as well as the refined strategy correspond to more complex class graphs.

It makes sense to require compatability between the strategy graph and the base graph.

{\em Given graphs G$_{1}$=(V$_{1}$,E$_{1}$) and
G$_{2}$=(V$_{2}$,E$_{2}$)
and a name map N: V$_{2}$ $\to$ V$_{1}$,
\noindent G$_{1}$ is compatible with
G$_{2}$ } $\Longleftrightarrow$
{\em
$\forall$
e = (e$_{s}$, e$_{t}$) $\in$ E$_{1}$,
$\exists$ p $\in$ Paths[G2](N(e$_{s}$), N(e$_{t}$))} 
The intuition is that each edge of the ICG defines a path in the class graph. This means that the interface "matches" the class graph in terms of paths ; we can embed the paths in the ICG in the paths in the class graph. We use the compatability concept in two stages. At the adaptive level we check that the ICG is compatible with each strategy (graph) specified in the behavior definition part of an APPC. At the instantiation level we check that the concrete class graph is compatible with the interface class graph.

A refined strategy is compatible with the non-refined strategy, according to the definitions.

It is useful to define equivalence between strategy graphs. Equivalence holds if refinement holds in both directions, possibly with different name maps.

Example:
Strategy graph G1: Nodes A,B; Edges (A,B)
Strategy graph G2: Nodes A,B,C; Edges (A,B) (A,C) (C,B)
G1 and G2 are equivalent according to all three refinement definitions.

We need a simple example, where G1 is an expansion of G2 but G1 is not a refinement of G2.

G2: Nodes: A,B,C Edges: (A,B) (B,C)
G1: Nodes: A,B,C Edges: (A,C) (C,B) (B,C)
Source: A
Target: C
Name map: identity.
G1 is not a refinement of G2. But G1 is an expansion of G2. NO! since for (A,C) there is no path in G2 from A to C so that (A,C) is an expansion of that path.

This works (a nicer example is in the paper): G2: Nodes: A,B,C,D. Edges: (A,B) (B,C) (A,D) (D,C). G1: Nodes: A,B,C,D. Edges: (A,B) (B,A) (A,D) (D,C). Source A, Target C.

G1 is an expansion of G2 because: There are two kinds of paths in G1 from Source to Target

A (B A)* D C
A D C
The corresponding paths in G2 are:
A B C
A D C
and the paths in G1 are expansions of the corresponding paths in G2

However, G1 is not a refinement of G2: The edge (B,C) in G2 defines an empty path set in G1 if we are not allowed to go through node A.

There is a connection between no-surprise strategies and graph refinement. A no surprise strategy is a strategy with node set M where each strategy edge has the constraint "bypass all of M" associated with it. If we require that each strategy edge defines a non-empty path set in the base graph, then we have: The base graph is a refinement of the strategy graph.

The paper talks only about three relations. There is a fourth one, called compatability which is a kind of expansion in the other direction. Below is a discussion of the relevant relations, including compatability.

1. We want to define subtraversals. why important: want to be sure we get only a subset of paths satisfied by: path-set-refinement 2. Paths in base graph G1 exist in condensed form in strategy graph G2. why important: when generalizing a class graph we don't want to introduce new paths satisfied by: expansion 3. Paths in strategy graph G2 exist in expanded form in base graph G1. why important: computation requires the full G2 (this is the case most of the time) satisfied by: compatability (not yet in paper) polynomial: check for each strategy graph edge whether it defines a non-empty path set. 4. We want to generalize a graph G2 to a graph G1 so that the connectivity of G2 is "without surprises" in G1. why important: adaptive program will generalize properly and run correctly. satisfied by: refinement polynomial: For all pairs (u,v) in V2 compute PathSet(G1,(u,v) bypassing E2) Check whether non-empty iff (u,v) in E2. 5. Given two generic programs (strategies), does one express a subset of the programs expressed by the other? satisfied by: refinement Note: compatability and refinement are closely related. Both operate on pairs of nodes of the strategy graph.

Relevant email: >> from Doug Orleans

Hi Boaz:

>> >
>> >5) All of the examples use the identity function name map.  Maybe name 
>> >   maps can be discarded altogether?  Or else you should provide an
>> >   interesting name map example, e.g. one that creates a cycle from a
>> >   line strategy.
>>
>The name map is no more than an annoying technicality for the most part.

For stating and proving the theorems it would be nice if
we could operate without name map. To prove the general case
we could use a metatheorem: If a property holds with the identity
name map then it also holds with a general name map.

Is this doable?

>The only situtaion where the name map is interesting is when is it's not
>one-to one, or, more commonly, if it not onto. In the latter case it is
>helpful since it indicates which set id the bigger one (running
>sometimes contrary to intuition); we have never dealt with non
>one-to-one name maps. Any thoughts?...
>

We have dealt with non one-to-one mappings and Doug is
adding this capability to the AP library. Johan is using
this capability in his class graph views where the
strategy graph (called class graphview)
may be much bigger than the class graph.
The favorite example is the in-laws example.

-- Karl