All geek questions in one place

Ensure the smoothness of flowcharts

I have a question: is there any link (e.g. paper) with proof of planarity of flowchart diagrams? Can anyone suggest an algorithm for generating flowcharts of (planar) layouts?

I know that there are some tools for converting code into a block, but I do not know their internal components.

+4
source share
2 answers

I do not agree with Hooked. Flowcharts with some restrictions (using loops is NOT one of them) are flat. Some examples:

  • A single primitive command translates to a flat graph (single node)
  • Operator sequence: if the operators can be translated into flat graphs, the sequence itself can be transferred to a flat graph (just by connecting these subgraphs)
  • Function: same as above
  • A ( repeat-until , while-do , etc.) loop is a sequence of statements that form a loop. Cycles are also great if they are properly nested (and such designs are designed for the right jack).
  • Goto goto ( goto or break / continue / return that can jump) are not ok. If you have a nested loop and inside you jump out of the outer loop, such an edge will clearly intersect the loop (loop, function) that contains it. If the code is translated to exit one loop at a time, that's good too. (This translation is not too different from just introducing nodes to model intersections).

There should be a more systematic way to formally prove that the block diagram obtained from the compositions of a certain set of structures is planar, I would like to think about it after 5 minutes, but no luck :)

update : By the way, goto can trivially create K3.3 or K5, for example, this is K5 (in a good old-fashioned QBasic!):

 00 GOTO (INT(RND * 5) * 10) 10 GOTO (INT(RND * 5) * 10) 20 GOTO (INT(RND * 5) * 10) 30 GOTO (INT(RND * 5) * 10) 40 GOTO (INT(RND * 5) * 10)
+4
source

It depends on what you call a "flow chart." If the flowchart is a simple view, i.e. a directed graph, where no node points up (to a node that you may have previously visited), then what you described is a tree whose nesting in the plane is trivial.

If, however, your block diagram has cycles (cycles), then simply build a counterexample, a graph that does not fit into the plane. For a far-fetched example (since no restrictions were specified), consider the full K5 graph in which each node is connected to all the others. This chart is not flat.

As for drawing graphs, I would recommend the excellent GraphViz tool, which attracts (among other things) beautiful flowcharts with automatic layout. You can choose a rendering engine that tries to preserve some order in your chart, and there is an explicit option for hierarchical charts.

+1
source

Source: https://habr.com/ru/post/1304118/

More articles:


All Articles