Flow graph
In computer science, a flow graph (also spelled flowgraph) is a directed graph with a distinguished root node that can reach every vertex.[1] Sometimes an additional restriction is added specifying that a flow graph must have a single exit (sink) vertex as well.[2]: 319
A flow graph is essentially an abstraction obtained from the notion of flow chart, with the non-structural elements (like node contents and types) removed.[3][4]
Perhaps the best know sub-class of flow graphs are control flow graphs (CFG), used in compilers and program analysis. An arbitrary flow graph may converted to a CFG by performing an edge contraction on every edge whose source node has outdegree 1 and whose target node has indegree 1.[5] Another type of flow graph commonly used is the call graph, in which nodes correspond to entire subroutines.[6]
Flow graphs have also received a number of qualified synonyms (perhaps indented to disambiguate them from CFGs), including unlabeled flowgraphs,[7] and proper flowgraphs.[3] Flow graphs (rather than CFGs) are sometimes used in software testing.[3][6]
When enriched with the single-exit property, flow graphs have two properties not shared with directed graphs in general. Flow graphs can be nested, which is the equivalent of a subroutine call (although there is no notion of passing parameters), and flow graphs can also be sequenced, which is the equivalent of sequential execution of two pieces of code.[2]: 323 Prime flow graphs are defined as flow graphs that cannot be decomposed via nesting or sequencing using a chosen pattern of subgraphs, for example the primitives of structured programming.[2]: 339 Theoretical research has been done on determining, for example, the proportion of prime flow graphs given a chosen set of graphs.[8]
See also
References
- ^ Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 1372. ISBN 978-1-4398-8018-0.
- ^ a b c Norman Elliott Fenton; Gillian A. Hill (1993). Systems Construction and Analysis: A Mathematical and Logical Framework. McGraw-Hill. ISBN 978-0-07-707431-9.
- ^ a b c Horst Zuse (1998). A Framework of Software Measurement. Walter de Gruyter. pp. 32–33. ISBN 978-3-11-080730-1.
- ^ Angelina Samaroo; Geoff Thompson; Peter Williams (2010). Software Testing: An ISTQB-ISEB Foundation Guide. BCS, The Chartered Institute. p. 108. ISBN 978-1-906124-76-2.
- ^ Peri L. Tarr; Alexander L. Wolf (2011). Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. p. 58. ISBN 978-3-642-19823-6.
- ^ a b Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7.
- ^ Lowell W. Beineke; Robin J. Wilson (1997). Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics. Clarendon Press. p. 237. ISBN 978-0-19-851497-8.
- ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1017/S0963548300001991, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1017/S0963548300001991instead.
 | This computer science article is a stub. You can help Wikipedia by expanding it. |
 | This article has not been added to any content categories. Please help out by adding categories to it so that it can be listed with similar articles, in addition to a stub category. (July 2014) |