1. Preliminaries and Concepts
A head vector is a graph description consisting of a list of n non-negative integer numbers a_1 a_2 ... a_n where the i-th number indicates the parent (the head) of the i-th node. A head vector usually contains 0 elements to indicate nodes with no parent. For example, in
(1) head of node: 0 1 2 3 4 5 6 7 8
index of node: 1 2 3 4 5 6 7 8 9
the first node has no parent (no head), the second vertex has as parent the first vertex, the third vertex's parent is the second vertex, and so on. The head vector above describes a graph path of 9 vertices. Needless to say that the actual head vector are the numbers in the first line 0 1 2 3 4 5 6 7 8. By replacing some parents with a few zeros we describe a forest. The following example describes a forest of three 3-vertex graph paths:
(2) head of node: 0 1 2 0 4 5 0 7 8
index of node: 1 2 3 4 5 6 7 8 9
If we do not use zeros, we can describe cycles. The following describes a 4-vertex cycle
(3) head of node: 2 3 4 1
index of node: 1 2 3 4
Simply enough, by Edge list we refer to the list of pairs of connected edges in our graph. The list of edges of each of the graphs described above are:
(1) {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {7,8}, {8,9}
(2) {1,2}, {2,3}, {4,5}, {5,6}, {7,8}, {8,9}
(3) {1,2}, {2,3}, {3,4}, {4,1}
In this Ipelet, you can write an edge list as a sequence of integer numbers separated by an arbitrary amount of spaces, commas, and even by the character |. The Ipelet will get rid of those for you.
Informally, a linear arrangement describes the position of each vertex of a graph along a horizontal line. In more formal words, a linear arrangement is a function that maps every vertex to a natural number. For example, with the following linear arrangement
vertex | position
1 - 4
2 - 3
3 - 1
4 - 2
we place vertex 1 at position 4, vertex 2 at position 1, and so on. In a horizontal line, this looks like this
vertex: 3 4 2 1
position: 1 2 3 4
Inverse linear arrangements tell what vertex each position has. These are the other, more intuitive side of the same coin. An inverse linear arrangement simply acts as the opposite of a linear arrangement: it gives us, for every position, what vertex there is in that position. For the linear arrangement given above, its inverse is
position | vertex
1 - 3
2 - 4
3 - 2
4 - 1
Linear arrangements (and also inverse linear arrangements), simplify our task in arranging the vertices of a graph. For example, given the head vector
head of node: 0 1 1 1 1
index of node: 1 2 3 4 5
the ipelet will draw vertex 1 at position 1. If we wanted vertex 1 to be placed at position 3 (and we don't care about the others), we could modify the head vector like
head of node: 3 3 0 3 3
index of node: 1 2 3 4 5
However, given the original head vector
head of node: 0 1 1 1 1
index of node: 1 2 3 4 5
and the arrangement 3 1 2 4 5, vertices will be mapped every vertex to the indicated positions:
vertex | position
1 - 3
2 - 1
3 - 2
4 - 4
5 - 5
which is what we wanted.
