||It has been suggested that this article be merged into rooted graph. (Discuss) Proposed since July 2014.|
In computer science, a flow graph (also spelled flowgraph) is a directed graph with a distinguished root node that can reach every vertex. Sometimes an additional restriction is added specifying that a flow graph must have a single exit (sink) vertex as well.:319
Perhaps the best known 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. Another type of flow graph commonly used is the call graph, in which nodes correspond to entire subroutines.
The general notion of flow graph has been called program graph, but the same term has also been used to denote just CFGs. Another term used to denote flow graph is rooted directed graph.:308 Flow graphs have also received a number of qualified synonyms (perhaps indented to disambiguate them from CFGs), including unlabeled flowgraphs, and proper flowgraphs. Flow graphs (rather than CFGs) are sometimes used in software testing.
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.: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.:339 Theoretical research has been done on determining, for example, the proportion of prime flow graphs given a chosen set of graphs.
- Accessible pointed graph — the same notion as used in logic
- Cyclomatic complexity
- Modular decomposition
- Term graph
- Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 1372. ISBN 978-1-4398-8018-0.
- Norman Elliott Fenton; Gillian A. Hill (1993). Systems Construction and Analysis: A Mathematical and Logical Framework. McGraw-Hill. ISBN 978-0-07-707431-9.
- 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.
- Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7.
- K. Thulasiraman; M. N. S. Swamy (1992). Graphs: Theory and Algorithms. John Wiley & Sons. p. 361. ISBN 978-0-471-51356-8.
- Alejandra Cechich; Mario Piattini; Antonio Vallecillo (2003). Component-Based Software Quality: Methods and Techniques. Springer Science & Business Media. p. 105. ISBN 978-3-540-40503-0.
- Chen, Xujin (2004). "An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs". Lecture Notes in Computer Science: 306–317. doi:10.1007/978-3-540-30551-4_28.
- 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.
- Cooper, C. (2008). "Asymptotic Enumeration of Predicate-Junction Flowgraphs". Combinatorics, Probability and Computing 5 (3): 215. doi:10.1017/S0963548300001991.
|This computer science article is a stub. You can help Wikipedia by expanding it.|