Modelica建模软件中拓扑排序相关算法研究  

Research on topological sorting related algorithms in Modelica simulation software

作　　者：魏欣[1,2,3] 曹建文[1,2] 

机构地区：[1]中国科学院软件研究所并行计算实验室,北京100190 [2]中国科学院计算机科学重点实验室,北京100190 [3]中国科学院研究生院,北京100049

出　　处：《计算机工程与设计》2010年第4期691-695,共5页Computer Engineering and Design

基　　金：国家自然科学基金委员会-中国工程物理研究院(NSAF)联合基金项目(10776035);国家973重点基础研究发展计划基金项目(G2005CB321702)

摘　　要：为了提高现有OpenModelica软件对DAE系统的预处理模块中求强连通分量与拓扑排序部分的性能,提出了基于Ko-saraju算法实现的策略。阐述了Modelica软件的实现原理,叙述了拓扑排序相关算法在其中的重要性,分析了现有Modelica软件中使用的求强连通分量与拓扑排序部分的算法,比较了Tarjan算法的实现方案与Kosaraju算法实现方案。对两种方案进行了比较和分析结果,表明了Kosaraju算法方案的可行性和有效性。To improve the efficiency of finding strongly connected components and topological sorting,belonging to preprocessing module of differential algebraic equation system of OpenModelica software,a strategy based on Kosaraju algorithm is presented.Firstly,the principle of Modelica software is provided.The importance of topological sorting related algorithm is described.The algorithms used to find strongly connected components and topological sort in current Modelica software is analyzed.Strategies using Tarjan algorithm and Kosaraju algorithm are compared.The two strategies are realized by analyzing and comparing the results,the strategy using Kosaraju algorithm is proved feasibility and validity.

关 键 词：MODELICA DAE求解 强连通分量 拓扑排序 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]