This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

cs-236:optimizing-rule-evaluation [2017/12/08 09:39] kylej13 [Part 1: strongly connect components] |
cs-236:optimizing-rule-evaluation [2017/12/22 21:21] (current) kylej13 [Rule Grouping and Evaluation Order] |
||
---|---|---|---|

Line 66: | Line 66: | ||

Reversing the edges in step 1 is very direct. Returning to the example from the previous section, the reversed graph as an adjacency list is | Reversing the edges in step 1 is very direct. Returning to the example from the previous section, the reversed graph as an adjacency list is | ||

<code> | <code> | ||

- | Reverse Forest | + | Reverse Dependency Graph |

R0: R1 | R0: R1 | ||

R1: R0,R2 | R1: R0,R2 | ||

Line 73: | Line 73: | ||

R4: R4 | R4: R4 | ||

</code> | </code> | ||

- | The reverse graph is the graph used to compute the topological ordering. It is tempting to compute this ordering on the original forest, and in many cases it works, but such an approach does not work for any arbitrary graph (see section 3.4 of ''[http://www.cs.berkeley.edu/~vazirani/algorithms/chap3.pdf Algorithms]'' for an explanation). It is equally tempting to try to follow the edges backwards on the original graph, but why deal with such added complexity? | + | The reverse graph is the graph used to compute the topological ordering. It is tempting to compute this ordering on the original graph, and in many cases it works, but such an approach does not work for any arbitrary graph (see section 3.4 of ''[http://www.cs.berkeley.edu/~vazirani/algorithms/chap3.pdf Algorithms]'' for an explanation). It is equally tempting to try to follow the edges backwards on the original graph, but why deal with such added complexity? |

The topological ordering is computed by looping through each vertex in the graph and performing a depth-first search starting from that vertex if it has not already been visited in a previous search. During post-order traversal, push each vertex onto a stack when the depth-first search ''leaves'' the vertex after visiting it. The topological ordering is based on the order of the vertices in the stack after all nodes have been visited. Be sure that the vertices are looped through in the same order that the rules appear in the Datalog program. For the example, the topological ordering, having started the depth-first search from vertex ''R0'' is | The topological ordering is computed by looping through each vertex in the graph and performing a depth-first search starting from that vertex if it has not already been visited in a previous search. During post-order traversal, push each vertex onto a stack when the depth-first search ''leaves'' the vertex after visiting it. The topological ordering is based on the order of the vertices in the stack after all nodes have been visited. Be sure that the vertices are looped through in the same order that the rules appear in the Datalog program. For the example, the topological ordering, having started the depth-first search from vertex ''R0'' is | ||

Line 84: | Line 84: | ||

</code> | </code> | ||

- | The last step to compute SCCs starts a depth-first search from the greatest post-order traversal number (POTN) to the least POTN on the ''original graph.'' In the view of a stack, that is the top of the stack to the bottom of the stack. Any vertex visited in the search belongs to the same SCC. The process is repeated until everything is visited in the graph. For the running example, the first depth-first search is started from vertex ''R3'' to create the SCC of ''{R3}''. The ''R3'' vertex is removed from the stack. ''R4'' is now the top, the depth-first search creates the SCC ''{R4}'', and it is then removed from the stack as well. ''R0'' is now the top of the stack, so a depth-first search is started at ''R0''. '''The depth-first search must not reset the visited information between searches.''' The visited information is what prevents the search from moving into another already completed SCC. The second depth-first search from ''R0'' yields the SCC ''{R0, R1, R2}''. The vertex is popped from the stack leaving ''R1'' on top. ''R1'' has already been visited so it is popped. The same is true for ''R2''. If you printed out the strongly connected components in the order you discovered them it would look like: | + | The last step to compute SCCs starts a depth-first search from the greatest post-order traversal number (POTN) to the least POTN on the ''original graph''. In the view of a stack, that is the top of the stack to the bottom of the stack. The process is repeated until everything is visited in the graph. This produces a DFS forest where each tree represents one SCC. For the running example, the first depth-first search is started from vertex ''R3'' to create the SCC of ''{R3}''. The ''R3'' vertex is removed from the stack. ''R4'' is now the top, the depth-first search creates the SCC ''{R4}'', and it is then removed from the stack as well. ''R0'' is now the top of the stack, so a depth-first search is started at ''R0''. '''The depth-first search must not reset the visited information between searches.''' The visited information is what prevents the search from moving into another already completed SCC. The second depth-first search from ''R0'' yields the SCC ''{R0, R1, R2}''. The vertex is popped from the stack leaving ''R1'' on top. ''R1'' has already been visited so it is popped. The same is true for ''R2''. If you printed out the strongly connected components in the order you discovered them it would look like: |

<code> | <code> | ||

Strongly Connected Components: | Strongly Connected Components: |