Reduced Graphs
Chapters > Graphs
Nodes which have more than one predecessor are targets of more than one path, like node
Bob in the picture. Now node Bob is also head of the new edge (Neil,Bob). Obviously, using the new edge we can prove the legitimacy of the edge (Joan,Bob) which then would become redundant. Therefore, removing the particular edge (Joan,Bob) does not affect the topology of the graph. After the change, the graph becomes list-structured as shown.
Bob in the picture. Now node Bob is also head of the new edge (Neil,Bob). Obviously, using the new edge we can prove the legitimacy of the edge (Joan,Bob) which then would become redundant. Therefore, removing the particular edge (Joan,Bob) does not affect the topology of the graph. After the change, the graph becomes list-structured as shown.
Whenever a new edge is introduced, the algorithm checks whether any known edges became redundant. If so the redundant edges are removed from the graph.
But there are times when we would like to keep the redundant edges for the sake of 
expressiveness. An example is an if-then-clause in a control-flow graph of a computer program: "A; if T then B; C;".
The reduction of the graph would eliminate the explicit jump over the statement B (represented by the dashed edge in the picture). The resulting graph would contain the edges; {(A,T), (A,B), (A,C), (T,B), (T,C), (B,C)}.
expressiveness. An example is an if-then-clause in a control-flow graph of a computer program: "A; if T then B; C;".The reduction of the graph would eliminate the explicit jump over the statement B (represented by the dashed edge in the picture). The resulting graph would contain the edges; {(A,T), (A,B), (A,C), (T,B), (T,C), (B,C)}.
On the other hand, modelling the clause using an edge-oriented graph would explicitly show
the edge (T,C). It would contain the edges {(AT,TC), (AT,TB), (TB,BC)}. The edge-orientation allows us to represent all paths through the graph as {[A, T, C], [A, T, B, C]} instead of the only path [A, T, B, C] would otherwise be possible.
the edge (T,C). It would contain the edges {(AT,TC), (AT,TB), (TB,BC)}. The edge-orientation allows us to represent all paths through the graph as {[A, T, C], [A, T, B, C]} instead of the only path [A, T, B, C] would otherwise be possible.
Controlling the redundancy of existing edges, and their removal if necessary, are both constant time operations. The operation must be repeated for each predecessor of the head of the new edge, though.