CN108595208B

CN108595208B - Method for converting ladder diagram capable of processing function vertex into instruction sequence

Info

Publication number: CN108595208B
Application number: CN201711488500.4A
Authority: CN
Inventors: 王郁昕; 何宁; 王金华; 徐光美; 张睿哲; 张敬尊
Original assignee: Beijing Union University
Current assignee: Beijing Union University
Priority date: 2017-12-30
Filing date: 2017-12-30
Publication date: 2021-11-26
Anticipated expiration: 2037-12-30
Also published as: CN108595208A

Abstract

The invention discloses a method for converting a ladder diagram capable of processing function vertices into an instruction sequence. In the method, the graph G=<V, E> consists of a set of finite vertices V and edges E; The printout of the in-order traversal is slightly altered to obtain a different specification of the instruction sequence. The binary expression tree is directly stored in the memory, and the translation process of the expression is omitted. After obtaining the sequence of subsequent traversal of the binary tree, the expression calculation based on the stack is performed to directly obtain the calculation result; this method uses the binary expression The tree data structure is the goal, and the calculation results used later can be automatically cached, and it is not necessary to cache all the parallel-merged results, thereby saving storage space. The processing of the ladder diagram mainly focuses on how to translate it into a list of instructions so that the programmable logic controller (PLC) can execute these instructions to complete the control tasks expressed by the ladder diagram.

Description

Method for converting ladder diagram capable of processing function vertex into instruction sequence

Technical Field

The invention relates to a method for converting a ladder diagram into an instruction sequence, in particular to a method for converting a ladder diagram capable of processing function vertexes into an instruction sequence, and belongs to the technical field of industrial control.

Background

Ladder Diagrams (LD) are widely used in the field of industrial control, and the processing of Ladder diagrams mainly focuses on how to translate them into instruction lists so that programmable controllers (PLC) can execute the instructions to complete the control task expressed by the Ladder diagrams. The ladder diagram is essentially an operational expression described by a connection structure between operational units, and the expression includes only two kinds of operations, corresponding to a series structure and a parallel structure, respectively. The methods for converting ladder diagrams into instruction lists are not few, but are more or less problematic. A method is presented for translating a ladder into the IEC 61131-3 instruction sheet, where there may be function vertices in the converted ladder to complete a specific function call. However, this method is not perfect in processing the function of the function vertex, and does not consider the problem that the function vertex must calculate its input in advance. While the algorithm does not give time for the algorithm to execute.

The transformation of the ladder diagram into the instruction list is essentially a transformation of the diagram into a binary expression tree. A binary expression tree, called BET for short, is one of binary trees, and an ergodic sequence obtained after the middle-order ergodic of the tree is an expression. Any subtree of the tree is called a binary expression subtree and is denoted as SUB-BET.

Disclosure of Invention

The invention provides a method for converting a ladder diagram into a binary expression tree, which comprises the following steps: the LD-BET method not only overcomes the defects of the prior method, but also mainly aims at not converting into an instruction list but also aims at a binary expression tree data structure. The printout of the middle-order traversal of the tree is slightly changed to obtain instruction sequences with different specifications, i.e. the ladder diagram can be translated into various instruction sequences. Meanwhile, the binary expression tree can be directly stored in the memory, the translation process of the expression is omitted, and after the sequence of the subsequent traversal of the binary tree is obtained, the stack-based expression calculation can be carried out, so that the calculation result is directly obtained. The algorithm has the other characteristic that the calculation results used for the second time later can be automatically cached, and all the results combined in parallel do not need to be cached, so that the storage space is saved.

The invention discloses a method for converting a ladder diagram of a processable function vertex into an instruction sequence, which comprises the following steps: graph G < V, E > consists of a finite set of vertices V and edges E. If G is a graph, V-G.V represents the set of vertices in the graph, and E-G.E represents the set of edges in the graph; any ladder diagram is represented as a directed acyclic graph, or DAG. Some constraints must also be satisfied, and a DAG graph that can satisfy these constraints is referred to as an LDGraph.

The LD-BET method uses 2 objects, one being nodes for describing the BET tree and the other being vertices for describing the LDGraph. The node object comprises attributes of vertex, left, right and pi, and the node set is marked as N. All nodes forming the BET tree form a node set N_BETAnd is also

The vertex attribute indicates the vertex included in the node, i.e., indicates which vertex in the graph the node corresponds to. left denotes the left pointer, right denotes the right pointer, and π denotes the parent pointer, all pointing to other nodes in the BET tree. The node object has no special name attribute, and the node name is represented by the name attribute of the vertex object contained therein. The NODE object is created by a NODE (vertex) method, and three NODEs are changed to belong to N by an ADD-NODE method_BETThe node (b). The vertex object contains attributes of name, Adj ', buffer, buffer', root, pi, d, color, conntionType, and functionType. The vertex name is represented by a name attribute, and Adj represents an adjacency list of the vertex; the graph is described in the form of an adjacency list, which for vertex v represents a set { Adj₁,Adj₂,……,Adj_nTherein Adj_iE.v, i ═ 1,2, … …, n. The set represents that there is a directed edge between each element from v to the set v.adj; the adjacency table vertex1.adj of vertex1 has { vertex 2, vertex 3, vertex 6, vertex 7, vertex 10, vertex 20, vertex 21 }. Adj' is a linked list that collects the series branches injected into the parallel vertex, which are used in parallel. For vertex v its linked list v.adj' represents an ordered sequence<Adj'₁,Adj'₂,……,Adj'_n>Of which Adj'_i∈N_BETI is 1,2, … …, n. The ordered sequence indicates that from v to each element of the sequence, there is a series branch of the injection v, and the sequence order represents the injection precedence order. buffer, buffer' is used to buffer the intermediate results when generating the BET sub-tree. root represents the root of the BET subtree associated with the vertex. And pi represents the parent vertex of the vertex. d is used to represent the distance of the vertex from the initial vertex. The color is used to identify the vertex visit status to determine whether the vertex has been visited during the traversal process. The vertex object is created by the vertex (name) method, and the parameter represents the name attribute of the vertex.

And classifying the vertexes into a series type vertex and a parallel type vertex according to the connection relation. The vertex of the series connection type: in the figure, the in-degree and out-degree are not more than1 vertex, by V_SAnd (4) showing. Parallel connection type vertex: the vertex with in-degree greater than 1 or out-degree greater than 1 in the figure is represented by V_PRepresents;

V_S∪V_PG.V. The connection relation classification is represented by a vertex attribute connectionType, and the corresponding values are respectively SERIAL and PARALLEL, and respectively represent a SERIAL vertex and a PARALLEL vertex.

Dividing the vertex into an initial vertex, a termination vertex, a relay vertex, a coil vertex, a function vertex, an auxiliary relay vertex and an auxiliary coil vertex according to the function classification; the classification is represented by a vertex attribute functional type, corresponding values are respectively GS, GT, RELAY, COIL, FUNCTION, VSF, RELAY, VCORL, and corresponding connection relations are respectively: parallel, series, parallel.

Drawings

FIG. 1 is a directed graph of the transformation of Ladder Diagram.

Fig. 2 is a schematic diagram of a tandem type branch structure.

FIG. 3 is a schematic diagram of a vertex adding structure.

FIG. 4 is a schematic diagram of an example of a serial BET tree formation process. .

FIG. 5 is a diagram of the result of processing the Adj' attribute of vertex 25 through lines 1-13.

Fig. 6 is a graph of the merged results of fig. 5.

Fig. 7 is a graph of the process and results of fig. 6.

Fig. 8 shows vertex 11 as a common trailing vertex between vertex x1 and vertex 14.

FIG. 9 is a diagram of the output caching process for the results of the computation of the left sub-tree.

FIG. 10 is a schematic diagram of the corresponding process of BET tree formation.

FIG. 11 is a diagram of a data structure in the Adj' attribute of vertex 25

Fig. 12 is a diagram of a BET tree formation process corresponding to fig. 3.

Fig. 13 shows the instruction representation.

Detailed Description

The invention is described in detail below with reference to the figures and examples.

Initial vertex: the only vertex in the graph, which is connected with any vertex and has an in-degree of 0, is G_sShown generally at the far left end of the figure. The white vertices in fig. 1 are series vertices and the gray vertices are parallel vertices. Y is₀And Y₁Is a coil type of tandem vertex.

Terminating the vertex: the only vertex in the figure which can be reached from any vertex and has the out degree of 0 is G_tThis representation is generally drawn at the right-most end of the figure. Introduction of auxiliary vertex G in LDgraph for uniform processing of coil vertices_tAll the coil type vertices are injected into the vertex, and a specific example is shown in fig. 3 (1). Both the terminating vertex and the auxiliary function vertex are artificially post-added to the graph G. The initial and terminating vertices are forced to be parallel vertices, with the vcoil type vertices being used for processing of auxiliary function vertices, while other parallel vertices are generally not provided with the functional type attribute, the purpose of which will depend on the specific application. In addition to the secondary vertices, the funtionanttype attribute is a known attribute, i.e., determined with the given graph G.

Tandem type branching: in the figure, a path among 2 parallel-type vertexes passes through all vertexes of the path which are in a serial-type, and two ends of a serial branch are parallel-type vertexes which are only two parallel-type vertexes in the serial branch. If the serial vertex is ignored and each serial branch is an edge, a graph is actually formed by the serial branch and the parallel vertex, and G' can be used<V_P,E_P>Showing such a diagram. The serial branch distance of each serial branch is 1, and the distances in the method are all referred to as V epsilon V in G', without specific indication_PTo G_SThe distance of (c).

Tail vertex of the series branch: the first vertex on the series branch, which is a parallel vertex. The tail vertex of the series branch is called tail vertex for short, and is denoted by v_tObviously, there is v_t∈V_P。

Are connected in series toFirst vertex of branch: the last vertex on the series branch, which is a parallel vertex. The first vertex of the serial branch is called the first vertex for short. The tail vertex may follow the series of branches to reach the head vertex, denoted v_hObviously, there is v_h∈V_P。

Minimum tail vertex and minimum series branch: among all the serial branches injected into the parallel vertex, there must be one in series with a tail vertex closest to the initial vertex compared to the other tail vertices, called the minimum tail vertex, denoted v_tn. The concatenation branch where the smallest tail vertex is located is called the smallest concatenation branch. Namely, the minimum series branch between two parallel type vertexes is the series branch with the largest span; the smallest serial branch is not unique and, in figure 1,<1,2,25>and<1,3,4,5,25>are all the smallest serial branches of vertex 25, vertex1 is the smallest tail vertex of vertex 25, and

vertices

16, 13, 22, 1 are all tail vertices of vertex 25.

LDGraph defines: except that G_sAnd G_tIn addition, all the parallel vertices in the DAG graph satisfy that when walking in reverse along each edge that hits its tail vertex, it must pass through its smallest tail vertex. For a given graph G, its inverse graph is denoted G^T. If at G^TIn the presence of v₁,v₂Two vertices, from vertex v₁Starting to G_sHas passed v in the path₂Then call v₂Is covered with v₁. The DAG graphs do not overlap each other. The smallest tail vertex completely covers the other tail vertices in the LDGraph. Only if the graph satisfies the LDGraph definition will the Adj' list of each parallel vertex contain all the information that can be merged for parallel. Figure 1 is an LDGraph and figure 2 is not an LDGraph because for vertex 9, if vertex 3 is the smallest tail vertex it does not overlap tail vertex 6, its serial branch through vertex 4 does not pass through vertex 3. The algorithm proposed by the present invention is only used to process LDGraph if vertex 6, as the smallest tail vertex, also cannot cover vertex 3.

FIG. 2: non-LDGraph, if vertex 3 is the smallest tail vertex, then when walking along the opposite side of tail vertex 6 that is injected into vertex 9, the serial branch that passes through vertex 4 does not pass through the smallest tail vertex 3 of vertex 9. Likewise, vertex 3 cannot be covered if vertex 6 is the smallest tail vertex.

There may be function vertices in the LDgraph, such as vertex 17 and vertex 23 in FIG. 1, which become function type vertices. Such vertices are completely different from relay type vertices, and the logical operation relationship between input and output is broken, and the input and output can be considered to have no relationship, because the output of the procedure called by the function vertex can be any value of the bootean value. In order to process the function vertices, auxiliary function vertices and auxiliary relay vertices need to be added to the LDGraph. The rule of adding is to change the tail vertex on the serial branch where the function vertex is located into a vertex of a vcoil type so that the tail vertex becomes an auxiliary coil vertex, and simultaneously, an auxiliary relay vertex is added on all output edges of the tail vertex for representing the output result of the auxiliary coil vertex, the name of the auxiliary relay vertex is the same as that of the tail vertex, but for convenience of explanation, the auxiliary relay vertex is represented by the name of the tail vertex plus' ″, and the essence of the auxiliary relay vertex is not different from that of the relay vertex. Then at the tail vertex and vertex G_tThe serial branch containing only one auxiliary function vertex is added between the auxiliary function vertex and the tail vertex, and the auxiliary function vertex name and the tail vertex are of the same name, but are represented by "" plus "" tail vertex name "" for the convenience of description. The effect of adding this series of branches is to advance the computation of the vcoil vertices to ensure that these vertices already have the computed result when the auxiliary relay vertices are used. However, the introduction of such serial branches would destroy the principle of tail vertex coverage, but only at the processing vertex G due to this condition_tThis problem can be handled by a special handling procedure (see BUILD-summary 3 procedure). If

vertices

17 and 23 in FIG. 1 become function-type vertices, an example of the addition of auxiliary vertices is shown in (2) in FIG. 3. The thin dashed circles in the figure represent auxiliary function vertices, the thick dashed circles represent auxiliary relay vertices, and

vertices

16 and 22 become auxiliary coil vertices.

Tail node and minimum tail node: each vertex in the LDGraph can find a corresponding node in the BET tree, so there is a correspondence between the vertex and the node. The node in the tree containing the minimum tail vertex is called the minimum tail nodeIs represented by n_tn. While nodes in the tree that contain other tail vertices are called tail nodes. The BET sub-tree corresponding to the converted smallest serial branch is called the last BET sub-tree, and the root of the last BET sub-tree is denoted by r_tn. For purposes of discussion, a vertex symbol is sometimes used to denote a node containing the vertex, e.g., G_tThe node representation includes G_tThe nodes of the vertices.

FIG. 3(1) adds the termination vertex G to FIG. 1_t(2) after vertex 17 and vertex 23 in FIG. 1 become function type vertices, it is necessary to add 2

auxiliary function vertices

16 and 22, and the function type attribute of both vertices is set to VSF and 3 auxiliary relay vertices 16', 16', 22 '. The functionType attribute of

parallel vertices

16 and 22 is set to VCOIL.

The BET sub-tree corresponding to the branch is called the last BET sub-tree, and the root of the BET sub-tree is denoted by r_tn. For purposes of discussion, the node, G, is sometimes referred to as being included with a vertex symbol_tThe node representation includes G_tThe nodes of the vertices.

Operation node and string connection point: nodes in the BET tree, if representing operations such as AND, OR, ST, EMPTY, etc., are referred to as operation nodes, AND are denoted by +, +, ST, -respectively, in the figure. The vertices contained in the operation nodes are called operation vertices and are denoted by v_opIts name attribute represents the OPERATOR, its functional attribute is set to OPERATOR, none of these vertices belong to graph G, i.e.

A node is a string junction if its vertex attribute is a string vertex.

Merging of series vertices and merging of parallel vertices: the combination of each series vertex on the series branch by means of the AND NODE AND the ADD-NODE process is called as series combination; the merging of each series branch into a parallel vertex by means of an OR NODE and ADD-NODE process is referred to as a parallel merge. In either combination, the combined result produces a BET sub-tree.

The LD-BET algorithm consists of six components. The first part reads in map G. The second section sets the connection attribute connectionType for each vertex in the graph. The third part adds auxiliary vertices to the graph. The fourth part combines the vertices on the series branches, and the fifth part combines the series branches injected into the parallel vertices. The sixth section spreads out each parallel vertex in the BET tree to form a BET tree without parallel vertices. Each part in turn is composed of one or more processes. The vertex color of the graph G is restored to white after each step.

LD-BET

1read the graph G

2SET-CONNECTIONType

3ADD-AUXILIARY-VERTEX

4DFS

5BFS

6BUILD-TREE

The first part includes algorithms for converting ladder diagram into LDGraph, format verification and judging whether it is LDGraph, but these algorithms are not discussed in the present invention, which begins with obtaining a qualified LDGraph diagram G. Sections 2-6 are described in detail below.

SET-CONNECTIONTYPE(G)

SUB-SET-CONNECTIONTYPE(u)

The SET-CONNECTIONYPE process adopts a depth-first search method, a connection attribute is SET for each vertex, and if the vertex is single-input single-output, the connection attributes of the vertices are SET in series; the connection attribute is set to parallel if multiple input or multiple output. Lines 1-3 are all the vertices in FIG. G painted white and their connected attributes set to in-line. Line 5 start vertex G_sThe parallel vertex is forced to be set. Lines 7-8 judge whether the out degree of each vertex is greater than 1, if so, the vertex is a parallel vertex; current vertex in line 13u points to a gray vertex whose in-degree must be greater than 1, so the gray vertex is arranged as a parallel vertex. Line 9 traverses all adjacent vertices of vertex u, detecting the color attributes of those vertices, where

Representing the contiguous vertices of u. The 11 th row is set with a vertex pi attribute for recording the parent vertex of the vertex, which is the inverse (transposed) G of the current G graph^TThe formation of (A) creates conditions. The entire process visits all vertices in graph G once in turn, indicating that a vertex has been visited if a neighboring vertex is grayed out, and not visited if white, then the SUB-SET-connection process can be recursively invoked to continue visiting the white vertex. In all algorithms of the method, the color attribute of the vertex is used for recording the access state of a certain object. From the depth-first search run time of the graph, the run time of the process can be obtained as O (V + E), where V and E written in O represent the number of vertices and the number of edges in graph G, respectively.

ADD-AUXILIARY-VERTEX(G)

The ADD-AUXILIARY-VERTEX process first creates an AUXILIARY coil VERTEX set V containing 0 elements_coil. All the coil vertices and function vertices in the graph G are found in lines 2-9, and line 4 adds an injection termination vertex G to all the coil vertices_tOne edge of (2). Lines 6-9 find the tail vertex of the branch in series where the function vertex is located and incorporate it into V_coilAnd (4) concentrating. The use of variations in color attributes avoids repeated incorporation. Lines 10-20 process all auxiliary coil vertices in turn. Line 13 creates an auxiliary relay vertex, lines 14-16 add the auxiliary relay vertex to the series branch immediately adjacent to the tail vertex, line 17 changesThe connected nature of the tail vertices makes them VCORL. Line 18 creates an auxiliary function vertex and lines 19-20 add the auxiliary function vertex to the series branch connecting the vcoil vertex and the terminating vertex. Line 6 simplifies some details of the find tail vertex, the tail vertex can be found backwards through the pi attribute function vertex, and there are two conditions for stopping the backward search: hit the tail vertex or hit the function vertex. The latter condition ensures that the tail vertex only needs to be processed once when there are multiple function vertices on the series branch. Thus, the run time for rows 1-9 is O (V + E), and the total run time is also O (V + E).

ADD-NODE(op,leftChild,rightChild)

In the conversion of LDGraph into a binary expression tree (binary expression tree), ADD-NODE process is required, which forms a binary tree with three NODEs, tree root np, left child leftChild, right child rightChild. If either the left child or the right child does not exist, the other child is returned. If both left and right children are present, the tree root is returned, which is an operation node, as can be seen in line 1 and line 14. The functional attribute of the operation vertex in line 2 is set to OPERATOR. Lines 8-13 deal with several special children, in each case the operation vertices are given different names, the role of which will be explained later in the discussion. 17, 18 enable each binary node to easily find its own parent. The run time of this process is O (1).

DFS(G)

The DFS process merges all the cascading vertices on the same cascading branch in the order of depth-first search. And 7, packaging the current vertex into a NODE by using a NODE process, forming a new sub-tree by using an ADD-NODE process, enabling the right sub-tree of the root of the original BET tree and the newly packaged NODE to become left and right children of the root of the sub-tree respectively, and then grafting the left and right children onto the original root to become the right children of the root of the atomic tree. Row 6 points the root of the current vertex to the root of its parent vertex, so the root of each vertex of the entire concatenated branch is actually the root of the first concatenated vertex of the branch, representing the tree root of the BET subtree formed. The BET grows continuously as the search proceeds along the entire series branch, newly created nodes are added to the BET continuously with the identity of the right child, and the tree grows continuously high until a parallel vertex is encountered. The processing of the first tandem vertex on the tandem branch is performed on line 8, with the resulting vertex wrapped by the left child of the BET being one of the parallel vertices adjacent to the vertex. It can be seen from line 7 that the left child has no variability in the process of merging in series, so the parallel vertex merged into the BET tree from line 8 is the tail vertex of the entire series branch. The BET tree for the entire tandem branch is referred to as the "tandem BET tree". Lines 9-11 perform a depth first search, similar to the SET-CONNECTIONYPE process. An example of a serial BET tree formation process is given in fig. 4.

In addition, topological distances are required to be set for the parallel type vertexes so as to carry out topological ordering on the parallel type vertexes. Following the processing terminating vertex G_tIt is necessary to know which vertices must be processed before other vertices. The 1 st action sets an initial value for the distance.

Lines

13 and 14 are executed each time a parallel vertex is encountered. The smaller the distance, the more advanced the process. The runtime from the depth-first search of the graph may be given as O (V + E) for the runtime of the process.

In FIG. 4, vertices 1-5 represent a series branch,

vertices

1 and 5 are parallel vertices, and vertices 2-4 are series vertices. (1) And (2) and (3) describe the merging process of the vertexes on the series branch according to the running sequence of the algorithm. Light gray circles represent nodes in the BST tree, AND "+" represents the concatenation operator AND. The root attributes of all the cascading vertices on the cascading branches eventually point to the tree root of the generated BST.

BFS(G)

SKIP-SERIAL-VERTICES(u)

The BFS process processes all parallel vertices in graph G in order of breadth first search. Lines 1-6 plus lines 11-13 are typical breadth first search algorithms, with the search for the entire graph G starting with the initial vertex G_s. ENQUEUE and DEQUEUE denote DEQUEUE and ENQUEUE methods, respectively. Rows 1-13 initially merge the parallel vertices such that the series branches incident on the parallel vertices form an OR operation, each series branch is merged into the formed BET sub-tree by an OR node, and all of the incident parallel vertices v_hThe BET sub-tree corresponding to the series branch of (a) is stored in v_hIn Adj', the attribute data structure is a list, similar to the structure of an adjacency list, but with emphasis on the order of the elements in the list.

Lines

8 and 9 are used to find the first vertex v on the series branch_h. The SKIP-SERIAL-verify process is used to search along the series branch until the first vertex on the branch is encountered and returned. The parent vertex of the encountered parallel vertex is also set in the searching process, for the serial vertex, the 2 nd line belongs to the repeated setting, because the previous process has set the pi attribute of the serial vertex, but is very important for the first vertex, because a plurality of serial branches can be shot into the first vertex, it is necessary to specify which serial branch is connected currently, and this information can be obtained by returning the pi attribute of the vertex, for the convenience of explanation, the vertex represented by the pi attribute is called as the first parent vertex, obviouslyThe first parent vertex is a tandem vertex. V in the course of BFS-PARALLEL-VERTICES_hPi represents the first parent vertex on the currently processed serial branch, the root attribute of which stores the BET subtree root corresponding to the serial branch, and the left child of which contains the tail vertex of the serial branch. The U-shaped is the ordered combination of the two lists, and the latter list element is inserted into the tail of the former list in turn or the latter set element is inserted into the tail of the former list. Line 10 sequentially merges the roots of the BET subtrees corresponding to the branches connected in series in the first parent vertex to vertex v_hAdj' of (1). v. of_hAll injected vertices v are finally held in Adj_hThe roots of the BET subtrees corresponding to the serial branches of (1). In FIG. 1, the result of the Adj' attribute of vertex 25 after being processed through lines 1-13 is shown in FIG. 5.

FIG. 5 shows the DFS-SERIAL-VERTICES processing performed on vertex 25 of FIG. 1, after the root attribute of each of the series BET subtrees has been saved in the root attributes of

VERTICES

2, 5, 23, 15, 18, 19, the result is processed through lines 1-13 of the BFS process, and the result is shown. Each element in the list of Adj 'is sequentially denoted as Adj'₁,Adj'₂……Adj'_nIs then Adj'₁,Adj'₂,Adj'₃,Adj'₄,Adj'₅,Adj'₆Corresponding to 2.root,5.root,23.root,15.root,18.root,19. root.

The tail vertices of the series branches may be different from each other OR the same, if the tail vertices on the series branches are the same, the series branches may be merged with the parallel operator OR, for vertex 25 in fig. 1, 2.root and 5.root may be merged in its Adj' list, and 18.root and 19.root may be merged. Lines 14-28 describe specific implementations of merging.

Lines

14,15 find all the parallel vertices in graph G, and then line 18 resets the parallel vertex parent vertex. Tree root Adj ' of the first subtree in Adj ' due to breadth-first search '₁The vertex included in the left child of (2) is the tail vertex of the minimum serial branch, and the vertex is set as the parent vertex of the current parallel vertex u, so the parent vertex of the parallel vertex is also the minimum tail vertex. For example, in FIG. 5, vertex 25 is referenced by vertex number 1 as its parent, rather than other parallel typesAnd (4) a vertex. Lines 19-25 traverse an Adj' list of parallel vertices that holds the roots of the series BET tree of all the series branches incident on the parallel vertices, including the tail vertices of the series branches in the left children of the roots. Two serial branches can be merged by or if their tail vertices are the same. The 21 rows determine whether the two tail vertices are equal, and if so, 22 rows are executed, which function to merge the two serially connected BET trees into one BET tree through an OR operation node, where the right children of the two original trees become the left and right children of the right child of the new composition tree, respectively, and the left child of the new composition tree may be the left child of any one of the two original trees because they both contain the same tail vertex. If the two branches in series differ in their tail vertex, 23 lines are executed which add the root of the BET tree directly to the temporary list Adj_TIn (1). With the two-by-two merge strategy, 24 rows and 25 rows exchange merge and merge roles, which is ready for further merge actions. Line 26 saves the last merged result to the temporary list Adj_TIn (1). Line 27 will temporarily list Adj_TAll elements in (a) are reversed in order so that the closer the tail vertex (contained in the left child of the BET subtree root) to the initial vertex is the further back in the list, where the distance measure is the number of serial branches, and two parallel type vertices connected by one serial branch are at a distance of 1. It is clear that the smallest end node is ranked at the end of the list. Line 28 resets the Adj' attribute with the combined outcome. The combined results of FIG. 5 are shown in FIG. 6.

FIG. 6 "+" indicates the parallel operator OR. (1) And 2.root, and 5.root, combining the results by means of an OR operation node. (2) Root remains unchanged. (3) Root remains unchanged. (4) Root,19.root the results of the combination are performed by means of OR operation nodes.

It is demonstrated below for any one parallel vertex v_hV. thereof_h.Adj'_nVertex must be the minimum tail vertex, where n represents the index of the last element in the Adj' list, and the tail vertices are ordered when the serial branches are merged by means of the OR operation node, i.e. the serial branches represented by different tail vertices do not appear alternately, that is to say the sameThere are no other tail vertices between the tail vertices of (1), so no cross-merge situation occurs. For example, for the vertex 25 in fig. 1, the merging order does not necessarily occur in the arrangement of 2.root, 23.root, 5.root or 18.root,15.root,19. root, that is, 2.root,5.root is necessarily one group, 18.root,19.root is necessarily one group, there is no other vertex between them, but the order between the trees in each group can be any order.

Evidence: due to the role of line 9, lines BFS 1-13 actually perform breadth first search on graph G'. 6-13 rows are for the tail vertex v_tAdjacent vertex v of_hGo through the traversal, obviously v_tAnd v_hFor a certain initial vertex v, is 1_hAll v are v if the tail vertices of the series branches injected into them are the same_tThen means v_hAnd v_tWith heavy edges in between. For head vertex v with heavy edge injection_hInformation of the tail vertices associated by the heavy edges is continuously recorded in the Adj 'list thereof, so that the heavy edges ensure that the same tail vertices are necessarily adjacent in the Adj' list of the head vertex. While in graph G' the heavy edges may be merged by 14-26 rows. In addition, because breadth-first search is essentially by distance from the initial vertex G_sSo the elements in the Adj' list of vertices are ordered, and the order of the elements in the list after 28 rows have been executed is the tail vertex data G_sThe distance is farther from the far to the near, the distance is farther to the front in the Adj' list, and the distance G is processed by 27 lines_sThe further back in the Adj' list, which is desirable because the latter algorithm requires minimum tail vertex finishing. Lines 1-13 are essentially breadth-first searches of FIG. G, with run times of O (V + E) and 14-28 with run times of O (V + E)_P) Thus, the total run time is O (V + E).

BUILD-SUBTREE(u)

The main role of the BUILD-SUBTREE process is to belong to the parallel vertex u-andthe preliminary merging results of the series branches stored in Adj' are further merged, so that the series branches incident into the parallel vertex u all form parallel operation, and the result is stored in u.root. The processing of a single parallel vertex is divided into three cases to be performed separately. The general case of 5 rows of processing, np, holds the tree root of the BET subtree formed. The 3-line processing vertex is the terminating vertex G_tThe case (1). The case of the 2-line treatment is that there is already a well-treated BET sub-tree but the previous results need to be used a second time. The root attribute of all the parallel type vertices is empty before the BUILD-SUBTREE procedure call, and if the attribute is not empty, the vertex is processed. The handling of the three cases is accomplished by calling the BUILD-SUBTREE-3, BUILD-SUBTREE-2, BUILD-SUBTREE-1 sub-processes, respectively.

BUILD-SUBTREE-3(u)

In BUILD-SUBTREE-3 process, r_tnRoot of the last BET Tree representing injection u, v_tnThe minimum tail vertex representing u is represented. Rows 3-6 initialize the tail vertices of each series branch in the u.adj' list. All trailing vertices are colored gray, the color of the vertex indicates whether processing continues, and processing stops if a gray vertex is encountered. The buffer and buffer' attributes are cleared. Both attributes are used to cache the temporarily generated BET subtree when processing the parallel vertex, but buffer' corresponds to the processing result of the vcoil vertex and buffer corresponds to the processing result of the other parallel vertex. Rows 7-28 build a BET tree using all subtrees in the u.adj' list. The construction process is according to the graph G'^TDirected edges proceed, which are in the opposite direction to the edges in the graph G'. The construction path at this time belongs to a reverse construction path, which is different from the path of constructing the BET sub-tree in the previous process.

Lines

8, 9 represent the right child of the root as np, which is actually the root of the serially branched BET subtree without the tail vertex. The tail vertex of each series branch is denoted v_tAt this time, the serial branch is merged by the BFS process, so the same tail does not appear in the u.adj' listAnd (4) a vertex. Current tail vertex v_tPainted white by 10 lines so that the vertex can start to be processed, since all vertices are initially grey. Line 11 is a parallel merge of the BET subtree cached by the current tail vertex with np. Since the processed results for the tail vertices covered by the current tail vertex are stored in the buffer in the form of BET subtrees, the previous merged results are first merged before the current tail vertex is further processed. The action of line 11 can also be understood as a parallel type merge in terms of vertex emittance. Lines 12 and 15-17 are the current vertex v_tContinuously along G 'as long as no processed vertex is encountered'^TThe method comprises the following steps of searching for edges, carrying out serial combination once a parallel vertex is encountered, and adding a mark to a processed parallel vertex to indicate that the vertex is processed. Each parallel vertex is processed only once, which also means that the series combination resulting from the minimal tail vertex overlay is done only once. Line 16 by pair current vertex v_tIndicates the vertex v_tHaving been processed, the following row 26 can detect whether the smallest tail vertex needs to be merged in series into the BET sub-tree by the name of the last BET tree root. The final BET tree corresponding to vertex u is composed of BET subtrees in the u.adj' list, but there is no fear that the BET tree is corrupted by modifying the node name, since we have modified the root name of the BET subtree, while the complete calculable BET subtree is its right child, as can be seen from line 8. Lines 13-14, which indicate that a violation of the coverage principle has occurred if the encountered vertex has been processed, require immediate termination of the search and indicate the occurrence of the above by blacking out the vertex. Lines 18-22 deal with the case where the trailing vertex is black. If the current tail vertex funtionanttype attribute is VCORL, then the BET subtree generated by running lines 12-17, whose root is stored in np, needs to be merged into the BET subtree cached by the minimum tail vertex buffer' attribute. Finally all the injected vertexes v_tIf its tail vertex is a VCORL vertex, all of the parallel branches are merged into v_tBuffer' in the BET subtree. The functional type attribute of the parallel vertex if not VCOIL, then the tailThe nodes are firstly connected in series and combined into the temporary BET sub-tree np, and then the combined result is connected in parallel and combined into the BET sub-tree cached by the minimum tail vertex buffer attribute. Finally all the injected vertexes v_tIf its tail vertex is a non-VCORL black vertex, will merge into v_tBuffer cached BET subtree. Lines 23-24 handle the case of the smallest tail vertex, since line 11 executes first, so the BET subtree cached by the buffer attribute does not have to be processed repeatedly. The 25 lines deal with the case where non-minimum tail vertices encounter the minimum tail vertex in the search, which is the majority case. At this time, the current vertex v_tIs the minimum tail vertex v_tnThe temporary BET tree is merged in parallel into the BET subtree cached by the buffer attribute. When all tail vertices in the u.adj 'list are processed, the processing result is stored in the buffer and buffer' attribute of the minimum tail vertex. For the subtrees in buffer, it is necessary to determine whether to merge the minimum tail vertices into the BET tree in series, which is generally an affirmative answer. However, if the minimum tail vertex has already been processed by another path or the minimum tail vertex is a VCOIL type vertex, the minimum tail vertex does not need to be serially merged. Lines 26-27 complete the above process. Since we want the smallest tail node to be closest to the root of the tree, it will add to the BET subtree of the buffer cache by means of the AND' operation node. The final minimum tail node becomes the right child of the root of the BET subtree. The AND' operation node is actually an AND operation node, with the additional effect of labeling the node to indicate that the right child of such a node is a minimal tail node. It should be noted that the BET sub-tree has a different position of the smallest tail node than the other tail nodes, the former being the right child and the latter being the left child, and this feature is used in the subsequent process. In line 28, the two BET sub-trees in buffer and buffer' are finally combined in parallel and then returned. The purpose of caching the BET sub-trees with different caching attributes is to ensure that the sub-trees in buffer 'are prioritized, since the BET tree is always processed and accessed in left-right order, the order of the 27 rows of merging parameters satisfies the requirement that the sub-trees in buffer' be prioritized. The process and results of FIG. 6 are shown in FIG. 7, where node 1 is the smallest tailAnd (4) nodes.

Each parallel vertex is processed only once, i.e. only one BET sub-tree is formed for all the serial branches injected into it, but in fig. 8 either vertex x1 or vertex 14 requires the result of vertex 11. If the vertex 11 is not the minimum tail vertex, then the BUILD-SUBTREE-3 process is treated as a black tail vertex. If vertex 11 is the smallest tail vertex, it is processed by the BUILD-SUBTREE-1 procedure.

BUILD-SUBTREE-1(u)

FIG. 7 Adj'₁,Adj'₂,Adj'₃,Adj'₄Corresponding to 18.root,15.root,23.root,2.root in fig. 6, respectively. r is_tnIs 2.root, v_tnVertex1. (1) v. of_tAfter execution for vertices 16, 15-17, 12, and 25, v_tIs the vertex 13, v_tThe results in buffer are shown in the figure. (2) v. of_t For vertex 13, the results in np after line 11 has been executed are shown. (3) v. of_tThe results in np after execution for

vertex

13, 15 rows are shown, when v is_tBeing the apex 13. (4) v. of_tThe results in np are shown after execution for vertex 13,

lines

16, 17, 12 and then 15 more lines. Then lines 16, 17, 12 are executed again, at which point v_t＝＝v_tnThen 25 lines are executed, the result of np being saved at v_tnIn buffer. (5) v. of_tThe result of np after execution for the

vertices

22, 11 and 15-17 lines is shown as 23.root, and the result of 25 lines after execution is also stored as v_tnIn buffer. (6) v. of_tFor vertex1, the result np after line 11 execution is shown, which is saved at v after line 24 execution_tnIn buffer. (7) v. of_tThe results after execution for vertex1, line 27 are shown.

If the root attribute is empty, the vertex is accessed for the first time, if a BET tree (the tree root of a general BET is an operator node) already exists in the root and the vertex name corresponding to the root node is not a parallel vertex name, the 2 nd access is represented, and the 2 cases which are not met represent more than 2 accesses to the vertex. The process corresponding to 3 cases is to generate a BET subtree, add a cache vertex to the BET subtree, and return the BET subtree directly to the cache vertex. The first process is performed by the BUILD-summary-3 process, and the second process is performed by the BUILD-summary-1 process. In the BUILD-SUBTREE-1 process, line 2 first finds the parent pi of the root node of the BET SUBTREE stored at the current vertex, which is ready for the SUBTREE to be added back. If the processed parallel vertex u is processed, the result of u.root needs to be cached by virtue of ST nodes, and finally the BET subtree in the root attribute is replaced by the parallel node corresponding to the parallel vertex. Np in line 5 is the root of a BET subtree and the address of the cache is given by the right child of np, i.e. the name attribute of u. This is possible because all vertices in the pre-processing of graph G are given different names, and the parallel vertex names are given different numbers. To improve space efficiency, the cache addresses represented by the names of the parallel vertices may eventually need to be further optimized to arrange the addresses together to form a continuous space, but this is not discussed in this method. The calculation result of np left child will be saved to right child through ST node, when the result of original left child is needed again, the right child is given directly. Lines 6-8 are newly formed BST trees from line 5 added back to the original BST tree if the original subtree u.root is the right child now or the right child, otherwise the left child. When meeting the processed parallel vertex for the 2 nd time, the BST tree is much longer than that when processing the same vertex for the first time, at this time, the subtree pointed by the u.root is only one branch, in order to cache the original result of the branch, the 5-8 lines actually do to cut the subtree pointed by the u.root, and the cache vertex with the name of the current vertex as the cache address is grafted through the ST node and then is connected back to the original BET tree. Root in line 9 points to a new node, which contains the name of the vertex that reveals the cache address information. The application of the cache node can be understood as optimization of BST because the calculation of the real expression can be performed only once when the result of the same subtree is used many times, and the calculation result can be directly used many times later without repeated processing. This optimization is mainly accomplished by the above-described process.

Lines

3 and 4 deal with that if pi itself is an ST node, no cache is added for the subtree, since a cache already exists, and only the cache address needs to be returned, which is the name of the vertex contained by the right child of the current node. As can be seen, the run time for the entire process is O (1).

When u.functional type is TERMINAL in BUILD-SUBTREE, the position of nodes needs to be adjusted, but the parent pointers of the nodes do not need to be maintained at this time, because the nodes are G_tThe children of the node cannot be referenced by other nodes.

BUILD-SUBTREE-2(u)

BUILD-SUBTREE-2 procedure for processing TERMINAL vertex G_tFirst, line 1 is aligned with vertex G_tAll the tail vertexes in the system are sorted according to the d attribute of the tail vertexes, and the tail vertexes pass through G_tThe SORT actually topologically orders these tail vertices, which ensures that the top vertices are processed before the bottom vertices, so that the bottom vertices can use the result of the top vertices, since G is the result of the generation of G_tThe trailing vertices in (1) may not satisfy the relationship of vertex coverage. 2-10 rows in pair G_tAll subtrees in the Adj' list are traversed, if the root node of a subtree is not an ST node, then a 4-7 row "left traversing" operation needs to be performed in order to separate the coil type vertex from the concatenation branch, making it an output buffer for the left subtree computation result, the process of which is shown in fig. 9. Note that the operation NODE used for merging the coil type vertices is ST, as can be seen from the ADD-NODE process.

FIG. 8: vertex 11 becomes the common trailing vertex of vertex x1 and vertex 14

When the u.functional type in BUILD-SUBTREE is TERMINAL, the position of the node needs to be adjusted, but the parent pointer of the node does not need to be maintained at the momentFor these nodes are all G_tThe children of the node cannot be referenced by other nodes.

BUILD-SUBTREE-2(u)

FIG. 9 is a drawing showing Y_nIs a coil type vertex and (2) is the result of (1) left rotation.

Since the coil type vertex is always the last in the concatenation branch, all nodes in the BET subtree that correspond to them must be the right child of the ST node, a in fig. 9 is the smallest tail vertex, and a and b should be concatenated and then fed into the coil type vertex. Lines 8-10 merge the coil type vertices and the vcoil type vertices separately, and since each series branch is an independent output branch, the merging is done by an EMPTY node, which indicates that the two branches merged have no relationship to each other and are independent of each other. Row 11 merges the np and np 'subtrees, the np' subtree indicating to the left child that the subtree was processed before the np subtree. Due to the operation of "lifting andthe operation time of the ADD-NODE process is O (1), so that the operation time of lines 2-10 is O (V)_P) Run time of line 1 is defined by pair | V_PThe algorithm for sorting I vertexes is determined, and the running time of the sorting algorithm is not set to be O (V)_PlgV_P) Therefore, the run time of the BUILD-SUB-TREE2 process is determined by the sorting algorithm in line 1, and is O (V)_PlgV_P)。

BUILD-TREE(G)

1np＝BUILD-SUBTREE(G_t)

2WALK-PARALLEL-NODE(np)

3return np

WALK-PARALLEL-NODE(n)

All the vertices of the parallel type in graph G, except the terminating vertex, are tail vertices, which all correspond to respective BET subtrees whose roots are stored in their root attributes. Each tail vertex in the resulting BET tree has a corresponding node pointed to by its root attribute. The BUILD-TREE procedure is to establish the BET TREE corresponding to the termination vertex, which is the BET TREE finally needed, but this time, the BET TREE also includes many end NODEs, and these NODEs need to recursively construct BET subtrees corresponding to these NODEs by means of the WALK-false-NODE procedure until no end NODEs exist in the BET TREE. The WALK-search process performs a preorder traversal on all NODEs in the BET sub-tree, where the input parameter n is a NODE of the BET, and when a certain tail NODE is traversed, that is, if the conditions of 3 rows or 8 rows are satisfied, the BET sub-tree with the tail vertex included in the tail NODE as an input parameter needs to be constructed by means of the BUILD-summary process, so that the BET tree grows whenever the tail NODE is encountered. The strategy adopted in the whole process is to construct and traverse, so whether the left and right children are tail nodes is judged during further traversal, if so, a BET subtree is constructed, and then traversal is carried out along the root of a new subtree. The father nodes of the tail nodes are all operation nodes, so that the judgment of the 2 nd row is needed. Lines 3-7 handle the case of the left child and lines 8-12 handle the case of the right child.

Lines

5, 6 and 10, 11 add information of the parent node to the root of the new subtree.

Lines

7, 12, 16, 17 perform the typical pre-order traversal function. Rows 13-15 process the smallest tail node, which is traversed last while traversing the new subtree since the smallest tail node is the right child of its parent, which exactly follows the processing order of the tail nodes, i.e., the smallest tail node must be processed last since it is closest to the terminating node, but this is not the same as the execution order. The final BET tree will be executed in left-to-right order, so the parent of the smallest tail node must be found and then the left and right children are swapped. The use of the operation node AND 'can facilitate the realization of the task, AND the 15 lines finally restore the AND' to the AND. When the BUILD-TREE process is completed, the root of the complete BET TREE is returned. If the input parameter G of the BUILD-TREE (G) process is shown in FIG. 1, the BET tree corresponding to the process is formed as shown in FIG. 10.

FIG. 10 shows a process of BET tree formation corresponding to FIG. 1. In fig. 10, (10) the original parallel nodes are replaced by subtrees with gray nodes as tree roots.

Fig. 10 (1) shows the result of line 1 execution in the BUILD-TREE procedure, and then traversing the BET TREE (1) in the order of left-first-right-first traversal, first encountering the parallel vertex 25, and then calling BUILD-SUBTREE to construct the BET SUBTREE of this vertex, the result of which is shown in fig. 7 (7). Then, the new sub-tree is traversed, and if a parallel vertex is encountered, BUILD-SUBTREE is called to construct the BET sub-tree of the vertex, and the process is recursively carried out until no parallel vertex exists in the BET tree. The sequence numbers in FIG. 10 indicate the order of the parallel vertex processing, with the light colored vertices replaced by the BET subtree below. Since the vertex 25 is accessed 2 times AND an ST operation node needs to be added, the AND operator represented by a thick line is the result of the left rotation process. The BET tree formed by the vertex 25 changes from the BET tree shown in fig. 7 (7) to the BET tree shown in fig. 10 (9). The BET tree shown in FIG. 10 (7) has one more operator NODE, which is the result of the initial vertex, and the extra NODE is converted to a null NODE by the DELETE-REDDANCE-NODE process.

If in FIG. 1The vertices 17 and 23 become function vertices, as shown in fig. 3, and the corresponding BET tree is formed as shown in fig. 12. Wherein (1) is the terminating vertex G after line 1 of BUILD-SUBTREE-2 is executed_tThe data structure of the attribute Adj'. (2) The BET TREE is formed after the execution of the process, the TREE root of the TREE is finally assigned to np in the BUILD-TREE process, and then the BET TREE is traversed according to the sequence of traversing from left to right. The BUILD-SUBTREE process is invoked each time a parallel-type vertex is encountered in order to construct a BET sub-tree for that vertex, and this process recurses until there are no parallel-type vertices in the BET tree. The sequence numbers in FIG. 12 indicate the order of the parallel vertex processing, with the light vertex replaced by the BET sub-tree below it. Since

vertices

22, 16, 25 are visited multiple times, it is necessary to add ST operation nodes, the bold line nodes representing nodes containing function vertices and the dashed line nodes representing nodes containing auxiliary relay vertices. (11) Representing the final BET tree formed. Next, the process of forming the BET tree of (9) is described.

FIG. 11 shows the data structure in the Adj' attribute of vertex 25. Wherein, the bold line node represents a node containing a function vertex, and the dotted line node represents a node containing an auxiliary relay vertex. The "+" node represents a parallel merge to the same tail node.

For vertex 25, the data structure of attribute Adj' is shown in fig. 11 after processing by BFS. BUILD-SUBTREE-3 is then called to construct a BET tree for vertex 25. Minimum tail vertex v_tnIs the vertex1, r_tnIs 2. root. Beginning tail vertex v_tFor vertex 16, the condition is true when row 13 is asserted, since VCORL vertices are processed before vertex 25. The right subtree of root is then saved into the buffer' attribute of vertex1, run 20 rows, 18. Line 7 is then executed, tail vertex becomes vertex 13, and by executing lines 12 and 15-17, the tail vertex is continually moved toward the smallest tail vertex and the parallel vertices encountered along the way are merged in series into the temporary BET sub-tree represented by np. Finally, the formed BET tree is saved to the tail vertex v_tIn buffer of (2), the tail vertex v at this time_tIs the smallest tail vertex1. Line 7 is then executed, with the trailing vertex becoming vertex 23, which is processed similarly to vertex 16, except thatIn the row 20, since the buffer' of the minimum tail vertex is not empty, the result needs to be merged with the result of the vertex 16 in parallel to form the left sub-tree shown in fig. 12 (9). Line 7 is then executed, with the tail vertex becoming the smallest tail vertex1, and line 11 is executed to form the BET tree as the left sub-tree of the right child as represented in FIG. 12 (9). Since the condition of 26 is true, the minimum tail vertices are merged into the BET tree in series by line 27, forming the right sub-tree as represented by (9) in FIG. 12. In row 28, the results of buffer' and buffer are combined in parallel to form the BET sub-tree as represented in FIG. 12 (9).

Since the serial vertex in the LDGgraph only has one emitting edge and one incident edge, and the parallel vertices can not be directly connected, there is | V_P|<|V_S+2|, then O (V)_P)＝O(V_S)，O(E)＝O(V_S) Finally, we can get: o (V) ═ O (V + E) ═ O (V)_S)。

Even if we add some auxiliary vertices and auxiliary edge (1) formula, because the number of auxiliary relay vertices does not exceed the number of edges, the number of auxiliary function vertices does not exceed | V_SL. If the sorting procedure in procedure BUILD-SUBTREE-2 is not considered, for the BUILD-TREE procedure, every vertex of graph G is traversed and the tandem vertex is visited only once. The parallel vertex as the tail vertex can be accessed for a plurality of times, but the access times are restricted by the associated edges, so the total access time of the parallel vertex is O (E), and meanwhile, the BET tree for constructing each parallel vertex is only performed once, and the main process of the construction is to replace the parallel vertex by a subtree with a series node as a leaf node, so the total processing time of the parallel vertex is O (V)_P+ E) so that the total treatment time is O (V + E) and, according to equation (1), the treatment time with the BUILD-TREE process is O (V)_S) I.e. the processing time of the process is only linearly related to the number of vertices in the series. If the sorting procedure in the procedure BUILD-SUBTREE-2 is considered, the runtime of the BUILD-TREE procedure is determined by the pair G_tDetermining the sorting time of the tail vertex, wherein the sorting time is O (V)_SlgV_S) Due to O (V)_P)＝O(V_S)。

DELETE-REDUNDANCE-NODE(n)

The DELETE-REDUNDANCE-NODE process performs an early traversal of the BET tree, setting it to a null NODE by

lines

3 and 5 when a redundant NODE is encountered, and ensuring that its left child is not null after the null NODE to facilitate the conversion of the BET tree into an instruction list. In addition to leaf nodes, a node is considered redundant when either the left child or the right child appears to be an empty node. The BET trees in fig. 10(10) and fig. 12(11) are processed by the DELETE-redundancy-NODE process, and the parent NODE of NODE 50 becomes an empty NODE.

The conversion from LDGraph to BET tree is now complete. After the BET tree is obtained, it can be easily converted into various instruction lists, and a method for converting the BET tree into an instruction list conforming to the IEC 61131-3 specification is given below.

OUTPUT(n)

And the OUTPUT process performs middle-order traversal on the BET tree, and OUTPUTs a corresponding instruction code according to the properties of the encountered nodes in the traversal process. When the right subtree is converted, if the right subtree is not an isolated node, brackets are required to be added to the instruction. Lines 7-9 judge the encountered node, if it is a non-isolated right subtree AND the root of the tree is an AND OR operation node, it needs to add right brackets to the subtree, AND the left brackets are already added by the PRINT-intubations process.

PRINT-INSTRUCTIONS(n)

In the PRINT-INSTRUCTIONS process, lines 2-14 perform instruction code conversion on the right subtree root, and lines 16-28 perform instruction code conversion on the left subtree root. The two conversion methods are very similar, except that the conversion to the right subtree root, which is a non-isolated node AND is an operation node AND OR, requires the addition of a left bracket. If the print statement is in the form of "" end "" indicates space but not line feed after completion of printout, and no end symbol indicates line feed after completion of printout. How a function type vertex is then executed lines 7-9 or lines 21-23, EN and ENO representing two buffer addresses for buffering the input and output values of the function vertex, respectively. If the main register is represented by A, ST EN represents that the value of A is put into EN, when the function calling is carried out through the CAL instruction, the sub-process called by the CAL instruction firstly obtains input from EN, then executes the sub-process, and finally stores the operation result in ENO. LD ENO indicates that the value of ENO is put into A, so the logical expression is linked to the sub-process through both buffers EN, EN. If the node is ST type, the vertex name is output, and the name of the vertex is 'ST'. If the node is empty, no printing is performed. If the node is a relay type node, the name of the vertex is directly output.

Fig. 13 is an instruction table, if only one character string appears in one row in the instruction table, as in the case of bold display in the instruction table, an "LD" character string needs to be added before the instruction character string, which is relatively simple and the specific process is not described again. Although the OUTPUT process aims at specific instruction formats, the method has no loss of generality, and the OUTPUT requirements of different instruction lists can be met only by modifying the corresponding instruction formats in the PRINT-INSTRUCTIONS process.

And (4) conclusion:

the introduction of the vertex covering concept enables us to define LDgraph more accurately, thereby more accurately defining the application range of the algorithm of the method. The LDgraph can be converted into a BET tree through 6 processes of an LD-BET algorithm, and vertexes in the LDgraph are classified according to functions and connection relations. Auxiliary vertexes need to be added to the function vertexes to process the non-continuity of the function vertexes, and the termination vertex G_tThe introduction of (2) facilitates the handling of the coil-type vertices. Based on vertex classification, through depth-first search-based algorithmSerially combining the serially connected vertexes on the serially connected branches; and carrying out parallel combination on tail vertexes injected into the parallel vertexes through an algorithm based on breadth-first search. Each parallel vertex may have multiple tail vertices but only one minimum tail vertex, and when the combination of all tail vertices reaches the minimum tail vertex, the parallel combination of the parallel vertices is completed. Parallel combination starting at the terminating vertex G_tAnd the merging result is a BET tree containing parallel nodes, the tree is traversed, and a parallel merging process is called for the encountered parallel nodes, so that the BET tree without the parallel nodes is finally generated. The runtime of the generative BET tree algorithm is O (V)_S) The sorting run time for the output vertices is taken into account by the term O (V)_SlgV_S)。

After the BET tree is formed, the IL can be generated by simply traversing the BET tree, and although the method gives an example of generating an instruction list conforming to the IEC 61131-3 specification, the IL conforming to any specification can be generated according to a similar method. A stack structure is introduced and combined with a subsequent traversal of the generated BET tree, the logical operation result of the BET tree can be directly calculated, and therefore the generation process of an IL table can be skipped for direct calculation in practical application.

FIG. 12 shows a process of BET tree formation corresponding to FIG. 3. (1) The symbol before the middle vertex is for indicating that the vertex is an auxiliary function vertex, and the name of the actual vertex is the name without the wave number, so that the auxiliary prefixes of the auxiliary vertices in the following drawings (1) are all removed. (9) The dotted node in (11) and (11) indicates that the included vertex is an auxiliary relay vertex, and unlike fig. 3 but in accordance with the actual case, the vertex name is not given an auxiliary suffix "'". The bold line nodes indicate that the vertices it contains are function nodes. (11) The original parallel nodes in the tree are replaced by subtrees with gray nodes as tree roots.

Claims

1. the ladder diagram of a processable function vertex is converted into the method for the instruction sequence, it is characterized in that: the LD-BET method adopted comprises six parts, and the first part comprises that the ladder diagram is converted into the algorithm of LDGraph and the verification format and the judgment are whether it is LDGraph, obtain a qualified LDGraph graph G, and read it into graph G; the second part sets the connection attribute connectionType of each vertex in the graph; the third part adds auxiliary vertices to the graph; the fourth part merges the vertices on the series branch, The fifth part merges the series branches injected into the parallel vertices; the sixth part expands each parallel vertices in the BET tree to form a BET tree without parallel vertices; each part consists of one or more processes ; After each step is completed, the vertex color of the graph G must be restored to white; after the LDGraph is converted into a BET tree, the obtained BET data is converted into an instruction table that conforms to the IEC61131-3 specification;

Two objects are used in the adopted LD-BET method, one is the node used to describe the BET tree, and the other is the vertex used to describe the LDGraph; the node object contains the vertex attribute node object through the NODE(vertex) method Create, through the ADD-NODE method, all three nodes become nodes belonging to _NBET ; the vertex object contains name, Adj, Adj', buffer, buffer', root, π, d, color, conntionType, functionType attributes; For vertex v, its adjacency list v.Adj represents a set {Adj ₁ , Adj ₂ ,..., Adj _n }, where Adj _i ∈ V, i=1, 2,...,n; the set represents from v to set There is a directed edge between each element of v.Adj; Adj' is a linked list, used to collect series branches that are injected into parallel vertices, and the parallel merge of series branches should use it; for vertex v, its linked list v .Adj' represents an ordered sequence <Adj' ₁ , Adj' ₂ ,..., Adj' _n >, where Adj' _i ∈N _BET , i=1,2,...,n; There is a series branch of injection v between each element of the sequence, and its arrangement represents the order of injection; respectively applying sets and ordered sequences to the representation of series and parallel nodes will facilitate series and parallel The merge of parallel vertices adopts the breadth-first algorithm, and the structure of the ordered sequence preserves the depth relationship between the vertices; the search of the series vertices adopts the depth-first search, which uses a set with a relatively simple structure to represent that there will be no loss between vertices. Connection relationship information; since series merge and parallel merge are used alternately in the BET tree generation algorithm, these two structures are also used interchangeably;

buffer, buffer' is used to cache the intermediate results when the BET subtree is generated; part of the directed graph is converted into a BET subtree through the processing of the BUILD-SUBTREE algorithm and cached in buffer and buffer', and the two caches also retain The position of the root of the BET subtree in the directed graph; the two caches establish a connection for the graph and tree transformation;

The BET subtree is a branch of the BET tree, and all the BET subtrees will form a BET tree, the vertices of which are the vertices of the functionType=FUNCTION type.

2. a kind of ladder diagram that can process function vertex according to claim 1 is converted into the method for instruction sequence, it is characterized in that: according to connection relation classification, vertex is divided into series type vertex and parallel type vertex; Vertices whose in-degree and out-degree are not greater than 1 are represented by V _S ; parallel vertices: vertices with in-degree greater than 1 or out-degree greater than 1 in the graph, define the connection type according to the out-degree and in-degree of the vertex, except the initial vertex Except for the connection type that needs to be specified, other connection types are automatically obtained, including terminal vertices, and there are multiple terminal vertices; for scalable input applications, any vertex with an out-degree greater than 1 can be used as the initial vertex , which creates conditions for partial reuse of ladder diagrams.

3. a kind of ladder diagram that can process function vertex according to claim 1 is converted into the method for instruction sequence, it is characterized in that: vertex is classified according to function, when functionTyp=FUNCTION, handle vertex except series and parallel type , these vertices have some self-defined calculation and logic functions, the logic operation result of the ladder diagram is used as the input of this type of vertex, and the output of this type of vertex is used as the input of the ladder diagram.