Printer Friendly

A Software Engineering Perspective on Algorithmics.

1. INTRODUCTION

By a component we mean an encapsulated piece of code, which is not intended to be a stand-alone module, but to perform a specific task within a large software package or even within several distinct software packages. For example, every subroutine may be viewed as a component in this sense, because the functional details are encapsulated by the interface of the subroutine. Abstract data types (see Appendix B) are a more sophisticated example of components in this sense, because unlike subroutines, they are able to encapsulate state information in addition to the pure functionality.

We will discuss the problem of designing efficient, adaptable implementations of algorithm components. In practice, adaptability is important for several reasons:

--Throughout the lifetime of a project, the requirements on the functionality of a single component may change repeatedly. Reimplementing this component from scratch repeatedly is expensive and often infeasible. Extensive modifications of the core of the component are error-prone(1) and also often infeasible. In particular, extensive modifications of sophisticated algorithmic codes are error-prone. Ideally, adapting an algorithm component to changing requirements should amount to straightforward "error-proof" modifications of a few small, nonalgorithmic pieces of customization code (see Appendix A for the exact usage of this term in this paper).

--Often, software is implemented in a prototypical fashion. This means that first a raw prototype is implemented, which is then refined step-by-step throughout several development cycles. An example is the experimental development of algorithms. In larger projects, such a prototypical approach is feasible only if all components are easily customizable to new, revised versions of the software package.

--Implementing complex components (e.g. sophisticated algorithms) is expensive and requires special expertise. In this respect, it is desirable to have (in-house or third-party) repositories of complex components, which are reusable in many different contexts. However, to be widely reusable, a component must be adaptable to a large range of possible requirements, which are potentially unforeseen in the design phase of this component.

Many libraries offer efficient data structures and algorithms for various algorithmic problem domains. However, an implementation of an algorithm in a library need not fit seamlessly into every application. The integration may enforce significant overhead both in development/maintenance and in run-time efficiency. In some cases, this overhead may be so large that reimplementing an algorithm from scratch might be more practical than reusing an existing implementation.

In summary, the problem of designing efficient, adaptable algorithm components is apparently not satisfactorily understood.

Intent. As a field of research the topic "practical requirements on algorithm components" is quite new and not yet mature. So far, the practical experiences of algorithmicians have not made their way into a systematic basis for discussions, evaluations, and comparisons of design and programming techniques. It is my feeling that typical threads of argumentation found in the literature are too unspecific. For example, the statement of criteria is often limited to "maintainability" and "reusability," which are rather vague criteria. This is certainly not a sufficient basis for more than an ad hoc argumentation.

The main intent of this paper is to demonstrate that a basis for serious discussions, evaluations, and comparisons is possible and helpful. The core is a set of concrete goals, which try to communicate practical experiences concerning the question of what unspecific goals like "maintainability" and "reusability" really mean in algorithmic software development. These concrete goals are quite general and widely problem-independent and might appear ubiquitously in all fields of algorithmics. To illustrate, motivate, and justify this selection of goals, an extensive requirements analysis for an example from the realm of graph and network algorithms is presented: Dijkstra's algorithm for shortest paths in networks and its application in a concrete scenario.

However, our understanding of the various facets of the problems involved in designing adaptable algorithm components is still limited. It seems that the example chosen is quite close to the "borderline" between the aspects that are well understood and the aspects that are not. Here, the problem of adaptability is highly nontrivial and complex, but relatively well understood--well enough to draw a sound (yet probably nonexhaustive) set of concrete goals from it. Hence, this example may serve as a good "acid test" for programming methodologies in view of the state of the art. Evaluating a programming methodology through such an acid test means designing an algorithm component in the spirit of this methodology and evaluating this component in view of the concrete goals.

This approach may be called "analysis by checklist." The list of concrete goals is the checklist, and for each goal one can check whether or not it is addressed by a programming methodology, and if so, how well this methodology fulfills the goal.

Clearly, this paper does not--and cannot--cover all relevant aspects of the problem. The selection and ranking of criteria and the review of the literature in view of these criteria is necessarily subjective and reflects my bias. In particular, the set of concrete goals is to be regarded as a systematic, yet preliminary starting point for discussion. Other researchers may contribute other viewpoints (and may use the proposed approach as a pattern for formulation).

A single example cannot serve as the ultimate "acid test." However, it seems that a representative list of test cases is not yet available and will require a great deal of future research. For this purpose, not only the concrete set of presented goals is submitted to discussion by this paper; the general methodological approach--an extensive test case and a set of concrete goals derived from this case--is also submitted as a future discussion topic.

Overview. In Section 2, we will systematically discuss the obstacles that stand in the way of efficient, adaptable implementations of graph algorithms. We will identify two key problems: flexible choice in the organizing of underlying data and flexible integration of algorithms into software packages. Then, in Section 3, we will discuss the problem in view of a specific example, namely the problem of finding shortest paths in networks and its application to traffic information systems.

In Section 4, we will review the intent of this paper in light of this case study. Afterwards, in Section 5, we will conclude a couple of concrete, problem-independent goals from this case study. The scope of these goals will be analyzed more systematically in Section 6. Section 7 is devoted to the review of existing approaches. This includes a systematic review of the author's work in this field, which is summarized in Gluche et al. [1998], Kuhl et al. [1996, 1997] and Weihe [1997, 1998]. See http://www.or.uni-bonn.de/card-weihe. eng.html for further details of this research. See also http://www.mpi-sb.mpg. de/LEDA/MANUAL/Graphs_Iterators. html and http://www.mpi-sb.mpg.de/ LEDA/friends/git.html for an integration of these concepts in the Library of Efficient Data Structures and Algorithms (LEDA, cf. Mehlhorn and Naher [1995]). Finally, Section 8 briefly discusses the problem how to document adaptable algorithm components.

Audience and required background. This paper addresses people working in algorithmics, in software engineering, and also in the various application domains of algorithmics, who are interested in the software-engineering aspects of algorithmics.

Reading this paper requires some basic background knowledge in algorithmics, notably in graph algorithmics. Introductory chapters of textbooks on graph algorithms and Dijkstra's algorithm (e.g. chap. 23 and 25 in Cormen et al. [1994]) should cover all necessary preknowledge, except for a few examples, which illustrate or motivate specific aspects. In any case, we will give references to further details in the literature, and crucial aspects will be explained in detail in this paper. Moreover, a basic background knowledge in programming is assumed. Besides that, the paper should be self-contained. In particular, all details of nonalgorithmic aspects (e.g. features of programming languages) are briefly introduced when needed. A few central aspects are deferred to an appendix and treated systematically there.

Since most of the practical work underlying this paper was done in one language (C++), a certain bias towards this language is unavoidable. Nonetheless, the presentation is abstract and does not require C++ literacy.

To some extent, the discussion of concrete details will be based on LEDA [Mehlhorn and Naher 1995](2) and the Standard Template Library (STL [Musser and Saini 1995]; see Appendix E for a brief introduction into the essential design principles of the STL). The STL greatly influenced the definition of the C++ standard library(3) and the design of many other recent libraries. However, we merely use these two libraries as mature examples and representatives for many other libraries. Nonetheless, preknowledge of these two libraries is not required.

Domain, application, context. To avoid ambiguities, we need some basic common vocabulary and a common intuition of what this vocabulary means. The following vocabulary is essential for the rest of the paper:

--A domain (or application domain) is a broad field of research such as VLSI design, traffic logistics,or computer-aided design, which is not necessarily algorithmic in nature, but offers various algorithmic problems.

--An application is a specific algorithmic problem occurring in some domain. Thus, an application defines the required algorithmic functionality of the desired algorithm component in abstract, mathematical or informal, terms. For example, the problem of finding a shortest path from some source node to some target node in a network embedded in the plane with respect to the Euclidean lengths of the edges is an application occurring in traffic logistics. The desired algorithmic functionality is described by the input (a directed graph, a pair of coordinates for each node in the plane, the source node, and the target node), the output (a path from the source node to the target node), and optional restrictions on resource requirements such as the run time and the maximum peak of space usage throughout the execution.

--A context is more specific than an application in that it also describes the required nonalgorithmic functionality. For example, the description of an application does not define the exact organization of the input and the output. In a context in which conversions of data structures are infeasible, the algorithm component must be able to process the input and deliver the output exactly in the form dictated by the context. Another example concerns algorithms that have exorbitant run times and are to be used in interactive systems. Such an interactive context might require that the algorithm is frequently interruptable to allow the end-user to interact with the system without significant delay times.

A context may also include nontechnical restrictions. For example, it may be necessary to have a simple, "idiot-proof" documentation of the algorithm components. Apparently, not every design can be documented in such a way. Hence, such a requirement significantly restricts the design options.

Using this terminology, we can state our goal more precisely:
   An algorithm A should be implemented as an algorithm component AC such that
   AC is adaptable to every context whose underlying application is solvable
   by A from a theoretical viewpoint.


2. THE PROBLEM

Many implementations of algorithms are not written for a specific application, but are intended to be used in many different contexts, ideally in all contexts that are covered by the algorithm from a theoretical perspective. However, this goal is hard to achieve. In the following two subsections, we will consider two general problems, which we regard as essential. In principle, the first problem means that an algorithm component should be adaptable to the lower level, and the second problem, that it should be adaptable to the higher level. "Lower level" means the underlying data structures, and "higher level" the client code which calls the algorithm.(4) A third case may be of interest: an algorithm A calls an algorithm B, in which case one algorithm is the lower level of the other. However, this case is sufficiently covered by the second case; the client of an algorithm component may also be an algorithm component.

2.1 Adaptation to the Lower Level: Underlying Data Structures

Problem: The algorithm is implemented on top of data structures which are different from the data structures dictated by the context.

In general, this problem can be solved by converting all data structures back and forth. However, the induced overhead might not always be acceptable. If the complexity of an algorithm is sublinear in the size of the input and the output, even the asymptotic complexity is increased. For example, an algorithm that only accesses a small area in a large two-dimensional geometric data structure could be sublinear. Even more, if algorithms are not implemented monolithically, but are hierarchically composed of the existing implementations of simpler algorithms, many conversions may be necessary to plug all of these algorithms together. Moreover, a large number of conversion routines requires a lot of programming effort. In the worst case, a quadratic number of conversion routines is necessary.(5)

A common attempt to overcome these problems is to define a set of basic data structures and to implement all algorithms and all contexts on top of these data structures. In other words, these data structures are intended to set a standard, on which all algorithms are to be implemented. Clearly, at first glance, this would solve the problem. Many libraries offer such a set of data structures. For example, LEDA provides basic data structures such as lists, stacks, and various tree types, data structures for directed and undirected graphs, and geometric data structures.

However, this strategy causes two problems.

Problem I: In general, no particular implementation of a data structure satisfies all potential requirements in an efficient manner.

For instance, many graph algorithms rely on an efficient way of answering the following question: given two nodes, is there an edge connecting these nodes, and if so, deliver one. Roughly speaking, this requires either a matrix, whose rows and columns are nodes and whose entries are edges, or a dictionary type (hash, search tree, grid file, ...), whose key type is "pair of nodes" and whose information type is "edge." On the other hand, the induced overhead may not be acceptable for algorithms which do not require this feature. In fact, in case of a matrix solution, the asymptotic space requirement might be increased; in case of a dictionary solution, inserting and deleting edges puts an additional nonconstant factor on the run time.

A more basic example, which appeared quite frequently in my own practical work, is the question whether or not a graph should support associative copies. This means that a new graph object is created as a logical copy of an existing graph object, and these two graph objects record and maintain a mapping between corresponding nodes and edges. Many algorithms require such a mapping. If the graph type does not support such a mapping, this mapping must be implemented in the algorithm itself. This is inconvenient, makes the complex algorithmic code even more complex, and may be a permanent source of bugs. Moreover, the algorithm cannot use an existing subroutine for copying a graph, because the mapping between corresponding nodes and edges cannot be reconstructed efficiently afterwards. However, inserting such a feature in the underlying data structure not only affects the performance but also causes specification problems. For example, some algorithms shrink the copy of the graph by identifying nodes with each other. It is not clear in which way the mapping between the nodes and edges of the graph objects should be maintained throughout modifications like these. There are several reasonable options for maintaining the correspondence throughout nonsimultaneous modifications of two corresponding graph objects. It is not at all clear whether there exists a scheme which satisfies all concerned algorithms.

Problem II: Basic data structures must be generic in order to be independent of particular applications.

For example, for an all-purposes graph data structure, this means that node and edge attributes such as lengths, capacities, and costs, must be freely choosable, because every algorithmic (and nonalgorithmic) problem on graphs requires another set of attributes.

To give a concrete example, LEDA provides two ways of associating attributes with nodes and edges in a graph:

--The graph classes themselves are generic(6) and parameterized by information types for nodes and edges. Typically, the generic type parameters are instantiated by records, which comprise all node and edge attributes, respectively.

--In addition, LEDA provides so-called node and edge array classes. Basically, a node or edge array is a normal or associative array and contains the values of a single node (or edge) attribute for all nodes (edges). Such an array can be instantiated at every stage to introduce a new attribute for nodes or edges.

These two possibilities seem to be the two fundamental ways of attaching generic attributes to nodes and edges without compromising efficiency.(7) Often, the first alternative is strongly preferable: a normal node (respective edge) array causes serious problems when nodes are inserted and removed by the algorithm; on the other hand, an associative array causes a significant loss of performance. These problems do not occur in the first alternative. Nonetheless, all algorithms in LEDA receive and deliver attribute settings as node and edge arrays. This comes as no surprise: otherwise, collaborating algorithms would have to agree on a common naming convention for all attributes. However, there are two prohibitive obstacles to such a convention:

--The same attribute may have different meanings in collaborating algorithms. For example, a minimum-cost flow algorithm may use a shortest-path algorithm and a maximum-flow algorithm as subroutines, and the edge attribute that appears as the residual capacity inside the minimum-cost flow algorithm and the maximum-flow algorithm is also the length inside the shortest-path algorithm. If all of these algorithms are implemented within the same project, it may be possible to retain a common name for this attribute (there might not be a name for this attribute which is intuitive in all of these algorithms, but this might be only a minor nuisance). However, when the shortest-path algorithm and the maximum-flow algorithm have already been implemented as general-purpose components which are now reused for the minimum-cost flow algorithm, it is unlikely that the developers of these two components anticipated this specific application in which the length is just the residual capacity. Hence, it is unlikely that these implementations agree on a common name for this attribute.

--Two different attributes may have the same meaning. For example, shortest paths in a traffic network shall be determined either according to the number of kilometers or the total time of traveling. In such a case, both attributes--the length in kilometers and the total time of traveling--must be assigned the same identifying name, which is impossible.

Some languages (e.g. Ada) provide means of renaming record components. Such a mechanism may solve the problem to some extent. However, other mainstream languages do not provide such a feature, so we cannot even regard this particular facet of the general Problem II as satisfactorily solved.

Moreover, in some cases it is not even reasonable to explicitly store an attribute at all. For example, consider a graph whose nodes are points in the plane, and assume that the length of an edge is the Euclidean distance of its incident nodes. Since the number of edges may be quadratic in the number of nodes, it may be reasonable not to allocate space for the edge lengths, but to compute an edge's length from the node coordinates when needed.

In such a case, no renaming mechanism or any other feature of mainstream languages will solve the problem.

2.2 Adaptation to the Higher Level: Client Code

Problem: The algorithmic and nonalgorithmic functionality of the implementation of an algorithm should be extensible and modifiable.

In the Introduction (section on domains, applications, and contexts), the notions of algorithmic and nonalgorithmic functionality were introduced. Many algorithms in the literature--notably the fundamental ones--are generic in the sense that the exact details of the algorithmic functionality are variable within certain limits. In other words, such a "theoretical" algorithm only serves as a pattern for concrete algorithms. Essentially, drawing a concrete algorithm from such a pattern means four things:

(1) For each subproblem, an algorithm is chosen from the set of all algorithms which solve this subproblem. Example: Typical maximum-flow algorithms apply solvers for subproblems such as graph search and path search [Ahuja et al. 1993]. These solvers should be exchangeable inside an implementation of a maximum-flow algorithm.

(2) The output is varied or extended. Example: A depth-first search or breadth-first search algorithm may either deliver a mere labeling of all visited nodes or additional information such as the traversal order. Moreover, it may alternately deliver the tree induced by the search, which comprises all visited nodes and all traversed edges. This tree may be encoded as a 0/1-labeling of the edges, as an (acyclic) object of the graph class, as an object of a specific tree class, or whatsoever.

For instance, many libraries (including LEDA) provide an implementation of depth-first search which only delivers a node labeling or the traversal order of all nodes. Constructing a depth-first tree from this information amounts to performing another depth-first search.(8) This simple example demonstrates that the concrete variation of the output cannot always be delegated to postprocessing routines. Consequently, this flexibility should be inherent in the implementation of the algorithm itself.

(3) Special algorithmic techniques are added. Often, correctness and efficiency of an algorithm can only be guaranteed if additional algorithmic techniques are applied. Techniques to improve the efficiency of an algorithm will be called speed-up techniques throughout the paper. Basically, numerical stability is the aspect of correctness that asks for special algorithmic techniques (all other aspects of correctness will be treated as nonalgorithmic functionality; see the next item). The application of data types for floating-point arithmetic with an unbounded number of digits is a simple example of algorithmic techniques that improve the numerical stability (which is, however, of limited applicability due to its inherent inefficiency).

An extensive case study of speed-up techniques will be given in Section 3.2.

(4) Nonalgorithmic functionality is incorporated. Examples: Section 3.1, Item 6.

3. AN ILLUSTRATIVE TEST CASE

In this section we will investigate the concrete meaning of the individual aspects worked out in Section 2 in view of the announced extensive, illustrative test case. To be as concrete as possible, Section 3.2 focuses on a specific, realistic application scenario.

This test case may be viewed as one possible "acid test." A component which implements Dijkstra's algorithm passes this test, if it is adaptable to all listed variations without sacrificing efficiency. If such a component has been implemented according to some general programming methodology, this programming methodology is also said to pass this test. Formulated the other way round: the number of separate algorithm components required to cover all of these scenarios may give a hint to which degree the applied programming methodology is appropriate for the design of truly flexible algorithmic components.

3.1 General Requirements on Flexibility

(1) Variations of the graph data structure: The choice of the underlying graph data structure is affected by decisions on the abstract (mathematical) and on the technical level. Items 1(a), (b), and (d) are examples of decisions on the abstract level, namely mismatches between the abstract data type expected by the algorithm and the abstract data type enforced by the context. On the other hand, Item 1(c) addresses the technical level. The last two items may be viewed as somewhere "in-between" the abstract and the technical level.

(a) Graph abstractions: Although Dijkstra's algorithm is naturally formulated as an algorithm for directed graphs, it can be applied to undirected graphs, bidirected graphs [Derigs 1988], and hypergraphs [Lengauer 1990],(9) just to mention a few (see Figures 1 and 2(e)). Each of these graph abstractions may be interpreted as a directed graph:

--The usual interpretation of undirected graphs as directed graphs regards each undirected edge as two antiparallel directed edges with identical attribute values (Figure 2(b)).

--In principle, a bidirected graph is an undirected graph such that for each node the edges incident to this node are partitioned into two sets (Figure 1(b)). For bidirected graphs there are two natural interpretations as directed graphs. First, for each node the bipartition of all incident edges is dropped, which reduces this case to the undirected case. Second, only a certain sort of path is considered, namely paths such that for each intermediate node the two incident edges of a path belong to different partition sets in the partition of the edges incident to this node.

--The usual interpretation of an undirected hypergraph H (Figure 2(e)) is equivalent to a normal, bipartite graph G = (V [union] W, E), where the nodes of H correspond to V, the hyperedges of H to W, and a node of V is connected with a node of W by an edge in E if and only if their corresponding node and edge in H are incident. The lengths of the edges in G must be defined such that for [v.sub.1], [v.sub.2] [element of] V, w [element of] W, {[v.sub.1], w}, {[v.sub.2], w} [element of] E, the length of the path [v.sub.1] [right arrow] w [right arrow] [v.sub.2] [element of] G equals the length of the hyperedge of H corresponding to w.

(b) Special graph classes: Many applications only need solutions for special graph classes such as bipartite graphs, interval graphs [Golumbic 1991], planar graphs and grid graphs [Lengauer 1990; Nishizeki and Chiba 1988] (see Figures 2(c) and (d)), and many others. In such a case, it may be reasonable not to use a general graph data structure, but to implement a special data structure, which only represents graphs of this class and whose functionality is somewhat different: on one hand, the functionality is usually extended in order to exhibit the rich structure of the special graph class. On the other hand, basic functionality, such as inserting and removing nodes or edges, must be restricted or even disabled to prevent manipulations which would drive the graph out of this special class. In the extreme case, such a graph data structure is not at all implemented as a graph. For example, an interval graph may be implemented as a set of intervals.

Dijkstra's algorithm may be useful for virtually every data structure that represents such a special class of graphs, because it does not change the structure of the graph.

(c) Different implementations of the same kind of graph: The underlying graph data structure may be different in different contexts even if these contexts agree on a common graph abstraction (Item 1(a)) and special graph class (Item 1(b)). For example, the concrete graph data structure may be taken from different libraries in different contexts.

(d) Different views on the same graph: For example, consider the case that the graph contains first-class and second-class edges, and in some situations only first-class edges shall be considered for shortest paths, whereas in other situations all edges are to be considered.(10) The edges belonging to different classes may be implemented by two separate lists of incident edges for each node, or they may be implemented by a single list, where first-class and second-class edges are merely distinguished by a flag for each edge.

(e) Implicit representation: The underlying graph is only given implicitly. For example, consider the problem of finding shortest paths on the line graph H of an undirected graph G, that is H contains a node for every edge in G, and two nodes are connected in H by an undirected edge if and only if the corresponding two edges in G are incident to a common node. Since the size of H may be quadratic in the size of G, it might not be reasonable to materialize H, but to run Dijkstra's algorithm on an implicit representation of H (for example, G itself would be an appropriate implicit representation of H).

(f) Hierarchical decomposition: The underlying graph is hierarchically decomposed into smaller graphs. For example, this technique is applied in geographic information systems. Here we only sketch one concrete realization of this general technique [see also Schulz et al. 1999].

[ILLUSTRATIONS OMITTED]

The graph (e.g. a traffic network) is decomposed into overlapping connected subgraphs such that every pair of nodes in such a subgraph has a shortest connecting path which is completely inside this subgraph. The shortest paths between all pairs inside such a subgraph are determined in a preprocessing phase and stored permanently. The nodes in such a subgraph which also belong to other subgraphs are the boundary nodes of this subgraph. To find a shortest path from some node s to some node t, first the subgraphs [G.sub.s] and [G.sub.t] to which s and t belong are identified. If [G.sub.s] = [G.sub.t], one table-lookup suffices. Otherwise, the shortest paths from s to all boundary nodes of [G.sub.s] and the shortest paths from all boundary nodes of [G.sub.t] to t are looked up.

To find the missing segment of the shortest path between [G.sub.s] and [G.sub.t], it suffices to find a shortest path from the set of boundary nodes of [G.sub.s] to every boundary node of [G.sub.t], where the distances of the boundary nodes of [G.sub.s] are not 0 as in the usual definition of the shortest-path problem, but equal to their distances from s in [G.sub.s]. This path is determined in an auxiliary graph, whose node set is the union of the boundary nodes of all subgraphs, and two nodes are connected by an edge if and only if they belong to a common subgraph. The length of this edge is the shortest-path length in the corresponding subgraph and again determined by a table-lookup. A final table-lookup for each edge of the shortest path in the auxiliary graph suffices to construct the corresponding shortest path in the original graph.

(2) Variations of the numeric types: The numeric types of edge lengths and node distances may be different in different contexts (both types may even be different within the same context). In fact, every type that fulfills a certain algebraic specification may be used [Lengauer and Theune 1991].

This also includes composed number types. For example, pairs of numbers as the number type with the normal lexicographic order can be used to express two criteria with strictly different priorities. The algorithm then finds the optimal path with respect to the second criterion among all paths that are optimal with respect to the first criterion. Interval arithmetic is another example of combined types. The length of an edge is here replaced by an interval, which bounds the true (yet unknown) length from both sides. The computations of node distances must then apply interval arithmetic. Consequently, the distance of a node is also represented by an interval.

Another, more abstract aspect of the numeric type implies further relevant degrees of freedom: the numeric type must come with a representation of "infinity," which is used to initialize the distances of all nodes (except for the root) in the beginning of Dijkstra's algorithm. For example, infinity may be simulated by a very large value of the type of node distances, by a reserved, "impossible" value of this type (e.g. a negative value), or by an additional Boolean node attribute. See Item 2 in Section 3.2 for yet another, more sophisticated example.

(3) Variations of the priority queue: From a theoretical point of view, a Fibonacci heap is the best implementation [Cormen et al. 1994]. However, if the number of edges is linear in the number of nodes (e.g. in planar graphs), a simple d-heap achieves the same asymptotic run time and may have a better "big-oh factor." On the other hand, if all edge lengths are small integral numbers, the dial implementation might be preferable [Ahuja et al. 1993]. Basically, this means that the priority queue is a bounded first-in-first-out queue (see Schulz et al. [1999] for an experimental evaluation).

(4) Variations of the organization of the node and edge attributes (node distances and edge lengths):

(a) Attached to items: The attributes of nodes (respective edges) may be organized as a record, which is attached to every node (edge), and a single attribute such as the node distance (edge length) is a slot in this record. The type of the record and the name of this slot may be dictated by the context and thus cannot be chosen freely by the developer of the algorithm component.

(b) Separate from the graph structure: The distances of all nodes (respective lengths of all edges) are stored in an additional associative array, and the ID of a node (edge) serves as the key to access the corresponding item in this array.

(c) Cache: The data is cached in a buffer and retrieved when needed.

(d) Implicit organization: A node or edge attribute is not explicitly stored at all, but is computed when needed. For example, if all first-class edges in Item 1(d) have the same length value, and likewise all second-class edges, third-class edges, and so on, it is not necessary to store the edge lengths explicitly: it suffices to store the class of every edge and an additional, small table outside the graph, in which the lengths of all classes (and possibly many further class-specific attributes) are listed.(11)

Another example was mentioned at the end of Section 2.1: if the nodes are points in the plane and the length of an edge is defined as the distance of its endnodes, it suffices to store the distances and to compute the length of an edge when needed.

(5) Variations of the algorithmic functionality:

(a) Shortest paths from one root to all other nodes: For example, Dijkstra's algorithm may deliver an assignment of distances to all nodes or a tree of shortest paths rooted at this node.

(b) Shortest paths from a set of roots to all other nodes: The roots may be initialized with different distance values, in particular, not necessarily with zero as in the usual definition of the algorithm (see Item 1(f) for a concrete example).

(c) A shortest path from one node s to another node t: For reasons of efficiency, the algorithm should terminate immediately when the distance value of t is determined. An implementation of Dijkstra's algorithm should preferably deliver a list of all nodes or edges on the path, which is ordered from s to t or the other way round.

(6) Various nonalgorithmic requirements on the functionality:(12)

(a) On-line checkers: A simple example of an on-line checker for Dijkstra's algorithm is to check that the sequence of updating values of node distances is monotonously increasing.

(b) Operation counting [Ahuja et al. 1993, chap. 18]: The most interesting example might be the number of nodes and edges visited in order to compute a shortest path from some node s to some other node t.

(c) Animation of the algorithm running in slow motion: For Dijkstra's algorithm, this could mean highlighting the currently processed node or the whole frontier line of the search (see Figure 4). It is important to note that animation is also useful for algorithm components which are implemented for purposes other than animation. In fact, a careful animation allows visual debugging of the algorithmic code. If available, this greatly supports the debugging of complex algorithmic code. After all, some sorts of bugs only appear in very large instances--too large to be grasped other than by visual aids.

[ILLUSTRATION OMITTED]

(d) Concrete organization of the input and output data: Some details may be left deliberately open such that they are determined later at run time, immediately before the algorithm is invoked (e.g. by user interaction or by a configuration file). For instance, this may happen if the meaning of the edge lengths is not known at compilation time. To give a concrete example: the length of an edge in a traffic network may be a combination of two or more criteria such as the estimated run time and the cost for traveling along this edge. This combination may reflect the preferences of an end-user, which are determined interactively and thus not known at compilation time.

(e) Interactive control: It is sometimes desirable to control the running algorithm through a user interface.

(f) Saving snapshots: Frequent savings of the algorithm's current state on an external device for recovery after a crash.

(g) Suspension and termination: Client code which calls an algorithm should be able to suspend or terminate the algorithm at frequent stop points in order to react on real-time requirements (if this functionality is not offered by the algorithmic component itself, a complex, expensive multi-process solution is necessary).

(h) Robustness: Roughly speaking, a component is called robust with respect to a specification of its input and output, if (i) it applies run-time checkers to test its (given) input and its (self-produced) output for conformance with this specification, and (ii) in case of a failure, invokes some exception-handling mechanism in a well-specified way. Complete robustness is achieved, when success of the run-time checkers is necessary and sufficient for the input and output to satisfy all aspects of the specification. On the other hand, we speak of partial robustness, when only necessary conditions are checked.

For example, Dijkstra's algorithm only requires that all edge lengths are nonnegative. A complete run-time check of this condition is straightforward and efficient. In the scenario of Item 5(a), there is also a simple, efficient complete run-time checker for the output: for each node w, except for the root node, there must be an edge (v, w) such that the distance of v is strictly smaller than the distance of w, and the absolute value of the difference equals the length of (v,w).(13) However, in the scenario of Item 5(c), this run-time checker only guarantees partial robustness, because some of the nodes in the graph were not visited. In fact, this test can only guarantee that there is no shorter path which solely contains nodes visited during the search. On the other hand, a complete robustness checker may even increase the expected asymptotic complexity of a single shortest-path computation in the scenario of Item 5(c), which means that such a checker may or may not be acceptable for debugging sessions, but must be turned off in the production code for reasons of efficiency.

In summary, the robustness of a component must also be flexibly adaptable to allow a context-specific compromise between robustness, efficiency, and adaptability. See Blum and Wasserman [1994] for an introduction to partial and complete output checking for implementations of algorithms.

3.2 Concrete Application

As mentioned above, we next discuss a concrete scenario: a traffic information system. Here we are given a traffic network, that is, the nodes are cities and towns, and the edges are traffic connections. The system receives an unbounded number of pairs (s, t) of nodes as run-time events. The core of the system is an algorithm component for shortest paths. For each pair, the system has to activate this component (see Figure 3). This is a special case within the wide range of algorithmic problems that are best solved by Dijkstra's algorithm [Cormen et al. 1994, sec. 25]. Our concrete application offers a wealth of algorithmic speed-up techniques. Unless stated otherwise, s is the node from which the search starts. We refer to Schulz et al. [1999] for a concrete experimental case study on algorithms for information systems in the public railroad transport in Germany.

[ILLUSTRATION OMITTED]

(1) The first, most basic speed-up technique is to let the algorithm terminate immediately when the shortest path from s to t is found. Actually, the usual, "textbook" version of Dijkstra's algorithm computes shortest paths from s to all other nodes. Unfortunately, the typical implementations of Dijkstra's algorithm in libraries [Mehlhorn and Naher 1995] and in the literature [Flamig 1995] follow the textbook version and do not even allow this simple speed-up technique.

(2) In combination with the first technique, the following trick can be applied to achieve an expected run time that is sublinear in the size of the graph for a single shortest-path computation: the node distances are not initialized with a value representing infinity in every shortest path computation. Instead, a version stamp is maintained for every node, which is the number of the last shortest path computation in which the distance of this node was updated. If the version stamp of a node is not up to date, this node is regarded as having infinite distance (clearly, to avoid an integer overflow, all version stamps must be reset to the initial value after a huge number of steps).

(3) In goal-directed search, the length l(v,w) of an edge (v,w) [element of] E is replaced by the reduced length l'(v, w) := l(v, w) - [Delta](v, t) + [Delta](w, t), where [Delta](x,y) is a lower bound on the shortest path from x to y: for example, the Euclidean distance of x and y [Lengauer 1990, sec. 3.8.5.1]. It is easy to see that this modification maintains the relative lengths of the (s, t)-paths compared to each other. Therefore, goal-directed search computes a shortest path with respect to the original edge lengths. However, there is empirical evidence that this modification may direct the search faster towards t.

(4) In bidirectional search [Lawler et al. 1983; cf. Lengauer 1990, sec. 3.8.5.2], a shortest (s, t)-path is computed from s and in a backward direction, from t, simultaneously. That is, two executions of Dijkstra's algorithm are "merged" into one loop, in each step one of these two algorithms is chosen to scan one single node, and this choice of the algorithm is on-line. The algorithm terminates when one node has been scanned by both searches. The concatenation of the shortest path from s and the backwards shortest path from t to this node yields a shortest (s, t)-path.

(5) Variations of the A* algorithm for shortest (s, t)-paths in the plane also fit into this general scheme [Kanal and Kumar 1988]. The effective length of an edge is a combination of its nominal length and an additional cost function, which assigns penalty factors to the edges: the larger the angle between the direction of an edge and the direction towards t, the larger is the penalty factor. The pure A* algorithm guarantees a shortest path. However, some variations applied in practice no longer guarantee this. In any case, there is empirical evidence that the strong trend towards t, which is imposed by the additional cost function, may drastically reduce the number of nodes to be visited until a (usually short) path is found.

To achieve a run time which only depends on the number of visited nodes and edges, not on the size of the whole graph, we must apply the trick introduced in Item 2 above. Moreover, we must compute the effective length of an edge on-line, namely when this edge is accessed during the search from s to t. The reason for this is the following: since the effective length of an edge depends on t, it must be recomputed for every shortest-path computation. The edges to be considered for a pair (s, t) are not known in advance. So it follows that the only alternative to online computations would be to compute the effective lengths of al! edges in the network immediately before starting the search, which would destroy the sublinear effect.

(6) For reasons of efficiency, only paths from s to t which do not leave a certain region (e.g. an ellipse with foci s and t) are considered. This approach is reasonable whenever it may be safely assumed that the real shortest path does not deviate too much from the straight segment connecting s with t. For reasons of efficiency, it may be necessary for the algorithm to disregard the (usually much larger) part of the graph outside the ellipse.

(7) Such an ellipse may not capture the shortest path, but again for reasons of efficiency, it may be reasonable to start with this ellipse and to add selected nodes and edges outside this ellipse online, that is, depending on the current state of the shortest-path algorithm. In other words, two algorithms--a shortest path routine and a routine that extends the search horizon on-line--are "merged" into one loop and affect each other.(15)

(8) In Schulz et al. [1999] yet another strategy is applied. The data are preprocessed such that every edge can be assigned a certain piece of information. Whenever a search meets this edge, this piece of information is evaluated to decide whether or not this edge is to be processed. The piece of information assigned to an edge in Schulz et al. [1999] is two angles, and an edge is only to be processed if the destination is in the circle sector spanned by these two edges. If not, the edge may be safely dropped. (See Figures 5-8.)

[ILLUSTRATIONS OMITTED]

4. DISCUSSION OF THE AIM

As stated in the Introduction, we will discuss the aim of our project in light of the acid test in Section 3.

Like many other basic graph algorithms, Dijkstra's algorithm is not too difficult to implement. The effort needed to adapt a very general implementation may equal or even exceed the effort needed to implement, from scratch, an almost optimal version that is tailored to the specific context. However, we think that, from a software-engineering perspective, there are still good reasons to favor general-purpose algorithm components that are adaptable to various contexts by some additional customization code:

--If an algorithm component is well designed and documented for customization (see Appendix A), adapting it to a new context is a relatively straightforward task, whereas implementing even a simple graph algorithm requires some basic understanding.(16)

--Usually, algorithmic code is complex and fragile. Thus, maintenance of a software system is much easier if the algorithmic code is not affected when changing requirements are to be incorporated. In other words, the algorithm component should be well designed for customization in the sense of the Appendix A.

This aspect is even more important since the people doing the maintenance need not necessarily be the people who developed the package.(17) Hence, it cannot generally be assumed that the people who maintain an algorithm component are algorithmicians themselves.

--It is often argued that basic components which are heavily reused are much more reliable than ad hoc solutions (for example, this is extensively discussed in Meyer [1995, chap. 6]).

--By definition (Appendix A), the code that customizes a well-designed algorithm component is not seriously error-prone. If all changes only affect the customizing code, the result of the revision is more reliable.

--Often, code is based on third-party libraries. When such a piece of code must be ported, the chances are high that some of these libraries are not available on the target platform for whatever reason (for example, see the discussion in the preface of Musser and Saini [1995]). If the code is implemented from scratch and tailored to the original platform and the original library, customizing the code to the new context is very expensive and error-prone. On the other hand, if all algorithms are implemented from the very beginning in view of customization, the pieces of code that must be adapted should turn out to be small, and the modifications might not affect the rest of the code.

--Even a "simple" algorithm such as Dijkstra's can be speeded up by heuristic techniques which are not found in most textbooks about graph algorithms (see Section 3.2 for a few examples). Therefore, an implementation from scratch by a nonexpert is probably not as efficient as it could be. If an all-purpose implementation comes with documentation and an environment which formulate, support, and encourage various algorithmic customizations including speed-up techniques,(18) this gives a programmer of client code an opportunity to make use of these techniques. However, it is important that such heuristic techniques are not "hard-wired" in the algorithm, but can be easily turned on and off, because a heuristic technique may be useless or even increase the run time in contexts for which it was not developed.

--Reused components need not be documented again. This may reduce the effort for documentation significantly. The client code becomes more self-explanatory, and the documentation of client code may be leaner.

The question remains whether it is reasonable to aim at one implementation for all contexts. A less ambitious aim would be to implement several variations of Dijkstra's algorithm, each of which only covers a subset of all cases in Section 3. However, the following aspects might make an all-in-one solution desirable:

--A real-world context might consist of a combination of the various aspects from Section 3, and all of these aspects must be covered simultaneously. It seems that this can only be guaranteed by a single implementation which covers virtually all contexts.

--When minor details of the context change, chances are high that a variant which only covers a subset of all contexts cannot be adapted to the new context and must be replaced by another variant. This may result in a major revision of the client code.

5. GENERAL GOALS

As in Section 2, we will distinguish adaptability to the lower level from adaptability to the higher level. In both cases, we will formulate, explain, and discuss a few concrete goals, which try to capture the lessons learned from Section 3.

5.1 Adaptation to the Lower Level: Underlying Data Structures

Items 1-4 in Section 3.1 and Items 2, 3, 5, 6, and 8 in Section 3.2 are concrete examples where adaptability to the lower level is required.

General Goal 1: The underlying data structures should not be hard-wired in an algorithm component, but kept variable (using some sort of conceptual polymorphism).

A type is conceptually polymorphic within some component, if the name of the type in the source code of this component is a formal "placeholder" for an actual type, which can be chosen from a certain set of types. In other words: the actual type is not fixed, but may be chosen from some set of types when the component is used. The set of types from which the actual type may be chosen is usually described by syntactical prerequisites. See Appendix D, for a more extensive discussion of conceptually polymorphic features of the mainstream object-based and object-oriented programming languages.

It might be obvious that Goal 1 is absolutely mandatory in order to achieve adaptability to the lower level, and that conceptual polymorphism is absolutely mandatory to achieve Goal 1.

General Goal 2: An algorithm component should not access the complex data structures directly, but through some additional layer of indirection. This layer should decouple the algorithm component from the data structures such that a modification of the data structures only requires a revision of the code in this layer, not of the algorithm component itself.

In other words, the collaboration of algorithms and data structures is mediated by some additional helper types, which connect algorithms with data structures (and also separate them from each other in some sense). Adapting an algorithm to a data structure amounts to implementing these helper types, and changes of this data structure are only propagated to these helper types. In particular, no sophisticated algorithmic code must be changed when the underlying data structures are changed. In Section 4, we noted that this may make maintenance easier and more reliable.

Such an additional layer of indirection is necessary because otherwise it cannot be generally assumed that an algorithm component and its underlying data structures fit seamlessly together. After all, the details of the underlying data structures may be dictated by the context, and the context may dictate an organization that does not fit into the algorithm component.

General Goal 3: The additional layer of indirection addressed in the second general goal should be implemented in a very modular fashion, that is every aspect of the interface to the lower level should be factored out into a separate, very small component in this layer

In principle, this means that the interfaces of algorithms to the lower level may be organized as a "toolbox," which contains a couple of conceptually polymorphic components, and from which the interface may be constructed. In the idea] case, customizing an algorithm to the lower level amounts to instantiating these conceptually polymorphic helper types in a context-specific manner and to plugging these instantiations together.

In particular, the following arguments motivated this goal:

--A minor change in the implementation of the underlying data structures should only cause minor, local changes in the implementation of the indirection. For example, if the organization of a single node or edge parameter is modified (Item 4 in Section 3.1), this should not affect more than one (very small) component in this layer.

--Likewise, if the functionality that an algorithm component requires from the underlying data structure is changed slightly (e.g. if an algorithm requires an additional node or edge attribute from an underlying graph), only a few, very small components inside the intermediate layer should be affected.

--Sometimes it is desirable to insert additional functionality in this mediating layer of indirection. For example, it may be desirable to perform some additional bookkeeping inside this layer (e.g. the "time stamps" introduced in Item 2 in Section 3.2). Again, integrating such functionality should only cause minor, local changes.

--In some cases, an algorithm shall be applied to a data structure that does not really fit into the algorithm's requirements. Item 4(d) in Section 3.1 is an example of that: the coordinates of nodes are provided by the underlying graph data structure, but the lengths of edges are requested by the algorithm. The necessary transformation must be performed inside the additional layer of indirection which adapts the data structure to the algorithm. The algorithm to compute the length of an edge from the node coordinates should be factored out into a single component.

The building blocks of such a modular decomposition of the additional layer of indirection must be conceptually polymorphic to allow a flexible construction of this layer. In every context in which Item 6(d) in Section 3.1 is not relevant, static polymorphism suffices for that. "In theory," the overhead caused by a modular decomposition may then be negligible, because it may be optimized away by the compiler. It might be worth mentioning that a few C++ compilers already come close to this ideal.

5.2 Adaptation to the Higher Level: Client Code

General Goal 4: An algorithm component should offer its clients frequent occasions to invoke context-specific code during the execution of the algorithm. There should be at least one occasion in every iteration of the core loop(s).

Probably every non-trivial algorithm essentially consists of one or a few loops (or nested loops), plus some pre- and postprocessing operations for each loop.(19) We call these loops the core loops of the algorithm. For example, Dijkstra's algorithm has one core loop. In each iteration of this loop, the current distance estimation of exactly one node is updated, provided that the currently available information allows that.

Obviously, the fourth general goal is a necessary condition for Items 6(a)-(c) and (e)-(g) in Section 3.1.

General Goal 5: An algorithm component should offer its clients frequent stop points throughout the execution of the algorithm such that the client is able to terminate the algorithm at any such stop point or suspend it temporarily and continue the execution later on.

This goal is motivated by Items 5(c) and 6(e) and (g) in Section 3.1.

General Goal 6: At each of the stop points addressed in the fourth general goal, an algorithm component should allow full read access to its logical state (a restricted, disciplined write access may also be useful).

Roughly speaking, the logical state of a component at some stage of its lifetime is defined as the bunch of information about its current state which is necessary to predict its behavior in all possible threads of interaction with other components throughout the rest of its lifetime. It is important to note that full read access is not necessarily achieved in any reasonable way by type abstraction. In fact, from an abstract viewpoint, a priority queue is a type whose elements can only be read at its front. Roughly speaking, type abstraction means that this viewpoint is reflected by an implementation of priority queues. In other words, no element except for the topmost element can be accessed through the interface of the data type. Type abstraction is also desirable and is often recommended as a principle to achieve clean designs.

For example, many libraries provide classes for priority queues which exactly offer those access methods that constitute priority queues as an abstract data type [Cormen et al. 1994]. More specifically, this includes methods for reading and removing the topmost element (i.e. the one with highest priority), inserting a new element, and changing the priority of an arbitrary element (identified by an ID, which is usually delivered by the queue when the element is inserted). Interacting with such a class means calling its methods. However, the logical state of a priority queue is not fully determined by the topmost element, which is the only readable one. Rather, it is described by the set of all items in the priority queue along with their current priority values. Only this whole bunch of information suffices to predict the outcome of all possible sequences of future method calls.

In principle, these access methods allow full read access on the logical state. In fact, it suffices to repeatedly read and remove the elements step-by-step until the priority queue is empty and then to reinsert all of these elements in an arbitrary order. However, this strategy has two drawbacks, which may be prohibitive in some cases:

(1) Virtually all reasonable implementations of priority queues could be equipped with an additional access method to the set of items and priority values that requires time linear in the current size of the priority queue and only constant additional space (namely if some kind of iteration mechanism is applied). In contrast, the above strategy requires an additional log-factor for the run time (e.g. for the common heap implementation [Cormen et al. 1994]), and the additional space requirement is inevitably linear.

(2) The priority queue is no longer stable. Various algorithms rely on the assumption that the top item does not change as long as no modifying access method is invoked (i.e. inserting a new item, removing the top item, or changing the priority of an item). Typical implementations of priority queues guarantee stability. However, in a context in which the priority values are not pairwise different, this guarantee is lost if the logical state is read this way, for example, by a client of the algorithm that animates the dynamic behavior of the priority queue. Even the normal heap implementation of priority queues becomes unstable, no matter in which order the elements are reinserted. The algorithm component is not aware of this "read" process and may become corrupted.

Hence, a reasonable realization of full read access to the logical state of a priority queue requires an additional means of iterating over the current items beyond the functionality that constitutes priority queues from an abstract viewpoint.

Items 6(a)-(c) and (f) in Section 3.1 obviously require full access to the logical state of a component implementing Dijkstra's algorithm. Moreover, many speed-up techniques rely on extensive knowledge about the current state of the core algorithm. For example, Item 4 in Section 3.2 is of this kind: the on-line choice of the search (either the forward or the backward search), which shall perform the next step requires knowledge about the current logical states of both searches. However, the subalgorithm that performs this choice should also be exchangeable, and is therefore unpredictable at the time when Dijkstra's algorithm is implemented as a component. In particular, it is not predictable which knowledge about the current logical state will be required by this unknown subalgorithm. Hence, there might be no alternative to full inspectability of the logical state. In principle, this means full access to the current frontier line of the search. Technically speaking, this is just the contents of the priority queue. The reader is referred to Weide et al. [1996] for an in-depth discussion.

Even the simple example of priority queues shows that the sixth general goal does not seamlessly conform to the concept of type abstraction. In fact, for an algorithm component, the "right" abstraction is not that clear. For example, in Section 2.2, Item 2, we have seen that the right abstraction of the output of an algorithm--even for an algorithm as simple one as depth-first search--is not at all clear. This indicates that rigorous abstraction should not be the main goal for the development of algorithm components.

Note that, nonetheless, the sixth general goal does not contradict the encapsulation of implementation details. In other words, the most important argument for abstraction is not an argument against Goal 6.

General Goal 7: Preprocessing and postprocessing should be separated from the core of an algorithm and regarded as some kind of customization rather than as a part of the algorithm component. The residual core should be the unit of reuse, not the algorithm as a whole.

Dijkstra's algorithm includes some preprocessing, but no postprocessing. In the preprocessing, the priority queue and the node distances are initialized.

From an algorithmic viewpoint, the only difference between Items 5(a) and (b) in Section 3.1 is in the initialization: the roots of the search (along with their distance values) are the initial members of the priority queue. Making an implementation of Dijkstra's algorithm customizable to both cases amounts to extracting the initialization of the queue from the algorithm component and making it a part of the customizing code.

Item 2 in Section 3.2 demonstrates that the initialization of the node distances should not be a hard-wired part of the algorithm component either. On the other hand, Item 2 in Section 2.2 discusses an example where a flexible postprocessing is desirable.

General Goal 8: The core loops of several algorithm executions should be "mergeable" into one loop.

The bidirectional search technique for Dijkstra's algorithm (Section 3.2, Item 4) is an example. Moreover, Item 7 in Section 3.2 may be viewed as another example, in which two different algorithms are merged into one loop.

To mention another important example: a component which realizes a search strategy such as simulated annealing [Vidal 1993] can be easily applied in a pseudo-parallel fashion, if the component satisfies the eighth general goal. This means that several instantiations of this algorithm explore different parts of the search space and every instantiation performs exactly one search step until the next one is invoked in a round-robin style.

Another example is the concept of primal-dual algorithm in algorithmic fields such as linear programming [Lawler 1976; Papadimitriou and Steiglitz 1982]. Often it makes perfect sense to implement both the primal and the dual strategy as stand-alone algorithm components. However, the primal-dual algorithm relies on the possibility to combine both strategies such that each iteration of the primal loop is followed by an iteration of the dual loop and vice versa.

General Goal 9: The specific format of the output of an algorithm component should be modifiable with minor effort.

This goal is motivated by the remarks on variations of the output in Item 5, Section 3.1 (see also Item 2 in Section 2.2).

General Goal 10: Algorithm components which are exchangeable within an application from a theoretical viewpoint should also be easily exchangeable in each context based on this application.

This goal is not motivated by the test case in Section 3, but it is quite natural, and its omission would result in an obvious gap (and Item 1 from Section 2.2 serves as a motivation for Goal 10). In principle, this is the intent of the strategy design pattern [Gamma et al. 1995], applied to the case where the client is itself an algorithm. See Gamma et al. [1995] for a motivation of this goal in a more general setting. The issue of numerical stability, which will be discussed in the very next section, gives yet another example.

6. ON THE SCOPE OF THE TEST CASE AND THE GOALS

To summarize Section 3, the following main aspects were covered by the test case:

(1) Variations of the underlying data structures.

(a) Variations of the abstract data types (e.g. Items 1(a) and (b) in Section 3.1).

(b) Variations of the implementation of an abstract data type (Item 1(c) in Section 3.1).

(c) Variations of the element attributes (Items 2, 4, and 6(d) in Section 3.1).

(2) Variations of the algorithmic functionality.

(a) Variations of the output (Item 5 in Section 3.1).

(b) Speed-up techniques (Section 3.2).

(3) Additional, nonalgorithmic requirements.

(a) Monitoring (Items 6(a)-(c) in Section 3.1).

(b) Control (Items 6(e)-(g) in Section 3.1).

(c) Robustness (Item 6(h) in Section 3.1).

All of these aspects are quite general and problem-independent, and might appear ubiquitously in the algorithmic realm.

The following aspects are not relevant for Dijkstra's algorithm and were thus not explicitly addressed in Section 3:

(1) Numerical stability. For algorithms that rely on nontrivial floating-point arithmetic, there is typically a tradeoff between numerical stability and efficiency. The best compromise between these two conflicting goals may vary from context to context. A systematic analysis of the impact on adaptability is still missing.

However, it should be noted that three fundamental possibilities of compromises can already be identified, and each of them is indeed covered by the test case in Section 3:

(a) The choice of the data type for floating-point computations. On one hand, very efficient, yet unstable data types are available as built-in types in most mainstream programming languages. On the other hand, all computations could be done using exact arithmetic, which is, however, prohibitively slow in many situations. Some work on reasonable compromises has been done throughout the last few years.

A programming methodology is appropriate for this aspect if, and only if, it is appropriate for Item 2 in Section 3.1. Hence, this aspect is implicitly covered by the test case.

(b) Interval arithmetic is often used to express and handle numerical uncertainty. Floating-point numbers are replaced by enclosing intervals, and the normal arithmetic rules are replaced by the corresponding interval rules. This technique may be viewed as a special case of the previous technique (cf. Item 2 in Section 3.1) and is thus implicitly covered as well.

(c) The choice of strategies for certain critical operations. To give a concrete example, the computation of the sign of a determinant is a critical operation in geometric computing and has been extensively investigated throughout the last years. Here the adaptability problem is how to seamlessly exchange one strategy for another one. Hence, this is a case for the tenth general goal.

See Schirra [1998] for a general overview of algorithmic techniques for numerical stability.

In summary, although numerical stability is not a serious issue for shortest paths in networks, the concrete adaptability problems resulting from this issue for other algorithms seem to be covered by various aspects identified in the test case. Thus, there is good hope that a more systematic analysis of the numeric realm will lead to a similar set of goals. The open question is whether the trade-off between efficiency and numerical stability may cause adaptability problems that cannot be solved by an appropriate choice of data types and isolated strategies alone.

(2) Structural changes of the underlying data structures. Dijkstra's algorithm does not change the structure of the graph. Many graph algorithms apply the basic modifying operations: inserting and removing nodes and edges. Other graph algorithms apply more complex modifying operations such as shrinking subgraphs or decomposing graphs into their biconnected components. In principle, complex operations of this kind can always be expressed as sequences of basic insertion and deletion steps. However, such a reduction is not always appropriate, so a systematic taxonomy of required functionality, like in the STL (see Appendix E and especially Figure 11), is necessary as a basis for the exchange of algorithms and data structures. However, to obtain a manageable system of requirements it might be necessary to identify a relatively small set of basic modifying operations and to reduce all potential modifying operations to these basic ones.

[ILLUSTRATION OMITTED]

The question is whether an acceptable compromise between simplicity and flexibility exists. Preliminary experiences(20) suggest that there is still a lot of work to do before a meaningful systematic analysis will be within our reach.

(3) Logical write access. The sixth general goal asks for some kind of read access to the logical state of the algorithm during its execution. There are also practical scenarios in which a truly mutual interaction between client code and algorithm component is required, that is the client also needs to influence the behavior of the algorithm during its execution. An analysis of these scenarios might be much more difficult. To the best of my knowledge, the only work that explicitly addresses this issue is of Weide et al. [1996]. However, Weide et al. [1996] stays on a quite general, abstract level and does not base the analysis on case studies of significant complexity.

In summary, the last two items probably require a significant extension of the list of concrete goals, whereas the first item seems to fit nicely into the scheme.

7. REVIEW OF EXISTING APPROACHES

Several scientific communities and subcommunities have contributed proposals on how to achieve general goals like maintainability and reusability. In fact, people working in structured programming, object-oriented programming, functional programming, software reuse, and formal specification, just to mention a few, have contributed to this field. Moreover, user communities of various programming languages have attacked these problems in a language-dependent manner. Recently, research on this topic has started in various algorithm communities.

All of this work seems to be done more or less in isolation without much interaction between the individual communities. Thus, we do not claim that the presented review of existing approaches will give a true survey of all of the relevant literature. Since each of these communities looks at the problem from a different perspective, it does not seem possible to compare the general merits of these approaches in a fair manner. The following is important to note:
      We will not try to estimate the true merits of the individual
   approaches. The only aim is towards an analysis of these approaches in view
   of the goals presented in Section 5. An analysis based on another set of
   criteria (e.g. an extension as suggested at the end of Section 6) may yield
   different results.


In particular, the discussion topics are not grouped according to existing approaches but according to main themes. Therefore, one approach, library, or language may be discussed at several places if it contributes to more than one theme.

Again, we consider the adaptation to underlying data structures and the adaptation to client code separately.

7.1 Adaptation to the Lower Level: Underlying Data Structures

Type specialization. Item 1(b) in Section 3.1 suggests an approach based on type specialization. Basically, this means that every special class of graphs is realized by a separate type, but these types are not stand-alones. Instead, if type A represents a graph class which is a special case of the graph class of type B, then A is implemented as a specialized version of B. Every algorithm which is based on B may then also be applied to an object of type A.

To give a concrete example: in LEDA, the type planar_map is derived from the general graph type. In particular, every graph algorithm for general graphs may also be applied to a planar graph, even if this graph is not organized as an object of the general graph type, but as a planar map.

In this sense the special-case hierarchy of graph classes constitutes an isomorphic hierarchy of abstract data types. For instance, grid graphs are a special case of planar graphs, bipartite graphs are a special case of perfect graphs [Golumbic 1991], and so on. See Brandstadt et al. [1999] for an extensive survey of graph specializations.

Moreover, this kind of type specialization can also be used to attack the other parts of Item I in Section 3.1. For example, the LEDA class for general undirected graphs is declared to be a specialization of the class for general directed graphs. Hence, an algorithm like Dijkstra's that is designed for directed graphs may also run on undirected graphs (see Item 1(a)).

LEDA's design is not based on type specialization, and so its use in LEDA is rather sporadic. In contrast, for instance, the PlaNet package [Brandes et al. 1999] was an attempt to base the design of a visualization tool for graph algorithms on a hierarchy of type specializations, which was intended to reflect the hierarchy of abstract, mathematical graph classes in a natural way. At any stage during a session, the user is confronted with a current special graph class, which (s)he can replace by another special graph class at any time (by direct choice or by navigation through the hierarchy of graph classes). The system offers the user all objects from the database of graph objects which belong to this graph class or one of its specializations and all algorithms for this graph class or one of its generalizations. Hence, in each state it is guaranteed that every eligible algorithm works well with every eligible graph object.

In principle, this approach has proven feasible. However, in this project, we constantly encountered a number of problems, which suggest that this approach is not a good base for algorithm components:

--Restricted functionality: As mentioned in Item 1(b) of Section 3.1, a data type A for a specialized graph class usually cannot offer all functionality of the general graph class B from which it was derived through type specialization. In fact, otherwise, it is impossible to safely guarantee that every object of A actually represents a graph from the corresponding special abstract graph class. There are two possible options.

First option: A provides all functionality promised by B and allows that objects of type A leave the corresponding abstract graph class. This option is often chosen. Typically, such a type A is equipped with an additional method that checks whether the object currently falls into this graph class. This option is not always practical. For example, if B represents general graphs, B might offer a means of adding or deleting nodes or edges. On the other hand, if A represents rectangular grid graphs [Lengauer 1990; Nishizeki and Chiba 1988], the graph might be represented as some kind of matrix, which only allows column and row operations. In this case, realizing such basic modifying node/edge operations cannot be immediately mapped onto the implementation and, thus, require additional internal bookkeeping (e.g. a separate list of single nodes and edges). This might be more complex (and less reliable) than the implementation of the grid itself and significantly increase the overhead in development/maintenance and run time. However, even if this option is practical in some cases: experience shows that a class A that promises, but does not guarantee, that every object fulfills certain properties may be a major source of inconsistencies.

Second option: Type A only offers restricted functionality compared to B and thereby ensures that no object of type A leaves the corresponding abstract graph class. However, this means that the semantics promised by B are not fulfilled by A, which violates the Liskov substitution principle [Liskov 1988; Martin 1996]. A common attempt to overcome this problem is to offer operations which would drive an object out of its special class, but to catch such requests and invoke an exception-handling mechanism. However, this still means that an object of type A does not behave as promised by B. FAQ #118 in Cline and Lomow [1994] drastically characterizes this sort of design as "a design error that creates a mess."

--Conflicting options for type specialization: This is the classical "circle-ellipse dilemma" [Weihe 1998]. The relation between directed and undirected graphs is an example of this dilemma from graph algorithmics.

Many algorithms for directed graphs are also applicable to undirected graphs. In Section 3.1, Item 1(a), an undirected graph was interpreted as a directed graph by viewing each undirected edge v - w as a pair of antiparallel edges, v [right arrow] w and w [right arrow] v. In other words, undirected graphs may be viewed as the special case of directed graphs in which the graph is symmetric and the attribute values of two antiparallel edges are identical.

This is not the only possible way of interpreting undirected graphs as a specialization of directed graphs. For instance, in LEDA, undirected graphs are also a specialization of directed graphs. However, here an undirected edge is just a directed edge for which the orientation is meaningless. This relation between directed and undirected graphs is appropriate for many algorithms which are naturally formulated in terms of undirected graphs, for example, algorithms for spanning-tree and matching problems.

These options seem to be inherently contradictory. Moreover, in the first option (i.e. undirected graphs are symmetric graphs with symmetric edge attributes), there are further options in case an algorithm modifies the values of an edge attribute. For example, in algorithms for single-commodity flow problems, a flow augmentation step shall silently change the flow on all reverse edges such that the sum of two antiparallel flows is maintained. On the other hand, algorithms for multicommodity flow problems usually treat the flows on two antiparallel edges as independent of each other. Although these two algorithmic problems are almost identical, they require completely different, conflicting ways to access symmetric attributes.

In summary, a natural type specialization relation between directed and undirected graphs which is suitable for all algorithms does not seem to exist. Many further examples of this general problem can be found in algorithmics.

--Proliferating hierarchy: The literature on pure and algorithmic graph theory reveals a huge special-case hierarchy of graph classes [Brandstadt et al. 1999]. Of course, in no software package can this hierarchy be completely realized. Only a small fraction of this conceptual hierarchy will be realized. However, this fraction will change over time. The crucial point is that this typically means more than merely adding new leaves to the existing hierarchy. In fact, an extensive restructuring effort might be necessary to keep the hierarchy manageable after new leaves are added. This is usually called refactoring and has been identified as one of the major maintenance problems in object-oriented modeling [for example, see Opdyke and Johnson 1993].(21)

The fact that (dynamic) polymorphism and type specialization are strongly coupled in various programming languages is discussed in Appendix D. In particular, the first general goal in Section 5.1 can be achieved by type specialization (though with the above-mentioned general problems). Moreover, the second general goal can also be achieved: if an algorithm is based on a base class A to represent graphs, adapting the algorithm to a graph data structure amounts to implementing a specialized version B of A, which "wraps" an A-compatible interface around the data structure (design pattern adapter [Gamma et al. 1995]).

However, this use of type specialization does not address the third general goal (nonetheless, techniques which do address the third general goal may in turn profit from a well-devised incorporation of type specialization).

See Taivalsaari [1996] for an in-depth discussion of type specialization and other uses of inheritance.

Composition of components in layers. This general technique has two different aspects.

--Extending the functionality through additional layers: This is also known as "vertical design" and mainly addresses the third and fourth items in the discussion immediately after the third general goal in Section 5.1. In this approach, components are built from primitive building blocks. Every building block is designed to form an intermediate layer, which adds a specific aspect of functionality to the whole component. Building a complex component then amounts to selecting the building blocks whose functionality is desired and piling these blocks on top of each other. For example, Batory et al. [1993] demonstrates this technique for normal queues. Every aspect, such as the choice of the underlying container type (linear list, doubly-linked list, array, etc.), the storage management, and an optional garbage management technique, is realized by a building block. Each building block is based on an abstract interface of a queue and in turn provides an abstract interface of a queue. This allows a composition in layers.

As a prerequisite, these components must be "plug-compatible." Ideally, each building block provides the same conceptually polymorphic interface. Then an arbitrary selection of building blocks may be plugged together in an arbitrary order. However, Batory et al. [1993] demonstrates that this total compatibility is not even realistic for components as simple as normal queues, not to mention more complex components such as graphs.

This means that the choices for two different aspects cannot be assumed to be polymorphically exchangeable. In the extreme case plug-compatibility can only be achieved for pairs of aspects. To achieve global "pluggability," we need a strict, very restrictive scheme. For example, we could reserve every layer for one particular aspect and fill every layer by a realization of its aspect (a dummy filler, if the aspect is irrelevant for a component). In particular, when a component is built from such a layered set of building blocks, none of the layers may be omitted. This would solve the problem, but seems impractical: whenever a new aspect comes into the game, all existing components which were built from this set must be revised.

--Modifying the functionality through additional layers: This aspect addresses one of the problems of type specialization which were discussed in the beginning of this subsection: conflicting options. To stick to the example of directed and undirected graphs: a directed graph data structure D G and an undirected graph data structure UG are not made compatible by means of inheritance, but by additional types, DG' and UG'. An object of the type DG' (respective UG') keeps an internal UG (DG) object, offers the same interface as DG (UG), and realizes a directed (undirected) view on the internal UG (DG) object. Then DG and DG' may be made polymorphically exchangeable, and likewise UG and UG'. So, a component that implements an algorithm on directed graphs may be applied to a real directed graph of type DG or to an undirected-viewed-as-directed graph of type DG', and vice versa.

For instance, this design principle is reflected by the various graph types in the standard library for the Sather programming language [Omohundro 1993].(22) To give a concrete example: there is a graph-view type which keeps an internal directed graph and provides the same interface as this internal graph. However, this type exchanges the meaning of in-going and out-going edges of a node: every in-going edge in the internal graph is presented as an out-going edge and vice versa. In other words, this type simulates the reverse graph of the internal graph. Another graph-view type realizes a filter on directed graphs. This type is associated with two predicates, [P.sub.n] and [P.sub.e], where [P.sub.n] applies to nodes and [P.sub.e] to edges. The view presented by this type is a subgraph of the internal graph. This subgraph contains all nodes for which [P.sub.n] is fulfilled and all edges such that [P.sub.e] is fulfilled for this edge and [P.sub.n] for both endnodes. One problem occurs in both aspects of composition in layers: the third general goal formulated in Section 5.1 is not really achieved. In fact, the functionality design of a queue (see above) may concern many methods of the queue, potentially all of them. For example, garbage collection must at least be incorporated in the insert and remove methods of the queue, in the constructor, and in a method for final clean-up. On the other hand, a reverse graph view, as in the Sather graph library, might affect virtually every method. Consequently, every building block is a "fat" component, which contradicts Goal 3.

Linear iterators. The concept of iterators is quite common in object-oriented programming and one of the fundamental design patterns [Gamma et al. 1995]. We will briefly review this concept.

An iterator type is a light-weight type (typically one or two pointers and possibly some bookkeeping information) and associated with a linear container class, for example, linear list, stack, queue, array, or search tree. A valid object of an iterator type is associated with a container object and a single item in this container. At least, an iterator provides methods for three tasks:

(1) accessing the data of the associated item;

(2) testing the iterator for validity;

(3) advancing the iterator to the very next item (once all items have been passed, the iterator becomes invalid).

The iterator approach has been adopted in various previous work. Among all of this work, the design of the STL [Musser and Saini 1995] had--and still has--the most practical impact. In fact, the core of the STL has become part of the C++ standard library,(23) and the design principles of the STL have greatly influenced the other parts of this library. Appendix E briefly describes the design ideas behind the STL.

Iterators may form an additional layer of indirection as required in the second general goal from Section 5.1. The interface of this layer to algorithms may be kept conceptually polymorphic, so that the first general goal is also achieved. The design of the STL demonstrates this: every linear container type comes with some specific iterator types, and every algorithm solely accesses the underlying containers by means of iterators. In other words, exchanging a data structure amounts to exchanging the representing iterator type. To some extent, an iterator-based design also achieves the third general goal in Section 5.1. The key insight is that composition in layers (see above) may also be applied to such an iterator-based layer of indirection.(24) Experience shows that the problems of composition in layers, which were discussed above, are more easily manageable in this case, because only the iterator types are involved. These types are small and not too sophisticated (and thus easy to revise in a maintenance process).

Gluche et al. [1998] implements an exemplary building block for composing STL iterators in layers. An object FI of this filter iterator type contains an object I of another iterator type, which is conceptually polymorphic in FI, and provides access to a selection of the items over which I iterates. More specifically, FI is associated with a predicate. This predicate applies to the items over which I iterates. The advance method of FI advances I until I meets an item that fulfills the predicate (or until I becomes invalid, in which case FI also becomes invalid). However, two important questions remain open:

--The concept of iterators has been developed for linear containers. Typically, a more complex data structure also exhibits some linear structure. For example, a graph may be viewed as a linear container of nodes and a linear container of edges. However, this view does not really capture the essence of a graph structure. Other ways of iterating over the elements of a graph, which allow navigation through the structure, are also necessary. Hence, to be generally useful for algorithmics, the concept of iterators must be extended.

--Items 1(a) and (b) in Section 3.1 require that an algorithm is adaptable to different data structures. This is not a real problem in the STL, because there all data structures are linear and thus not too different from each other. In contrast, the differences between various graph abstractions need further consideration.

Adjacency iterators. In principle, it is well-understood how the concept of iterators may be extended to complex data structures such as graphs. Several libraries reflect this (e.g. the AAI base class library(25)). The following kinds of iterators are needed especially for graphs:

--A linear node iterator type, which iterates over the set of all nodes in a graph.

--A linear edge iterator type, which iterates over the set of all edges in a graph.

--An adjacency iterator type, which is associated with a fixed node and iterates over the nodes adjacent to this node (in other words, over the edges incident to this node).

Any kind of navigation through the structure of a graph may be reduced to a sequence of operations on a dynamically changing set of adjacency iterators. This set always identifies the nodes which form the current "frontier line" of the navigation (see Figure 3). The current adjacent node (incident edge) of an adjacency iterator implicitly marks the borderline between the edges incident to this node which have already been scanned for navigation from the edges incident to this node that were not yet seen. To push the frontier line forward, adjacency iterators must provide an additional clone method, which applies to every valid adjacency iterator and places a new adjacency iterator on the current adjacent node.

For example, a depth-first search could maintain a stack of adjacency iterators. A forward step in this search would then amount to calling the additional clone method for the top element of the stack, pushing the resulting adjacency iterator onto the stack, and advancing the previous top element to its next adjacent node. A backtrack step is performed whenever the top element has become invalid or is placed on a node that has already been seen before. In contrast, a breadth-first search could maintain a normal queue of adjacency iterators. Here, a forward step would mean to remove the top element I from the queue, traverse the list of the nodes adjacent to I, apply the additional clone method in every iteration step to I, and append the resulting adjacency iterators to the queue.

Linear node and edge iteration are special cases of sequentially iterating over a linear sequence of items, which is well understood. However, the third type of iteration raises two questions:

(1) What exactly do the terms "adjacent" and "incident" mean here? What do they mean for directed graphs; what do they mean for undirected graphs and other variants?

(2) Item 1(a) in Section 3.1 requires that the meaning of "adjacent" and "incident" for one type of graph be mapped onto the meaning for another type of graph (see the second open question at the end of the previous approach, linear iterators). How can this mapping be achieved without sacrificing the third general goal in Section 5.1?

To the best of my knowledge, these questions have not been addressed systematically or formally up to now. However, they seem to be too complex to be discussed purely informally. Appendix F introduces a rigorous formal framework, which is intended to answer these questions satisfactorily.

Data accessors. Item 4 in Section 3.1 is not addressed at all in any of the programming methodologies discussed so far. In fact, in typical implementations of graph algorithms, the organization of the node and edge attributes is hard-wired, even if much care is taken to decouple the algorithm from the organization of the graph structure otherwise. This is a serious gap in the encapsulation of the underlying graph data structure. The concept of data accessors is intended to fill in this gap. This concept was originally introduced in [Kuhl and Weihe 1997] to enhance the flexibility of the algorithms in the STL (see Appendix E).

The key abstraction for Item 4 in Section 3.1 is to regard an attributed graph (i.e. a graph with node and edge attributes) as a graph that is equipped with two tables: one table of node attributes and one table of edge attributes. By a table, we mean a bunch of data that is organized into rows (nodes/edges) and columns (attributes). All entries in a column are of the same data type, which may be regarded as the column's type. Every row is a record which contains one slot for every column. In this perspective, a table is merely a conceptual entity; the physical organization of the data in data structures is arbitrary and need not reflect this conceptual viewpoint. Typically, an implementation of a table is based on a linear container type, whose items are associated with the rows of the table. For example, the item type of this container may be a record type comprising one slot for each column. Alternatively, the container may contain a mere ID for each row, and the values of the individual attributes are stored in separate data structures. Note that these two extreme cases correspond to Items 4(a) and (b) in Section 3.1 (see also the discussion of Problem II in Section 2.1).

In any case, iterators can be used to sequentially access the rows of a table. This decouples algorithms from the concrete organization of the sequence of rows. However, the organization of the columns is not encapsulated. For instance, suppose a table is organized as a list of a record type which stores the values of all columns, and suppose this table contains a column named a. Reading and overwriting the value of this column in the row identified by the STL-style iterator iter looks like this in C++ (see Figure 9):

x = (*iter) .a; (*iter) .a = y

[ILLUSTRATION OMITTED]

The evaluation of the expression (*iter) yields a reference to the current row of iter. The second line of code is legal only if the attribute a is writable. If such a statement occurs in an algorithm, this hardwires the organization of each row as a record of column values. To change the organization of the attributes, each such line of code in the algorithm must be modified. This contradicts the second general goal in Section 5.1.

To encapsulate the access to column a, this task is delegated to a data accessor object da, which is firmly associated with its column (in contrast to iterators, which are not firmly associated with individual rows). This object provides a method get, which receives an iterator iter as an argument and delivers the value of its associated column in the row identified by iter. Moreover, if this column is writable, da provides an overwriting method set. In summary, if a data accessor a is used to encapsulate the access to a, the above code snippet in STL style would be replaced as follows:

x = da.get(iter); da.set (iter,y);

The syntactical difference is marginal. However, it bears strong consequences: if such a line of code appears in an algorithm and da is conceptually polymorphic in this algorithm, then the implementation of get and set may be changed silently by exchanging the actual type of da. This closes the gap in the encapsulation of complex data structures, which violated the second general goal in Section 5.1. Figures 9 and 10 illustrate the difference.

[ILLUSTRATION OMITTED]

Like iterators, data accessors may also be organized by composition in layers. Kuhl and Weihe [1997] demonstrates this by means of an example from business administration: the rows of a table are the employees of a company, and the total salary of an employee is composed of a fixed and a variable part. These two parts are materialized attributes of employees. A data accessor for the total salary may be a primitive building block based on two further data accessors: one for the fixed part and one for the variable part of the salary. Hence, if the meaning of the total salary in relation to the fixed and the variable part changes (e.g. if a third kind of salary is added), only this building block is affected.

Method get of this building block calls the method get of both underlying data accessors and delivers the sum of their results. On the other hand, method set overwrites the variable part by the second argument (which is regarded as the new total salary) minus the fixed part.(26)

Items 4(c) and (d) in Section 3.1 are further typical tasks of data accessors composed in layers: a caching mechanism for an attribute is naturally delegated to a building block for data accessors, which encapsulates a reference to the data cache. On the other hand, computing the Euclidean length of an edge from the coordinates of its endnodes is naturally realized as a building block which is based on data accessors for node coordinates.

A combination of iterators and data accessors is especially useful in achieving the third general goal from Section 5.1. In fact, such a combination separates row-oriented aspects such as iteration over selected rows (the filter iterator in the above section about linear iterators) from column-oriented aspects such as computing the Euclidean length of an edge. If an aspect is modified, only the corresponding component must be changed. It seems that this cannot be satisfactorily achieved unless column-oriented aspects are factored out into components like data accessors, which are only loosely coupled with iterators.

The reader is referred to [Gluche et al. 1998; Kuhl and Weihe 1997] for all technical details and in-depth discussions.

Aspect-oriented programming (AOP). This new concept does not fit into our discussion, because it does not address the design of components as it is usually understood. Nonetheless, we briefly touch upon AOP, because it has been gaining much attention throughout the last few years and it addresses most goals from Sections 5.1 and 5.2. See Kiczalez et al. [1997] for an introduction and a discussion of related approaches, Irwin et al. [1997] and Mendhekar et al. [1997] for instructive case studies from the algorithmic realm (matrix algebra and image processing), and Videira Lopes and Kiczales [1998] for an integration into Java (called AspectJ).(27)

Like vertical design (see the paragraphs on "composition of components in layers" earlier in Section 7.1), AOP factors out every aspect into a separate set of exchangeable units, which realize this aspect in different ways. However, these units are of a new kind: each of these units realizes a choice for an aspect in its pure, abstract form, which means that it does not depend on the details of the implementations of the other aspects. This is where the new language features are needed: any such unit is explicitly defined to serve as a choice for an aspect, and a component is customized in the source code by a set of choices for its aspects. It is the compiler's task to build the component by interweaving these aspects into one block of code.

For instance, Items 1-4 in Section 3.1 would make good aspects in the sense of AOP. To give a concrete example: each of the examples in Item 4(d) could be realized as a separate programming unit (called an aspect program), which may be summarized like this: "at every point where the length of an edge is to be read, the value is to be computed from other information as specified in this aspect program." From a pragmatic viewpoint, the main difference from a conventional implementation of this transformation as a separate unit is that such a unit need not be manually invoked at every point where it applies. Instead, only the above summary has to be specified in a certain language, and the compiler (more precisely, the weaver) inserts all invocations automatically.

Hence, in theory, the three goals from Section 5.1 are achieved with optimal locality: the transformation is not only factored out into a small unit of source code; it is not even necessary to refer to it at any other point in the code because the aspect program itself provides a specification where to interweave it. Preliminary case studies [Irwin et al. 1997; Mendhekar et al. 1997] suggest that this is not pure theory. Furthermore, at the end of Section 7.2 we will see that AOP is also useful for the goals from Section 5.2. In summary, a broad acceptance of AOP and an integration into mainstream programming languages would be quite promising for algorithmic software development.

Integration of algorithms and data structures. Finally, a completely different approach should be mentioned, one which does not regard the underlying data structures as a base of algorithms, but as an integral part of them. This means that the algorithm plus its underlying data structures are viewed as one, indivisible component. For example, Weide et al. [1994] implements such a design for Kruskal's algorithm for minimum spanning trees. (Integration of algorithms and data structures is but a minor aspect of Weide et al. [1994]. See Section 7.2, paragraph on "algorithmic generators and loop kernels," for the crucial aspects of the concept in Weide et al. [1994]).

Despite the merits of this approach,(28) it seems that it is at odds with the general goals in Section 5.1, as they amount to a loose coupling between algorithms and their lower level (the data structures).

7.2 Adaptation to the Higher Level: Client Code

Traditionally, algorithms are implemented as subroutines. In contrast, in all of the following approaches, algorithms are implemented as abstract data types (see Appendix B). Such a data type provides one or more methods which execute the whole algorithm or parts of the algorithm. The latter kind of methods allows the client to control the execution of the algorithm. If this control is fine-grained, that is, if these methods perform elementary, fast steps of the algorithm, the overhead caused by the additional method calls may not be negligible. However, modern compilers might be able to optimize away these method calls through in-lining techniques (at least if the algorithm component is not dynamically polymorphic in the client).

Strategy pattern. This is one of the fundamental design patterns [Gamma et al. 1995] and addresses the tenth general goal in Section 5.2. The other general goals in Section 5.2 are not addressed. Every algorithm is implemented as an abstract data type which provides a method to execute the algorithm as a whole. If two algorithms are exchangeable from a theoretical viewpoint, they are kept exchangeable by means of conceptual polymorphism.

In programming languages which allow one to treat subroutines as first-class objects (see Appendix C), conceptual polymorphism of algorithms can be expressed even if they are not implemented as abstract data types, but as mere subroutines. Nonetheless, if algorithms are implemented as data types, the strategy pattern can often be applied more smoothly and conveniently. The reason is the following: assume that algorithms [A.sub.1], ..., [A.sub.k] are exchangeable from a theoretical viewpoint. Now, every algorithm Ai may be parametrized by additional control parameters, which appear in the argument list of [A.sub.i], but not in that of any other algorithm [A.sub.j]. However, these differences in the argument lists destroy exchangeability. On the other hand, if [A.sub.1], ..., [A.sub.k] are implemented as abstract data types, these control parameters can be moved to the argument lists of the constructors. Hence, the methods of [A.sub.1], ..., [A.sub.k] which execute the algorithms proper may all have the same syntax, which ensures exchangeability.

In the beginning of Section 2, we mentioned that composing algorithms with subalgorithms may be viewed as a special case of the problem to adapt algorithms to clients. This suggests the application of the strategy pattern to keep subalgorithms exchangeable inside an algorithm. In a case study on algorithms for the maximum-flow problem, Gallo and Scutella apply this idea rigorously to compose an algorithm hierarchically from its subalgorithms at run time [Gallo and Scutella 1993]. However, apparently, the subalgorithms in Gallo and Scutella [1993] were not designed for adaptability to various contexts; they were just designed to fit into the system presented in Gallo and Scutella [1993], which is entirely devoted to the maximum-flow problem. It is not clear whether this approach achieves flexible adaptability as it is understood here. In fact, an algorithm A may be exchangeable with algorithm B in one context and with algorithm C in another context, but B and C are not compatible. A simple example is breadth-first search, which is exchangeable with depth-first search in some sense, and with Dijkstra's algorithm in another, incompatible sense.

One possible approach is to implement all algorithms as stand-alones and to add context-specific conceptual polymorphism afterwards. The first part of Weihe [1998] demonstrates this technique in C1++.(29)

Algorithmic generators and loop kernels. Algorithmic generators have been introduced by Flamig [1995]. The approach presented in Weide et al. [1994] organizes algorithms in a quite similar fashion. An algorithmic generator is basically an algorithm component which computes and delivers its output step-by-step on request. The running example in Flaming [1995] is an algorithm that computes all prime numbers within a specified interval of integral numbers in increasing order. At any stage, the logical state of an instance of the algorithmic generator is defined by this interval and by the last delivered prime number. The component provides a method to deliver the very next prime number. To fetch all prime numbers, a client must contain a loop, in which this method is invoked until the algorithm generator indicates that all prime numbers have been delivered (e.g. this can be indicated by delivering an impossible value).

The main intent of algorithmic generators is to achieve the ninth general goal in Section 5.2. The idea is the following: if the client is able to fetch the output of an algorithm piece-by-piece, the client itself may format the output according to its own needs.(30)

As a by-product, algorithmic generators achieve the fourth general goal from Section 5.2. Moreover, the general goals 5 and 8 are achieved, because the client controls the core loop: suspension and termination are controlled through the break condition of the loop; on the other hand, to merge the core loops of several algorithms into one algorithm, it suffices to implement a loop whose body performs one iteration of each of these core loops. The general goals 6 and 7 are not addressed and not achieved. This is a pity, because it seems that the full value of the general goals 4, 5, 8, and 9 highly depends on the sixth general goal.

The loop-kernel concept has been developed independently and is extensively discussed in Weihe [1997]. In retrospect, it may be viewed as a variation of algorithmic generators, which additionally realizes the general goals 6 and 7 in Section 5.2.

Algorithms as iterators. This technique may be viewed as a special case of algorithmic generators. For example, in the AAI base class library,(31) depth-first search and breadth-first search are realized as linear node iterators. In other words, the output is the set of all nodes that are visited during the search. From a client's perspective, there are two differences to a normal node iterator:

--The order in which the nodes are visited reflects the search strategy.

--Only the nodes reachable from the root(s) of the search are visited.

Clearly, only a few algorithms may be interpreted as node or edge iterators. For these algorithms, the general goals 5 and 8 from Section 5.2 are achieved; goals 6, 7, and 9 are not addressed and not achieved. Again, this might reduce the value of the other goals.

Iteration in Sather. Iterators in Sather [Omohundro 1993] (called iteration methods in the following to avoid ambiguities) generalize typical loop constructs in mainstream programming languages [Murer et al. 1996].(32) In Sather, iteration methods are specific methods of abstract data types, which are not really subroutines as described in Appendix B. Such an iteration method may only be called within a loop. Unlike a normal subroutine, it may have two different ways of terminating the methods: a yield statement passes the flow of execution over to the point immediately after the call to the method, and a quit statement breaks the loop, which means that execution is resumed at the point immediately after the loop.

In other words, a yield statement is much like a normal return statement in subroutines, whereas a quit statement is similar to a combination of such a return statement and an unconditional loop break immediately afterwards. However, there is a subtle difference: throughout the loop, an iteration method may have its own, private, internal state. This state may only be modified inside this iteration method, and the state is lost once the loop terminates. In other words, the iteration method realizes an anonymous object, which behaves like an algorithm iterator (see the previous approach above) and whose lifetime is bound to the execution of the loop. This anonymous object is initialized in the call to the iteration method in the very first iteration of the loop. In each further iteration, this call advances the iteration method to its next state. When the flow of control leaves this loop and reenters it later on, a new anonymous object is created, which is completely independent of the object in the previous execution of the loop.

An algorithm could be implemented as an abstract data type such that the execution of its core loops is delegated to iteration methods. Such an iteration method would receive an argument of the Boolean type, which decides whether a call to the iteration method shall end with a yield or quit statement. Such a design is quite similar to loop kernels, and the general goals 4 and 8 are clearly achieved. Goal 6 is also straightforwardly achievable. However, goal 7 might not be easy to achieve, because the preprocessing (i.e. the initialization) and the iteration are performed by the same method. There are certainly work-arounds, but this might not conform to the philosophy of iteration in Sather.

Moreover, a temporary suspension of an algorithm (general goal 5) might cause design problems. As usual, consider an example where an algorithm component in an interactive system is temporarily suspended to allow a completely unrelated user interaction. Since iteration methods in Sather are strictly bound to loops, all interactive functionality must be mixed into the core loop(s) of the algorithm. However, a clean design might not always be possible without a strict separation of these mutually unrelated tasks.

Algorithm frameworks. Frameworks are a general object-oriented design methodology [Lewis "and friends" 1995]. See Holland [1992] for a concrete example of an algorithm framework. In an algorithm framework, the algorithm is designed as a base class, and this base class provides a method which executes the algorithm as a whole. The crucial design task is to identify the "skeleton" of the algorithm, which is common to all applications, and to determine all points in the algorithm where a possibility to change or extend the behavior is necessary to achieve flexible adaptability. Each of these points is realized as a method of the base class. Derived classes may overwrite these methods to customize the algorithm to concrete contexts.

If designed carefully, an algorithm framework actually achieves the fourth general goal from Section 5.2. The sixth general goal is not addressed explicitly, but is also easily achievable: for this, the base class must export its logical state to all derived classes. The general goals 7, 9 are not addressed. Goal 10 could be realized by leaving the choice of subalgorithms to subclasses.

In principle, the general goals 5 and 8 may also be achieved. This is a trivial and natural task if algorithms are implemented as, say, algorithmic generators or loop kernels (see above). However, in the case of algorithm frameworks, this task might not be trivial at all, and the design of the whole software system may suffer. In fact, frameworks are intended to control the execution, which means that the core loops are implemented inside the framework [like in Holland 1992]. However, goals 5 and 8 require that this control can be taken over by the client. As in the previous approach (iterators in Sather), this may lead to an undesired interdependence of the algorithm and unrelated parts of the package.

Robustness-oriented design. In Item 6(h) in Section 3.1, the notion of robustness was introduced. This is a primary design goal of the Karla library [Frick et al. 1995].(33) Ideally, every algorithm component is based on a specification of its functionality and comes with integrated robustness checkers, which completely check the component against this specification.

In Section 3.1, we saw that a complete robustness checker that is acceptable for all variants of Dijkstra's algorithm is not likely to exist. Hence, the question whether incorporated robustness checkers preserve efficiency and adaptability remains open and might require further practical research.

AOP revisited. As announced at the end of Section 7.1, we conclude Section 7.2 with a discussion of AOP in view of the goals stated in Section 5.2. First of all, the output of an algorithm and its subroutines may be viewed as aspects in the sense of AOP. This means that Goals 9 and 10 are addressed and certainly achieved.

However, the notion of aspect in the sense of AOP is more general than it has revealed itself to be so far. In fact, Kiczalez et al. [1997], Mendhekar et al. [1997], and Irwin et al. [1997] discuss several further classes of aspects. Among them, the class of fusion aspects is particularly interesting in view of the goals from Section 5.2. Roughly speaking, a fusion aspect is a rule that tells the compiler (weaver) a loop pattern. Any two loops that conform to this pattern could be folded into one loop.

For example, Mendhekar et al. [1997] defines a fusion pattern for simple iterations over the pixels of a two-dimensional image and use this pattern to fold a chain of image-processing filters into one filter. Basically, such a filter consists of a loop over all pixels and applies a certain operation to each of them. All of these loops are folded into one loop, which meets every pixel once and whose body applies the operations of all filters.(34) Obviously, such a fusion pattern is closely related to goals 4 and 8. Goal 5 might also be realizable.

8. DOCUMENTATION

It is fairly easy to specify the functionality of an algorithm component which is implemented in a traditional style, that is as a single, monolithic subroutine with fixed, hard-wired data structures for the input and the output. In fact, it suffices to specify the set of feasible inputs (preconditions) and the output as a function of the input (postconditions). Optionally, such a specification could also include an estimation of resource requirements (notably run time and space) as a function of the input and the output.(35) The problem of formulating this kind of specification is well understood, and sufficient formal methods are available for it.

However, the problem is much more complex if an algorithm component is designed according to the genera] goals 1-10. Basically, there are three reasons for that:

--Users might expect that an algorithm component is designed in the traditional style, and another design may cause confusion. This confusion must be taken into account by the author of the documentation.

--Experience shows that a high degree of flexibility may be a source of confusion in itself.

--The fourth, fifth, and sixth general goals from Section 5.2 introduce a new aspect: state. A traditional implementation can be documented in a purely declarative, state-less style. However, if a component offers stop points and exports its logical state at these stop points, the behavior of the component depends on its current state, which in turn depends on the "history" of the component. State-oriented documentation is usually based on representation invariants. See [Meyer 1994] for a thorough introduction.

In the adaptation of our concepts to LEDA,(36) we tried to overcome these problems. Due to this aim, we additionally implemented a couple of subroutines, which are mere partial or complete customizations of the loop-kernel class (cf. Section 7.2) for typical types of contexts (incl. pre- and postprocessing). Clearly, these subroutines are much more convenient to use than the loop kernel itself. Typically, the implementation of such a customizing subroutine is very short. Thus, if the annotated sources of these subroutines are freely distributed as a part of the documentation, they may also serve as tutorials for using the full power of the underlying loop kernel. Moreover, it might be reasonable to implement various speed-up techniques in advance and to describe their potential applications and their usage in the documentation.

Empirical experience must show if this kind of documentation will be broadly accepted by users.

9. CONCLUSION AND OUTLOOK

In this paper, we addressed the question what flexible adaptability of an algorithm component really means. However, this problem has many facets, and we only could touch upon some of them.

The limits of this paper were worked out in Section 6. Each of these limiting aspects may be regarded as an interesting future research direction.

ACKNOWLEDGMENTS

I would like to thank the LEDA people--Kurt Mehlhorn, Stefan Naher, and Christian Uhrig--for fruitful discussions and for a lot of constructive criticism. Special thanks to my co-workers, Dietmar Kuhl and Marco Nissen. Finally, I would like to thank one of the anonymous reviewers for his/her critical view and many helpful suggestions.

(1) In this paper, terms like "error-prone" always refer to errors that are not caught by the compiler and must therefore be found by extensive test runs. This distinction results from the general experience that compilation-time errors are relatively "cheap" and, by definition, never make the delivered production code unreliable.

(2) See also http://www.mpi-sb.mpg.de/LEDA.

(3) C++ Final Draft International Standard, ISO/IEC 14882.

(4) This distinction will reappear in several later sections.

(5) For example, effects like these occurred in a project in which I was involved a few years ago and which used conversions to integrate various algorithms for scheduling problems into one package.

(6) To be precise, C++ class templates. See Appendix D.

(7) Weihe [1997, sec. 2.2] discusses several variations of these two alternatives.

(8) Unless the underlying graph data structure supports access to the in-going edges of a given node. In this case, the predecessor of a node v [element of] V in the depth-first tree can be determined by a scan over the node labels of all tails of its in-going edges: the tail with the maximum label less than the label of v is the predecessor. However, in general, such a support cannot be assumed.

(9) Basically, a hypergraph differs from a normal graph in that a node may connect more than two edges as indicated in Figure 2(e). For conciseness, we will only consider undirected hypergraphs. The variety of definitions for directed hypergraphs is another example of the diversity of graph abstractions.

(10) This example was taken from Soukop [1994, sec. 2.6].

(11) This is an example of the design pattern flyweight [Gamma et al. 1995]. This scenario may appear in contexts in which the length of an edge models nongeometric aspects such as graded travel charges.

(12) Items 6(e)-(g) might not be important tasks especially for Dijkstra's algorithm, since this algorithm is very fast even on very large instances. However, these items are listed here for completeness, because they may be important for many other algorithms with higher run times.

(13) In the presence of zero-length edges, the test is more complicated, but still efficient.

(14) These figures stem from a joint project with the Deutsche Bahn AG; permission to visualize the data is granted by the TLC/Deutsche Bahn AG.

(15) For example, heuristic strategies of this kind have been implemented in an earlier version of the online information system of the Deutsche Bahn AG, the central German train and railroad company.

(16) Frequently, one can observe articles in various newsgroups, which are posted by people with little background in graph algorithms and urgently ask for implementations of Dijkstra's algorithm and other "simple" graph algorithms. This shows that do-it-yourself is often not a feasible alternative for programmers of client code.

(17) Some companies even delegate this task to other companies, which specialize in maintenance; see Pigorski [1997].

(18) Basically, by that we mean a documentation which includes an excerpt from Section 3.2 on a more technical level and a set of auxiliary data structures such as various priority queues, which support the different alternatives. A first attempt was made in Nissen and Weihe [1996], in which the environment is composed of the LEDA-specific implementation of the toolbox and of the data structures provided by LEDA itself; see also http://www.mpi-sb.mpg. de/LEDA/MANUAL/Graphs_Iterators.html and http://www.mpi-sb.mpg.de/LEDA/friends/git. html.

(19) Often, algorithms are presented in a recursive style. Clearly, every recursion can be turned into an iteration. For example, Flaming [1995] provides guidelines for that task especially for C++.

(20) One concrete example was analyzed in Nissen [1998]: the matching algorithm by Edmonds and its variations. This algorithm "shrinks blossoms," which basically means that cycles are collapsed into single nodes. For some implementations of the underlying graph abstraction, it may be favorable to map this complex modification onto basic modification steps such as node/edge insertion and deletion. However, for other implementations this strategy would be very bad. A common abstraction is necessary (and was developed in Nissen [1998]) to adapt an algorithm component to both kinds of implementations. So far it is unclear whether or not there is a generally appropriate abstraction for structural modifications beyond ad hoc techniques tailored to specific algorithms.

(21) Nonetheless, on a conceptual level, it is desirable to lean the abstract specification of the hierarchy of graph classes on the mathematical special-case relationships. The first part of Weihe [1998] introduces programming techniques which are intended to help translate such a mathematical hierarchy into a manageable software system (using geometric shapes as a running example).

(22) See also the Sather homepage; http://www.icsi. berkeley.edu/Sather.

(23) C++ Final Draft International Standard, ISO/IEC 14882.

(24) Unfortunately, this is not a central design principle of the STL, and only two building blocks for iterators (iterator adapters) are provided in the C++ standard; see Appendix E.

(25) http://www.aai.com/ AAI / IUE / spec / base / base-classes.html.

(26) This example demonstrates that even nonmaterialized attributes may be writable.

(27) The home page of the AOP project, http://www. parc.xerox.com/spl/projects/aop, provides up-to-date details.

(28) In the beginning of Section 7, it was noted that the "true merits" of the individual approaches are not the focus of this paper, only their relations to the goals from Section 5.

(29) Weihe [1998] uses geometric data structures as a running example. However, the presented techniques are fairly general and also apply to algorithm components.

(30) Dijkstra's algorithm and other graph algorithms are not presented as algorithmic generators in Flaming [1995], but in a traditional style as subroutines. This is not surprising, since the ninth general goal is not particularly relevant for Dijkstra's algorithm. For example, if an algorithm merely delivers the distance of every node from the root, a shortest-path tree can be constructed from this output as follows (see also Item 6(h) in Section 3.1): for every node w except for the root, one incoming edge (v, w) is identified, such that the difference between the distances of v and w from the root equals the length of (v, w). Special care must be taken if there are zero-length edges.

(31) See http://www.aai.com/AAI/IUE/spec/base/base-classes.html.

(32) See also the Sather home page; http://www. icsi.berkeley.edu/Sather. Section 4.5 in Murer et al. [1996] gives an example (in-order iteration over binary trees) which demonstrates that iteration methods allow an impressingly easy reformulation of inherently recursive algorithms in an iterative style. See also Footnote 19 for this aspect.

(33) See the Karla home page; http://i44www.info.uni-karlsruhe.de/~zimmer/karla.

(34) It might be worth mentioning that the concept of expression templates [Veldhuizen 1995] allows the efficient realization of such a folding in C++ (which is, however, quite tricky and much less elegant).

(35) For example, restrictions on the asymptotic run time are an integral part of the STL specification.

(36) See again http://www.mpi-sb.mpg.de/LEDA/ MANUAL/Graphs_Iterators.html.

(37) Classes are often defined in the literature as equivalence classes of objects, which share certain properties and behavior. From a pragmatic viewpoint, both views are identical.

(38) An extension to Eiffel; Sather home page: http://www.icsi.berkeley.edu/~sather.

(39) An extension to Java; Pizza home page: http://cm.bell-labs.com/cm/cs/who/wadler/pizza.

(40) For convenience, we regard the return value of a function as a member of the argument list.

(41) Clearly, semantical conformance is not decidable and is, thus, neither checkable at compilation time nor at run time. A few languages (e.g. Ada95) provide renaming features. Such a feature allows the use of concrete types whose syntactical functionality does not exactly conform to the usage of the placeholder type inside the component.

(42) To be precise, the second iterator refers to a sentinel behind the last item. However, this minor technical detail is irrelevant in our context.

(43) Unless the node type is dynamically polymorphic in the adjacency iterator; however, this is usually not desired.

REFERENCES

AHUJA, R.K., MAGNANTI, T.L., AND ORLIN, J.B. 1993. Network Flows. Prentice Hall, Englewood cliffs, NJ.

BATORY, D., SINGHAL, V., SIRKUN, M., AND THOMAS, J. 1993. Scalable software libraries. In Proceedings of the 1st ACM Symposium on Foundations of Software Engineering, pp. 191-199.

BLUM, M. AND WASSERMAN, H. 1994. Program result-checking: A theory of testing meets a test of theory. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS '94), pp. 382-392.

BRANDES, U., NEYER, G., SCHLICKENRIEDER, W., WAGNER, D., AND WEIHE, K. 1999. PlaNet--A software package of algorithms and heuristics for disjoint paths on planar networks. Discrete Appl. Math. 92, pp. 91-110.

BRANDSTADT, A., LE, V.B., AND SPINRAD, J. 1999. Graph Classes: A Survey. SIAM Books, Philadelphia, PA.

CLINE, M.P. AND LOMOW, G.A. 1994. C++ FAQs. Addison-Wesley, Reading, MA.

CORMEN, T., LEISERSON, C., AND RIVEST, R. 1994. Introduction to Algorithms. MIT Press, Cambridge, MA.

DERIGS, U. 1988. Programming in Networks and Graphs: On the Combinatorial Background and Near-Equivalence of Network Flow and Matching Algorithms. Springer, Berlin.

FLAMIG, B. 1995. Practical Algorithms in C++. Coriolis Group Book.

FRICK, A., ZIMMER, W., AND ZIMMERMANN, W. 1995. On the design of reliable libraries. TOOLS 17, 13-23.

GALLO, G. AND SCUTELLA, M.C. 1993. Toward a programming environment for combinatorial optimization: A case study oriented to maxflow computations. ORSA J. Comput. 5, 120-133.

GAMMA, E., HELM, R., JOHNSON, R., AND VLISSIDES, V. 1995 Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA.

GLUCHE, D., KUHL, D., AND WEIHE, K. 1998. Iterators evaluate table queries. ACM SIGPLAN Notices 33, 1, 22-29.

GOLUMBIC, M.C. 1991. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.

GROSS, J.L. AND TUCKER, T.W. 1987. Topological Graph Theory. Wiley, New York.

GUIBAS, L.J. AND STOLFI, J. 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graphics 4, 2, 74-123.

HOLLAND, I. 1992. Specifying reusable components using contracts. In Proceedings of the 6th European Conference on Object-Oriented Programming (ECOOP '92), 287-308.

IRWIN, J., LOINGTIER, J.-M., GILBERT, J.R., KICZALEZ, G., LAMPING, J., MENDHEKAR, A., AND SHPEISMAN, T. 1997. Aspect-oriented programming of sparse matrix code. In Proceedings of the International Conference on Scientific Computing in Object-Oriented Parallel Environments (ISCOPE '97). LNCS, Vol. 1343, Springer, Berlin.

KANAL, L. AND KUMAR, V. 1988. Search in Artificial Intelligence. Springer, Berlin.

KICZALES, G., LAMPING, J., MENDHEKAR, A., MAEDA, C., VIDEIRA LOPES, C., LOINGTIER, J.-M., AND IRWIN, J. 1997. Aspect-oriented programming. PARC Tech. Rep. SPL97-008 P9710042, http:// www.parc.xerox.com/spl/projects/aop/tr-aop.htm.

KREFT, K. AND LANGER, A. 1996. Iterators in the standard template library. C++ Rep. 8, 7, 30-37.

KREFT, K. AND LANGER, A. 1997. Building an iterator for the STL and the Standard Template Library. C++ Rep. 9, 2, 20-27.

KUHL, D., NISSEN, M., AND WEIHE, K. 1997. Efficient, adaptable implementations of graph algorithms. In On-Line Proceedings of the 1st Workshop on Algorithm Engineering (WAE '97). http://www.dsi.unive.it/~wae97/proceedings.

KUHL, D. AND WEIHE, K. 1997. Data access templates. C++ Rep. 9, 7, 15-21.

LAWLER, E.L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York.

LAWLER, E.L., LUBY, M., AND PARKER, B. 1983. Finding shortest paths in very large networks. In Proceedings of the 9th International Workshop on Graph-Theoretic Concepts in Computer Science. Trauner, Linz Austria, pp. 184-199.

LENGAUER, T. 1990. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, New York.

LENGAUER, T. AND THEUNE, D. 1991. Efficient algorithms for path problems with general cost criteria. In Proceedings of the 18th International Colloquium on Automata, Languages and Programming (ICALP '91).

LEWIS, T. "AND FRIENDS." 1995. Object Oriented Application Frameworks. Prentice Hall, Englewood Cliffs, NJ.

LISKOV, B. 1988. Data abstraction and hierarchies. ACM SIGPLAN Notices 23, 5.

MARTIN, R.C. 1996. The Liskov substitution principle. C++ Rep. 8 (Mar.).

MEHLHORN, K. AND NAHER, S. 1995. LEDA: A library of efficient data structures and algorithms. Commun. ACM 38, 96-102.

MENDHEKAR, A., KICZALES, G., AND LAMPING, L. 1997. RG: A case-study for aspect-oriented programming. Xerox PARC Palo Alto Tech. Rep. SPL97-009 P9710044, February 1997. http://www.parc.xerox.com/spl/groups/eca/pubs/ papers/PARC-AOP-RG97/.

MEYER, B. 1994. Object-Oriented Software Construction. Prentice Hall, Englewood Cliffs, NJ.

MEYER, B. 1995. Object Success: A Manager's Guide to Object Orientation, its Impact on the Corporation, and its Use for Reengineering the Software Process. Prentice Hall, Englewood Cliffs, NJ.

MURER, S., OMOHUNDRO, S., STOUTAMIRE, D., AND SZYPERSKI, C. 1996. Iteration abstraction in Sather. Trans. Program. Lang. Syst. 18, 1, 1-15.

MUSSER, D.R. AND SAINI, A. 1995. STL Tutorial and Reference Guide. Addison-Wesley, Reading, MA.

NISHIZEKI, T. AND CHINA, N. 1988. Planar Graphs: Theory and Algorithms. North-Holland, Amsterdam. Annals of Discrete Mathematics, Vol. 32.

NISSEN, M. 1998. Graph iterators--decoupling graph structures from algorithms. Diploma thesis, Univ. of Saarbrucken, Germany. Http://www. mpi-sb.mpg.de/~marco/english.html.

NISSEN, M. AND WEIHE, K. 1996. Combining LEDA with customizable implementations of graph algorithms. Http://www.informatik.unikonstanz.de/Preprints.

OMOHUNDRO, S. 1993. The Sather programming language. Dr. Dobb's J. 18, 11, 42-48.

OPDYKE, W.F. AND JOHNSON, R.E. 1993. Creating abstract superclasses by refactoring. In Proceedings of the ACM Computer Science Conference, pp. 66-73.

PAPADIMITRIOU, C.H. AND STEIGLITZ, K. 1982. Combinatorial Optimization:Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ.

PIGORSKI, T.M. 1997. Practical Software Maintenance. Wiley, New York.

SCHIRRA, S. 1998. Robustness and precision issues in geometric computation. In Algorithmic Foundations of Geographic Information Systems, Marc van Kreveld et al., (Eds.) Springer, Berlin. LNCS, Vol. 1340.

SCHULZ, F., WAGNER, D. AND WEIHE, K. 1999. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. In Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE '99), LNCS, Vol. 1668, Springer, Berlin.

SOUKOP, J. 1994. Taming C++. Addison-Wesley, Reading, MA.

TAIVALSAARI, A. 1996. On the notion of inheritance. ACM Comput. Surv. 28, 3, 438-479.

VELDHUIZEN, T. 1995. Expression templates. C++ Rep. 7, 26.

VIDAL, R.V.V. 1993. Applied Simulating Annealing. Springer, Berlin. Lecture Notes in Economics and Mathematical Systems, Vol. 396.

VIDEIRA LOPES, C. AND KICZALES, G. 1998. Recent developments in Aspect J. In Proceedings of the 12th European Conference on Object-Oriented Programming (ECOOP '98).

WEIHE, K. 1997. Reuse of algorithms: Still a challenge to object-oriented programming. In Proceedings of the 12th ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA '97) 34-48.

WEIHE, K. 1998. Using templates to improve C++ designs. C++ Rep. 10, 2, 14-21.

WEIDE, B.W., EDWARDS, S.H., HEYM, W.D., LONG, T.J., AND OGDEN, W.F. 1996. Characterizing observability and controllability of software components. In Proceedings of the 4th International IEEE Conference on Software Reuse, 62-71.

WEIDE, B.W., OGDEN, W.F., AND SITARAMAN, M. 1994. Recasting algorithms to encourage reuse. IEEE Software, 80-88.

APPENDIX A: CUSTOMIZATION CODE

Programming languages offer various ways to make a component (e.g. a subroutine or data structure) more flexible. Some details are left open in this component and must be filled in by the client code. We say that a component is well designed for customization if

--the effort to implement the customization information is negligible in comparison to the effort needed in implementing the component itself and

--the task of implementing the additional customization information is straight-forward (even from limited documentation) and not seriously prone to error.

For example, a routine for sorting an array of numbers relies on a comparison function for the number type. This is a binary predicate function for the number type. There are various ways to incorporate such a comparison function into an implementation of a sorting algorithm, for instance:

--The code of the sorting algorithm contains implementations of several alternative comparison functions, and an additional integral input parameter selects the alternative.

--The comparison function is realized as a callback function, that is as a first-class object (see Appendix C), which is also handed over to the sorting algorithm as an additional input parameter.

--Conceptual polymorphism (Appendix D) is used to abstract from the idea of a state-less function. The comparison function is integrated into a conceptually polymorphic abstract data type (Appendix B), which also allows the encapsulation of additional data, on which the return value of the comparison function may depend.

Note that the latter possibility could be used to realize various other ways of customization, For example, a function object with state information could read additional customization information from a file, a socket, or another external source.

A sorting algorithm with a customizable comparison function is a good example of a well-designed customizable component. The real code of typical comparison functions can be implemented in a straightforward way within a few lines of code. The encapsulating code around these few lines (e.g. a function header or the declaration of an encapsulating abstract data type) is straightforward, and the possibilities to introduce errors that are not caught by the compiler are limited and easy to survey. Hence, the encapsulation code is usually not significantly error-prone in the sense of Footnote 1.

APPENDIX B: ABSTRACT DATA TYPES

Formally, an abstract data type A is formed by a ground set, optional auxiliary sets, and methods. In the object-oriented literature, abstract data types are often identified with classes, which are the feature of choice for the implementation of abstract data types in mainstream object-oriented languages.(37)

An object of A in a program has a certain lifetime, and throughout its lifetime, it is assigned an element of the ground set. This is the state of the object. Methods are subroutines whose input, output, and in/out arguments are elements of the ground set or elements of the auxiliary sets. A method of A may change the state of objects of type A. However, no subroutine except for the methods of A is allowed to change the state of an object of type A (this principle is usually called encapsulation). An abstract data type must come with one or more methods of a special kind, which are called the constructors of A and initialize the state of an object of type A. One of these constructors must be invoked at the beginning of the lifetime of every object.

For example, a stack of integral numbers is an abstract data type whose ground set is the set of all finite ordered sequences of integral numbers (incl. the empty sequence). Many implementations of the abstract data type "stack" provide exactly one constructor, which takes no additional arguments and assigns the empty sequence to the new stack. Moreover, methods like push, pop, top, and empty are common. The set of binary truth values (true, false) is an auxiliary set and used as the output of method empty.

APPENDIX C: SUBROUTINES AS FIRST-CLASS OBJECTS

Some languages offer built-in data types which allow one to store the addresses of subroutines in variables. The subroutine may be called through this variable. Pointers-to-functions in C and C++ are a low-level example of that; higher-order functions in functional languages are an example on a more abstract level. Pointers-to-methods in C++, closures in Sather,(38) and higher-order methods in Pizza(39) store the addresses of methods of abstract data types. All of these examples are strongly typed, meaning that every variable of such a built-in data type is bound to a specific number, a specific order, and specific types of the arguments of the subroutine.(40) This argument list must be specified in the declaration of the variable, and the variable can only store the addresses of subroutines whose argument lists match this declaration. Moreover, if a variable shall store the addresses of methods, not subroutines, it is further bound to a specific abstract data type and cannot store the address of a method of any other abstract data type. (The Java standard class java.lang.reflect. Method provides equivalent functionality, however, not strongly typed in this sense.)

APPENDIX D: CONCEPTUAL POLYMORPHISM

The term "polymorphism" is used in different ways in the literature. This appendix explains the usage in this paper. The meaning of the term is often bound to specific features of object-oriented programming languages. To indicate that our usage is more general and abstract, we will speak of "conceptual polymorphism" throughout the paper.

Conceptually polymorphic features in programming languages allow the programmer to leave open certain types in the implementation of components, so that this component may be used with different types. Inside the implementation of this component, these types are represented by "placeholders," which are formal type identifiers. The types that are eligible for replacing a placeholder are called polymorphically exchangeable with respect to this formal type.

Existing conceptually polymorphic features may be classified according to two schemes:

--Static/dynamic polymorphism: Whether or not the concrete type must be chosen at compilation time or this decision can be deferred until the component is actually invoked at run time. For instance, the latter sort of polymorphism allows the definition of inhomogeneous sequences.

A concrete example of an inhomogeneous sequence is a sequence of different geometric shapes such as points, rectangles, and ellipses. These different geometric entities are usually represented by different abstract data types. Nonetheless, a list of objects representing geometric shapes may contain a mixture of different shape types. From the viewpoint of a list's client, all of these objects appear as objects of the placeholder type, which represents general geometric shapes. If conforming to the Liskov substitution principle [Liskov 1988; Martin 1996], this placeholder type merely offers methods such as rotating or translating shapes, which are applicable to all kinds of geometric shapes (in contrast, for example, to stretching in one dimension, which does not apply to symmetric shape types like circles and squares).

--Syntax-based/declaration-based polymorphism: This concerns the set of types from which a concrete type can be chosen to replace the placeholder in the component. A necessary condition for a type to be eligible is that it must support the functionality which is used within the component to work with objects of the formal placeholder type. This conformance requirement is purely syntactical.(41) Syntax-based polymorphism means that this requirement is also sufficient. In contrast, declaration-based polymorphism additionally requires that a concrete type is explicitly declared to be a candidate for replacing the placeholder.

Most common object-oriented languages offer inheritance, which allows a declaration-based dynamic polymorphism: the base class is the placeholder, and the derived classes are eligible to replace the placeholder. A few languages provide additional features especially for this sort of polymorphism (e.g. interfaces in Java).

Static polymorphism is realized in various programming languages by generic features. For example, this kind of polymorphism is syntax-based in Ada (generics) and C++ (templates), and declaration-based in Eiffel and in the most prominent proposals for adding genericity to Java. The main difference between Ada generics and C++ templates in this respect is that a generic Ada component must come with an explicit specification of the (syntactic) functionality required from the placeholder, whereas a C++ compiler must infer this information from the ways a placeholder is accessed inside a template. In the languages with declaration-based genericity, a declaration of eligibility is expressed by the corresponding mechanisms for dynamic declaration-based polymorphism: a concrete type is eligible to replace a certain placeholder in a static setting if and only if it is eligible to replace the same placeholder in a dynamic setting.

Dynamic, syntax-based polymorphism is realized in the SmallTalk programming language. Here, every type is polymorphic, and every object is of an anonymous type. As with C++ templates, there is no explicit placeholder, but the required syntax is implicitly defined "by usage." Whether or not an object provides the requested functionality is only determined at run time (in contrast to C++). If an object cannot appropriately react on such a request, an exception is raised, which means immediate termination of the whole program, unless this exception is caught and handled appropriately.

Many languages allow explicit overloading, that is different subroutines may be given the same name, provided the argument lists are sufficiently different, so no call to a subroutine may be ambiguous. This feature may be regarded as a simple version of static, syntax-based polymorphism and is also known as ad hoc polymorphism.

APPENDIX E: STANDARD TEMPLATE LIBRARY (STL)

The STL [Musser and Saini 1995] is completely based on static, syntax-based polymorphism as defined in Appendix D. The core functionality offered by the STL is a set of basic containers such as vectors, stacks, lists, and priority queues, all of which represent linearly ordered collections of items of a fixed type, the item type. The key abstraction in the STL is the concept of iterators (see the introduction of linear iterators in Section 7.1). In the STL, basic container algorithms such as copying and sorting do not access the containers directly, but indirectly, by means of iterators. The concrete types of the iterators are template parameters of the algorithm. Hence, bringing a new data structure into the game amounts to implementing appropriate iterator classes. This is not too much work, recipes are available [Kreft and Langer 1996, 1997], and the algorithmic code is not affected.

Inside an algorithm, a container is specified by two iterators, which refer to its first and last item.(42) The benefit is a high degree of flexibility: for example, restricting an algorithm to a subsequence of a container simply amounts to calling the algorithm with iterator objects referring to the beginning and the end of the subsequence. Moreover, STL comes with two iterator adapters, which allow one to seamlessly change the meaning of iteration in the spirit of composition in layers (Section 7.1): one adapter reverses the direction of iteration, which means that the algorithm is applied to the reverse container (although the container itself is not changed at all); the other one realizes each write access by inserting a new item at the end of the container (the default behavior of write access is overwriting the value of the item to which the iterator currently refers).

In the STL iterators are classified into input, output, forward, bidirectional (aka backward), and random iterators (see Figure 11). Roughly speaking, input iterators are only required to allow read access to an item's data, whereas output iterators are only required to allow write access. Forward iterators must allow read and write access. Bidirectional iterators are forward iterators that also provide a means of advancing the iterator in backward direction. Finally, random iterators are bidirectional iterators that can also be placed on a random item, which is specified by its position in the container.

This classification has been adopted for the STL (and for the C++ standard), because it reflects the functionality of the underlying containers: for a file that is open for reading (resp., writing), an input (output) iterator is appropriate; on the other hand, for a singly-linked list (resp., doubly-linked list, array), a forward (bidirectional, random) iterator is appropriate. This is a classification of requirements: a C++ class is one of these iterator classes if and only if its interface provides the required functionality. A hierarchy of requirements as in Figure 11 only appears on the conceptual, documentational level, not in the implementation, and does not induce an inheritance hierarchy or any other relation between the involved classes.

The following fundamental design rule allows maximal flexibility in combining algorithms with data structures:
      Data structures come with iterator classes of the highest type (in the
   hierarchy in Figure 11) whose required functionality can be easily and
   efficiently mapped onto the functionality provided by the underlying
   container. On the other hand, algorithms work on the lowest type in the
   hierarchy that fulfills the algorithm's requirements on the underlying
   container.


APPENDIX F: FORMAL FOUNDATION OF ADJACENCY ITERATORS

An adjacency iterator is associated with a fixed node and iterates over certain nodes which are regarded as being adjacent to the fixed node. See the discussion of adjacency iterators in Section 7.1. The meaning of adjacency depends on the underlying graph abstraction, that is directed graph, undirected graph, bidirected graph, etc. Hence, we first develop a generic scheme for different graph abstractions and then apply this scheme to various concrete graph abstractions.

F.1 Graph Views

An implementation of an algorithm must be based on a fixed abstract view of the underlying graph data structure, which may be different from the graph abstraction realized by this data structure. For example, in Section 3.1, Item 1, we noticed that Dijkstra's algorithm may be applied to directed graphs, undirected graphs, etc. However, even for an implementation that covers all of these cases, a fixed abstract view must be chosen on which the implementation is built. It seems that the abstract view "directed graph" is most appropriate for Dijkstra's algorithm (in contrast, for many other problems, including spanning-tree and matching problems, the abstract view "undirected graph" might be most appropriate). To adapt Dijkstra's algorithm to an undirected graph data structure, the abstract view "directed graph" must be expressed in terms of an undirected graph. We will say that the view "undirected graph" is adapted to the view "directed graph."

It is not reasonable to define a specific abstract view for every algorithm, but to define a couple of standardized abstract views (much like the small set of standardized abstract views on containers in Figure 11) and to base the implementation of every algorithm on one of them. Basically, there are two reasons for that:

--Since the number of abstract views in such a standard set is small, the number of adaptations of one abstract view to another one is small. In particular, it does not depend on the number of algorithms.

--The documentation for implementations of algorithms is leaner, because such a documentation may simply refer to the standard set in order to define the abstract view on which the algorithm is built.

F.2 Terminology

Throughout this section of the appendix, we will need the following basic definitions. A multiset is a finite set in which each element may occur more than once. The multiplicity of an element x of a multiset M is the number of occurrences of x in M and denoted by mult(M, x). This value is zero if x does not occur in M. The cardinality of a multiset is the sum of all multiplicities. The union [M.sub.1] [union] [M.sub.2] of two multisets is defined by addition of the multiplicities: mult([M.sub.1] [union] [M.sub.2], x) = mult([M.sub.1], x) + mult([M.sub.2], x). For a finite set S, M(S) denotes the set of all multisets whose elements belong to S. For M [element of] M(S), ord(M) denotes the ordinary set of elements of M, which is defined by

x [is not an element of] ord(M) for x [element of] S and mult(M, x) = 0,

x [element of] ord(M) for x [element of] S and mult(M, x) [is greater than] 0.

Moreover, for [M.sub.1], [M.sub.2] [element of] M(S), [M.sub.1] = [M.sub.2] is used to indicate that mult([M.sub.1], x) = mult ([M.sub.2], x) for all x [element of] S. An injection from a multiset [M.sub.1] [element of] M([S.sub.1]) onto a multiset [M.sub.2] [element of] M([S.sub.2]) is a multiset I [element of] M([S.sub.1] x [S.sub.2]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that all definitions except multiset union naturally extend the corresponding definitions for ordinary sets.

F.3 Incidence Structure

From Section 7.1 recall that an adjacency iterator iter is associated with a fixed node v and iterates over the nodes "adjacent" to v (in other words, over the edges "incident" to v). Moreover, recall that an adjacency iterator shall provide a clone method, which is applicable to valid objects and creates a new object referring to the current adjacent node.

We will not exclude loop edges (i.e. edges that connect a node with itself) and multiple edges. In fact, such a restriction would not make sense for most graph algorithms (although many textbooks and articles of original work assume this for notational convenience). Moreover, in many realizations of graphs (e.g. in realizations by adjacency lists), such a restriction cannot be efficiently maintained when edges are inserted. Hence, we drop this restriction.

Formally, we define an adjacency iterator type as an incidence structure. Such an incidence structure consists of four mappings, inc, adj, corr, and succ. Informally, inc(v) [element of] M(E) is the set of all edges incident to v [element of] V, which means the edges over which an adjacency iterator iter iterates if associated with v. Since we do not exclude loop edges, inc(v) may contain an edge twice.

On the other hand, adj(v) is the set of all nodes adjacent to v [element of] V, which are the nodes traversed by iter. If k edges point from v to some node w [element of] V, we have mult(adj(v), w) = k. Moreover, corr establishes the correspondence between the sequence of adjacent nodes and the sequence of incident edges over which iter iterates. Since this sequence depends on the node v with which iter is associated, corr maps pairs of nodes and edges onto nodes. More specifically, corr(v, e) = w means that v and w are the endnodes of e. Hence, we also require that corr is injective (in the sense of multisets).

The intent of succ is to identify the potential successor edges of every edge e [element of] E in graph algorithms that navigate through the graph structure. It follows that succ is closely related to the additional clone method of iter, which places a new iterator on the current adjacent node: succ is the set of all edges over which this new object iterates. For example, in a directed graph this is the set of all out-going edges of the node to which the current incident edge e of iter points. This means that the successors of e only depend on e. In contrast, in an undirected graph, the set of successors of e also depends on the orientation in which e is passed by the algorithm. In the formal definition of succ below, we will indicate this orientation by one of the endnodes of every edge. For notational convenience, we choose the head of the edge, the node on which the clone of iter is placed (the "link" between e and its successors).

Definition 1 (Incidence Structure) Let V and E be two finite sets. An incidence structure on (V, E) is a quadruple (inc, adj, corr, succ), where

inc : V [right arrow] M(E),

adj : V [right arrow] M(V),

corr : {(v, e): v [element of] V, e [element of] inc(v)} [right arrow] V,

succ: {(w,e): w [element of] V, e [element of] E, ([exists]v [element of] V: corr(v, e) = w)} [right arrow] M(E).

such that corr is an injection (in the sense of multisets), [[union].sub.e [element of] inc(v)] corr(v, e) = adj(v) for v [element of] V, E = ord([[union].sub.v [element of] V] inc(v)), and [[Summation].sub.v [element of] V] mult(inc(v), e) [is less than or equal to] 2 for e [element of] E.

F.4 Graph Views Revisited

Equipped with this terminology, we now turn our attention to the first question raised in the description of adjacency iterators in Section 7.1. More specifically, we will give a few examples of specific graph views, which might demonstrate the flexibility of incidence structures as a formal base (and the need for such a complex definition of incidence structures).

Directed graph: Informally, inc(v) is the set of edges leaving node v. Therefore, the incidence structure must also fulfill [[Sigma].sub.v [element of] V] mult(inc(v), e) = 1 for e [element of] E, which means that the sets inc(*) form a partition of E. Moreover, succ(w, e) = inc(w) for corr(v, e) = w, where v, w [element of] V and e [element of] E. To say it informally: the out-going edges of a node w are the successors of the in-going edges of w.

Two-way directed graph: This means that, from every node, both its in-going and out-going edges are accessible, and that both sets of edges are clearly distinguished from each other. Therefore, we superimpose two incidence structures, ([inc.sub.1], [adj.sub.1], [corr.sub.1], [succ.sub.1]) and ([inc.sub.2], [adj.sub.2], [corr.sub.2], [succ.sub.2]), such that

w [element of] [adj.sub.1](v) ?? v [element of] [adj.sub.2](w) for v, w [element of] V;

[corr.sub.1](v, e) = w ?? [corr.sub.2](w, e) = v for v, w [element of] V, e [element of] E;

[e.sub.1] [element of] [succ.sub.1] (v, [e.sub.2]) ?? [e.sub.2] [element of] [succ.sub.2] (v, [e.sub.1]) for v [element of] V, [e.sub.1], [e.sub.2] [element of] E.

Undirected graph: To model undirected graphs, we impose the following restrictions on the incidence structure:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

In other words, every edge is incident to exactly two nodes, these two incidence relations are indistinguishable, and the successors of an edge e at node v are all edges incident to v.

Bidirected graph: From Section 3.1, Item 1(a), recall the definition of bidirected graphs. The bidirected graph view is a variation of the undirected graph view. In a bidirected graph, the edges incident to a node are divided into two partition sets [Derigs 1988], making every set inc(v) the union of two sets: inc(v) = [inc.sub.1](v) [union] [inc.sub.2](v). Note that a global definition of mappings [inc.sub.1], [inc.sub.2]: V [right arrow] M(E) does not make any sense. In fact, for every node, the numbering of these two sets is arbitrary, and the common numbering of [inc.sub.1](v) and [inc.sub.1](w) for v [is not equal to] w bears no meaning.

The sets [inc.sub.1](v) and [inc.sub.2](v) are not necessarily disjoint: a loop edge may cross the partition line. This partition of inc(v) naturally induces partitions adj(v) = [adj.sub.1](v) [union] [adj.sub.2](v) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). The first two conditions for undirected graphs are also valid for bidirected graphs. The difference between undirected and bidirected graphs is expressed in terms of the mapping succ: we require e [element of] [inc.sub.1](v) ?? succ(v,e) = [inc.sub.2](v) and e [element of] [inc.sub.2](v) ?? succ(v,e) = [inc.sub.1](v) for v [element of] V, e [element of] inc(v). This condition replaces the third condition for undirected graphs above.

Bipartite graph: Clearly, undirected and directed bipartite graphs G = (V [union] W, E ) are special cases of general undirected and directed graphs. However, often it is necessary to have different adjacency iterator types for nodes of V and nodes of W. For example, the nodes in V are often assigned another set of attributes than the nodes in W. In this case, the nodes in V are of another type than the nodes in W. Consequently, two different adjacency iterator types are mandatory.(43) To capture this difference, we again superimpose two incidence structures, ([inc.sub.1], [adj.sub.1], [corr.sub.1], [succ.sub.1]) and ([inc.sub.2], [adj.sub.2], [corr.sub.2], [succ.sub.2]). In that, [inc.sub,1] and [adj.sub.1] are defined on V and [inc.sub.2] and [adj.sub.2] on W, and we require that [[union].sub.v [element of] V] [inc.sub.1](v) = [[union].sub.v [element of] W [inc.sub.2](v) = E. Moreover, we have [adj.sub.1](v) [element of] M(W) for v [element of] V, [adj.sub.2](v) [element of] M(V) for v [element of] W, [succ.sub.1] (v, e) = [inc.sub.2](v) for v [element of] W, e [element of] [inc.sub.2](v), and [succ.sub.2](v, e) = [inc.sub.1](v) for v [element of] V, e [element of] [inc.sub.1](v). Intersection-free embedded graph with faces: This is an example of a special graph class that exhibits more structure than is defined for general graphs. An intersection-free embedding of a graph in a surface assigns each node a point on this surface and each edge a Jordan curve such that the endpoints of the edge's image are the images of the endnodes and the images of any two edges are disjoint except at the image of a common endnode [Gross and Tucker 1987]. The image of a graph divides the rest of the surface into disjoint faces. Many algorithms on this class of graphs assume that the graph structure is enhanced by a representation of these faces: G = (V [union] F, E), where F is the set of faces.

The relation between V, F, and E may be represented in different ways, which induce different superimpositions of incidence structures. For example, the quad-edge representation [Guibas and Stolfi 1985] may be modeled by four incidence structures, [adj.sub.1] : V [right arrow] M(V), [adj.sub.2] : V [right arrow] M(F), [adj.sub.3] : F [right arrow] M(V), and [adj.sub.4] : F [right arrow] M(F). Roughly speaking, every edge e [element of] E is incident to two nodes, [v.sub.1] and [v.sub.2], and two faces, [f.sub.1] and [f.sub.2], such that

[corr.sub.1]([v.sub.1], e) = [v.sub.2] and [corr.sub.1]([v.sub.2], e) = [v.sub.1],

[corr.sub.2]([v.sub.1], e) = [f.sub.1] and [corr.sub.2]([v.sub.2], e) = [f.sub.2],

[corr.sub.3]([f.sub.1], e) = [v.sub.1] and [corr.sub.3]([f.sub.2], e) = [v.sub.2],

[corr.sub.4]([f.sub.1], e) = [f.sub.2] and [corr.sub.4]([f.sub.2], e) = [f.sub.1].

Hypergraph: Hypergraphs of any kind (directed, undirected, ...) are not regarded as graph views of their own. Instead, a hypergraph H = (V, E) is modeled as a bipartite graph G = (V, E) with bipartite node set V = V [union] E. A node v [element of] V is connected with a node e [element of] E by an edge in E if and only if e is incident to v in H.

Mixed graph: For example, consider a graph G = (V, [E.sub.1] [union] [E.sub.2]), where [E.sub.1] is a set of undirected edges and [E.sub.2] a set of directed edges. Of course, this case can be modeled by a superimposition of a directed and an undirected incidence structure.

F.5 Adaptation of Graph Views

Finally, we consider the second question raised in the description of adjacency iterators in Section 7.1. We only give a few examples of how one graph view A may be adapted to another graph view B. Considering these examples, it might be straightforward to implement an adjacency iterator [it.sub.B] which is based on an adjacency iterator [it.sub.A] for A and offers view B. Adaptations of other graph views might also be obvious.

--Two-way directed graph [right arrow] undirected graph: Recall that a two-way directed graph is modeled by two incidence structures, ([inc.sub.1], [adj.sub.1], [corr.sub.1], [succ.sub.1]) and ([inc.sub.2], [adj.sub.2], [corr.sub.2], [succ.sub.2]). The undirected graph view, which simply drops the orientations of edges, is modeled by ([inc.sub.1] [union] [inc.sub.2], [adj.sub.1] [union] [adj.sub.2], [corr.sub.1] [union] [corr.sub.2], [succ.sub.1] [union] [succ.sub.2]).

--Undirected graph [right arrow] directed graph: By that we mean that an undirected graph is viewed as a symmetric directed graph. The incidence structure is identical (and the implementation of an adapting iterator is trivial).

--Bidirected graph [right arrow] directed graph: An adaptation of a bidirected graph view to a directed graph view has the following consequence: an algorithm that navigates over the incidence structure of a directed graph view regards one node v as two different nodes, [v.sub.1] and [v.sub.2]. More specifically, whenever it enters v via an edge in [inc.sub.1](v), it regards v as [v.sub.1], and otherwise as [v.sub.2]. The incidence structure (inc', adj' , corr', succ') seen by this algorithm is defined by the rule inc'([v.sub.1]) = [inc.sub.2](v) and inc'([v.sub.2]) = [inc.sub.1](v). This naturally induces adj', corr', and succ'.

--Intersection-free embedded graph with faces [right arrow] bipartite graph: A graph G = (V [union] F, E) with faces as described above naturally induces an undirected bipartite graph G' = (V [union] F, E'), where {v, f} [element of] E' if and only if node v is on the boundary of face f. For example, if G is represented by a quad-edge structure (i.e. four superimposed incidence structures as introduced above), the incidence structures ([inc'.sub.1], [adj'.sub.1], [corr'.sub.1], [succ'.sub.1]) and ([inc'.sub.2], [adj'.sub.2], [corr'.sub.2], [succ'.sub.2]) for the bipartite graph view may be straightforwardly defined such that the following rules are fulfilled for v [element of] V and f [element of] F:

mult([inc'.sub.1](v), {v, f})= mult([adj.sub.1](v) [union] [adj.sub.2](v), {v, f}),

mult([inc'.sub.2](f), {v, f})= mult([adj.sub.3](f) [union] [adj.sub.4](f), {v, f}).

Preliminary parts of this work previously appeared in the proceedings of the 12th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '97), pp. 34-48, and in the online proceedings of the 1st Workshop on Algorithm Engineering (WAE '97), http://www.dsi.unive. it/~wae97/proceedings.

Author's address: Forschungsinstitut fur Diskrete Mathematik, Lennestrasse 2, 53113 Bonn, Germany.
COPYRIGHT 2001 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2001 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:WEIHE, KARSTEN
Publication:ACM Computing Surveys
Geographic Code:1USA
Date:Mar 1, 2001
Words:27464
Previous Article:A Guided Tour to Approximate String Matching.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters