Lie-Quan Lee
Jeremy G. Siek
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.
- 1.Netlib repository, http://www.netlib.org/.]]Google Scholar
- 2.University of Florida sparse matrix collection. http://www-pub, cise.ufl, edu/,,~ davis/sparse/.]]Google Scholar
- 3.Austern, M. H. Generic Programming and the STL. Addison Wesley Longman, inc, October 1998.]] Google ScholarDigital Library
- 4.Cormen, T. H., Leiserson, C. E., and Rivest, R. L. Introduction to Algorithms. The MIT Press, 1990.]] Google ScholarDigital Library
- 5.Forster, M., Pick, A., and Raitner, M. Graph Template Library. http://www.fmi.unipassau.de/Graphlet/GTL/.]]Google Scholar
- 6.Gamma, E., Hetm, R., Johnson, R., and Vlissides, J. Design Patterns: Elements of Reusable Object- Oriented Software. Addiaon Wesley Publishing Company, October 1994.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 8.George, A., and Liu, J. W.-H. Computer Solution of Large Sparse Positive Definite Systems. Computational Mathematics. Prentice-Hall, 1981.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 10.Jacobson, I., Booch, G., and Rurnbaugh, J. Unified Software Development Process. Addison-Wesley, 1999.]] Google ScholarDigital Library
- 11.Knuth, D. E. Stanford GraphBase: a platform for combinatorial computing. ACM Press, 1994.]] Google Scholar
- 12.Lee, M., and Stepanov, A. The standard template library. Tech. rep., HP Laboratories, February 1995.]]Google Scholar
- 13.Liu, J. W. H. Modification of the minimum-degree algorithm by multiple elimination. ACM Transaction on Mathematical Software 11, 2 (1985), t41-153.]] Google ScholarDigital Library
- 14.Mehlhom, K., and Naeher, S. LEDA. http://www.mpisb.mpg.de/LEDA/leda.html.]]Google Scholar
- 15.Meyer, B. Object-Oriented Software Construction. Prentice Hall, 1997.]] Google ScholarDigital Library
- 16.Object Management Group. UML Notation Guide, version 1. I ed.,September 1997. http://www.rational.com/uml/.]]Google Scholar
- 17.Saad, Y. Iterative Methods for Sparse Minear System. PWS Publishing Company, 1996.]] Google ScholarDigital Library
- 18.Samaragdakis, Y., and Batory, D. Implementing layered designs with mixin layers. In The Europe Conference on Object-Oriented Programming (1998).]] Google ScholarDigital Library
- 19.Siek, J. G., and Lumsdaine, A. The matrix template library: A genetic programming approach to high performance numerical linear algebra, in International Symposium on Computing in Object-Oriented Parallel Environments (1998).]] Google ScholarDigital Library
- 20.Sick, J. G., and Lumsdaine, A. Mayfly: A pattern for light-weight genetic interfaces. In PLOP99 (1999). Accepted.]]Google Scholar
- 21.Skiena, S. implementing Discrete mathematics. Addion-Wesley, 1990.]] Google ScholarDigital Library
- 22.Skiena, S. S. The Algorithm Design Manual. Springer- Verlag New York, Inc, 1998.]] Google ScholarDigital Library
- 23.Veldhuizen, T. L. Expression templates. C++ Report 7, 5 (June 1995), 26-31. Reprinted in C++ Gems, ed. Stanley Lippman.]] Google ScholarDigital Library
Index Terms
- The generic graph component library
Recommendations
The generic graph component library
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 ...
Local diagnosability of generic star-pyramid graph
The problem of fault diagnosis in network has been discussed widely. In this paper, we study the local diagnosability of a generic star-pyramid graph. We prove that under the PMC model the local diagnosability of each vertex in a generic star-pyramid ...
Largest connected component of a star graph with faulty vertices
In order to make a full evaluation of an interconnection network, it is essential to estimate the minimum size of a largest connected component of this network provided the faulty vertices in the network may break its connectedness. Star graphs are ...
Comments