The generic graph component library

ABSTRACT

In this paper we present the Generic Graph Component Library (GGCL), a generic programming framework for graph data structures and graph algorithms. Following the theme of the Standard Template Library (STL), the graph algorithms in GGCL do not depend on the particular data structures upon which they operate, meaning a single algorithm can operate on arbitrary concrete representations of graphs. To attain this type of flexibility for graph data structures, which are more complicated than the containers in STL, we introduce several concepts to form the generic interface between the algorithms and the data structures, namely, Vertex, Edge, Visitor, and Decorator. We describe the principal abstractions comprising the GGCL, the algorithms and data structures that it provides, and provide examples that demonstrate the use of GGCL to implement some common graph algorithms. Performance results are presented which demonstrate that the use of novel lightweight implementation techniques and static polymorphism in GGCL results in code which is significantly more efficient than similar libraries written using the object-oriented paradigm.

REFERENCES

• 1: Netlib repository, http://www.netlib.org/.
• 2: University of Florida sparse matrix collection. http://www-pub, cise.ufl, edu/,,~ davis/sparse/.
• 3: Matthew H. Austern, Generic programming and the STL: using and extending the C++ Standard Template Library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Forster, M., Pick, A., and Raitner, M. Graph Template Library. http://www.fmi.unipassau.de/Graphlet/GTL/.
• 6: 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
• 7: George, A., and Liu, j. W.H. User's guide for SPARSPAK: Waterloo sparse linear equations packages. Teeh. rep., Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 1980.
• 8: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 9: Grimes, R. G., Lewis, J. G., and Duff, i. S. User's guide for the harwell-boeing sparse matrix collection. User's Manual Release 1, Boeing Computer Services, Seattle, WA, October 1992.
• 10: Ivar Jacobson , Grady Booch , James Rumbaugh, The unified software development process, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 11: Donald E. Knuth, The Stanford GraphBase: a platform for combinatorial computing, ACM Press, New York, NY, 1993
• 12: Lee, M., and Stepanov, A. The standard template library. Tech. rep., HP Laboratories, February 1995.
• 13: Joseph W. H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.141-153, June 1985 [doi>10.1145/214392.214398]
• 14: Mehlhom, K., and Naeher, S. LEDA. http://www.mpisb.mpg.de/LEDA/leda.html.
• 15: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 16: Object Management Group. UML Notation Guide, version 1. I ed.,September 1997. http://www.rational.com/uml/.
• 17: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 18: Yannis Smaragdakis , Don S. Batory, Implementing Layered Designs with Mixin Layers, Proceedings of the 12th European Conference on Object-Oriented Programming, p.550-570, July 20-24, 1998
• 19: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: A Generic Programming Approach to High Performance Numerical Linear Algebra, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.59-70, December 08-11, 1998
• 20: Sick, J. G., and Lumsdaine, A. Mayfly: A pattern for light-weight genetic interfaces. In PLOP99 (1999). Accepted.
• 21: Steven Skiena, Implementing discrete mathematics: combinatorics and graph theory with Mathematica, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 22: Steven S. Skiena, The algorithm design manual, Springer-Verlag New York, Inc., New York, NY, 1997
• 23: Todd Veldhuizen, Expression templates, C++ gems, SIGS Publications, Inc., New York, NY, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Programmer workbench
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Measurement, Performance, Theory