الگوریتم اکتشافی برای رسم نمودار جریان

A flow diagram is a graphical presentation of an energy or chemical system with its components and their interconnections through mass and energy streams. An automatic drawing algorithm of flow diagrams has been developed and presented in this article. It heuristically imitates all the procedures carried out by a designer, starting with his conceptual understanding of the system's topological structure and finishing with graphically representing the system on the paper or screen. The topological structure of the system is given as input in the form of digraph. As a first step, it is transformed to a planar digraph by introducing new vertices representing crossings between the various streams. The near-optimum (smallest) number of crossings is determined heuristically. Then the flow diagram is drawn on the screen using special mechanical engineering symbols for the components of the system. Horizontal and vertical lines represent streams of mass or energy, identified by different colors. Unnecessary expansion of the drawing area is avoided by the application of linear and integer-linear programming algorithms.

One significant task during the design of a system is to create a picture that shows the structure of the system, i.e. the components and their interconnections. In the case of a thermal system (power plant, cogeneration system, refrigeration unit, etc.), this picture is given by the flow diagram. The designer's conceptual work is drawn on paper or on screen, either manually or with the aid of computer aided design software (CAD). This process is tedious and time consuming, more so if several alternative solutions (diagrams) have to be drawn for evaluation, comparison and final selection. It would be of great help to the designer if his conceptual work could be automatically transformed to a diagram with the aid of an appropriate software tool. One approach to encounter the problem of automatic design is through expert systems. A good example of a ruled-based expert system in architectural design is found in Ref. [10]. Our approach comes under the field of intelligent CAD. An algorithm for such a purpose has been developed and presented in the following. It makes use of the theory of planar digraphs [1], [2], [4] and [5]. A plane digraph is a digraph with no crossings between edges. A digraph, which can be transformed to a plane digraph, is called planar digraph. The algorithm has been developed in C++ using various data structure algorithms, including data structures for digraph representation [6], [7], [8] and [9]. The input to the algorithm is a digraph representing the topological structure of the system. The algorithm is heuristic and it implements the steps that a designer follows, in order to draw not only a correct but also an aesthetically acceptable diagram. Speaking rigorously, a heuristic algorithm is a decision tree searching method, which takes advantage of expert's information about searching priorities [3] and [14]. In the algorithm, the search stops when the first correct and aesthetically acceptable diagram is found. It doesn't attempt to find a better one by searching further. In this way, the execution time is significantly reduced. However, the algorithm may be easily extended to a truly heuristic algorithm, if an appropriate heuristic function is defined, which determines a numerical value for the produced diagram quantifying the aesthetic result, even though this may be subjective. Two of the main characteristics of the algorithm are the following: (i) it heuristically finds the near optimum (smallest) number of crossings between streams, and (ii) it avoids the unnecessary expansion of the drawing area. The algorithm is based on the appropriate transformation of the problem to: an integer linear programming (ILP) problem, which is solved by the Branch and Bound method [12] and [13]; and to a linear programming (LP) problem, which is solved by the Simplex method [11], [12] and [13]. The following analysis refers to flow diagrams of thermal systems. However, it can be easily extended to diagrams of other engineering systems such as electrical, electronics, water piping, etc. 2. The main parts of the algorithm A key idea of the algorithm is to imitate all the procedures carried out by a good designer. For this purpose, the procedure followed by a designer is divided into steps, which then are translated into mathematical and computer science language. The first level of this division consists of three subproblems, which the designer should solve sequentially. These are the following: Problem 1 (modification of the topology). Given the topological structure of the system as a digraph, transform it to a digraph with an equivalent flow information with each vertex having degree ≤4. Check if this digraph is planar. If it is not, force it to be planar by heuristically introducing a near-optimum (smallest) number of new vertices representing crossings between edges. Transform the planar digraph to a plane digraph and identify the regions, the angles and the new introduced edges/vertices of the final plane digraph. A well-known “planarity testing algorithm” [1] (it tests if a graph is planar or not) is extended here, in order not to stop if it detects that the digraph is not planar, but to continue and gradually transform it to planar by introducing new crossing vertices. Problem 2 (identification of the geometry). Given the output plane digraph of Problem 1, with crossings, properly assign integer values 1, 2 or 3 to angles. These values express its size in multiples of the right angle, in such a way that it is possible for the produced digraph to fit on a hidden, uniform, orthonormal square grid. In order for the procedure above to be feasible, probably some edges will be recursively divided in two successive edges with a new vertex between them and two new angles will be produced. The assignment of the integer values to all angles and the decisions about which edges will recursively be divided must lead to a new digraph with the minimum possible number of edges (or, equivalently, the minimum number of edge divisions). Then, the length of all the edges is adjusted in order to fit the digraph on a hidden, uniform, orthonormal square grid to avoid unnecessary expansion of the drawing area. This procedure will assign integer numbers to edges, which will express their lengths as multiples of the length of the edge of the unit square of the hidden, uniform, orthonormal square grid. Also, in a similar way, integer coordinates are assigned to vertices. Problem 3 (engineering drawing). The correspondence between the components of the input digraph (vertices and edges) and the components of the thermal system is given. The rules for drawing the flow diagram are specified and implemented. Using the aforementioned and the results of Problem 2, the flow diagram is drawn on the screen.

In this article, a heuristic algorithm for drawing flow diagrams of engineering systems using as input only the topological structure of the system has been presented. The main focus on the design of the algorithm was given in the minimization of the execution time, whereas the clarity of a legible produced flow diagram has been also a strong criterion on designing the algorithmic substeps. Short execution time is essential for system synthesis interactive software, where several alternative flow diagrams must be considered for comparison, evaluation and decision making. However, if one is willing to sacrifice execution time in order to gain clarity or more readability of the resulted flow diagrams, one can modify or append certain steps in the algorithm. Terms such as “clear” or “fine” or “readable” flow diagram do not have a strict and rigorous definition, because subjective criteria are often involved. However, almost all mechanical engineers can distinguish between a fine as opposed to a messy presentation of an energy-system flow diagram. The development cycle followed at this heuristic algorithm, which is also a general development cycle for possible extensions of it, is as follows. Step 1. Consider and implement a set of engineering drawing rules. Step 2. Inspect many of the resulting flow diagrams. Step 3. If the results are acceptable (fine, not messy flow diagrams), then go to Step 4. Else update and implement a new set of engineering drawing rules in order to produce acceptable results and go to Step 2. Step 4. Finish. Two examples of how one can modify and extend the algorithm (sacrificing execution time) are given below. In the first example a rule of readability is considered, which is expressed as “if a given step cause less line segments (edges) in the final diagram compared with an alternative step, then prefer it”. A mathematically rigorous method for minimization of number of edges, presented in Appendix A, may be preferred instead of a heuristic (but faster) one presented in 5.1 and 5.2. The second example is as follows. Until now we have considered crossing vertices as artificial components of the system and so we have manipulated boundary hyperedges independently on whether they connect real or artificial components. Consider a stream pipe connecting two system component vertices A and B and that in its way from A to B passes through crossings. This stream pipe is represented by more than one boundary hyperedges. Consider also that the geometrical coordinates of A and B are XA,YA and XB,YB, respectively. An engineering drawing rule may be defined that the whole stream pipe connecting A and B be entirely embedded inside the parallelogram having as two opposite vertices the (XA,YA) and (XB,YB). This rule is not included in our algorithm and the adjustment of such stream pipes to be entirely embedded inside the above parallelogram, if possible, may be included as a final regulation step. In conclusion, this article not only presents a complete heuristic algorithm for drawing energy-system flow diagrams, but also, by considering the previous discussion, it can serve as a guideline for producing alternative heuristics, closer to other engineers feeling about the meaning of the term “fine flow diagram”. Applications of this algorithm or of variations of the algorithm may be utilized as tools for the presentation of engineering systems including mechanical, electronics, electrical, etc., during all the stages of the design and evaluation of system alternatives.