Analysis

Systems in Rust

Preamble

This builds off the DAG lab.

• Implement graph algorithms.

Basically, after completing the lab, implement functions to compute the height and depth of nodes.

As a bonus problem, compute the height and depth of the entire graph (optional).

Review: The BS CS

• New for 2025, the BS CS has a lot of classes in it (16, up from 10)
• They form a DAG (so does the BA thanks to CS-351).
• Instead of advising separately from teaching, let’s just use advising as the application domain.
• Here is a dot diagram of a simplified version of the degree.
  • Basically, I picked the most common class within any possible distribution.
  • So “Any Software Class” becomes CS-262: Web Development.

• You can see the code that made that in the source, but I also formulated it as concisely as I could manage here:

C151:C280
C151:C152
C151:D351
C152:C271
C152:C351
C152:C262
C271:C371
C351:C480
C371:C480
C480:C481
M150:M251
M150:M280
M150:P221
M251:C351
M251:M352
P221:P222

Review: Two Representations

• Do something like this.

src/lib.rs

#[derive(Debug)]
struct Node {
    data: String,
    next: Vector<String>,
}

• You will probably at some point want to use a dictionary or something a lot like that on this task.
• The use of std::collections::HashMap should be basically familiar, and some helpful combinations of methods can be found on this page.
  • Struct HashMap
• You certainly do not have to use a HashMap, and I had no intention of doing so until I realized I was lazy.

An Aside

• You can probably improve your quality of life with a type alias.

type Graph = std::collections::HashMap<String, Node>;

Your task

• Load the prerequisite edges into Rust.
  • Use std::io:stdin::lock().lines()
  • I terminated on an empty line.
• Build a DAG out of nodes.
  • Basically, conditionally add a node.
    • Look at .or_insert_with(|| <thing you want to insert);
      
• Compute the height and depth of two non-trivial nodes, I choose CS 152 and CS 371.
  • I stored the inputs in data.txt.

$ cargo run -- < data.txt
   Compiling dag v0.1.0 (/home/user/tmp/dag)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.25s
     Running `target/debug/dag`
[src/main.rs:61:13] depth(String::from("C152"), &graph) = 1
[src/main.rs:62:13] depth(String::from("C371"), &graph) = 3
[src/main.rs:63:13] height(String::from("C152"), &graph) = 4
[src/main.rs:64:13] height(String::from("C371"), &graph) = 2