5/12/22, 6:30 PM README.md · master · ECE 275 SS 2022 / Student Groups / Q Almustafa / project-3-graph-search · GitLa
https:
git.engr.arizona.edu/ece-275-ss-2022/student-groups/q-almustafa/project-3-graph-search/-
lo
maste
README.md 1/3
[ci skip] Initial commit for assignment 'project-3-graph-search' for student Q Almustafa
Connor Fuhrman authored 3 weeks ago
README.md 4.23 KiB
Project 3: Graph Search!
Overview:
You will implement Dijkstra's shortest path algorithm to search a randomly generated directional multi-graph. Students are encouraged to
utilize outside li
aries to complete the task, e.g., the Boost Graph Li
ary or LEMON. Graphs will be constructed from input either from
stdin or from a file.
Specifics:
Project 3 will be tested as a black-box executable, i.e., the tester only cares about input and output to/from your executable. The tester will
consider all .cpp files utilized in the 'src' directory to compile an executable graphsearch . The executable shall callable as such:
or as
Note the first invocation will read the graph file from the given filename whereas the second will receive input from stdin .
Graph files will be generated at random and will have the following format:
which denotes an edge from src to dst with weight of weight .
Nodes will be identified by a string (e.g., A , BB , ZZZZZ ) and weights will be nonzero positive integers. The graph structure must allow fo
multiple edges between nodes.
A full example is shown below:
./graphsearch inputFile startNode endNode
./graphsearch startNode endNode
src dst weight
A G 622248
A G 872009
A G 341222
A H 40298
B A 676352
B G 510175
B G 35479
B G 665581
C F 737414
C F 608912
C F 350101
C J 62951
D G 695028
D G 82954
D I 413678
D F 974334
E G 400473
E J 994358
E A 917377
E H 677216
F B 703432
F J 518717
F G 303687
F G 279940
Engineering Students Gitla
Phone: XXXXXXXXXXor Email: XXXXXXXXXX
https:
git.engr.arizona.edu/ece-275-ss-2022/student-groups/q-almustafa/project-3-graph-search/-/commit/a687b8a78388a0fd33f364ecfed4fcbf9aaa3f17
https:
git.engr.arizona.edu/connorfuhrman
https:
git.engr.arizona.edu/ece-275-ss-2022/student-groups/q-almustafa/project-3-graph-search/-/pipelines/26335
mailto: XXXXXXXXXX
5/12/22, 6:30 PM README.md · master · ECE 275 SS 2022 / Student Groups / Q Almustafa / project-3-graph-search · GitLa
https:
git.engr.arizona.edu/ece-275-ss-2022/student-groups/q-almustafa/project-3-graph-search/-
lo
maste
README.md 2/3
Note that you should create your own input files for local testing and ensure you can produce the proper path before submitting to the
tester.
Upon finding the shortest path from S to G your program shall print the following format
where W is the total cost of the path and Ni Nj denotes an edge from Ni to Nj
e.g.,
shows a path of cost XXXXXXXXXXfrom node A to D .
If no path is available your program shall print
where S and G are the start and goal node identifiers.
Hint:
This is a directional multigraph but you actually could get away with not creating a multi-graph and only keeping the edge with the least
weight between any two given nodes. Note that this is only applicable when a shortest path output is desired and is not the case in general!
Reguarding either reading from stdin or a file: https:
stackoverflow.com/questions/ XXXXXXXXXX
eading-from-stdin-in-c. We will discuss in
lecture that std::cin is a std::istream type object which has a polymorphic relationship with a std::ifstream type object. Therefore,
one could have a function which returns a std::istream& type object which is a reference to either std::cin or a std::ifstream
object. Note also that stdin is a valid C FILE* stream: https:
stackoverflow.com/questions/ XXXXXXXXXX/using-file-f-stdin.
Li
aries:
My solution utilized the LEMON li
ary found here. A useful tutorial can be found here and a useful mailing list posting is found here. This
li
ary (and the Boost graph li
ary) are preinstalled in the tester. If you wish to utilize another please reach out ASAP so it may be installed
in the tester.
Testing:
Testing is done via randomly generated graphs. There are 'small', 'medium', and 'large' tests. Note that a simple depth-first or
eadth-first
search will not conclude in the allotted time for each test. Each test is worth 1/3 of the overall grade and, as usual, scores are output in the
esults INI file.
Extra Credit:
Pass the tests with and without using an existing li
ary for 50% extra credit. Submit, via email to the instructor, a less than 2 page PDF
document detailing your design choices for the purpose-built graph class and compare/contrast to the chosen li
ary. Include the commit
hash for both passing tests in the PDF submission.
G D 209520
G B 89436
G J 227978
G F 984018
H G 722159
H G 27516
H G 417079
H F 35386
I J 290148
I H 758062
I B 847293
I B 665569
J F 547955
J F 833890
J A 784643
J G 637685
W: S N1 N2 N3 ... G
567953: A G D
No path exists from S to G
Engineering Students Gitla
Phone: XXXXXXXXXXor Email: XXXXXXXXXX
https:
stackoverflow.com/questions/ XXXXXXXXXX
eading-from-stdin-in-c
https:
stackoverflow.com/questions/ XXXXXXXXXX/using-file-f-stdin
https:
lemon.cs.elte.hu/trac/lemon
https:
log.sommer-forst.de/2016/09/28/solving-the-shortest-path-problem-2-lemon-graph-li
ary
http:
lemon.cs.elte.hu/pipermail/lemon-use
2011-January/000324.html
mailto: XXXXXXXXXX
5/12/22, 6:30 PM README.md · master · ECE 275 SS 2022 / Student Groups / Q Almustafa / project-3-graph-search · GitLa
https:
git.engr.arizona.edu/ece-275-ss-2022/student-groups/q-almustafa/project-3-graph-search/-
lo
maste
README.md 3/3
Engineering Students Gitla
Phone: XXXXXXXXXXor Email: XXXXXXXXXX
mailto: XXXXXXXXXX