Introduction
Directed graphs are free of any restriction, except rigorous enforcement of the rule of transitivity, and the principle “same objects have one and the same meaning”. Causality (cause/effect), temporal ordering (before/after), transactions with two addressees (sender/receiver), control-flow of computer programs, and workflow in general are some examples.
A graph is defined by its objects (nodes, vertices), and relations between two objects (edges, arcs). Objects and relations among them define intrinsically the unique topology (connectedness) and structure (composition) of the respective graph.
We categorize directed graphs in four groups of increasing complexity according to their topology and structure:
- 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 a pair of trees
Proposed is an incremental algorithm which can explicate and encode the topology and structure of a directed graph. The algorithm uses a similar approach to mathematical induction, and its basic procedure is rather trivial:
- Start with an empty graph
- Receive an edge (fact)
- Determine the type of the edge
- Determine the scope of the changes on the graph
- Add the edge to the graph based on its type
- Adjust topological and structural encoding of the graph
- Continue until all edges are processed
General information about directed graphs and details of how each edge is processed will be published in individual chapters. Here is a list of planned chapters:
- Facts
- Transitivity and Paths
- Graphs
- Algorithm
- Guidelines
- Edge Types
- Processing a Tree-Edge (Part 1)
- Processing a Cross-Edge
- Processing a Tree-Edge (Part 2)
- Encoding the Graph