基于构件的若干图算法开发和生成

Components-Based Graph Algorithms Development and Generation

软件构件技术可显著提高程序的可靠性和开发效率,极大减少开发成本.泛型程序设计有助于降低编程的复杂度,为重用构件开发提供有效支持.介绍了生成式程序设计思想及泛型程序设计技术,分析了图算法领域的关键特征及领域共性问题,并对广度优先搜索、单源最短路径、所有顶点对最短路径等一类问题进行抽象,设计出相应的泛型图算法构件,进一步借助PAR方法中的泛型机制进行描述,并在PAR平台程序生成系统上进行构件组装生成具体的算法程序.

Software component technology not only significantly improves the reliability and development efficiency of programs,but also reduces the development cost.Generic programming contributes to reducing the complexity of programming,and supports the development of reusable components.Generative programming and generic programming are introduced here,and some characteristics and common features of graph algorithms are analyzed,based on which generic graph algorithm components are abstracted from a class of problems,such as the breadth-first search problem,single source shortest path problem and all vertex-pairs shortest path problem.Further,it is described by means of generic mechanisms of PAR,and several graph algorithm programs are generated via component assembly supported by PAR platform.