1
$\begingroup$

What is a reducible flow graph? sorry if this is a stupid question but I'm having trouble finding an answer.
Also multiple equivalent definitions and some motivation would be nice too.

$\endgroup$
  • 1
    $\begingroup$ Googling "reducible flow graph" seems to give a lot of relevant hits. $\endgroup$ – David Richerby Feb 14 '18 at 18:57
  • $\begingroup$ en.wikipedia.org/wiki/Interval_(graph_theory) $\endgroup$ – D.W. Feb 14 '18 at 19:49
  • $\begingroup$ I've found weird definitions like A flowgraph is reducible when it does not have a strongly connected subgraph with two (or more) entries which I believe should be equivalent to being acyclic??? Or a flowgraph is reducible if Every back edge has its source dominated by its target, for all DFS trees I also don't understand this definition wouldn't every edge have it's source dominated by it's target by definition? $\endgroup$ – Hao S Feb 14 '18 at 23:40
1
$\begingroup$

This blog post summarises the situation well my opinion, but let me go through some of your concerns:

Reducible is NOT equivalent to acyclic: consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with a loop from $z$ to $y$. Then there is an SCC $\{y,z\}$ so it is not acyclic. But it is reducible because the SCC $\{y,z\}$ has a single entry point y. Notice how this corresponds to a program with a while/for loop. On the other hand, if you consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with again a loop $z\rightarrow y$ but also a forward jump $x\rightarrow z$. Not this is not reducible anymore because the SCC $\{y,z\}$ has two entry points: $y$ can be entered from $x$, but $z$ can also be entered from $x$. This intuitively corresponds to a program like that:

x: if <some condition> goto z
y: do { <instruction>
z: }while(<cond condition}
w: end

Notice how there is no way to jump to $z$ without a goto, this is the point of reducibility and it corresponds to well-structured code without goto.

Concerning the back edges, if you take the counter-example for above, notice that there are two different ways to explore this tree in a DFS:

  • from $x$, explore $z$ then $y$ and $w$: in this case the edge $z\rightarrow y$ is part of the spanning tree built by the DFS. But $z$ does not dominate $y$ because the path $x\rightarrow y$ does not go through $z$.
  • from $x$, explore $y$ then $z$ then $w$: in this case the edge $y\rightarrow z$ is part of the spanning tree built by the DFS. But $y$ does not dominate $z$ because the path $x\rightarrow z$ does not go through $y$.

Maybe the source of your confusion is that domination is related to the initial vertex $x$, and not to the DFS. Recall that a vertex $y$ dominates a vertex $z$ if every path from the initial vertex to $z$ goes through $y$.

$\endgroup$
  • $\begingroup$ I'm confused because of when he says A flowgraph is reducible when it does not have a strongly connected subgraph with two (or more) entries Isn't a directed cycle a strongly connected subgraph with more than 2 entries? $\endgroup$ – Hao S Feb 18 '18 at 17:18
  • $\begingroup$ I explained that in my answer: an entry is a node of the SCC which has an edge coming from outside the SCC. $\endgroup$ – Amaury Pouly Feb 18 '18 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.