On Module Arrangement in Generating Assemble Programs via Directed Graph

On Module Arrangement in Generating Assemble Programs via Directed Graph

Creators Yamaguchi Satoru

Creators Wu Ren

Creators Yanagida Hidenori

In order to support automatically generating an assemble program by combining prepared assemble program modules, we propose in this paper a general way to create multiple arranging patterns of modules obeying given arrange order relations that represent the relative arranging position of modules in a program. It is carried out with time complexity O(1 V I Z) by transforming the arrange order relations into a directed graph AOR-G and then on AOR-G giving multiple sequences of nodes, equivalent to arranging patterns of modules, through constructing a layer graph. Furthermore, to improve the search time costed in constructing the layer graph, we propose two algorithms respectively to delete extra edges from AOR-Ca whose information has been included in other arrange order relations, and to extract a related graph G r (a minimum subgraph of AOR-G) to a given node set r, representing the modules required to be used in a generating program. Finally we give three operations to reduce the related graph G r by deleting unnecessary nodes for the generating program, trying to further improve the time complexity O(1 V I 2 ).

[ISSN]0513-1693

[NCID]AN00243950