DAG

Systems in Rust

Preamble

You know what a DAG is. Now make one in Rust.

• Implement a relatively non-trivial graph.
• Review the CS major requirements.
• Review I/O, strings, and (maybe) maps

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

Two Representations

• Depending on the use case, it is not unreasonable to express such a graph as an ordered pair of a set of nodes and a set of edges (of which the above is the set of edges).
  • Or even just a set of edges?
• Depending on the use case, it is not unreasonable to create a struct Node for each course.
  • Today we’ll do this one (otherwise you just use a Vec<T> - yawn!)
  • We’ll do something much just, just still use a vector but use it to store a node’s… postrequisities (I don’t know the word).

  src/lib.rs

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

Implementation Detail

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

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);
      
• Print it, somehow.
  • dbg!() is fine but I wrote a loop over the hashmap.
• Here’s how it looked - I run, then copy+paste the edges, then press enter to generate an empty line.
  • The output follows.
  • You should have 14 lines - there are 16 courses and all but CS 151 and MATH 150 have pre-reqs.

$ cargo run
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/dag`
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

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