LAOV网络及其拓扑排序算法

J4 ›› 2012, Vol. 34 ›› Issue (3): 170-175.

LAOV网络及其拓扑排序算法

王桂平1，张帅2

（1.重庆大学计算机学院，重庆 400030；2.浙江财经学院信息学院，浙江杭州 310018）

收稿日期:2010-11-23 修回日期:2011-03-13 出版日期:2012-03-26 发布日期:2012-03-25
基金资助:
国家自然科学基金资助项目（50975250）；浙江省自然基金资助项目（Y1110671）

The LAOV Network and Its Topological Sorting Algorithm

WANG Guiping1,ZHANG Shuai2

（1.School of Computer Science,Chongqing University,Chongqing 400030；
2.School of Infomation,Zhejiang University of Finance and Economy,Hangzhou 310018,China）

Received:2010-11-23 Revised:2011-03-13 Online:2012-03-26 Published:2012-03-25

摘要/Abstract

摘要：

针对网格工作流调度、生产和施工计划的制订等领域的特殊需求，引入了一类顶点带层次的AOV网络－LAOV网络。本文对AOV网络、层次、LAOV网络进行了严格的定义，并对顶点层次取值的几种情形作了详细的讨论。然后针对其中一种合理情形的LAOV网络提出了拓扑排序算法，讨论了栈或队列的选择、有向回路的判定等问题，并分析了算法的复杂度。最后对LAOV网络及拓扑排序算法进行实验分析。因为算法输出的解不唯一，在实验分析时设计了评判程序对算法输出进行验证。实验分析结果表明算法是正确的，时空效率也比较好。

关键词: AOV网络, 层次, LAOV网络, 拓扑排序, 网格工作流

Abstract:

For special needs in grid workflow scheduling, production and construction planning, and so on. a kind of AOV network with all vertices possessing a level (denoted by LAOV) is introduced. The definitions of AOV, level and LAOV are given. Several cases of the level of vertices are discussed in detail. Then the topological sorting algorithm for a reasonable one of the LAOV networks is presented. Some problems are discussed, such as the choice of stack or queue, the determination of directed circuits, etc. And the complexity of the algorithm is analyzed. Finally, an experimental analysis of LAOV and its topological sorting algorithm is carried out. Because the output of the algorithm is not unique, a special judge program is written to verify the correctness of the output. The experimental results show that the algorithm is correct, and its time and space efficiency is well.

Key words: AOV network;level;LAOV network;topological sorting;grid workflow

王桂平1，张帅2. LAOV网络及其拓扑排序算法[J]. J4, 2012, 34(3): 170-175.

WANG Guiping1,ZHANG Shuai2. The LAOV Network and Its Topological Sorting Algorithm[J]. J4, 2012, 34(3): 170-175.

参考文献［11］

［1］	顾寄南，张林鍹，张国胜，等. 基于推理的有向图拓扑排序装配顺序规划及优化研究［J］. 机械工程学报，2002，38(12)：142145.
［2］	王明福. 基于AOV网的应用程序构建模型研究［J］. 计算机工程与应用，2007，43(6)：8587.
［3］	王明福. 基于AOV网模型的应用程序开发技术研究［J］. 微电子学与计算机，2001，18(4)：4346.
［4］	李义军，任子真. 拓扑排序和强连通算法在源代码分析中的应用［J］. 计算机系统应用，2009，18(1)：9698.
［5］	O’Brien A, Newhouse S, Darlington J. Mapping of Scientific Workflow within the eProtein Project to Distributed Resources［C］∥Proc of UK eScience all Hands Meeting, 2004:404409.
［6］	Gallet M, Marchal L, Vivien F. Allocating Series of Workflows on Computing Grids［C］∥Proc of the 14th Int’l Conf on Parallel and Distributed Systems, 2008:4855.
［7］	Cao H J, Jin H, Wu X X, et al. DAGMap: Efficient and Dependable Scheduling of DAG Workflow Job in Grid［J］.The Journal of Supercomputing, 2010(51):201223.
［8］	Chen H, Ku WS, Sun MT, et al. The Partial Sequenced Route Query with Traveling Rules in Road Networks［J］. GeoInformatica, 2010,15(3):541569.
［9］	Huang L, Liu W, Liu Z. Algorithm of Transformation from PLC Ladder Diagram to Structured Text［C］∥Proc of 9th Int’l Conf on Electronic Measurement and Instruments,2009:778782.
［10］	殷人昆，陶永雷，谢若阳，等. 数据结构(用面向对象方法与C++描述)［M］. 北京：清华大学出版社, 1999.
［11］	Cormen T H，Leiserson C E，Rivest R L，et al. 算法导论［M］. 潘金贵,等译. 北京：机械工业出版社, 2009.

[1]	卓灵1，聂静1，肖静薇1，袁杨2，胡新1，陈柯1. 电力无线通信异构多网共存环境中的网络选择算法[J]. J4, 20160101, 38(01): 78-83.
[2]	王玉雷, 谢凯亮, 陈思贇, 胡杰, 常胜. 卷积神经网络硬件加速的通用性设计[J]. 计算机工程与科学, 2023, 45(04): 577-581.
[3]	李建红, 苏晓倩, 吴彩虹. 深度层次注意力矩阵分解[J]. 计算机工程与科学, 2023, 45(01): 28-36.
[4]	唐广镇, 陈卓. 访问策略隐匿的可追责层次属性加密方案[J]. 计算机工程与科学, 2022, 44(10): 1788-1794.
[5]	张宝华 , 李奀林 , 张华平 , 商建云. 基于层次体系的情感单元表示方法[J]. 计算机工程与科学, 2022, 44(01): 149-158.
[6]	张海玲, 邵玉斌, 贾继康, 龙华, 杜庆治. 基于二元与三元模型相结合的句法规则层次化分析算法[J]. 计算机工程与科学, 2021, 43(07): 1316-1323.
[7]	李文昊, 李英梅, 边奕心. 一种基于DBSCAN算法的代码包层次重构改进方法[J]. 计算机工程与科学, 2021, 43(04): 689-696.
[8]	孟昱煜，陈绍立，刘兴长. 面向排序学习的层次聚类特征选择算法[J]. 计算机工程与科学, 2019, 41(12): 2211-2216.
[9]	龚文聪1，袁景凌1,2，陈旻骋1，向尧1,赵子康1. 基于用户体验延迟的QoE层次评估模型[J]. 计算机工程与科学, 2019, 41(03): 479-484.
[10]	王铁旦，赵洋，彭定洪. 区间犹豫模糊的改进层次TODIM在云制造资源中的应用研究[J]. 计算机工程与科学, 2019, 41(03): 520-530.
[11]	张守宾，朱习军. 集成学习算法在中医证型分类预测中的应用[J]. 计算机工程与科学, 2019, 41(02): 328-334.
[12]	郭雪1，李铮2，张贺3，荣国平3，文俊浩1. Web服务组合策略研究及组合决策平台实现[J]. 计算机工程与科学, 2018, 40(08): 1358-1365.
[13]	李源1，刁胜权1，胡金柱1,2，翟宏森1，杨梦川1，黄文灿1. 基于语义与规则的有标复句层次体系研究[J]. 计算机工程与科学, 2017, 39(12): 2306-2313.
[14]	曹霞1，李岳阳1，罗海驰2，蒋高明1，丛洪莲1. 基于层次匹配下多种特征融合的蕾丝花边检索方法[J]. 计算机工程与科学, 2017, 39(09): 1691-1699.
[15]	张凤荔1，周洪川1，张俊娇1，刘渊2，张春瑞2. 基于改进凝聚层次聚类的协议分类算法[J]. 计算机工程与科学, 2017, 39(04): 796-803.