The Refinement Relation of Graph-Based Generic Programs

Karl Lieberherr^{1} and Boaz Patt-Shamir^{1}^{2}

1 College of Computer Science Northeastern University Boston, MA 02115, USA

                            lieber@ccs.neu.edu
                    http://www.ccs.neu.edu/home/lieber

2 Dept. of Electrical Engineering–Systems Tel Aviv University Tel Aviv 69978, Israel

                            boaz@eng.tau.ac.il

Abstract. version 4, Sep. 7, 98

This paper studies a particular variant of Generic Programming, called Adaptive Programming (AP). We explain the approach taken by Adaptive Programming to attain the goals set for Generic Programming. Within the formalism of AP, we explore the important problem of refinement: given two generic programs, does one express a subset of the programs expressed by the other? We show that two natural definitions of refinement coincide, but the corresponding decision problem is computationally intractable (co-NP-complete). We proceed to define a more restricted notion of refinement, which arises frequently in the practice of AP, and give an efficient algorithm for deciding it.

1 Introduction

What is Generic Programming (GP)? The organizers of this Dagstuhl workshop view GP to have the following important characteristics:

– Expressing algorithms with minimal assumptions about data abstractions, and vice versa, thus making them as interoperable as possible.

– Lifting of a concrete algorithm to as a general level as possible without losing efficiency, i.e., the most abstract form such that when specialized back to the concrete case the result is just as efficient as the original algorithm.

GP is about parametric polymorphism and we think that non-traditional kinds of parametric polymorphism lead to particularly useful forms of Generic Programming. By non-traditional kinds of parametric polymorphism we mean that parameterization is over larger entities than classes. In this paper we focus on parametrization with entire class graphs and we outline how Adaptive Programming is a form of Generic Programming which attempts to satisfy the two characteristics mentioned above. We show the role of traversal strategies in Adaptive Programming by an analogy to Generic Programming and present new results about traversal strategies. We focus on the concept of graph refinement which is important when traversals are specialized. We show that the obvious definition of refinement leads to a co-NP-complete decision problem and we propose a refinement definition which is computationally tractable and useful for practical applications. The results are summarized in Table 1.

Relationship  Complexity Symbol
path-set-refinement co-NP-complete G_{1} ≤_{N} G_{2}
expansion  co-NP-complete G_{1} ⪯_{N} G_{2}
refinement polynomial G_{1} ⊑_{N} G_{2}

Table 1. Graph relationships for software evolution. N is a mapping of nodes of G_{2} to nodes of G_{1}. G_{1} ≤_{N} G_{2} if and only if G_{1} ⪯_{N} G_{2}. G_{1} ⊑_{N} G_{2} implies G_{1} ≤_{N} G_{2}.

A generic program P defines a family of programs P (G), where G ranges over a set of permissible actual parameters. In this paper we let G range over directed graphs restricted by the program P. Those graphs are abstractions of the data structures on which the program operates. Given two generic programs P_{1} and P_{2}, an important question is whether the programs defined by P_{1} are a subset of the programs defined by P_{2}. We say that P_{1} is a refinement of P_{2}. For example, the generic program P_{1} “Find all B-objects contained in X-objects contained in an A-object” defines a subset of the programs determined by the generic program P_{2} “Find all B-objects contained in an A-object.” P_{1} and P_{2} are generic programs since they are parameterized by a class graph (e.g., a UML class diagram). Furthermore, the computations done by P_{1} are a refinement of the computations done by P_{2}.

Formalizing the notion of refinement between generic programs leads to graph theoretic problems which have several applications. Refinement can be used to define “subroutines” in adaptive programs as well as to define common evolution relationships between class graphs.

1.1 Adaptive Programming (AP)

Adaptive Programming [Lie92,Lie96] is programming with traversal strategies. The programs use graphs which are referred to by traversal strategies. A traversal strategy defines traversals of graphs without referring to the details of the traversed graphs. AP is a special case of Aspect-Oriented Programming [Kic96,KLM^{+}97].

AP adds flexibility and simultaneously simplifies designs and programs. We make a connection between GP (as practiced in the STL community) and AP (see Table 2). In GP, algorithms are parameterized by iterators so that they can be used with several different data structures. In AP, algorithms are parameterized by traversal strategies so that they can be used with several different data structures. Traversal strategies can be viewed as a form of iterators which

Kind  Algorithms Glue  Graphs
GP(STL) Algorithms Iterators Data Structures
AP Adaptive Traversal Class Graphs
Algorithms Strategies

Table 2. Correspondence between GP and AP

are more flexible than ordinary iterators. For details on the parameterization mechanism in AP, see [Lie96,ML98].

2 Traversal Strategies

Traversal strategies (also called succinct traversal specifications) are a key concept of AP. They were introduced in [LPS97,PXL95] together with efficient compilation algorithms. The purpose of a traversal strategy is to succinctly define a set of paths in a graph and as such it is a purely graph-theoretic concept. Since there are several works which demonstrate the usefulness of traversal strategies to programming [Lie96,PXL95,AL98,ML98] we are switching now to a mathematical presentation of the concepts underlying strategies without giving many connections to the practice of programming.

There are different forms of traversal strategies the most general of which are described in [LPS97]. In this paper we only consider a special case: positive strategy graphs. Positive strategy graphs express the path set only in a positive way without excluding nodes and edges. Positive strategies are defined in terms of graphs and interpreted in terms of expansions.

2.1 Definitions

A directed graph is a pair (V, E) where V is a finite set of nodes, and E ⊆ V ×V is a set of edges. Given a directed graph G = (V, E), a path is a sequence p = ⟨v_{0}v_{1} … v_{n}⟩, where v_{i} ∈ V for 0 ≤ i ≤ n, and (v_{i−1}, v_{i}) ∈ E for all 0 < i ≤ n.

We first define the notion of an embedded strategy graph.

Definition 1. A graph S = (V_{1}, E_{S}) with a distinguished source node s and a distinguished target node t is said to be an embedded strategy graph of a graph G = (V_{2}, E) if V_{1} ⊆ V_{2}.

Intuitively, a strategy graph S is a sort of digest of the base graph G which highlights certain connections between nodes. In the applications, a strategy graph plays the role of a traversal specification and the base graph plays the role of defining the class structure of an object-oriented program. For example, a strategy graph could say: Traverse all C-objects which are contained in Bobjects which are contained in A-objects. This would be summarized as a graph with three nodes A,B,C and an edge from A to B and an edge from B to C. In this paper, the base graphs are just graphs without the embellishments usually found in a class structure. The edges of the simplified class graphs we use here represent directed associations between classes (sometimes also called part-of relationships). (In [LPS97,PXL95] it is shown how to generalize the concept of a strategy graph for general class graphs used in object-oriented programs.) To complicate matters, strategy graphs can also play the role of class graphs. In this case refinement between strategy graphs means refinement between class graphs in the sense that we make the object structures more complex while preserving their essential shape.

A strategy graph S of a base graph G defines a path set as follows. We say that a path p is an expansion of a path p′ if p′ can be obtained by deleteing some elements from p. We define PathSet_{st}(G, S) to be the set of all s − t paths in G which are expansions of any s − t path in S.

Unlike embedded strategies, general strategies allow the node sets of the graphs S and G to be disjoint by using a “name mapping” between them.

Next we define the concept of a strategy graph independent of a base graph.

Definition 2. A strategy graph T is a triple T = (S, s, t), where S = (C, D) is a directed graph, C is the set of strategy-graph nodes, D is the set of strategy-graph edges, and s, t ∈ C are the source and target of T , respectively.

The connection between strategies and base graphs is done by a name map, defined as follows.

Definition 3. Let S = (C, D) be a graph of a strategy graph and let G = (V, E) be a base graph. A name map for S and G is a function N : C → V. If p is a sequence of strategy-graph nodes, then N (p) is the sequence of base graph nodes obtained by applying N to each element of p.

We next define expansion in the presence of a name map.

Definition 4. Let V_{1}, V_{2} be arbitrary sets, and let N : V_{2} → V_{1} be a function. We say that a sequence p_{1} of elements of V_{1} is an expansion under N of a sequence p_{2} of elements of V_{2} if N (p_{2}) is a subsequence of p_{1}, where N is applied to each element in the sequence.

With this definition, we define the concept of a path set.

Definition 5. Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be directed graphs, let N : V_{2} → V_{1} be a function, and let s, t ∈ V_{2}. PathSet_{st}(G_{1} , N , G_{2} ) is defined to be the set of all paths in G_{1} which are expansions under N of any s − t path in G_{2}.

The identity of s and t is assumed to be fixed, and we shall omit subscripts henceforth.

Using the terminology above, if the name map is the identity function I, then G_{2} is an embedded strategy for G_{1}. Note, for example, that PathSet(G, I, G) is exactly the set of all s − t paths in G. (Exercise for the reader: Prove that PathSet(G, I, G) = PathSet(G, I, H ), where H is the directed graph consisting of the single edge (s, t).)

We now turn to the first definition of the graph refinement relations. For the case of embedded strategy graphs, we say that a strategy graph G_{1} is a pathset-refinement of strategy graph G_{2} if for all base graphs G_{3} for which G_{1} and G_{2} are strategies, PathSet(G_{3} , G_{1} ) ⊆ PathSet(G_{3} , G_{2} ).

Example 1. Strategy graph G_{2}: Nodes A,B. Edges (A,B). Strategy graph G_{1}: Nodes A,B,X,Y. Edges (A,X), (X,B), (A,Y), (Y,B). Source A, Target B. Name map is the identity map. G_{1} is a path-set-refinement of G_{2}.

In the presence of name maps, the situation is more complex: First, we need the following technical concept (see Figure 1).

Fig. 1. Illustration for a function h extending g under f.

Definition 6. Let A, B, C be sets, and let f : A → B, g : A → C, h : B → C be functions. We say that h extends g under f if for all a ∈ A we have h(f(a)) = g(a).

Definition 7. Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be directed graphs, and let N : V_{2} → V_{1} be a function. We say that G_{1} is a path-set-refinement under N of G_{2}, denoted G_{1} ≤_{N} G_{2}, if for all directed graphs G_{3} = (V_{3}, E_{3}) and functions N_{1} : V_{1} → V_{3} and N_{2} : V_{2} → V_{3} such that N_{1} extends N_{2} under N, we have that PathSet(G_{3} , N_{1} , G_{1} ) ⊆ PathSet(G_{3} , N_{2} , G_{2} ).

Note that if G_{1} ≤_{N} G_{2}, then usually G_{2} is the “smaller” graph: intuitively, G_{2} is less specified than G_{1}.

We now define another relation for graph refinement, called “expansion.” This relation is more useful for exploring properties of graph refinement. For the case of embedded strategy graphs, we say that a strategy graph G_{1} is an expansion of strategy graph G_{2} if for any path p_{1} (from s to t) in G_{1} there exists a path p_{2} (from s to t) in G_{2} such that p_{1} is an expansion of p_{2}. In example 1, G_{1} is an expansion of G_{2}.

The general definition of expansion for positive strategies is:

Definition 8. Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be directed graphs, and let N : V_{2} → V_{1} be a function. We say that G_{1} is an expansion under N of G_{2}, denoted G_{1} ⪯_{N} G_{2}, if for any path p_{1} ∈ PathSet(G_{1} , I, G_{1} ) there exists a path p_{2} ∈ PathSet(G_{2} , I, G_{2} ) such that p_{1} is an expansion under N of p_{2}.

We now prove equivalence of the notions of “path-set-refinement” and “expansion”.

Theorem 1. Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be directed graphs, and let N : V_{2} → V_{1} be a function. Then G_{1} ⪯_{N} G_{2} if and only if G_{1} ≤_{N} G_{2}.

This theorem tells us that we can use the simpler definition of expansion instead of the more complex definition of path-set-refinement which involves quantification over general graphs. Proof: Suppose first that G_{1} ⪯_{N} G_{2}. Let G_{3} be any graph, and suppose that N_{1}, N_{2} are as in Definition 7. Let p_{3} ∈ PathSet(G_{3} , N_{1} , G_{1} ). To show that G_{1} ≤_{N} G_{2}, it suffices to prove that p_{3} ∈ PathSet(G_{3} , N_{2} , G_{2} ). This can be seen as follows. By Definition 5, there exists a path p_{1} ∈ PathSet(G_{1} , I, G_{1} ) such that p_{3} is an expansion of p_{1} under N_{1}, i.e., N_{1}(p_{1}) is a subsequence of p_{3}. Since G_{1} ⪯_{N} G_{2}, we have by Definition 8 that there exists a path p_{2} ∈ PathSet(G_{2} , I, G_{2} ) such that p_{1} is an expansion of p_{2} under N, i.e., N (p_{2}) is a subsequence of p_{1}. It therefore follows that N_{1}(N (p_{2})) is a subsequence of p_{3}, and since N_{1} extends N_{2} under N, we get p_{3} ∈ PathSet(G_{3} , N_{2} , G_{2} ) as desired.

Next, suppose that G_{1} ≤_{N} G_{2}. Let p_{1} ∈ PathSet(G_{1} , I, G_{1} ). We need to prove that there exists a path p_{2} ∈ PathSet(G_{2} , I, G_{2} ) such that N (p_{2}) is a subsequence of p_{1}. This follows immediately from Definition 7, which says (by substituting G_{2} for G_{3}, I for N_{1}, and N for N_{2}) that PathSet(G_{2} , I, G_{2} ) ⊆ PathSet(G_{1} , N , G_{2} ).

The following problem arises naturally in many applications of strategies.

Graph Path-set-refinement Problem (GPP)

Input: Digraphs G_{1} = (V_{1}, E_{1}), G_{2} = (V_{2}, E_{2}) with s_{1}, t_{1} ∈ V_{1}, and a function N : V_{2} → V_{1}. Question: Does G_{1} ≤_{N} G_{2} hold true?

Unfortunately, it turns out that deciding GPP is hard. To prove that, we first consider a weakened version of GPP, defined as follows. Call an edge in a strategy redundant if its removal does not change the path sets defined by the strategy. For example, if there exists an edge from the source to the target, then all other edges are redundant, since all source-target paths are expansions of this edge anyway! More formally, an edge (u, v) in a strategy graph G is redundant if G ≤_{I} G − {(u, v)}. We define the following decision problem.

Redundant Strategy Edge (RSE)

Input: A digraph G = (V, E) with source and target nodes s, t ∈ V, and a distinguished edge (u, v) ∈ E. Question: Is the distinguished edge (u, v) redundant?

Theorem 2. RSE is co-NP-complete.

Proof: Consider the complement problem, namely, given G, s, t and (u, v) as above, whether G−{(u, v)} is a strict path-set-refinement of G. Call this problem co-RSE. We prove the theorem by showing that co-RSE is NP-complete. We first give an NP algorithm for co-RSE:

1. Generate a sequence p of nodes in V.

2. If p is not a path in G, halt the computation.

3. If p is an expansion under I of a path in G − {(u, v)}, halt the computation.

4. Return “(u, v) is not redundant.”

Next, we prove that co-RSE is NP-hard. This is done by reducing 3SAT [GJ79] to co-RSE. Fix an instance of 3SAT with m clauses c_{1}, …, c_{m} and n variables x_{1}, …, x_{n}. That is, we are given a Boolean formula, where each clause c_{i} consists of three literals y_{i1}, y_{i2}, y_{i3}, and each literal is either a variable x_{j} or its negation ¬x_{j}. We transform the formula to an instance of co-RSE as follows (see Figure 2 for an example).

Fig. 2. An example of the reduction linking satisfiability with non-redundancy of distinguished edge: the Boolean formula is (x_{1} ∨ x_{2} ∨ ¬x_{3}) ∧ (¬x_{1} ∨ x_{2} ∨ ¬x_{3}). The dashed arrow connecting d_{2} and u_{1} represents the distinguished edge. (¬ is shown as −.)

1. For each clause c_{i}, create four nodes labeled d_{i}, z_{i1}, z_{i2}, z_{i3}.

2. For each variable x_{j}, create three nodes labeled u_{j}, w_{j}, ¬w_{j}.

3. Create a source node s and a target node t. Below, we identify for convenience s = d_{0} and t = u_{n+1}.

4. For i = 1, …, m and k = 1, 2, 3, create edges (z_{ik}, d_{i}) and (d_{i−1}, z_{ik}).

5. For i = 1, …, n, create edges (u_{i}, w_{i}), (u_{i}, ¬w_{i}) and (w_{i}, u_{i+1}), (¬w_{i}, u_{i+1}).

6. For i = 1, …, m and k = 1, 2, 3, connect the node representing the literal y_{ik} and its corresponding w node. Specifically, if y_{ik} = x_{j}, create the edge (z_{ik}, w_{j}), and if y_{ik} = ¬x_{j}, create the edge (z_{ik}, ¬w_{j}).

7. Create an edge (d_{m}, u_{1}).

8. The co-RSE instance is given by G as defined above, where the distinguished edge is (d_{m}, u_{1}).

We now need to show that the instance of co-RSE constructed by the transformation is a YES instance if and only if the Boolean formula is satisfiable. First, we define a one-to-one correspondence between truth assignments and s−t paths containing the distinguished edge (d_{m}, u_{1}): each such path visits exactly one of w_{j}, ¬w_{j} for 1 ≤ j ≤ n; if w_{j} is in the path, we will have FALSE assigned to x_{j} in the corresponding truth assignment, and if ¬w_{j} is in the path, we assign TRUE to x_{j}.

Note that any s − t path in G − {(d_{m}, u_{1})} (i.e., a path not using the distinguished edge) must use one of the edges created at Step 6 of the transformation.

To complete the proof, observe that there exists a path which is not an expansion of a path in G − {(d_{m}, u_{1})} if and only if there exists a path passing through the distinguished edge which does not contain both endpoints of any of the edges created in Step 6. This in turn holds (using the corresponding truth assignment) if and only if there is a literal with value TRUE in each clause: the literals are connected to their FALSE values. It follows that the co-RSE instance is a YES instance if and only if the Boolean formula is satisfiable.

A direct implication of Theorem 2 is that the problem of finding a strategy with minimal representation is hard. With regard to the main point of this paper, we have the following easy corollary.

Corollary 1. GPP is co-NP-Complete.

This corollary tells us that when we build tools for AP we cannot use the general definition of expansion since it would result in a slow design tool for large applications. Proof: By reduction from RSE: given an instance (G, s, t, (u, v)) of RSE, define an instance of GPP by G_{1} = G − {(u, v)}, G_{2} = G, and ask whether G_{1} ≤_{I} G_{2}.

3 The Refinement Relation

In this section we define a more stringent version of the graph path-set-refinement relation, called the refinement relation. We argue that this relation is central to software engineering practices. We show that the path-set-refinement relation is a generalization of the refinement relation, and we give an efficient algorithm for deciding the refinement relation.

In this section we invoke a mathematical pattern called the Tractable Specialization Pattern (TSP) which has several applications in computer science. TSP is defined as follows: Given is a decision problem which has a high complexity but which we need to solve for practical purposes. We define a more strict version of the decision problem for which we can solve the decision problem more efficiently. The goal of the restricted version is that it does not disallow too many of the inputs which are occurring in practice. Fig. 3 shows two applications of TSP. The first is to graph properties in this paper and the second to contextfree grammar properties in language theory [HU79]. The second column in Fig. 3 shows a decision problem with its complexity. The third column shows a stricter form of the decision problem with the hopefully lower complexity.

Area  Decision Problem  Stricter
Graphs  path-set-refinement (co-NP-complete) refinement (polynomial)
Grammars ambiguous (undecidable)  LL(1) (polynomial)

Table 3. Applications of the Tractable Specialization Pattern

We first consider the case of embedded strategy graphs. Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be directed graphs with V_{2} a subset of V_{1}. We say that G_{1} is a refinement of G_{2}, denoted G_{1} ⊑ G_{2}, if for all u, v ∈ V_{2} we have that (u, v) ∈ E_{2} if and only if there exists a path in G_{1} between u and v which does not use in its interior a node in V_{2}.

Example 2. Strategy graph G_{2}: Nodes A,B,C. Edges (A,B), (B,C). Strategy graph G_{1}: Nodes A,B,C. Edges (A,C), (C,B), (B,C)). Source A, Target C. Name map is identity map. G_{1} is not a refinement of G_{2}. For the edge from A to B in G_{2} there is no path in G_{1} from A to B which does not go through C. However, strategy graph G_{3}: Nodes A, B, C, X. Edges (A,X), (X,B), (B,C) is a refinement of G_{2}.

The intuition behind the graph refinement relation is that we are allowed to replace an edge with a more complex graph using new nodes. In example 2, we replace the edge (A,B) by the graph (A,X),(X,B), where X is a new node and not one of A,B or C. Informally, G_{1} is a refinement of G_{2} if the connectivity of G_{2} is exactly and “without surprises” in G_{1}. ”Without surprises” means that the nodes of G_{2} can appear on paths only as advertised by G_{2}. For example, if G_{2} has nodes A, B and C and an edge (A,B) but not an edge (A,C) then a path A ... C ... B in G_{1} is disallowed. We first need the following technical concepts to define graph refinement in the presence of a name map.

Definition 9. Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be directed graphs, and let N : V_{2} → V_{1} be a function. Given a path p, let first(p) and last(p) denote its first and last nodes, respectively. A path p_{1} in G_{1} (not necessarily an s − t path) is pure if first(p) = N (u) and last(p) = N (v) for some u, v ∈ V_{2}, and none of the internal nodes of p is the image of a node in V_{2}.

We define refinements as strategies whose pure-path connectivity is the same as the edge-connectivity in the super-strategy. Formally, we have the following definition.

Definition 10. Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be directed graphs, and let N : V_{2} → V_{1} be a function. We say that G_{1} is a refinement of G_{2} under N, denoted G_{1} ⊑_{N} G_{2}, if for all u, v ∈ V_{2} we have that (u, v) ∈ E_{2} if and only if there exists a pure path in G_{1} between N (u) and N (v).

To justify Definition 10, we remark that the notion of strategies is particularly useful in evolution of software, where it is often the case that some crude concepts (and objects) are refined in the course of development. In such scenarios, refining an edge to a more complex structure is usually done with the aid of a refinement. It is important to check whether such an evolution leads to modifying the connectivity structure of the strategy, which is the question of deciding the refinement relation.

The following theorem states that the refinement relation is a subrelation of the path-set-refinement relation.

Theorem 3. If G_{1} ⊑_{N} G_{2}, then G_{1} ≤_{N} G_{2}.

Proof: Suppose that G_{1} ⊑_{N} G_{2}. By Theorem 1, it is sufficient to prove that G_{1} ⪯_{N} G_{2}. Let p any s − t path in G_{2}. Decompose p = p_{0}p_{1} ⋯ p_{n}, where each p_{i} is a pure path (this is possible since s, t are in G_{2}). By definition, we have that the sequence s = first(p_{0}), first(p_{1}), …, first(p_{n}), last(p_{n}) = t is a path in G_{2}. It follows that any s − t path in G_{1} is an expansion of an s − t path in G_{2}, and hence G_{1} ≤_{N} G_{2}.

The converse of Theorem 3 does not hold as demonstarted by example 3.

Example 3. We give an example of two graphs G_{1} and G_{2}, where G_{1} is an expansion of G_{2} but G_{1} is not a refinement of G_{2}. This proves that expansion does not imply refinement. An entire family of such examples is obtained by taking for G_{1} the directed cycle for n nodes and for G_{2} the complete graph for n nodes. As source we select the first node and as target the nth node. For n=3: G_{1}: Nodes A,B,C. Edges: (A,B), (B,C), (C,A). G_{2}: Nodes A,B,C. Edges: all ordered pairs. G_{1} is an expansion of G_{2} since G_{2} is complete and therefore it has all the paths we want. G_{1} is not a refinement of G_{2} because for (C,B) in G_{2} there is no path in G_{1} from C to B which does not use A, i.e., there is no pure path from C to B in G_{1}.

We now give an algorithm to decide whether G_{1} ⊑_{N} G_{2}. This is done by a simple graph search algorithm defined as follows.

First Targets Search (FTS)

Input: Digraph G = (V, E) a node v_{0} ∈ V, and a set of targets T ⊆ V.

Output: A subset T′ ⊆ T of the targets, such that for each t ∈ T′, there exists a path in G from v_{0} to t which does not contain any other target.

It is easy to implement FTS (using BFS or DFS) in linear time, assuming that we can test in constant time whether a node is a target. In Figure 3 we give a BFS-based algorithm, using a FIFO queue Q.

Procedure FTS(G, v_{0}, T)

mark v_{0} visited

insert v_{0} to tail of Q while Q ≠ ∅

remove u from head of Q

if u ∈ T then add u to output set  //…and don’t explore this path further

else for all v such that (u, v) ∈ E

if v is not marked visited then mark v visited insert v to tail of Q

end if end if

end while

Fig. 3. Algorithm for First Targets Search

Running FTS can detect superfluous or missing connectivity in G_{1}, when compared to G_{2} under N. The algorithm for deciding the refinement relation proceeds as follows.

Input: G_{1} = (V_{1}, E_{1}), G_{2} = (V_{2}, E_{2}), N : V_{2} → V_{1}.

1. Let T ⊆ V_{1} be the image of V_{2} under N, i.e., T = {N (v) | v ∈ V_{2}}.

2. For each node v ∈ V_{2}:

(a) Perform FTS from N (v) with targets T in G_{1}. Let the resulting set be T_{v}, i.e., T_{v} = FTS(G_{1}, N (v), T).

(b) If there exists u ∈ V_{2} such that (v, u) ∉ E_{2} and N (u) ∈ T_{v}, or (v, u) ∈ E

and N (u) ∉ T_{v}, return “G_{1} ⋢_{N} G_{2}” and halt.

3. Return “G_{1} ⊑_{N} G_{2}.”

The running time of the algorithm is O(|E_{1}| · |V_{2}|).

3.1 Related Work

This paper studies refinement relations between graphs. The Subgraph Homeomorphism problem (SH) is related but different from the problems studied here.

Definition 11. SH instance: graph G = (V, E) question: does G contain a subgraph homeomorphic to H, i.e., a subgraph G′ = (V′, E′) that can be converted to a graph isomorphic to H by repeatedly removing any vertex of degree 2 and adding the edge joining its two neighbors?

SH is NP-complete for variable H. See [FHW80] for general results. SH supports only limited graph refinements because only vertices of degree 2 may be removed.

[GJ79] mentions other refinement-style problems, such as graph contractability, graph homomorphism and D-morphism but none of those problems match our definition of graph refinement.

4 Conclusions

We have discussed how Generic Programming through parameterization of programs with entire graph structures (as opposed to only single classes) leads to more flexible programs. We introduced graph theory which is needed to better apply and understand this new form of generic programming, called Adaptive Programming.

We introduced the concept of refinement between graphs which has the following applications: It can be applied to 1. check efficiently whether one traversal is a subtraversal of another (path-set-refinement = expansion). 2. check whether one class graph is a generalization of another class graph so that the containment relationships are preserved (refinement). This kind of graph generalization relation is useful for automating the evolution of adaptive programs. 3. check whether an adaptive program defines a subset of the programs defined by another adaptive program (refinement). The results are summarized in Table 1.

5 Acknowledgements

We would like to thank Mira Mezini, Joshua Marshall, Doug Orleans, and Johan Ovlinger for the ideas they contributed to the paper. This work has been partially supported by the Defense Advanced Projects Agency (DARPA), and Rome Laboratory, under agreement number F30602-96-2-0239. The views and conclusions herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Defense Advanced Research Projects Agency, Rome Laboratory or the U.S. Government.

http://www.ccs.neu.edu/research/demeter/biblio/graph-refine.html contains further information about this paper including links to online versions of some related papers.

References

[AL98] Dean Allemang and Karl J. Lieberherr. Softening Dependencies between Interfaces. Technical Report NU-CCS-98-07, College of Computer Science, Northeastern University, Boston, MA, August 1998.

[FHW80] S. Fortune, John Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111–121, 1980.

[GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability. Freeman, 1979.

[HU79] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

[Kic96] Gregor Kiczales. Aspect-oriented programming. ACM Computing Surveys, 28A(4), December 1996.

[KLM^{+}97] Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Lopes, Jean-Marc Loingtier, and John Irwin. Aspect-oriented programming. In European Conference on Object-Oriented Programming, pages 220–242. Springer Verlag, 1997.

[Lie92] Karl J. Lieberherr. Component enhancement: An adaptive reusability mechanism for groups of collaborating classes. In J. van Leeuwen, editor, Information Processing ’92, 12th World Computer Congress, pages 179–185, Madrid, Spain, 1992. Elsevier.

[Lie96] Karl J. Lieberherr. Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns. PWS Publishing Company, Boston, 1996. ISBN 0-534-94602-X, entire book at www.ccs.neu.edu/research/demeter.

[LPS97] Karl J. Lieberherr and Boaz Patt-Shamir. Traversals of Object Structures: Specification and Efficient Implementation. Technical Report NU-CCS-97-15, College of Computer Science, Northeastern University, Boston, MA, Sep. 1997.

[ML98] Mira Mezini and Karl Lieberherr. Adaptive plug-and-play components for evolutionary software development. Technical Report NU-CCS-98-3, Northeastern University, April 1998. To appear in OOPSLA ’98.

[PXL95] Jens Palsberg, Cun Xiao, and Karl Lieberherr. Efficient implementation of adaptive software. ACM Transactions on Programming Languages and Systems, 17(2):264–292, March 1995.