[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]

    Program BFT;

    (*****************************************************************************)
    (*   Name:  BFT                                                              *)
    (*   Written by: William Hobday                                              *)
    (*   Last modified: March 5, 1989                                            *)
    (*                                                                           *)
    (*   Purpose: Implements the Bredth First traversal algorithm using the      *)
    (*            Graph, Tree, and Q units.  The following program produces BFT  *)
    (*            traversals of the following graphs starting from node C:       *)
    (*                                                                           *)
    (*                    Graph 1                   Graph 2                      *)
    (*                                                                           *)
    (*                  A - B - C - D              A - B   C                     *)
    (*                   \ / \ / \ /                                             *)
    (*                    E - F - G                                              *)
    (*                     \ / \ /                                               *)
    (*                      H - I                                                *)
    (*                       \ /                                                 *)
    (*                        J                                                  *)
    (*                                                                           *)
    (*            In case the adjacency graph as well as the corresponding       *)
    (*            spanning tree is printed.                                      *)
    (*                                                                           *)
    (*****************************************************************************)

    uses graph,Q,tree,crt; { graph is in math.swg
                             q is in pointers.swg !! }

    var A,B,C,D,E,F,G,H,I,J,K,L,M : Vertex;
        Grph1,Grph2: Vertex;

    (*****************************************************************************)
    (*   Name: Visit                                                             *)
    (*                                                                           *)
    (*   Purpose: Visits node by adding vertex to tree and placing it in the Q   *)
    (*            then marking the node as visited.                              *)
    (*   Input: Grph - The graph                                                 *)
    (*          VertexQ - the queue                                              *)
    (*          Father - the tree node to be added to                            *)
    (*          Name - name of the vertex to visit                               *)
    (*   Output: the modifed graph and queue                                     *)
    (*****************************************************************************)

    Procedure Visit( Grph : Vertex; var VertexQ : Queue; Father : TreeNode; Name: char );

    begin
       AddTreeNode( Father,Name );
       GetVertex( Grph,Name )^.visited := true;
       EnQueue( VertexQ,Name );
    end;

    (*****************************************************************************)
    (*   Name: SelectFatherNode                                                  *)
    (*                                                                           *)
    (*   Purpose:  Given a father node it test to see if it the valid one for    *)
    (*             when inserting into the tree.                                 *)
    (*   Input: Father - node to check                                           *)
    (*   Output: pointer to selected node                                        *)
    (*****************************************************************************)

    Function SelectFatherNode( Father : TreeNode ) : TreeNode;

    begin
       if Father^.Son = nil
          then begin
                  Father := Father^.Parent;
                  if Father^.brother = nil
                     then SelectFatherNode := Firstchild( father )
                     else SelectFatherNode := NextSibling( father )
               end
          else SelectFatherNode := FirstChild( father )
    end;

    (*****************************************************************************)
    (*   Name: SelectGraphNode                                                   *)
    (*                                                                           *)
    (*   Purpose: Given the graph it selects the next Node that has not been     *)
    (*            visited.                                                       *)
    (*   Input: Grph - pointer to start of graph                                 *)
    (*   Output: pointer to selected node                                        *)
    (*****************************************************************************)

    Function SelectGraphNode( Grph : Vertex ) : Vertex;

    begin
       While (Grph^.visited = True) and (Grph <> nil) do
          Grph := Grph^.Next;
       SelectGraphNode := Grph
    end;

    (*****************************************************************************)
    (*   Name: BFTraverse                                                        *)
    (*                                                                           *)
    (*   Purpose:  Given a graph and starting vertex this procedure produces a   *)
    (*             spanning tree of the Breadth First Traversal of the graph.    *)
    (*   Input: Grph - the start of the graph                                    *)
    (*          V - the vertex to start traversal at                             *)
    (*   Output: The spanning tree produce by the BFT                            *)
    (*****************************************************************************)

    Procedure BFTraverse( Grph : Vertex; V : Vertex);

    var Name,Name2 : char;
        VertexQ: Queue;
        BFTree,Father : TreeNode;

    begin
       NewQueue( VertexQ );
       while V <> nil do
             begin
                BFTree := NewTree( V^.Name );
                Father := BFTree;
                V^.Visited := true;
                EnQueue( VertexQ,V^.Name );
                while not empty( VertexQ ) do
                   begin
                      Name := DeQueue( vertexQ );
                      Name2 := FirstSuccessor( Grph,Name );
                      while Name2 <> #0 do
                         begin
                            if not GetVertex( Grph,Name2 )^.visited
                               then Visit( Grph,VertexQ,Father,Name2 );
                            Name2 := NextSuccessor( Grph,Name,Name2 );
                         end;
                      Father := SelectFatherNode( Father )
                   end;
                writeln('BFT Spanning Tree');
                writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
                PrintTree( BFTree );
                writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
                writeln;
                V := SelectGraphNode( Grph )
          end
    end;

    begin
       Grph1 := NewGraph;                                (* Initialize graphs *)
       Grph2 := NewGraph;
       A := NewVrtx(Grph1,'A');                          (* Add Vertices *)
       B := NewVrtx(Grph1,'B');
       C := NewVrtx(Grph1,'C');
       D := NewVrtx(Grph1,'D');
       E := NewVrtx(Grph1,'E');
       F := NewVrtx(Grph1,'F');
       G := NewVrtx(Grph1,'G');
       H := NewVrtx(Grph1,'H');
       I := NewVrtx(Grph1,'I');
       J := NewVrtx(Grph1,'J');
       K := NewVrtx(Grph2,'A');
       L := NewVrtx(Grph2,'B');
       M := NewVrtx(Grph2,'C');
       WtdJoin(A,B,1);                                   (* Join vertices *)
       WtdJoin(A,E,4);
       WtdJoin(B,A,1);
       WtdJoin(B,C,2);
       WtdJoin(B,F,4);
       WtdJoin(B,E,7);
       WtdJoin(C,B,2);
       WtdJoin(C,D,3);
       WtdJoin(C,G,5);
       WtdJoin(C,F,1);
       WtdJoin(D,C,3);
       WtdJoin(D,G,4);
       WtdJoin(E,F,2);
       WtdJoin(E,A,4);
       WtdJoin(E,H,3);
       WtdJoin(E,B,7);
       WtdJoin(F,E,2);
       WtdJoin(F,G,3);
       WtdJoin(F,B,4);
       WtdJoin(F,I,1);
       WtdJoin(F,C,1);
       WtdJoin(F,H,3);
       WtdJoin(G,F,3);
       WtdJoin(G,C,5);
       WtdJoin(G,D,4);
       WtdJoin(G,I,5);
       WtdJoin(H,I,5);
       WtdJoin(H,E,3);
       WtdJoin(H,J,2);
       WtdJoin(H,F,3);
       WtdJoin(I,H,5);
       WtdJoin(I,F,1);
       WtdJoin(I,G,5);
       WtdJoin(I,J,6);
       WtdJoin(J,H,2);
       WtdJoin(J,I,6);
       WtdJoin(K,L,1);
       WtdJoin(L,K,1);
       ClrScr;                                           (* display graph 1 *)
       writeln('                         Graph 1');
       BFTraverse( Grph1,c );
       Window(40,2,80,25);
       writeln('Adjacency Matrix');
       writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
       writeln;
       PrintGraph( Grph1 );
       delay(5000);
       Window(1,1,80,25);                                (* display graph 2 *)
       ClrScr;
       writeln('                         Graph 2');
       BFTraverse( Grph2,k );
       Window(40,2,80,25);
       writeln('Adjacency Matrix');
       writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
       writeln;
       PrintGraph( Grph2 )
    end.

[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]