Graphs and Driving Directions

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.

Part 1

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 part must be distinct from the two examples in the next part.

Part 2

*It is very likely that you will revise your solution to this problem while working on the next one. So, we suggest reading the next problem before trying to solve this one.**

This is the official campus map of Northeastern, and we have highlighted a few 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.

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

Part 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 receive full credit, your solution must use list abstractions where possible.