Form of a Graph
Chapters > Graphs
Graphs exist in uncountable forms. No two graphs are the same unless they are cloned.
A graph always starts as an empty one. It grows edge by edge like a swarm. With each new edge, it changes its topology, possibly its structure, and definitely its form. After all, it is the topology who determines the form, and not the form determines the topology.
No matter what the form of a graph looks like, it comes always in one of the flavors we mentioned in the Introduction, namely:
- Lists whose topology is represented by themselves
- Trees whose topology is represented by a pair of lists
- Well-nested Graphs whose topology is represented as if they are trees
- Ill-nested Graphs whose topology is represented by two pairs of lists
The structure is represented by the pre-dominator and post-dominator trees of the graph, which are based on the Single-Entry-Single-Target paradigm. Consequently
- The target of a sub-graph is the post-dominator of the entry, and it is not part of the sub-graph.
- The constituents of a sub-graph are its entry node, and all the nodes that are pre-dominated by the entry. All nodes must also be post-dominated by the target of the sub-graph, too.
- Two sub-graphs are either disjoint, or one completely includes the other. They cannot overlap each other.
- A node belongs to one and only one sub-graph.
If at least one sub-graph is ill-nested, the whole graph is categorized as ill-nested. The category of one sub-graph does not affect the category of another, unless they are nested.
The category of a graph can only be discovered if its topology is elaborated. The next edge can change the topology of the graph completely. Therefore, we will encode any graph using two pairs of lists. In case a graph is categorized besides being ill-nested, the pairs will be identical.