What is a flow in a graph? What is a cut? How do they relate? Describe some ideas around these two concepts.
A control flow graph (CFG) is a visual representation of the various paths the code of a computer program can take. A CFG is comprised of a series of symbols, called nodes, that are connected by arrows showing the route that each one can take to the next node. Each node represents a significant line or lines of programming code. There are several ways to render a CFG, but they are all generally read in the same way. In appearance, a control flow graph is not unlike a flowchart.
One of the primary purposes of creating a control flow graph is to discover whether there are parts of a computer program that are unnecessary. This can be achieved easily when looking at the control flow diagram. Any node that does not have an arrow connecting it to the rest of the nodes can be removed.
Another purpose a control flow graph serves is to help isolate problems such as infinite loops, where program execution does not move beyond a single node. Each arrow on the diagram shows what condition must be met to move to the node to which it points, so situations where that condition is never met can be spotted, because it causes the program to cycle back to the previous node over and over.
Finally, a control flow graph can help to create a program dependence graph. This type of graph shows what areas of a program are reliant on other parts. In computer science, this is used to establish an evaluation order to ensure that program code is executing in the correct sequence.
The visual nature of a control flow graph is one of the features that can make it potentially invaluable. Pieces of code that are never directly called or accessed will be fairly obvious, because there will either be no arrows linking it to the main program or the conditions will show that they can never be met to reach the code. There are computer programs that can automatically generate a control flow graph based on a series of source code files, further simplifying the process.
A control flow graph can be represented in any number of ways and, therefore, might appear differently depending on who has produced it. Some graphs use circles or squares exclusively to represent nodes while others use the same shapes as a standard flowchart . Although they are read in the exact same way, the method chosen is purely personal preference.
