Several Graph Algorithms Development And Generation Via Component Composition

Now, we have entered the big data and cloud computing era, followed by the explosion of diversity demand for software products. However, there are a number of problems with previous software development methods, such as low efficiency, lack of validity and reliability and so on. Thus, it is increasingly unable to meet the increasing software requirements.Because of this, how to improve the efficiency and reliability of software development has been the focus of many researchers.The practice shows that the software reuse technology based on component offers a effective way to solve this problem.Because it has the features of developing high reliability and high efficiency software. With the components in reusable application component library, a variety of applications can be assembled into. This relieves a lot of repetitive work and realizes the algorithm generated automation program finally.Generative programming technology provides support for component reuse and assembly.It includes domain engineering and application engineering.The former includes three periods: domain analysis, domain design and domain implementation. During the period of domain analysis, the commonality and variability of a particular field are analysised.Then a set of field requirements with reusability enough is extracted. Finally, after abstracting domain requirements the domain model is generated. Based on the domain model, reusable components are assembled for software development during application engineering.PAR method is a new software development method for the support of algorithm procedures formalized and automation. Radl is defined for describing the algorithm specifications and Apla is defined for describing the abstract programs.They can greatly simplify the algorithm and improve the efficiency and reliability of the algorithm and program. PAR platform which is used to support the PAR method is a new type of software development platform.It provides an effective combination of predefined data types,that makes programming easier and more reliable.Based on PAR method and its platform, this paper studied the question of several graph algorithms development and generation via component composition. The main work and research results are as follow:(1) The analysis and overview of generative programming technology, software reuse technology and PAR method and PAR platform is given.(2) By analyzing the commonness and variability of the breadth-first algorithm and the depth-first algorithm, “relax” and “dfs” which are generic algorithm components and their related components are designed.And the design of components are presented with Apla language.(3) With the support of the generic mechanism in the PAR method, the generic algorithm components and their related components are assembled. Breadth-first algorithm, Dijkstra algorithm, Floyd algorithm which are based on the idea of breadth-first search and depth-first algorithm, creating adjacency table algorithm, topological sort, strongly connected component which are based on the idea of depth-first search are generated. With the support of PAR platform, executable program algorithms are generated.(4) Aiming at the problem of component assembly, a graphical user interface of the component assembly prototype system is designed.This system allows the users select the corresponding components by themselves to produce the required algorithms via automated assembly.Thus the efficiency of graph algorithm development is greatly improved.