External Documentation BFT

I. Problem Specifications

A. Input specifications

1. The input will consist of the following graphs:

a. Graph 1

A - 1 - B - 2 - C - 3 - D
\ / \ / \ /
4 7 4 1 5 4
\ / \ / \ /
E - 2 - F - 3 - G
\ / \ /
3 3 1 5
\ / \ /
H - 5 - I
\ /
2 6
\ /
J

b. Graph 2

A - 1 - B C

2. The procedures NewVertex and WtdJoin will be
used to enter the structure into memory. The
syntax is a follows:

NewVertex( GraphName , VertexName )
WtdJoin( Vertex1 , Vertex2 )

Where Graphname is the graph, Vertexname is
the name of the new vertex, vertex1 is the
emanating vertex, and vertex2 is the
terminating vertex.

B. Processing Requirments and Goal Summary

1. Using the graph data supplied, the program is to
process it into a corresponding spanning tree as
well as an adjacency matrix.

C. Ouptut Specifications

1. The output will be formated to be clear and
understandable. A spanning tree will be
displayed as follows on the left side of the
screen:

BFT Spanning Tree

Level
0 1 2 3 4 5 6 7 8

C
A
B
D
E
F
H
I
J

Where C would be the root of the following tree

_C
/ \
/ \
A H I
/ \
B D F J

E

The adjacency matrix will be displayed in
standard form with 1's representing an arc
0's representing no arc. It will be on the
right hand side of the screen.


II. Algorithms and Data Structures

A. The solution to this problem broken into 4 parts.

1. The Graph unit
2. The Tree unit
3. The Queue unit
4. The Main program

B. High-level Psuedocode

1. The Graph unit

a. NewGraph
point graph to nil

b. NewVrtx
make new vertex
add to end of vertexlist

c. FirstSuccessor
find first vertex
does it exist?
yes return successor
no return null

d. NextSuccessor
Find first vertex
find second vertex
does it exist?
yes does it have successor?
yes return successor
no return nil
no return nil

e. Adjacent
do vertices exist?
yes see if arc exists
yes return true
no return false
no return fasle

f. ArcWeight
are they adjacent?

yes find arc
display weight
no weight = 0

g. WtdJoin
are they adjacent?
yes end procedure
no do vertices exist
yes join vertices
add arc to lists
set weight

h. RemoveArc
are they adjacent?
yes remove the arc node from vertice lists
no do nothing

i. PrintGraph
does graph exist?
yes print colum names
while vertices left
print row vertice name
compare row with each column
print result

j. PrintArc
are they adjacent?
yes print vertex names and arc weight

2. The Tree unit

a. NewTree
make new tree node
point root at it

b. Root
return root of tree

c. AddTreeNode
does node exist?
yes make new treenode
add to old node

d. DeleteTreeNode
Does node exist?
yes is it a leaf?
no remove node from list

e. Parent, FirstChild, Nextbrother
does node exist?
yes does it have (p,f, or n)
yes return node
f. PrintTree
Does tree exist?
yes while not done
write tree node name
PrintTree brother
PrintTree son

3. The Queue unit

a. NewQueue
Set tail to 0
set head to 0
set length to 0

b. EnQueue
is queue full?
no add data to end
yes overflow

c. DelQueue
is queue empty?
yes underflow
no remove data from front

d. Empty
is length = 0?
yes true
no false

3. The Queue unit

a. Visit
Add vertex to tree
set visited to true
put tree on queue

b. SelectFatherNode
is node^.son nil
yes node = parent
is node^.brother nil
yes node = son

c. SelectGraphNode
while not nil do
has vertex been visited?
no return node
yes goto next vertex and continue

d. GetVertex
search list for vertex of that name
found return node
not found return nil

e. BFT
intialize q and tree
visit first node
while q not empty do
remove name from queue
visit node

f. Main
enter all vertices
enter all arcs
do bft graph1
print adj matrix graph1
do bft graph2
print adj matrix graph2
end


C. The graph will be stored in a multilist linked
configuration. Each vertex contains the
following information:

Name - the name of the vertex
Emanate - pointer to list of emanating arcs
Terminate - pointer to terminating arc
Next - pointer to next vertex in list
Visited - boolean to determine if vertex
has been visited for BFT

Each ArcNode will consist of the following:

Weight - the weight of the arc
Vertex1 - Name of the emanating vertex
Vertex2 - name of the terminating vertex
Emanate - pointer to next emanating arc
Terminate - pointer to next terminating arc

The spanning tree produced by the BFT algoritm
will be stored as an ordered tree using linked
lists. Each Tree node will be structured as
follows:

Data - the data to stored at that node
Parent - pointer to parent node
Brother - pointer to next brother of node
Son - pointer to first son of node

The BFT algorithm requires the use of a queue. The
queue was implemented as a circular list in
contiguous storage:

Data - array of datatype to store data
head - location of head in data array
tail - location of tail in data array
length - length of thee queue

III. Status Reporting

A. Each unit was tested with a file. The listing are
included with the unit listings.

B. Error analysis - errors could exist if the
followings condtions are met for each procedure

1. NewQueue, NewTree, NewGraph, NewVrtx
no error conditions

2. First Successor
vertex DNE
No 1st successor

3. NextSuccessor
1st vert DNE
2nd vert DNE
No next successor

4. Adjacent
V1 or V2 DNE

5. ArcWeight, RemoveArc, PrintArc
V1 or V2 DNE
Arc DNE

6. WtdJoin
V1 or V2 DNE
Arc already exists

7. PrintGraph
Graph DNE

8. AddTreeNode
Node DNE

9. DeleteTreeNode
Node DNE
Node is not leaf

10. Parent, FirstChild, NextSibling
Node DNE
Respective node DNE

11. PrintTree, Root
Tree DNE

12. EnQueue
Q is full
Q DNE

13. DeQueue
Q is empty
Q DNE

14. Empty
Q DNE

C. The program could be improved in the following
ways:

1. New algoritm to print tree in standard tree form

2. Algorithm to print graph in readble form

3. use different faster routines where performance
is poor