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]

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]

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.
^ Norman Elliott Fenton; Gillian A. Hill (1993). Systems Construction and Analysis: A Mathematical and Logical Framework. McGraw-Hill. p. 319. 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.

This computer science article is a stub. You can help Wikipedia by expanding it.

[GrossYellen2013-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.

[FentonHill1993-2] Norman Elliott Fenton; Gillian A. Hill (1993). Systems Construction and Analysis: A Mathematical and Logical Framework. McGraw-Hill. p. 319. ISBN 978-0-07-707431-9.

[Zuse1998-3] Horst Zuse (1998). A Framework of Software Measurement. Walter de Gruyter. pp. 32–33. ISBN 978-3-11-080730-1.

[SamarooThompson2010-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.

[TarrWolf2011-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.

[Jalote1997-6] Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7.

[BeinekeWilson1997-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

See also

References