CD Actual 13

home *** CD-ROM | disk | FTP | other *** search

/ CD Actual 13 / CDA13.ISO / cdactual / demobin / share / program / Pascal / BFTGPH.ZIP / BFT.DOC next >

Wrap

Text File | 1991-09-09 | 11.2 KB | 358 lines

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