On this page:
graph_  traversal

Graph Traversals

For this homework set, you will design a graph traversal algorithm in Rust.

The objective of this homework is to deepen your knowledge of Rust, its standard library, and the trait system. It is also warm-up for Reflective Essay so that you can then focus on concurrency and communication.

Deadline Friday 27 February NOON.


The purpose of graph_traversal is to find a path through a graph. The program reads the graph from a file named on the command line and reads graph queries from standard input.

A graph specification is a file where each line consists of a list of word. The first word specifies a node in the graph and the remaining words enumerate the node’s reachable neighbors. The graph is assumed to be unorderedundirected. Each node mentioned as a neighbor must come with a line in the specification.

Consumers enter path queries one line at a time. A line consists of exactly two node names: the desired start and end node of the path.

Here is a simplistic example:

  $ cat ../graph/graph.dat

  a b d

  b a d


  d c


  $ ./graph_traversal graph.dat

  -> a d

  a b d

  -> a b

  a b

  -> a c

  a b d c

The lines starting with -> are queries.