Practice with graphs and functions that rely on accumulators.

Expectations
    • You and your partner must submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept no email submissions.
    • You must use the language specified at the top of this page.
    • Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses, so revisit it before submitting each assignment. (You can resubmit as many times as you like until the due date without penalty.)
    • Unless otherwise stated, every function and data definition that you design, including helper functions, must follow all steps of the design recipe.
Failure to comply with these expectations will result in deductions and possibly a 0 score.
Graded Exercises:
Exercise 1 In the graphs that we have seen so far, nodes have labels and edges are not labelled. However, there are situations where it is useful to assign label both nodes and edges. For example, the following picture depicts a graph with three nodes labelled A, B, and C, and and three directed edges labelled north, east, and northeast.

Design a data definition called ELGraph (edge-labelled graph), for graphs with labelled nodes and edges. You must include the data definition itself, an interpretation, and at least two examples. You may omit a function template.
You may either (1) assume that nodes and edges are labelled with strings, or (2) give your data definition two parameters (i.e., [ELGraph X Y]), which are the signatures for node and edge labels.
Note that your examples for this exercise must be distinct from the two examples in the next exercise.
Exercise 2 It is very likely that you will revise your solution to this exercise while working on the next one. So, we suggest reading the next exercise before trying to solve this one.
This is the official campus map of Northeastern:
www.northeastern.edu/campusmap/printable/campusmap.pdf
We have highlighted a few of the streets below:
 
Construct an ELGraph called given-street-graph, which represents the streets that we have highlighted.
Construct another ELGraph called my-street-graph that represents some other other collection of streets. You may choose streets around Northeastern, or use any other map. If you do use another map, include a link to the map, so that we can check your example. Your graph must have at least five nodes.
Exercise 3 Design a function called driving-directions that consumes (1) a graph of streets and directions (e.g., from the previous exercise), (2) the starting point, which is an intersection, and (3) the destination, which is another intersection. The function should produce a list of directions.
For example, the following check-expect may hold for your function:
(check-expect
  (driving-directions given-street-graph
                      "Forsyth Way and Huntington"
                      "St Stephen and Gainsborough")
  '("east to Forsyth St and Huntington"
    "east to Opera and Huntington"
    "north to Opera and St Stephen"
    "east to St Stephen and Gainsborough"))
Note that there are multiple possible routes through a graph. In practice, we often care about the shortest path or the cheapest path (e.g., fewest tolls). However, it is adequate for your function to produce any legitimate path.
Do not forget that most streets allow two-way traffic. You may either assume that all streets are two-way streets, or you may accurately model one-way and two-way streets in your map representation.
Exercise 4 Design a function called fully-connected? that produces #true if there exists a path between all pairs of points in an ELGraph graph.
To potentially receive full credit, your solution must use list abstractions where possible.
Exercise 5
(define-struct node [left value right])
(define-struct leaf [value])
; A [BT X Y] is one of:
; - (make-leaf Y)
; - (make-node [BT X Y] X [BT X Y])
; Interpretation: A [BT X Y] represents a binary tree with values _X_ at each
; node and values _Y_ at each leaf.
; Note: that a [BT X Y] may not be a binary search tree.
We define a path to a leaf in a [BT X Y] as the list of values that starts with the value at the root at ends with the value at the leaf.
For example, in the following tree:
(make-node (make-leaf 100)
           0
           (make-node (make-leaf 5) -3 (make-leaf 100)))
There are three paths to the three leaves:
(list 0 100)
(list 0 -3 5)
(list 0 -3 100)
Design a function called shortest-path-to-leaf that consumes a binary tree and produces the shortest path to a leaf. If there are multiple shortest paths, your function may produce any one of them.
To receive credit, the function definition must satisfy the following constraint: once the function visits a leaf with path length N, it must not visit any other leaf with path length greater than N.
Note: If you write a data definition for a path to a leaf, you may omit the template.
Hint: It may help to consider writing a helper function with two accumulators.
Exercise 6
; A BST is a [BT Number String] that is constrained to be a binary search tree:
; At every _(make-node l v r)_ in a BST, all node-values in _l_ are less than
;  _v_ and all node-values in _r_ are greater than _v_.
Design the function: is-bt-a-bst? : [BT Number String] -> Boolean which produces #true if its argument is a BST.
The naive way to solve this problem is to write a function that produces a list of the node values, and then checks that the list is in ascending order. The problem with this approach is that it effective visits all nodes twice: once in the tree, and then again in the list. This problem will not award credit for this solution.
Instead, find an alternate approach that only visits each node once.
Hint: You will need to write a helper function with two accumulators.
Hint: Draw a BST with at least five nodes. What are the constraints on the values at each node?