programming tree graphs

Programming Tree Graphs
Delphi project

	view Delphi source code listing of the Tree unit.
	download Tree - exerciser program.
	download complete Delphi - 7 project

Introduction

In mathematics a graph is simply a picture with dots.
Each dot may or not may be connected to another dot by a line.
Graph theory is about the properties of graphs.
Graphs are applied in a variety of fields such as

A graph is an abstract picture to define the interdependence of objects or events.
A dot (called node) represents such an event or object.
So, a node will have a list of properties.
A connection between two nodes indicates that transition is possible to the other situation,
or that (properties of) an object depend on other objects in some way.
Below is pictured a so called complete graph, each dot is connected to all other dots by a single line.

If a dot represents a person, then a line may indicate a handshake when people meet at a party.
If the graph is a computer network, then a line may be a direct cable connection.
In a complete graph there are n(n-1)/2 lines in the case of n dots.
To connect 20 computers directly needs 20(19)/2 = 190 cables.
If 20 people meet at a party then 190 pair of hands will be shaken.

Trees

A tree is a special type of graph.
If one connection in a tree is removed, two trees will result that have no commen nodes.
It is no longer possible to "travel" from each node to another.
Another property of a tree is that the route of point A to point B is the same as from B to A :
there are no loops.

Below is an exemple of a tree, possibly known from the theory of chances.

This tree could represent a file system where map A contains four files,
including B with three files including map C containing five files.

This article is about the programming of tree graphs.
It includes the creation of trees and also the changes and undo operations.
The Delphi project has two units:

The purpose is to test operations on trees before the tree structure is applied in a math text editor.
Such an editor is capable of handling roots, fractions, powers, matrices, parentheses...
The dots in the graph are called elements (lines, characters, fractions, roots, matrices, tables...)

Here a graph is pictured with elements A,B,C,D.
A is the parent, B,C,D are descendents (children) of A.
A may be a line of tekst with characters B, C and D.
Left is the math notation, right is the ICT notation known from file systems with maps and files.
In a computer program, an element is a record with a number of fields.
These elements are stored in an array[1.. ] so each element is numbered 1,2,3,......(0 is not an element).
How to program the connections between elements?
For this we have the fields parent , child , next and previous.

type Telement = record
                 parent   : dword;
		     child    : dword;
		     next     : dword;
		     previous : dword;
                .................;//properties , codes, x, y, width, height.....
		    end; 
		   
var element : array[1..500000] of Telement;

Note: dword = cardinal. The number of elements in the edotor is 500.000, the number of characters in a novel.

If the parent field of element[8] has value 2 this means that element[2] is the parent of element[8].
An element has one field to specify a child.
However, an element may have many children. What to do?
This problem is solved by introducing the next field.
In the figure below elements 2,3,4 are children of element[1]

Note: elements 2,3,4 all have element[1] as parent.
This is the same graph as before with elements A,B,C,D.

When programming trees it is very convenient to quickly move along the tree in all directions.
This is facilitated by the field previous.
In the above graph element 3 is the successor of 2. Elements 2 and 3 are successive children of element[1], so

    element[2].next = 3
    element[3].previous = 2

Hereafter I paint an element like this (a missing connection indicates 0)

If element[10] has successive children 20,21,22 then

Application in a math editor

Below is pictured a fraction with numerator and denominator, being part of a line of text.

The text line is a line element with the fraction element as a child.
The numerator and denominator are lines and children of the fraction element.
The numerator line has three children: character elements with codes x, - , 1
the denominator line has children with character codes x, +, 1.

This is the structure, an element

An element has sufficient information to paint itself in a bitmap.
The parent is responsible for the positioning of it's children, relative to itself.
Say, the numerator in the fraction changes from x - 1 to 1, the denominator changes to 2x + 25.
The changing element will report a change to it's parent, which recalculates the position of the children.
Also, the parent has to recalculate it's own dimensions and report changes to it's own parent.
In the above case, the fraction (division) line will grow longer, the 1 in the numerator will be neatly centered.

Summarizing

The next graph represents the fraction

Operations on Trees

The next operations are programmed

insert after	add element after a given element
insert before	add element before a given element
insert child	add child to an element
delete	hide an element
replace	replace an element by a new one, hide the old element
pack	place an element inside the previous element as a child.
undo	cancel the last operation

Insert after

This operation provides for adding elements: typing text, inserting tables, parenthesis, fractions
or the insertion of text lines on a page.

Element E is inserted after element A
Say element A has number a, and so on (B b, C c).
element[a].next is b which has to change to e.
element[b].previous was a, must change to e.
Also the value of fields next and previous of element[e] must be set to b and a.
element[e].parent must be the same as element[a].parent.

Insert before

This operation will mainly be used to insert an element before the first child.

In the picture above B and C are children of A.
Element E is inserted before B.
The next value of element e and previous value of element B have to be adjusted.
Element[a].child becomes e (was b).
Element[e].parent = a.
Note that element[e].previous = 0.

Insert child

This operation adds the first child to an element.

next and previous of element E are 0.

delete

Delete hides an element. The hidden element keeps all it's information.
Only the connection to the main tree is brooken.
This insures that the change can be cancelled later, by an undo operation.
In the picture below element E is deleted, including all it's children C,D,F.

Replace

This operation replaces one element by another.
The replaced element keeps it's information, enabling a later undo.
Replace will be used when the properties of an element change and undo must apply.
In the picture C is an unused element replacing E.

Pack

This operation moves a -next- element to the child position of the previous element.
This previous element will usually just be inserted to become parent of a row of next elements.
Pictured below is a tree with other trees as the result of pack operations.

Undo

An undo operation cancels the previous operation.
Normally, the undo system may remember a limited number of operations.
This number of operations may be cancelled by undo.
undolist : array[1.. ] holds a code for each operation and the number of the element involved.
Table below lists operations together with the cancelling operation

insert after	destroy
insert before	destroy
insert child	destroy
delete	restore
replace	reset
pack	unpack

destroy

The destroy operation permanently removes an element and resets all fields to zero.
The element type is set to free, the element may be used now for new operations.

restore, reset, unpack

These operations needs no further explanation.
Just one: in case of reset the replaced element is destroyed.

The undo domain

Say we save the last 10 operations, so by undo we are able to cancel our last 10 edit steps.
At step 11, we have to free place 10 in the undo array, by shifting elements 2..10 one place up.
Step 1 is lost.
If step 1 was an insert operation (after, before , child) no action is required.
But in the case of a delete or replace the element involved serves no further purpose and must be destroyed.

The Tree exerciser

Programming tree operations, like programming in general, generates many errors.
Before applying the tree structure, extensive testing is required.
Keep in mind, that in a multipage text thousands of elements are involved.
The tree-exerciser provides for testing the programmed tree procedures.
Below is a reduced image of the tree tester.

Element 1 is always at the left-top and cannot be removed.
In the editor it stands for the complete document.
Children are painted right of their parent.
Elements below each other and connected have the same parent.
Just one connection line is painted, which stands for both next - previous or
parent - child connections.
One element in the tree is marked. (colored yellow).
Operations are performed on this marked element.
An element is marked by a mouseclick.

In addition to the mentioned operations we notice several buttons:

init

To set all elements to zero and clear also the undo-array.
(place is reserved for 50 elements and 25 undo steps)

purge

Shifts the undo stack one place up, purging operation [1]. See before "undo domain".

destroy

Sets an element to zero, eliminating it for further use.
This operation will seldom be applied directly. It will be mainly the result of an undo or undo-stack-purge.

scan

Pressing the scan button calls function scanElement( ) which returns a new element in the tree as a result of
the currently marked element and the previous move direction.
Using scanElement it is easy to move through the tree in a certain direction.
This function is used to paint the tree and also to destroy part of the tree.

type TTreemove = (tmNone,tmParent,tmChild,tmNext,tmPrevious);

function ScanElement(var elmnt : dword; tm : TTreeMove) : TTreeMove;

tm is the last move in the tree.
Use tm = tmChild to start moving forward in a tree.
Calling scanElement subsequently using the result as the new value for tm,
moves the marker to the end of the tree and back to element[1] automatically.

Link

An entry of the undolist has a field called bwlink of boolean.
Linking unites multiple undo commands to act as one.
A linked undo operation may cancel a number of operations.
Say operations 10,11,12 are linked (these elements were once inserted all at one time).
undolist entries 11 and 12 will have the bwlink flag = true. In the case of an undo, first 12, then 11 will be cancelled.
Entry 10 has no link flag set, so this is the last undo operation.

Overview elements

Pressing this button displays all 50 elements with their values.
Active elements are painted in black, deleted elements are red and free elements are green.

Below I list all fields of an element as defined for this tester project.

const maxelement = 50;
      maxaction  = 25;  //undo actions
	  
type TElmntAction = (eaNone,eaInsertA,eaInsertB,eaDelete,eaReplace,
                     eaAddChild,eaPack);
     TElementStatus = (esFree,esDeleted,esActive);
     TElementtype = (elFree,elActive);
     TElement = record
                 eltype : TElementType;
                 marked : boolean;
                 x,y    : word;
                 parent : dword;
                 child  : dword;
                 next   : dword;
                 previous : dword
                end;
      TEditAction = record
                     elmnt  : dword;
                     action : TelmntAction;
                     bwlink : boolean;   //backward link
                    end;

var element : array[1..maxelement] of TElement;
    undolist : array[1..maxaction] of TEditAction;
    lastAction : word;
    freeElementcount : dword = 0;

For further details please refer to the source code listing or the complete Delphi-7 project.
(see top of page)