A software engineering perspective on algorithmics

ABSTRACT

An algorithm component is an implementation of an algorithm 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. Therefore, the design of algorithm components must also incorporate software-engineering aspects. A key design goal is adaptability. This goal is important for maintenance throughout a project, prototypical development, and reuse in new, unforseen contexts. From a theoretical viewpoint most algorithms apply to a range of possible use scenarios. Ideally, each algorithm is implemented by one algorithm component, which is easily, safely, and efficiently adaptable to all of these contexts. Various techniques have been developed for the design and implementation of algorithm components. However, a common basis for systematic, detailed evaluations and comparisons in view of the real practical needs is still missing. Basically, this means a set of concrete criteria, which specify what sort of adaptability is really required in practice, and which are well-justified by convincing, representative use scenarios. This paper is intended to be a first “milestone” on the way towards such a system of criteria. We will present a set of concrete goals, which are general and problem-independent and might appear ubiquitously in the algorithmic realm. These goals are illustrated, motivated, and justified by an extensive requirements analysis for a particular algorithm from a particular algorithmic domain: Dijkstra's algorithm for shortest paths in networks. Clearly, the field of algorithmics might be too versatile to allow a comprehensive, yet concise set of precise, justified criteria. Even a domain as restricted as graph and network algorithms includes aspects that are not fully understood. The analysis will include a discussion of the limits of the case study and the scope of the goals. The case study was chosen because it seems to be close to the “boderline” between the aspects that are well understood and the aspects that are not. Hence, this example may well serve as an“acid test” for programming techniques in view of the state of the art.

REFERENCES

• 1: AHUJA, R.K., MAGNANTI, T.L., AND ORLIN, J.B. 1993. Network Flows. Prentice Hall, Englewood cliffs, NJ.
• 2: Don Batory , Vivek Singhal , Marty Sirkin , Jeff Thomas, Scalable software libraries, Proceedings of the 1st ACM SIGSOFT symposium on Foundations of software engineering, p.191-199, December 08-10, 1993, Los Angeles, California, United States
• 3: BLUM,M.AND WASSERMAN, H. 1994. Program resultchecking: 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.
• 4: Ulrik Brandes , Wolfram Schlickenrieder , Gabriele Neyer , Dorothea Wagner , Karsten Weihe, PlaNet: A software package of algorithms and heuristics for disjoint paths in planar networks, Discrete Applied Mathematics, v.92 n.2-3, p.91-110, June 25, 1999 [doi>10.1016/S0166-218X(99)00048-7]
• 5: Andreas Brandstädt , Van Bang Le , Jeremy P. Spinrad, Graph classes: a survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 6: Marshall P. Cline , Mike Girou , Greg Lomow, C++ FAQs, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: DERIGS, U. 1988. Programming in Networks and Graphs: On the Combinatorial Background and Near-Equivalence of Network Flow and Matching Algorithms. Springer, Berlin.
• 9: Bryan Flamig, Practical algorithms in C++, John Wiley & Sons, Inc., New York, NY, 1995
• 10: FRICK, A., ZIMMER,W.,AND ZIMMERMANN, W. 1995. On the design of reliable libraries. TOOLS 17, 13- 23.
• 11: 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.
• 12: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 13: Dieter Gluche , Dietmar Kühl , Karsten Weihe, C++ toolbox, ACM SIGPLAN Notices, v.33 n.1, January 1998 [doi>10.1145/609742.609744]
• 14: GOLUMBIC, M.C. 1991. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.
• 15: Jonathan L. Gross , Thomas W. Tucker, Topological graph theory, Wiley-Interscience, New York, NY, 1987
• 16: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 17: Ian M. Holland, Specifying Reusable Components Using Contracts, Proceedings of the European Conference on Object-Oriented Programming, p.287-308, June 29-July 03, 1992
• 18: John Irwin , Jean-Marc Loingtier , John R. Gilbert , Gregor Kiczales , John Lamping , Anurag Mendhekar , Tatiana Shpeisman, Aspect-Oriented Programming of Sparse Matrix Code, Proceedings of the Scientific Computing in Object-Oriented Parallel Environments, p.249-256, December 08-11, 1997
• 19: L. Kanal , V. Kumar, Search in Artificial Intelligence, Springer-Verlag, London, 1988
• 20: 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.
• 21: KREFT,K.AND LANGER, A. 1996. Iterators in the standard template library. C CC Rep. 8, 7, 30-37.
• 22: KREFT,K.AND LANGER, A. 1997. Building an iterator for the STL and the Standard Template Library. C CC Rep. 9, 2, 20-27.
• 23: 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.
• 24: KUHL,D.AND WEIHE, K. 1997. Data access templates. C CC Rep. 9, 7, 15-21.
• 25: LAWLER, E.L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York.
• 26: 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.
• 27: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 28: T. Lengauer , D. Theune, Efficient algorithms for path problems with general cost criteria, Proceedings of the 18th international colloquium on Automata, languages and programming, p.314-326, June 1991, Madrid, Spain
• 29: Ted Lewis, Object oriented application frameworks, Manning Publications Co., Greenwich, CT, 1995
• 30: Barbara Liskov, Keynote address - data abstraction and hierarchy, ACM SIGPLAN Notices, v.23 n.5, p.17-34, May 1988
• 31: MARTIN, R.C. 1996. The Liskov substitution principle. C CC Rep. 8 (Mar.).
• 32: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, v.38 n.1, p.96-102, Jan. 1995 [doi>10.1145/204865.204889]
• 33: 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/.
• 34: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 35: Bertrand Meyer, Object success: a manager's guide to object orientation, its impact on the corporation, and its use for reengineering the software process, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 36: Stephan Murer , Stephen Omohundro , David Stoutamire , Clemens Szyperski, Iteration abstraction in Sather, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.1, p.1-15, Jan. 1996 [doi>10.1145/225540.225541]
• 37: David R. Musser , Atul Saini, The STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1995
• 38: NISHIZEKI,T.AND CHIBA, N. 1988. Planar Graphs: Theory and Algorithms. North-Holland, Amsterdam. Annals of Discrete Mathematics, Vol. 32.
• 39: NISSEN, M. 1998. Graph iterators-decoupling graph structures from algorithms. Diploma thesis, Univ. of Saarbr ucken, Germany. Http://www. mpi-sb.mpg.de/~marco/english.html.
• 40: NISSEN,M.AND WEIHE, K. 1996. Combining LEDA with customizable implementations of graph algorithms. Http://www.informatik.unikonstanz.de/Preprints.
• 41: Stephen M. Omohundro, The Sather programming language, Dr. Dobb's Journal, v.18 n.11, p.42-48, Oct. 1993
• 42: William F. Opdyke , Ralph E. Johnson, Creating abstract superclasses by refactoring, Proceedings of the 1993 ACM conference on Computer science, p.66-73, February 16-18, 1993, Indianapolis, Indiana, United States [doi>10.1145/170791.170804]
• 43: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 44: Thomas M. Pigoski, Practical Software Maintenance: Best Practices for Managing Your Software Investment, John Wiley & Sons, Inc., New York, NY, 1996
• 45: Stefan Schirra, Precision and Robustness in Geometric Computations, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.255-287, September 16-20, 1996
• 46: Frank Schulz , Dorothea Wagner , Karsten Weihe, Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.110-123, July 19-21, 1999
• 47: SOUKOP, J. 1994. Taming C CC . Addison-Wesley, Reading, MA.
• 48: Antero Taivalsaari, On the notion of inheritance, ACM Computing Surveys (CSUR), v.28 n.3, p.438-479, Sept. 1996 [doi>10.1145/243439.243441]
• 49: VELDHUIZEN, T. 1995. Expression templates. C CC Rep. 7, 26.
• 50: VIDAL, R.V.V. 1993. Applied Simulating Annealing. Springer, Berlin. Lecture Notes in Economics and Mathematical Systems, Vol. 396.
• 51: 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).
• 52: Karsten Weihe, Reuse of algorithms: still a challenge to object-oriented programming, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.34-48, October 05-09, 1997, Atlanta, Georgia, United States
• 53: WEIHE, K. 1998. Using templates to improve C CC designs. C CC Rep. 10, 2, 14-21.
• 54: Bruce W. Weide , Stephen H. Edwards , Wayne D. Heym , Timothy J. Long , William F. Ogden, Characterizing Observability and Controllability of Software Components, Proceedings of the 4th International Conference on Software Reuse, p.62, April 23-26, 1996
• 55: Bruce W. Weide , William F. Ogden , Murali Sitaraman, Recasting Algorithms to Encourage Reuse, IEEE Software, v.11 n.5, p.80-88, September 1994 [doi>10.1109/52.311066]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Design, Languages

Keywords:
algorithm engineering