IntroductionIn mathematics a graph is a picture of dots (also called node), which may be interconnected by lines.
Each dot (node) represents a situation or object.
An interconnecting line indicates a dependency between the dots or a transition.
Graph theory is about the properties of graphs.
Graphs are applied in a variety of fields such as
TreesA tree is just a type of graph.
Common properties of tree graphs are
This tree could represent a file system where map A contains four files,
including map B with three files including map C containing five files.
This article is about the programming of tree graphs.
It includes creation, modifications and also undo operations.
The Delphi-7 project has three units:
- buttons for creation and modification of the tree
3 : tree unit with all data structures, procedures and functions.
Form1, Unit1 allow testing of the tree procedures.
The data unit is only there to isolate the custom data from the tree properties.
Here a graph is pictured with elements A,B,C,D.
A is called the parent. B,C,D are descendents (children) of A.
B,C,D are dependent on A in some way.
A may be a line of tekst with characters B, C and D.
Left is the math notation, right is the ICT notation known also from file systems.
Data structuresThe tree is defined by an array, where each entry represents a node .
To define connections of a node with other nodes we need the properties
- child : the descendant
It is inconvenient to define an array per node with an entry for each child.
A better solution is to add a property next to each node to point to the next child of the parent.
To ease backward navigation between nodes, also a field previous is added to each node.
const maxelement = 50; type TLinks = record parent : dword; child : dword; next : dword; previous : dword; end; var Links : array[1..maxelement] of TLinks;This does not include application data, which is defined in the data unit.
For the sake of demonstration this simple data is choosen:
type TElement = record x : word; y : word; end; var Element : array[1..maxelement] of TElement;In reality, much more data will be defined such as codes, fonts, colors, screen position etc.
Each node has a number : it's entry in both the arrays TLinks and TElement.
So, the connections of node 23 to other nodes are found in Links,
the data of this node is found in Element.
Note, that the first element in the tree is 1.
Therefore, if a node does not have a parent, child, next or previous node, this is indicated by the value 0.
Below is pictured an element (node) and it's connections:
So, the parent field of nodes 2,3,4 will all be 1.
The next field of nodes 4,6,8,10 will be 0.
The previous field of nodes 1,2,5,7,9 will be 0.
Application in a math editorMath editors are more complicated than plain text editors because of fractions, roots and other special symbols.
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.
The tree structure allows for automatic alignment of text:
if the numerator length changes, the denominator position is changed to align with the numerator.
The next graph represents the fraction
Operations on Trees
Element statusThe status of an element is stored in bit positions 24..31 of the parent field.
type TElementStatus = (esFree,esActive,esDeleted,esReplaced,esUnpacked);
esActive : element is part of tree
esDeleted : element is deleted, will be activated again by undo
esReplaced : element was replaced by other element
esUnpacked: element is deleted parent
markMarking an element is not part of the tree operations, but only a function of the exerciser.
The links of the marked element are displayed at the left bottom of the screen.
Place after, Place before
procedure PlaceA(del,sel : dword);//place free element sel after del procedure PlaceB(del,sel : dword);//place free element sel before delThis operation provides for adding elements: typing text, inserting tables, parenthesis, fractions
or the insertion of text lines on a page.
Place before: Element 4 is placed before element 3.
Place Child after, place Child before
procedure PlaceChildA(del,sel : dword);//place free element sel as last child of del procedure PlaceChildB(del,sel : dword);//place free element sel as first child of delThis operation adds a new child to an element.
The child's position is either as the first or the last.
The operations are identical if the element has no children yet.
Element 5 is inserted as the first child of element 1.
Element 5 is inserted as the last child of element 1.
Move element after , before
procedure moveElA(del,sel : dword);//move active element sel after del procedure moveElB(del,sel : dword);//move active element sel after delThis operation removes element sel from the tree and inserts it after ( before) element del.
procedure ReplaceEL(del,sel : dword);//replace element del by sel //sel must be free element //del is part of treeReplace an element by a new element. Element 2 is replaced by element 4.
procedure packEl(del,sel : dword);//free element sel becomes parent of delMake an element the child of a new element.
Element 2 becomes the child of element 4
procedure unpackEl(sel : dword);//remove active element sel, children not deletedRemove the parent of an element.
Element 2 as parent of elements 4,5 is removed.
procedure deleteEL(del : dword);//delete element del, do not delete childrenThe selected element is removed from the tree, together with it's children.
Using the exerciser
For operations PlaceA, PlaceB, PlaceChildA, PlaceChildB, Replace, Pack, UnPack, Delete:
Press left mousebutton and hold.
Move element to destination, placing left top inside destination element.
Release left mousebutton.
The Undo systemEach operation is stored in a stack structure with entries:
const maxUndo = 25; .... type TLinkType = (ltNone,ltParent,ltChild,ltNext,ltPrevious); TELaction = (eaPlaceA,eaPlaceB,eaPlaceChildA,eaPlaceChildB,eaReplace, eaDelete,eaMoveA,eaMoveB,eaMoveChildA,eaMoveChildB, eaPack,eaUnpack,eaUndo,eaNone); TEditAction = record action : TELaction; elmnt : dword; //element linkEl : dword; //link element linktype: TLinkType; cc : dword; //child count bwlink : boolean; //backward link end; ......... var startflag,linkflag : boolean; UndoStack : array[1..maxundo] of TEditAction;Fields are:
elmnt : the element number on which action was performed
linkEl : element number on which elmnt was linked or which elmnt replaced
linkType : type of link, ltPrevious or ltParent
cc : child count, in case of UnPack operation
bwlink : flag indicating that operation is linked to earlier action.
Constant maxUndo is the maximum number of operations saved to be backed up.
To Undo the last operation
procedure UndoAction;To clear the Undo stack, removing all stored Undo data:
procedure purgeUndoStack;To link the next operation(s), Undoing them together at a later time:
procedure startLinking;To stop linking operations, undoing them separately later:
procedure stoplinking;Getting the saved Undo data in the stack:
function getstackdata(n : word) : TEditAction;
LinkingIn reality, an edit action may involve several basic tree operations.
An Undo operation has to include all operations that belong together.
Therefore the bwlink flag may be set, to link an entry in the Undo Stack to the previous entry.
procedure startlinking sets the startflag and clears the linkflag.
procedure registerAction pushes the undo information to the stack and than copies the startflag in the linkflag.
The next operations are now registered with bwlink := linkflag, so are linked to the earlier operation.
procedure stoplinking clears the startflag and the linkflag.
Destroying elementsDeleted or replaced elements are saved with their links and properties, because an undo operation
may make them active again.
There is no public procedure to free (destroy) an element directly.
However, if the UndoStack is full and another edit operation takes pace on the tree,
then the stack has to shift up which purges entry 1.
If this entry stored a deleted, replaced or unpacked element, it is impossible to put
this element into action again because it is outside the range of Undo.
Therefore this element is destroyed, giving it the free status so it may be used by future operations.
InitializationAt the beginning, the tree has to be initialized:
procedure initTree;This clears all links and sets Links to active.
Links may not be deleted, it is always the start (top) of the tree.
In the data unit:
procedure initTreeData;Clears all data fields in array Element[ ]
New elements added to the tree must be free.
To get the number of a free element:
function getFreeEl(var el : dword) : boolean;//return free element number el //return true if Ok, false if out of elements
function ParentEl(var nel : dword) : boolean; function ChildEl(var nel : dword) : boolean; function NextEl(var nel : dword) : boolean; function previousEl(var nel : dword) : boolean;The parent, child, next or previous element of nel is returned.
If no such element is present, nel is not changed and a false result is generated.
function ScanElement(var elmnt : dword; lt : TLinkType) : TLinktype;From element elmnt the next element is returned depending on the link type lt.
The purpose of this function is to step through the elements in a systematical way:
it = ltChild,
it = ltNext : search for child, than next, than previous, than parent
it = ltPrevious: search for previous, than parent
Successive calls to this function first addresses all children, then the next elements.
The elements are adressed twice: during the forward and during backward scan.
The protected procedure destroyELch uses the scanelement function as well
to destroy an Element together with it's children
Statusgetting all links of an element:
function GetElLinks(n : dword) : TElLinks;getting the status of an element:
function getELStatus(el : dword) : TElementStatus;Getting the number of children of an element:
function getChildCount(del : dword) : dword;getting the last child of an element:
function getLastChild(del : dword) : dword; //return 0 if no childGetting the tree's number of free elements, the last assigned element and the number of stored Undo actions:
function getTreeStatistics : TTreestats;//return tree statistics
procedure UndoAction;Undos the last action.
Added elements are removed from the tree and destroyd (= given the free status).
Deleted and replaced elements are restored.
To clear the complete Undo stack, making further Undos impossible:
procedure purgeUndoStack;This is also a way to destroy all deleted or replaced elements, generating new free elements to be used.
This concludes the tree-graph description.
For more details please refer to the source code.