Graphs

wBd1

A hastily cobbled together exercise since you claimed to know what graphs are.

Objective

  1. Implement an edge data structure.
  2. Create an API to read edges from a .tsv file into your data structure.
  3. Implement a node data structure.
  4. Populate your node data structure from your edge data structure.
  5. Implement Dikjstra’s algorithm over your node data structure.

I completed 1, 2, and 4 in 90 minutes. 4 was difficult as I was using a char * to store all node data then query the edges, so I added (3) for you.

Gemini was moderately helpful for this and you would be welcome to use it for this type of assignment, but you are responsible for ensuring e.g. every malloc has a corresponding free and all file pointers are closed and etc. etc..

The TSV

Here is the .tsv I used. It was partially generated by Gemini and I made it cooler (everything the same length).

Here is the .tsv I used. It was partially generated by Gemini and I made it cooler (everything the same length).

I removed the header (to make read-in easier). This is the three letter code of each the source and destination city, though edges are not directed so it is irrelevant which is which, followed by edge weight, the distance between cities in miles, and interstate name.

graph.tsv
SEA PDX 174 5
SEA ELN 107 90
ELN HES 133 82
ELN BTM 491 90
PDX HES 183 84
PDX SMF 579 5
HES BYI 427 84
BYI PIH 75  86
BYI OGD 148 84
BTM PIH 262 15
BTM BYG 442 90
PIH OGD 131 15
OGD SLC 38  15
SLC SMF 650 80
SLC CYS 440 80
SLC CVF 174 15
BYG CYS 299 25
CYS DEN 101 25
DEN CVF 514 70
DEN ABQ 449 25
ABQ LRU 224 25
ABQ FLG 324 40
CVF DAG 412 15
DAG FLG 358 40
DAG ONT 75  15
FLG PHX 144 17
SMF LAX 384 5
LAX ONT 39  10
ONT PHX 335 10
PHX LRU 387 10

SEA PDX 174 5 means Seattle is 174 miles from Portland on I-5.

The edge_t

This was my edge_t. There is one obvious optimization I did not use, but should have, and you are welcome to modify it, I just wanted you to see what I’m working with.

dijkstra.c
typedef struct edge_struct {
    char src[3];
    char dst[3];
    uint32_t mi;
    uint32_t name;  /* interstate # */
} edge_t;

You should probably write at least a print_edge or print_edges by the end of class, that dumps basically the .tsv contents back to console.

A Note

Since I was on the clock for this, I just used:

gcc dijkstra.c -w && ./a.out

The Key

Here’s what all the 3-letters mean.

Code City Junction TimeZone
ABQ Albuquerque, NM I-25 / I-40 Mountain
BTM Butte, MT I-15 / I-90 Mountain
BYG Buffalo, WY I-25 / I-90 Mountain
BYI Burley, ID I-84 / I-86 Mountain
CVF Cove Fort, UT I-15 / I-70 Mountain
CYS Cheyenne, WY I-25 / I-80 Mountain
DAG Barstow, CA I-15 / I-40 Pacific
DEN Denver, CO I-25 / I-70 Mountain
ELN Ellensburg, WA I-90 / I-82 Pacific
FLG Flagstaff, AZ I-17 / I-40 Mountain
HES Hermiston, OR I-82 / I-84 Pacific
LAX Los Angeles, CA I-5 / I-10 Pacific
LRU Las Cruces, NM I-10 / I-25 Mountain
OGD Ogden, UT I-15 / I-84 Mountain
ONT Ontario, CA I-10 / I-15 Pacific
PDX Portland, OR I-5 / I-84 Pacific
PHX Phoenix, AZ I-10 / I-17 Mountain
PIH Pocatello, ID I-15 / I-86 Mountain
SEA Seattle, WA I-5 / I-90 Pacific
SLC Salt Lake City, UT I-15 / I-80 Mountain
SMF Sacramento, CA I-5 / I-80 Pacific