Dec 092017

TP 5.0 source for weighted graphs. Includes Bredth first traversal routines. | |||
---|---|---|---|

File Name | File Size | Zip Size | Zip Type |

BFT.DOC | 11428 | 2699 | deflated |

BFT.EXE | 10192 | 5530 | deflated |

BFT.PAS | 8785 | 1735 | deflated |

GRAPH.PAS | 16223 | 2441 | deflated |

GRAPH.TPU | 5696 | 2590 | deflated |

Q.TPU | 1520 | 752 | deflated |

QUEUE.PAS | 4629 | 882 | deflated |

TESTGPH.PAS | 1742 | 538 | deflated |

TESTTREE.PAS | 1115 | 266 | deflated |

TREE.PAS | 10365 | 1548 | deflated |

TREE.TPU | 3184 | 1448 | deflated |

# Download File BFTGPH.ZIP Here

## Contents of the BFT.DOC file

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

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

December 9, 2017
Add comments