## Form of a Graph

Chapters > Graphs

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.