This paper introduces the general process of the search algorithm Structure through the knight problem. According to the characteristics of the problem, we detailed discuss the DFS（Depth First Search） algorithm and ...This paper introduces the general process of the search algorithm Structure through the knight problem. According to the characteristics of the problem, we detailed discuss the DFS（Depth First Search） algorithm and BFS（Breadth First Search） algorithm, and combine the two algorithms together to solve the knights coverage problem. This article has a good reference for the mixed-use scenarios which requires a variety of search algorithms.展开更多
电力系统仿真验证往往希望通过拓扑结构图直观地分析网络的潮流分布以及动态特性。然而电力系统机电暂态过程仿真软件如BPA、PSS/E和PSASP都不能自动地根据电力系统的电气联系合理地布置网络中的元件,而需要人为地调整各元件的位置来形...电力系统仿真验证往往希望通过拓扑结构图直观地分析网络的潮流分布以及动态特性。然而电力系统机电暂态过程仿真软件如BPA、PSS/E和PSASP都不能自动地根据电力系统的电气联系合理地布置网络中的元件,而需要人为地调整各元件的位置来形成一个直观的电气接线图。这种人为手动调整,不仅给仿真增加了工作量,更有可能带来更多的人为误差。为此,文中提出了基于图论的深度优先搜索(depth first searching,DFS)算法,依据电力系统的电气拓扑结构形成电力系统生成树的实现方法。用文中方法生成的IEEE9节点算例系统的可视化界面验证了该算法的有效性和准确性。展开更多
拓扑图自动生成算法是配电网拓扑接线图自动成图的核心。为此,详细阐述了拓扑图自动生成算法的基本思路,该算法的核心是采用深度优先遍历(depth first search,DFS)算法搜索两点之间的最大距离。同时提出了分层布局、综合实现的成图思想...拓扑图自动生成算法是配电网拓扑接线图自动成图的核心。为此,详细阐述了拓扑图自动生成算法的基本思路,该算法的核心是采用深度优先遍历(depth first search,DFS)算法搜索两点之间的最大距离。同时提出了分层布局、综合实现的成图思想,其具体实现分为3层:1)确定单条馈线的拓扑布局数组;2)确定两两变电站之间的拓扑布局数组;3)确定所有变电站之间的拓扑布局数组。将两两变电站之间的布局数组填充至所有变电站的布局数组中,可以得到配电网全网的布局数组,按照全网布局数组所确定的各变电站和各设备的坐标位置和互联信息,生成全网的拓扑接线图。该方法解决了直接一次性求取所有配电网设备在拓扑接线图中的坐标所导致的求解过程高度复杂甚至无解的问题,有效避免了交叉,大大减少了成图时间。最后,通过工程实际应用,验证了该算法的有效性和适用性。展开更多
Networks are a class of general systems represented by becomes a weighted graph visualizing the constraints imposed their UC-structure. Suppressing the nature of elements the network by interconnections rather than th...Networks are a class of general systems represented by becomes a weighted graph visualizing the constraints imposed their UC-structure. Suppressing the nature of elements the network by interconnections rather than the elements themselves. These constraints follow generalized Kirchhoff＇s laws derived from physical constraints. Once we have a graph; then the working environment becomes the graph-theory. An algorithm derived from graph theory is developed within the paper in order to analyze general networks. The algorithm is based on computing all the spanning trees in the graph G with an associated weight. This weight is the product ofadmittance＇s of the edges forming the spanning tree. In the first phase this algorithm computes a depth first spanning tree together with its cotree. Both are used as parents for controlled generation of off-springs. The control is represented in selecting the off-springs that were not generated previously. While the generation of off-springs, is based on replacement of one or more tree edges by cycle edges corresponding to cotree edges. The algorithm can generate a frequency domain analysis of the network.展开更多
For decades,engineers have utilized Petri nets to develop automated systems with specific functional requirements or characteristics.Nonetheless,the ex-isting formalism prevents the use of classic traversal techniques...For decades,engineers have utilized Petri nets to develop automated systems with specific functional requirements or characteristics.Nonetheless,the ex-isting formalism prevents the use of classic traversal techniques to examine and analyze a system’s functional behavior.This paper provides a novel tech-nique to represent Petri nets as directed Euler graphs.It enables design engi-neers to examine and traverse the various states of a system utilizing the vari-ous methodologies and traversal processes applicable to Euler graphs.In this study,we present an iterative approach for determining an optimal path in terms of the least number of edges(vertices)required to cover and contain the system’s states,which are represented as Petri nets.The goal is to leave one vertex and return to the same vertex of the graph in a finite number of steps.This is a new method for determining the attribute of the system’s reset,which is represented by Petri nets and allows the system to return to its starting state,the resting state.The goal is to broaden the ontological basis of Petri nets by displaying linkages or relationships between Petri nets that are akin to directed Euler graphs.展开更多
Due to the diversity of graph computing applications, the power-law distribution of graph data, and the high compute-to-memory ratio, traditional architectures face significant challenges regarding poor flexibility, i...Due to the diversity of graph computing applications, the power-law distribution of graph data, and the high compute-to-memory ratio, traditional architectures face significant challenges regarding poor flexibility, imbalanced workload distribution, and inefficient memory access when executing graph computing tasks. Graph computing accelerator, GraphApp, based on a reconfigurable processing element(PE) array was proposed to address the challenges above. GraphApp utilizes 16 reconfigurable PEs for parallel computation and employs tiled data. By reasonably dividing the data into tiles, load balancing is achieved and the overall efficiency of parallel computation is enhanced. Additionally, it preprocesses graph data using the compressed sparse columns independently(CSCI) data compression format to alleviate the issue of low memory access efficiency caused by the high memory access-to-computation ratio. Lastly, GraphApp is evaluated using triangle counting(TC) and depth-first search(DFS) algorithms. Performance analysis is conducted by measuring the execution time of these algorithms in GraphApp against existing typical graph frameworks, Ligra, and GraphBIG, using six datasets from the Stanford Network Analysis Project(SNAP) database. The results show that GraphApp achieves a maximum performance improvement of 30.86% compared to Ligra and 20.43% compared to GraphBIG when processing the same datasets.展开更多
文摘This paper introduces the general process of the search algorithm Structure through the knight problem. According to the characteristics of the problem, we detailed discuss the DFS（Depth First Search） algorithm and BFS（Breadth First Search） algorithm, and combine the two algorithms together to solve the knights coverage problem. This article has a good reference for the mixed-use scenarios which requires a variety of search algorithms.
文摘电力系统仿真验证往往希望通过拓扑结构图直观地分析网络的潮流分布以及动态特性。然而电力系统机电暂态过程仿真软件如BPA、PSS/E和PSASP都不能自动地根据电力系统的电气联系合理地布置网络中的元件,而需要人为地调整各元件的位置来形成一个直观的电气接线图。这种人为手动调整,不仅给仿真增加了工作量,更有可能带来更多的人为误差。为此,文中提出了基于图论的深度优先搜索(depth first searching,DFS)算法,依据电力系统的电气拓扑结构形成电力系统生成树的实现方法。用文中方法生成的IEEE9节点算例系统的可视化界面验证了该算法的有效性和准确性。
文摘拓扑图自动生成算法是配电网拓扑接线图自动成图的核心。为此,详细阐述了拓扑图自动生成算法的基本思路,该算法的核心是采用深度优先遍历(depth first search,DFS)算法搜索两点之间的最大距离。同时提出了分层布局、综合实现的成图思想,其具体实现分为3层:1)确定单条馈线的拓扑布局数组;2)确定两两变电站之间的拓扑布局数组;3)确定所有变电站之间的拓扑布局数组。将两两变电站之间的布局数组填充至所有变电站的布局数组中,可以得到配电网全网的布局数组,按照全网布局数组所确定的各变电站和各设备的坐标位置和互联信息,生成全网的拓扑接线图。该方法解决了直接一次性求取所有配电网设备在拓扑接线图中的坐标所导致的求解过程高度复杂甚至无解的问题,有效避免了交叉,大大减少了成图时间。最后,通过工程实际应用,验证了该算法的有效性和适用性。
文摘Networks are a class of general systems represented by becomes a weighted graph visualizing the constraints imposed their UC-structure. Suppressing the nature of elements the network by interconnections rather than the elements themselves. These constraints follow generalized Kirchhoff＇s laws derived from physical constraints. Once we have a graph; then the working environment becomes the graph-theory. An algorithm derived from graph theory is developed within the paper in order to analyze general networks. The algorithm is based on computing all the spanning trees in the graph G with an associated weight. This weight is the product ofadmittance＇s of the edges forming the spanning tree. In the first phase this algorithm computes a depth first spanning tree together with its cotree. Both are used as parents for controlled generation of off-springs. The control is represented in selecting the off-springs that were not generated previously. While the generation of off-springs, is based on replacement of one or more tree edges by cycle edges corresponding to cotree edges. The algorithm can generate a frequency domain analysis of the network.
文摘For decades,engineers have utilized Petri nets to develop automated systems with specific functional requirements or characteristics.Nonetheless,the ex-isting formalism prevents the use of classic traversal techniques to examine and analyze a system’s functional behavior.This paper provides a novel tech-nique to represent Petri nets as directed Euler graphs.It enables design engi-neers to examine and traverse the various states of a system utilizing the vari-ous methodologies and traversal processes applicable to Euler graphs.In this study,we present an iterative approach for determining an optimal path in terms of the least number of edges(vertices)required to cover and contain the system’s states,which are represented as Petri nets.The goal is to leave one vertex and return to the same vertex of the graph in a finite number of steps.This is a new method for determining the attribute of the system’s reset,which is represented by Petri nets and allows the system to return to its starting state,the resting state.The goal is to broaden the ontological basis of Petri nets by displaying linkages or relationships between Petri nets that are akin to directed Euler graphs.
基金supported by the National Science and Technology Major Project (2022ZD0119001)the National Natural Science Foundation of China (61834005)+1 种基金the Shaanxi Key Research and Development Project (2022GY-027)the Key Scientific Research Project of Shaanxi Department of Education (22JY060)。
文摘Due to the diversity of graph computing applications, the power-law distribution of graph data, and the high compute-to-memory ratio, traditional architectures face significant challenges regarding poor flexibility, imbalanced workload distribution, and inefficient memory access when executing graph computing tasks. Graph computing accelerator, GraphApp, based on a reconfigurable processing element(PE) array was proposed to address the challenges above. GraphApp utilizes 16 reconfigurable PEs for parallel computation and employs tiled data. By reasonably dividing the data into tiles, load balancing is achieved and the overall efficiency of parallel computation is enhanced. Additionally, it preprocesses graph data using the compressed sparse columns independently(CSCI) data compression format to alleviate the issue of low memory access efficiency caused by the high memory access-to-computation ratio. Lastly, GraphApp is evaluated using triangle counting(TC) and depth-first search(DFS) algorithms. Performance analysis is conducted by measuring the execution time of these algorithms in GraphApp against existing typical graph frameworks, Ligra, and GraphBIG, using six datasets from the Stanford Network Analysis Project(SNAP) database. The results show that GraphApp achieves a maximum performance improvement of 30.86% compared to Ligra and 20.43% compared to GraphBIG when processing the same datasets.
