\begin{sloppypar}
\raggedright\obeylines\setlength{\parindent}{0in}\setlength{\parskip}{0in}\setlength{\topsep}{0in}
si=sequence[int]
\hspace*{1pc}

putint = {\bf proc} (i:int)
\hspace*{0.4in} \% effects: outputs the integer i followed by a space to the primary
\hspace*{0.4in} \% output stream
\hspace*{1pc}

\hspace*{0.4in} stdout:stream := stream\$primary\_output()
\hspace*{1pc}

\hspace*{0.4in} stream\$puts(stdout,int\$unparse(i))
\hspace*{0.4in} stream\$putc(stdout,' ')
\hspace*{0.4in} {\bf end} putint
\hspace*{1pc}

putstr = {\bf proc} (s:string)
\hspace*{0.4in} \% effects: outputs the string s followed by a newline to the primary
\hspace*{0.4in} \% output stream
\hspace*{1pc}

\hspace*{0.4in} stdout:stream := stream\$primary\_output()
\hspace*{1pc}

\hspace*{0.4in} stream\$putl(stdout,s)
\hspace*{0.4in} {\bf end} putstr
\hspace*{1pc}

putnl = {\bf proc} ()
\hspace*{0.4in} \% effects: outputs a newline to the primary output stream
\hspace*{1pc}

\hspace*{0.4in} stdout:stream := stream\$primary\_output()
\hspace*{1pc}

\hspace*{0.4in} stream\$putc(stdout,'$\backslash$n')
\hspace*{0.4in} {\bf end} putnl
\hspace*{1pc}

breadth\_first\_graph = {\bf proc} (d: digraph, n:int)
\hspace*{0.4in} \% effects: prints breadth-first list of d starting with node n.
\hspace*{0.4in} \% Each successive level of nodes is printed on a separate line
\hspace*{1pc}

\hspace*{0.4in} visited:intset := intset\$create()\hspace*{0.3in} \% keep record of visited nodes
\hspace*{0.4in} thisline:queue := queue\$create()\hspace*{0.4in} \% initalize by creating thisline
\hspace*{0.4in} queue\$enq(thisline,n)\hspace*{1.5in} \% and enqueuing the index of the top
\hspace*{0.4in} intset\$insert(visited,n)\hspace*{1.2in} \% of the tree
\hspace*{1pc}

\hspace*{0.4in} {\bf while} \~{ }queue\$is\_empty(thisline) {\bf do}
\hspace*{0.8in} lastline:queue := thisline
\hspace*{0.8in} thisline := queue\$create()
\hspace*{0.8in} {\bf while} \~{ }queue\$is\_empty(lastline) {\bf do}
\hspace*{1.2in} i:int := queue\$deq(lastline)
\hspace*{1.2in} children:si := digraph\$successors(d,i)
\hspace*{1pc}

\hspace*{1.2in} putint(i)
\hspace*{1.2in} {\bf for} j:int {\bf in} si\$elements(children) {\bf do} \% add children to queue
\hspace*{1.6in} {\bf if} \~{ }intset\$member(visited,j) {\bf then} \% for next line if not
\hspace*{2.0in} queue\$enq(thisline,j)\hspace*{1.0in} \% if not already visited
\hspace*{2.0in} intset\$insert(visited,j)
\hspace*{2.0in} {\bf end}
\hspace*{1.6in} {\bf end}
\hspace*{1.2in} {\bf end}
\hspace*{0.8in} putnl()
\hspace*{0.8in} {\bf end}
\hspace*{0.4in} {\bf end} breadth\_first\_graph
\hspace*{1pc}

\%
\% test trees for the debugger
\%
\hspace*{1pc}

start\_up = {\bf proc} ()
\hspace*{0.4in} \% effects: tests breadth\_first\_graph with four different digraphs
\hspace*{1pc}

\hspace*{0.4in} d:digraph
\hspace*{0.4in} n1,n2,n3,n4:int
\hspace*{1pc}

\hspace*{0.4in} putstr(``Testing test\_graph\_1'')
\hspace*{0.4in} breadth\_first\_graph(test\_graph\_1(),1)
\hspace*{0.4in} putnl()
\hspace*{1pc}

\hspace*{0.4in} putstr(``Testing test\_graph\_2'')
\hspace*{0.4in} breadth\_first\_graph(test\_graph\_2(),1)
\hspace*{0.4in} putnl()
\hspace*{1pc}

\hspace*{0.4in} d,n1 := test\_graph\_3()
\hspace*{1pc}

\hspace*{0.4in} putstr(``Testing test\_graph\_3 one'')
\hspace*{0.4in} breadth\_first\_graph(d,1)
\hspace*{0.4in} putnl()
\hspace*{0.4in} putstr(``Testing test\_graph\_3 two'')
\hspace*{0.4in} breadth\_first\_graph(d,n1)
\hspace*{0.4in} putnl()
\hspace*{1pc}

\hspace*{0.4in} d,n1,n2,n3,n4 := test\_graph\_4();
\hspace*{1pc}

\hspace*{0.4in} putstr(``Testing test\_graph\_4 one'')
\hspace*{0.4in} breadth\_first\_graph(d,1)
\hspace*{0.4in} putnl()
\hspace*{0.4in} putstr(``Testing test\_graph\_4 two'')
\hspace*{0.4in} breadth\_first\_graph(d,n1)
\hspace*{0.4in} putnl()
\hspace*{0.4in} putstr(``Testing test\_graph\_4 three'')
\hspace*{0.4in} breadth\_first\_graph(d,n2)
\hspace*{0.4in} putnl()
\hspace*{0.4in} putstr(``Testing test\_graph\_4 four'')
\hspace*{0.4in} breadth\_first\_graph(d,n3)
\hspace*{0.4in} putnl()
\hspace*{0.4in} putstr(``Testing test\_graph\_4 five'')
\hspace*{0.4in} breadth\_first\_graph(d,n4)
\hspace*{0.4in} putnl()
\hspace*{0.4in} {\bf end} start\_up
\hspace*{1pc}

test\_graph\_1 = {\bf proc} () {\bf returns} (digraph)
\hspace*{0.4in} \% effects: returns a digraph with 1 node
\hspace*{1pc}

\hspace*{0.4in} d:digraph := digraph\$create()
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(d)
\hspace*{0.4in} {\bf end} test\_graph\_1
\hspace*{1pc}

test\_graph\_2 = {\bf proc} () {\bf returns} (digraph)
\hspace*{0.4in} \% effects: returns a reasonably complex digraph with no loops
\hspace*{1pc}

\hspace*{0.4in} d:digraph := digraph\$create()
\hspace*{0.4in} n1,n2,n3,n4,i:int
\hspace*{1pc}

\hspace*{0.4in} d, n1 := digraph\$add\_node\_and\_edge(d,1)
\hspace*{0.4in} d, n2 := digraph\$add\_node\_and\_edge(d,1)
\hspace*{0.4in} d, n3 := digraph\$add\_node\_and\_edge(d,1)
\hspace*{1pc}

\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,n1)
\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,i)
\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,i)
\hspace*{1pc}

\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,n2)
\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,n2)
\hspace*{1pc}

\hspace*{0.4in} d, n4 := digraph\$add\_node\_and\_edge(d,n3)
\hspace*{1pc}

\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,n4)
\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,n4)
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(d)
\hspace*{0.4in} {\bf end} test\_graph\_2
\hspace*{1pc}

test\_graph\_3 = {\bf proc} () {\bf returns} (digraph,int)
\hspace*{0.4in} \% effects: returns a small digraph and a node label for testing
\hspace*{1pc}

\hspace*{0.4in} d:digraph := digraph\$create()
\hspace*{0.4in} n1,n2,n3,n4,i:int
\hspace*{1pc}

\hspace*{0.4in} d, n1 := digraph\$add\_node\_and\_edge(d,1)
\hspace*{0.4in} d, n2 := digraph\$add\_node\_and\_edge(d,n1)
\hspace*{0.4in} d, n3 := digraph\$add\_node\_and\_edge(d,n2)
\hspace*{0.4in} d, n4 := digraph\$add\_node\_and\_edge(d,n3)
\hspace*{0.4in} d := digraph\$add\_edge(d,n4,1)
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(d,n3)
\hspace*{0.4in} {\bf end} test\_graph\_3
\hspace*{1pc}

test\_graph\_4 = {\bf proc} () {\bf returns} (digraph,int,int,int,int)
\hspace*{0.4in} \% effects: returns a big, ugly, circular, non-connected digraph and
\hspace*{0.4in} \%\hspace*{1.0in} a bunch of labels to test with
\hspace*{1pc}

\hspace*{0.4in} d:digraph := digraph\$create()
\hspace*{0.4in} n1,n2,n3,n4,n5,n6,i:int
\hspace*{0.4in} m1,m2,m3,m4,m5,m6,m7:int
\hspace*{1pc}

\hspace*{0.4in} \% The first piece
\hspace*{1pc}

\hspace*{0.4in} d, n1 := digraph\$add\_node\_and\_edge(d,1)
\hspace*{0.4in} d, n2 := digraph\$add\_node\_and\_edge(d,1)
\hspace*{0.4in} d, n3 := digraph\$add\_node\_and\_edge(d,1)
\hspace*{1pc}

\hspace*{0.4in} d, n4 := digraph\$add\_node\_and\_edge(d,n2)
\hspace*{0.4in} d, n5 := digraph\$add\_node\_and\_edge(d,n4)
\hspace*{1pc}

\hspace*{0.4in} d := digraph\$add\_edge(d,n1,n4)
\hspace*{0.4in} d := digraph\$add\_edge(d,n1,n5)
\hspace*{0.4in} d := digraph\$add\_edge(d,n4,n2)
\hspace*{1pc}

\hspace*{0.4in} d, n6 := digraph\$add\_node\_and\_edge(d,n3)
\hspace*{1pc}

\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,n6)
\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,n6)
\hspace*{1pc}

\hspace*{0.4in} \% The second piece
\hspace*{1pc}

\hspace*{0.4in} d, m1 := digraph\$add\_node(d)
\hspace*{0.4in} d, m2 := digraph\$add\_node\_and\_edge(d,m1)
\hspace*{0.4in} d, m3 := digraph\$add\_node\_and\_edge(d,m2)
\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,m2)
\hspace*{1pc}

\hspace*{0.4in} d, m4 := digraph\$add\_node(d)
\hspace*{0.4in} d, m5 := digraph\$add\_node\_and\_edge(d,m4)
\hspace*{1pc}

\hspace*{0.4in} d, m6 := digraph\$add\_node(d)
\hspace*{0.4in} d, m7 := digraph\$add\_node\_and\_edge(d,m6)
\hspace*{0.4in} d, i := digraph\$add\_node\_and\_edge(d,m6)
\hspace*{1pc}

\hspace*{0.4in} d := digraph\$add\_edge(d,m4,m2)
\hspace*{0.4in} d := digraph\$add\_edge(d,m5,m3)
\hspace*{0.4in} d := digraph\$add\_edge(d,m7,m5)
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(d,n1,m1,m4,m6)
\hspace*{0.4in} {\bf end} test\_graph\_4
\end{sloppypar}
