Directed vs Undirected RootedTrees

by Laurie L. Lacey, Ph.D., Schenectady County Community College, Schenectady NY, USA, laceyll@gw.sunysccc.edu, 2004 Laurie L. Lacey

NOTE: This worksheet constructs a maplet that can be used by the student in a Discrete math class to investigate trees.

Introduction

When this maplet is run, it allows the student to examine various aspects of rooted trees.  The results from Dijkstra's algorithm for shortest path spanning tree, Floyd's allpairs shortest path algorithm, and Prim's Algorithm may be examined.   The maplet opens with a window asking the student to input either a directed or undirected graph.  A different Maplet appears depending on the student's response.  The maplet was constructed using Maple 9.5

>

restart;

>	with(networks):with(Maplets[Elements]):s:='s':T:='T':S:='S':TF1:='TF1':TF2:='TF2':TF3:='TF3': TF4:='TF4':TF5:='TF5':G1:='G1':M:='M':q:='q':L:='L':

>	#Draw the graph

>

NewA:=proc()    local    V,E;  global G;                                                               V:=Maplets[Tools][Get]('TF0'::anything);                              E:=Maplets[Tools][Get]('TF1'::anything);                               new(G):                                                              addvertex(V,G): addedge(E,G): draw(G);                                end proc:

>

NewB:=proc()    local    V1,E1;  global G1;                                                               V1:=Maplets[Tools][Get]('TF5'::anything);                               E1:=Maplets[Tools][Get]('TF3'::anything);                             new(G1):                                                              addvertex(V1,G1): addedge(E1,G1): draw(G1);                           end proc:

>	#Finds minimal spanning tree using Prim's Algorithm

>	MinSpanTreeA:=proc() local s,T; s:='s':T:='T':                                                       s:=Maplets[Tools][Get]('TF2'::algebraic);                             T:=spantree(G,s):draw(T);                                             end proc:

>	MinSpanTreeB:=proc() local r,S;r:='r':S:='S':                      r:=Maplets[Tools][Get]('TF4'::algebraic);                              S:=spantree(G1,r):draw(S);                                            end proc:

>	#Finds short path tree using Dijkstra's algorithm

>	ShortPathTreeA:=proc() local q,L;q:='q':L:='L':                                                         q:=Maplets[Tools][Get]('TF2'::algebraic);                            L:=shortpathtree(G,q):draw(L);                                         end proc:

>	ShortPathTreeB:=proc() local  q,L;q:='q':L:='L':                     q:=Maplets[Tools][Get]('TF4'::algebraic);                             L:=shortpathtree(G1,q):draw(L);                                        end proc:

>	#Finds the daughters in a directed spanning tree

>	Daughter:= proc()  local s,T;s:='s':T:='T':                                                        s:=Maplets[Tools][Get]('TF2'::algebraic);            T:=spantree(G,s);op(convert(daughter(T),table));                      end proc:

>	#Finds the ancestors in a directed spanning tree

>	Ancestor:=proc() local s,T,H1;s:='s':T:='T':                          s:=Maplets[Tools][Get]('TF2'::algebraic);                    T:=spantree(G,s);op(convert(ancestor(T),table));                      end proc:

>	#Implements of Floyd's allpairs shortest path algorithm.

>	AllpairsA:=proc()                                                    op(convert(allpairs(G),table));                                       end proc:

>	AllpairsB:=proc()                                                     op(convert(allpairs(G1),table));                                      end proc:

>	#Uses Edmonds's matroid partitioning algorithm to find a partition of G into the minimum number of forests as many of which as possible are spanning trees.

>	ForestsA:=proc()                                                     op(convert(djspantree(G),table));                                     end proc:

>	ForestsB:=proc()                                                     op(convert(djspantree(G1),table));                                     end proc:

>	#Compute the diameter of the spanning tree obtained using Prim's Algorithm

>	DiameterA:=proc() local s,T;s:='s':T:='T':                                                                                               s:=Maplets[Tools][Get]('TF2'::algebraic); T:=spantree(G,s);diameter(T);                                      end proc:

>	DiameterB:=proc() local r,S;r:='r':S:='S':                                                                                                  r:=Maplets[Tools][Get]('TF4'::algebraic);  S:=spantree(G1,r);diameter(S);                                      end proc:

>

maplet := Maplet('onstartup' = 'A1',   Window['W1']('title' = "Directed vs. Undirected", 'layout' = 'BL1'),   BoxLayout['BL1'](      BoxColumn(         BoxRow("Is your graph directed or undirected?"),         BoxRow(            Button("Directed", RunWindow('W2')),            Button("Undirected", RunWindow('W3')),Button("Help", RunDialog('MD1'))         ),         BoxRow(            Button("Exit", Shutdown())         )      )   ),MessageDialog['MD1']( "For example, enter the vertices as {1,2,3,4}: and enter the edges of a directed graph as {[1,3],[1,4],[2,3],[2,4],[1,2]},weights=[7,14,2,3,8], and the edges of an undirected graph as [{1,2},{2,4},{2,3},{3,4}],weights=[3,2,1,3]", 'type'='information' ),                                                         Window['W2']('title'="Directed Trees", 'layout' = 'BL2'),   BoxLayout['BL2'](      BoxColumn(BoxColumn(["Enter the vertices of your graph ",                                    TextField['TF0']( value="{1,2,3,4,5}",('width' = 60))                ], ["Enter the edges and edge weights ",TextField['TF1'](value="{[1,3],[2,5],[1,4],[2,3],[2,4],[4,5],[1,2]},weights=[7,14,2,3,8,3,5]",('width'=60 ))],                                                                            BoxRow(["Enter Root of Tree: ",TextField['TF2'](value='1')]), TextBox['TB1']()),           BoxRow( Plotter['PL1']('height'=325, 'width'=250),              MathMLViewer['ML1']('value' = MathML[Export](" "), 'height'=325, 'width'=250),                        [                Button("GetGraph",Evaluate('PL1'="NewA",Argument('TF0'),Argument('TF1'))),                                                                                      Button("Clear",  Action(SetOption('TF1' = "" ),SetOption('TF0'=""),SetOption('TF2'=""),SetOption('TB1'=""),Evaluate( 'PL1' = "" ),Evaluate('ML1'=""))),                                                                                                                  Button("MinSpanTree ",Evaluate('PL1'="MinSpanTreeA",Argument('TF2'))),                                               Button("Short Path Tree",Evaluate('PL1'="ShortPathTreeA",Argument('TF1'),Argument('TF2'))),                                                         Button("Djspantree",Evaluate('ML1'="ForestsA",Argument('TF1'))),                 Button("DaughterSpanTree ", Evaluate( 'ML1'="Daughter",Argument('TF1'),Argument('TF2'))),                  Button("AncestorSpanTree ", Evaluate( 'ML1'="Ancestor",Argument('TF1'),Argument('TF2'))),                                                               Button("Allpairs",Evaluate('ML1'="AllpairsA",Argument('TF1'))),                                Button("DiamtrSpanTr",Evaluate('TB1'="DiameterA",Argument('TF1'),Argument('TF2'))),                  Button("Close", Shutdown(['TF1']))                    ])                 ) ), Window['W3']('title'="Undirected Trees", 'layout' = 'BL3'),    BoxLayout['BL3'](      BoxColumn(BoxColumn(["Enter the vertices of your graph ",                                    TextField['TF5']( value="{1,2,3,4,5}",('width' = 60))                ], ["Enter the edges and edge weights ",TextField['TF3'](value="[{1,5},{1,2},{4,5},{2,4},{2,3},{3,4},{1,3}],weights=[3,2,1,3,4,1,5]",('width'=60 ))],                                                              BoxRow(["Enter Root of Tree: ",TextField['TF4'](value='1')]), TextBox['TB2']()),              BoxRow( Plotter['PL1']('height'=325, 'width'=250),            MathMLViewer['ML1']('value' = MathML[Export](" "), 'height'=325, 'width'=250),                              [                                                                                      Button("GetGraph",Evaluate('PL1'="NewB",Argument('TF5'),Argument('TF3'))),                Button("Clear",  Action(SetOption('TF3' = "" ),SetOption('TF5'=""),SetOption('TF4'=""),SetOption('TB2'=""),Evaluate( 'PL1' = "" ),Evaluate('ML1'=""))),                 Button("Short Path Tree",Evaluate('PL1'="ShortPathTreeB",Argument('TF3'),Argument('TF4'))),                        Button("MaxDegShortPath",Evaluate('TB2'='maxdegree(shortpathtree(G1,TF4))')),                                                               Button("CountSpanTrees",Evaluate('TB2'='counttrees(G1)')),                 Button("Djspantree",Evaluate('ML1'="ForestsB",Argument('TF3'))),                  Button("MinSpanTree ",Evaluate('PL1'="MinSpanTreeB",Argument('TF3'),Argument('TF4'))),                                                                                                   Button("Allpairs",Evaluate('ML1'="AllpairsB",Argument('TF3'))),Button("DiamtrSpanTree",Evaluate('TB2'="DiameterB",Argument('TF4'))),                 Button("Close",Shutdown(['TF3']))                   ])              )  ),   Action['A1'](RunWindow('W1')) ): Maplets[Display](maplet);

This is a simple maplet that is designed to introduce some basic graph theory concepts regarding trees. The reader is encouraged to add basic error routines and to modify the maplet to include other features. Sample graphs have been entered so that the student can see the syntax.  The graphs are assumed to be connected. The student should note that, sometimes, in a directed graph, a spanning tree or shortpathtree cannot be found from an arbitrary vertex; the result will not be a tree.  If a tree is entered, then the shortpathtree and spantree commands return the given tree.  Depending on the graph and the chosen root of the tree, the shortpathtree and the spantree could be the same.  If the graph is a transport network then the vertex chosen as the root of the desired tree should be the source of the network, otherwise  the algorithm might not result in a tree. It is important to clear the fields and restart the Maplet before entering new graphs.  The notation and format were adapted from the Maplet Tutorial available with Maple 9.5 [1].  My thanks to Sylvain Muise [2] for the inspiration on how to make the tables of the daughter, ancestors, and allpairs commands to appear in the MathMLViewer.

[1] Examples, Maplet Tutorial , Maple 9.5,  Maplesoft Corporation 2004.

[2] Sylvain Muise, Artificial Neural Network Maplet, Maplesoft Applications CenterWebsite, 2002.

Disclaimer: While every effort has been made to validate the solutions in this worksheet, Waterloo Maple Inc. and the contributors are not responsible for any errors contained and are not liable for any damages resulting from the use of this material.