Directed vs Undirected RootedTreesby Laurie L. Lacey, Ph.D., Schenectady County Community College, Schenectady NY, USA, laceyll@gw.sunysccc.edu, \251 2004 Laurie L. LaceyNOTE: This worksheet constructs a maplet that can be used by the student in a Discrete math class to investigate trees.

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.5restart;

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 graphNewA:=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 AlgorithmMinSpanTreeA:=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 algorithmShortPathTreeA:=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 treeDaughter:= 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 treeAncestor:=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 AlgorithmDiameterA:=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.

[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.