Guidelines
Chapters > Algorithm
The objective of the algorithm is to explicate and encode the topology and structure of the underlying directed graph.
The algorithm uses an incremental approach. Starting with an empty graph, edges are processed one at a time. There are no restrictions as far as the order of insertions is concerned.
We will use mathematical induction to prove the correctness of the algorithm.
After inserting an initial edge (A,B), all four lists will be initialized to [A, B]. According to the rules given in the Lists, A and B are obviously connected. The pre-, and post-domination trees show that the only sub-graph of the graph is itself, with an Entry A, and a Target B. A pre-dominates B, and B post-dominates A.
In the subsequent chapters, a proof will be presented to demonstrate the accurate encoding of the topology and structure of the graph.
