Graphs
wBd1
A hastily cobbled together exercise since you claimed to know what graphs are.
Objective
- Implement an edge data structure.
- Create an API to read edges from a .tsv file into your data structure.
- Implement a node data structure.
- Populate your node data structure from your edge data structure.
- 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 10SEA 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
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:
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 |