Computer Science ›› 2020, Vol. 47 ›› Issue (11A): 584-590.doi: 10.11896/jsjkx.200200066

• Interdiscipline & Application • Previous Articles     Next Articles

Method for Transforming Directed Acyclic Graph into Algebraic Expression Tree

LI Hong-yu, WANG Yu-xin   

  1. Beijing Union University,Beijing 100101,China
  • Online:2020-11-15 Published:2020-11-17
  • About author:LI Hong-yu,born in 1972,master,associate professor.Her main research interests include software engineering,algorithm analysis,and image processing.
    WANG Yu-xin,born in 1965,master,associate professor.His main research interests include artificial intelligence and algorithm analysis.
  • Supported by:
    This work was supported by the Scientific Research Project of Beijing Municipal Education Commission (KZ201911417048).

Abstract: This paper presents a method for transforming a directed acyclic graph into an algebraic expression tree.This method can achieve series merging,parallel merging,and serialization merging of graphs,and it can handle functional vertices in graphs.Compared with the previous transformation methods,the transformation given in this paper can deal with moretypes of graphs and vertices,so it is more widely used.This article gives the conversion method and analyzes the running time of the conversion.Considering the actual application situation,the conversion time is only related to the number of edges in agraph,so the conversion time efficiency is high.

Key words: Algorithm, Directed acyclic graph, Ladder diagram, Merge, Tree, Vertex

CLC Number: 

  • TP312
[1] DUFFIN R J.Topology of series-parallel networks[J].Journal of Mathematical Analysis and Applications,1965,10(2):303-318.
[2] VALDES J,TARJAN R E,LAWLER E L.The recognition of series parallel digraphs[C]//Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing.ACM:1-12.
[3] HE X,YESHA Y.Parallel recognition and decomposition of two terminal series parallel graphs[J].Information and Computation,1987,75(1):15-38.
[4] EPPSTEIN D.Parallel recognition of series-parallel graphs[J].Information and Computation,1992,98(1):41-55.
[5] WELCH J T.Translating unrestricted relay ladder logic intoboolean form[J].Computers in Industry,1992,20(1):45-61.
[6] WELCH J T.An event chaining relay ladder logic solver[J].Computers in industry,1995,27(1):65-74.
[7] WELCH J T.Translating relay ladder logic for ccm solving[J].IEEE Transactions on Robotics and Automation,1997,13(1):148-153.
[8] ZHOU B,YIN K T,JIANG H H,et al.QoS-based Selection ofMulti-Granularity Web Services for the Composition[J].Journal of Software,2011,6(3):366-373.
[9] JAEGER M C,ROJEC-GOLDMANN G,MUHL G.QoS aggregation for Web service composition using workflow patterns[C]//IEEE EDOC Workshop.2004:149-159.
[10] JAEGER M C,ROJEC-GOLDMANN G,MÜHL G.QoS Aggregation in Web Service Compositions[C]//IEEE 2005.2005:181-185.
[11] ALRIFAI M,RISSE T,NEJDL W.A Hybrid Approach for Efficient Web Service Composition with End-to-End QoS Constraints[J].ACM Transactions on the Web,2012,6(2):1-31.
[12] YAN Y,ZHANG H.Compiling ladder diagram into instruction list to comply with iec 61131-3[J].Computers in Industry,2010,61(5):448-462.
[13] COMMISSION I E.International standard iec 61131-(third edition)[M].Programmable Logic Controllers part 3,2013.
[14] MAN M,JOHANSSON S,RZN K E.Implementation aspects of the plc standard iec 1131-3[J].Control Engineering Practice,1998,6(4):547-555.
[15] OTTO A,HELLMANN K.Iec 61131:A general overview and emerging trends[J].Industrial Electronics Magazine,IEEE,2009,3(4):27-31.
[16] JOHN K H,TIEGELKAMP M.Theprogramming languages of iec 61131-3,IEC 61131-3[C]//Programming Industrial Automation Systems.2010:99-205.
[17] THRAMBOULIDIS K,FREY G.Towards a model-driven iec61131-based development process in industrial automation[J].Journal of Software Engineering and Applications,2011,4(4):217.
[18] BONDY J A,MURTY U S R.Graph theory with applications[M].Macmillan London,1976:290.
[19] CORMEN T H,RIVEST R L,STEIN C.Introduction to Algorithms(third edition)[M].MIT Press,2009:603-610.
[20] CORMEN T H,RIVEST R L,STEIN C.Introduction to Algorithms(third edition)[M].MIT Press,2009:595-602.
[1] CHAI Hui-min, ZHANG Yong, FANG Min. Aerial Target Grouping Method Based on Feature Similarity Clustering [J]. Computer Science, 2022, 49(9): 70-75.
[2] LIU Xin, WANG Jun, SONG Qiao-feng, LIU Jia-hao. Collaborative Multicast Proactive Caching Scheme Based on AAE [J]. Computer Science, 2022, 49(9): 260-267.
[3] NING Han-yang, MA Miao, YANG Bo, LIU Shi-chang. Research Progress and Analysis on Intelligent Cryptology [J]. Computer Science, 2022, 49(9): 288-296.
[4] JIANG Yang-yang, SONG Li-hua, XING Chang-you, ZHANG Guo-min, ZENG Qing-wei. Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game [J]. Computer Science, 2022, 49(9): 333-339.
[5] CHENG Fu-hao, XU Tai-hua, CHEN Jian-jun, SONG Jing-jing, YANG Xi-bei. Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory [J]. Computer Science, 2022, 49(8): 97-107.
[6] CHEN Jun, HE Qing, LI Shou-yu. Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor [J]. Computer Science, 2022, 49(8): 237-246.
[7] TANG Feng, FENG Xiang, YU Hui-qun. Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation [J]. Computer Science, 2022, 49(7): 254-262.
[8] ZHANG Chong-yu, CHEN Yan-ming, LI Wei. Task Offloading Online Algorithm for Data Stream Edge Computing [J]. Computer Science, 2022, 49(7): 263-270.
[9] PAN Zhi-yong, CHENG Bao-lei, FAN Jian-xi, BIAN Qing-rong. Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC [J]. Computer Science, 2022, 49(7): 287-296.
[10] LIU Wei-ming, AN Ran, MAO Yi-min. Parallel Support Vector Machine Algorithm Based on Clustering and WOA [J]. Computer Science, 2022, 49(7): 64-72.
[11] SHAN Xiao-ying, REN Ying-chun. Fishing Type Identification of Marine Fishing Vessels Based on Support Vector Machine Optimized by Improved Sparrow Search Algorithm [J]. Computer Science, 2022, 49(6A): 211-216.
[12] LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[13] WANG Wen-qiang, JIA Xing-xing, LI Peng. Adaptive Ensemble Ordering Algorithm [J]. Computer Science, 2022, 49(6A): 242-246.
[14] LIU Bao-bao, YANG Jing-jing, TAO Lu, WANG He-ying. Study on Prediction of Educational Statistical Data Based on DE-LSTM Model [J]. Computer Science, 2022, 49(6A): 261-266.
[15] GAO Rong-hua, BAI Qiang, WANG Rong, WU Hua-rui, SUN Xiang. Multi-tree Network Multi-crop Early Disease Recognition Method Based on Improved Attention Mechanism [J]. Computer Science, 2022, 49(6A): 363-369.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!