Flow graph

From Wikipedia, the free encyclopedia
  (Redirected from Flowgraph)
Jump to: navigation, search
Not to be confused with Signal-flow graph or Flow network.

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 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.[5] Another type of flow graph commonly used is the call graph, in which nodes correspond to entire subroutines.[6]

The general notion of flow graph has been called program graph,[7] but the same term has also been used to denote just CFGs.[8] Another term used to denote flow graph is rooted directed graph.[9]:308 Flow graphs have also received a number of qualified synonyms (perhaps indented to disambiguate them from CFGs), including unlabeled flowgraphs,[10] 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.[11]

See also[edit]


  1. ^ Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 1372. ISBN 978-1-4398-8018-0. 
  2. ^ 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. 
  3. ^ a b c Horst Zuse (1998). A Framework of Software Measurement. Walter de Gruyter. pp. 32–33. ISBN 978-3-11-080730-1. 
  4. ^ 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. 
  5. ^ 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. 
  6. ^ a b Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7. 
  7. ^ K. Thulasiraman; M. N. S. Swamy (1992). Graphs: Theory and Algorithms. John Wiley & Sons. p. 361. ISBN 978-0-471-51356-8. 
  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. 
  9. ^ 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.  edit
  10. ^ 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. 
  11. ^ Cooper, C. (2008). "Asymptotic Enumeration of Predicate-Junction Flowgraphs". Combinatorics, Probability and Computing 5 (3): 215. doi:10.1017/S0963548300001991.  edit

External links[edit]