Editing Control-flow graph (section)

== Loop connectedness ==
The loop connectedness of a CFG is defined with respect to a given [[depth-first search]] tree (DFST) of the CFG. This DFST should be rooted at the start node and cover every node of the CFG.

Edges in the CFG which run from a node to one of its DFST ancestors (including itself) are called back edges.

The loop connectedness is the largest number of back edges found in any cycle-free path of the CFG. In a reducible CFG, the loop connectedness is independent of the DFST chosen.<ref name=":0">{{Cite journal|last1=Kam|first1=John B.|last2=Ullman|first2=Jeffrey D.|date=1976-01-01|title=Global Data Flow Analysis and Iterative Algorithms|journal=Journal of the ACM|volume=23|issue=1|pages=158–171|doi=10.1145/321921.321938|s2cid=162375 |issn=0004-5411|doi-access=free}}</ref><ref>{{Cite web|url=https://www.cs.umb.edu/~offner/files/flow_graph.pdf |archive-url=https://web.archive.org/web/20080725053222/http://www.cs.umb.edu/~offner/files/flow_graph.pdf |archive-date=2008-07-25 |url-status=live|title=Notes on Graph Algorithms Used in Optimizing Compilers|last=Offner|first=Carl|access-date=13 April 2018}}</ref>

Loop connectedness has been used to reason about the time complexity of [[data-flow analysis]].<ref name=":0" />