Name: [Solved] CS251 : Data Structures Project #07: Part 1 and 2: updated graph class
Brand: Assignment Chef
SKU: [Solved] CS251 : Data Structures Project #07: Part 1 and 2: updated graph class
Price: 25 USD
Availability: InStock
Rating: 5 (1 reviews)

5/5 - (1 vote)

Assignment

Weve been working with a graph class limited to at most 100 vertices. This limitation is due to the underlying implementation based on an adjacency matrix. Your assignment here in part 1 is to remove this limitation by rewriting the graph class to use an adjacency list representation. The list does not have to be a linked-list, you are free to use whatever data structure you want to represent a list of edges. And you are free to use any of the built-in C++ data structures: map, set, list, deque, etc.

A current version of the graph.h file is available on Codio: cs251-project07-graphs. A main program is also provided that reads a graph from an input file, and then outputs the graph to see if it was built correctly. Use this as an initial testing platform if you wish. A sample input file is available in graph.txt. If you prefer to work outside of Codio, these same files are available on the course dropbox under Projects, project07part01files.

You are going to completely rewrite the class, which means e.g. that you should delete the EdgeData structure, the AdjMatrix data member, and the MatrixSize constant. Your new class will have no size limit. You can even delete and replace the Vertices vector, its up to you. The class must remain templated with VertexT and WeightT, and you must retain all public functions as currently defined. Your job is to replace how they are implemented, but you must keep all existing public functions. In particular, here are the major steps (and requirements):

Delete all aspects of the adjacency matrix.
Replace with an implementation based on an adjacency list; see zybooks section 10.13.
Delete the constructor graph(int n).
Add a default constructor graph().
If you decide to dynamically-allocate memory, add a destructor. Youll also need to add a

copy constructor and operator= to properly make deep copies.

Re-implement all other functions. For addVertex, delete the if matrix is full check.
NO LINEAR SEARCH you are better than that. Any instances of linear search will result in an automatic 0. Example: a call to addVertex(v) has to check if v exists, and this must be done in O(lgN) worst-case time (where N is the # of vertices). You may assume the graph is sparse, which implies a vertex has a small number E of edges and thus E is significantly less than the total # of edges M. This allows you to use a linked-list for your adjacency list, and its legal to search this list in linear O(E) time since E is very small. What you cannot do is have a single list of *all* the graph edges, since this would require an expensive linear search of O(M) time.
Finally, update the dump() function to properly output the vertices and edges, based on your final implementation. When you output the edges, output in a readable format such as:

A: (A,B,80) (A,C,100),

B: (B,A,100) (B,F,123),

Grading, electronic submission, and Gradescope

Submission: graph.h.

Your score on this project is based on two factors: (1) correctness of graph.h as determined by Gradescope, and (2) manual review of graph.h for commenting, style, and approach (e.g. adherence to requirements). Since this is part 1, it is worth 50 points for correctness, and 10 points for manual review of commenting and style. In this class we expect all submissions to compile, run, and pass at least some of the test cases; do not expect partial credit with regards to correctness. Example: if you submit to Gradescope and your score is a reported as a 0, then thats your correctness score. The only way to raise your correctness score is to re-submit.

In this project, your graph.h will be allowed 12 free submissions. After 12 submissions, each additional submission will cost 1 point. Example: suppose you score 50 after 15 submissions, and you activate this submission for grading. Your autograder score will be 47: 50 3 extra submissions. Note that you cannot use another students account to test your work; this is considered academic misconduct because you have given your code to another student for submission on their account.

By default, we grade your last submission. Gradescope keeps a complete submission history, so you can activate an earlier submission if you want us to grade a different one; this must be done before the due date. We assume *every* submission on your Gradescope account is your own work; do not submit someone elses work for any reason, otherwise it will be considered academic misconduct.

Policy

Late work *is* accepted. You may submit as late as 24 hours after the deadline for a penalty of 10%. After 24 hours, no submissions will be accepted.

All work submitted for grading *must* be done individually. While we encourage you to talk to your peers and learn from them (e.g. your iClicker teammates), this interaction must be superficial with regards to all work submitted for grading. This means you *cannot* work in teams, you cannot work side-by-side, you cannot submit someone elses work (partial or complete) as your own. The Universitys policy is available here:

https://dos.uic.edu/conductforstudents.shtml .

In particular, note that you are guilty of academic dishonesty if you extend or receive any kind of unauthorized assistance. Absolutely no transfer of program code between students is permitted (paper or electronic), and you may not solicit code from family, friends, or online forums. Other examples of academic dishonesty include emailing your program to another student, copying-pasting code from the internet, working in a group on a homework assignment, and allowing a tutor, TA, or another individual to write an answer for you. It is also considered academic dishonesty if you click someone elses iClicker with the intent of answering for that student, whether for a quiz, exam, or class participation. Academic dishonesty is unacceptable, and penalties range from a letter grade drop to expulsion from the university; cases are handled via the official student conduct process described at https://dos.uic.edu/conductforstudents.shtml .

CS 251 : Data Structures Project #07: Part 2 of 2: navigating with Dijkstras alg

Background

Were all familiar with navigation apps. While we dont have the ability to display the results graphically, we can at least perform the back-end operations of loading the map, building the graph, and computing the shortest weighted path between two points. In our case were going to navigate between UIC buildings on the East campus, using the footpaths. But the foundation is there to extend the program to do more general navigation between any two points.

We are working with open-source maps from https://www.openstreetmap.org/. Browse to the site and type UIC into the search field, and then click on the first search result. Youll see the East campus highlighted. Notice the export button we used this button to download the map file (map.osm) well be working with.

Zoom in. Were going to focus on two features of a map: Nodes and Ways . A node is a point on the map, consisting of 3 values: id, latitude, and longitude. These are shown as red dots (there are thousands more). A way is a series of nodes that define something. The two most important examples in our case are buildings and footways. In the screenshot to the right, the buildings are labeled and the footways are the dashed lines. For a building, the nodes define the buildings perimeter. For a footway, the nodes define the endpoints of the footway, but might also include intermediate points along the way (especially if the footway is not a straight line). More details of openstreetmap are available on Wikipedia .

Assignment

The assignment is to write a console-based C++ program to input a campus map (e.g. UICs East campus) and navigate between buildings via footways. The program should be general enough to work with any college map, though we dont plan to extensively test this. Given the time constraints, were going to provide helper functions to read the map for you, which are available in XML format. Your job is to build the underlying graph, input two buildings from the user, and then use Dijkstras algorithm to find the shortest weighted path. This is repeated until the user enters # for the start building. Here are the main program steps:

Load map into xmldoc.
Read nodes.
Read footways.
Read buildings.
Add nodes as vertices.
Add edges based on footways.
Input start and destination buildings, locate on map.
Search the footways and find the nearest nodes to the start and destination buildings; these become the start and dest nodes.
Run Dijkstras algorithm from the start node.
Output the distance and path from start node to destination node. If no path exists, output Sorry, destination unreachable.
Repeat with another pair of buildings.

The footways dont actually intersect with the buildings, which is the reason for step #8: we have to find the nearest node on a footway. Then navigation is performed by moving from node to node (red dots) along one or more footways. The footways (dashed lines) intersect with one another, yielding a graph. The graph is built by adding the nodes as vertices, and then adding edges between the nodes based on the footways. Since our graph class created directed graphs, youll want to add edges in both directions. Nodes are identified by unique 64-bit integers; use the C++ datatype long long. The edges weights are distances in miles; use double.

From XML to data structures

An openstreetmap is represented as an XML document. Very briefly, an XML document is a text-based representation of a tree, with a concept of parent and children. An openstreetmap starts with an <osm> node, and contains <node>, <way>, and other child nodes:

<?xml version=1.0 encoding=UTF-8?>

<osm version=0.6 >

<node id=25779197 lat=41.8737233 lon=-87.6456365 /> .

</osm>

Looks very similar to HTML, right? HTML is a special case of XML. We are using tinyxml2 to parse the XML.

Functions are provided in osm.cpp to read the XML and build a set of data structures. First, here are the structure definitions (defined in osm.h):

// Coordinates:

// the triple (ID, lat, lon)

struct Coordinates

{

long long ID; double Lat; double Lon;

};

// FootwayInfo

// Stores info about one footway in the map. The ID uniquely identifies

// the footway. The vector defines points (Nodes) along the footway; the // vector always contains at least two points.

// Example: think of a footway as a sidewalk, with points n1, n2, ,

// nx, ny. n1 and ny denote the endpoints of the sidewalk, and the points // n2, , nx are intermediate points along the sidewalk.

struct FootwayInfo

{ long long ID; vector<long long> Nodes;

};

// BuildingInfo

// Defines a campus building with a fullname, an abbreviation (e.g. SEO), // and the coordinates of the building (id, lat, lon).

struct BuildingInfo

{ string Fullname; string Abbrev; Coordinates Coords;

};

A node is the map is stored as a Coordinate, a way as a FootwayInfo, and a building as a BuildingInfo. Here are the functions that load the XML and store the data in a set of data structures:

// Functions:

bool LoadOpenStreetMap(string filename, XMLDocument& xmldoc);

int ReadMapNodes(XMLDocument& xmldoc, map<long long, Coordinates>& Nodes); int ReadFootways(XMLDocument& xmldoc, vector<FootwayInfo>& Footways); int ReadUniversityBuildings(XMLDocument& xmldoc, map<long long, Coordinates>& Nodes, vector<BuildingInfo>& Buildings);

These functions build three data structures: Nodes, Footways, and Buildings. A drawing is provided in the Appendix on the last page, and heres the C++ declarations:

int main()

{

map<long long, Coordinates> Nodes; // maps a Node ID to its coordinates (lat, lon) vector<FootwayInfo> Footways; // info about each footway, in no particular order vector<BuildingInfo> Buildings; // info about each building, in no particular order XMLDocument xmldoc;

The nodes are stored in a map since youll need to do frequent lookups by ID. The footways are stored in a vector because there is no particular order to them; linear searches will be necessary. The buildings are also stored in a vector because it will be searched by partial name and abbreviation (and some buildings have no abbreviation), so an ordering is not clear; linear searches will be necessary.

Getting started

If you are working in Codio, some of the files were already provided in a sub-directory called part02. Save your work from part01, e.g. in the sub-directory part01 or locally on your machine. Then open a terminal window and copy the files from part02 up one level (..) to your home directory:

cd part02 cp * .. cd ..

Next, browse to the course dropbox, projects, project07-part02-files, and upload the files from the Codioupdates folder : main.cpp, osm.cpp, osm.h. Finally, in order to build the program, youll need to update the makefile to compile all four C++ files into one program.exe:

build:

rm -f program.exe

g++ -O2 -std=c++11 -Wall main.cpp dist.cpp osm.cpp tinyxml2.cpp -o program.exe

And this point you should be able to build and run the program, load the map, and output some stats about the UIC East campus map:

If you are working outside of Codio, all files necessary for part02 can be found in the course dropbox, projects, project07-part02-files folder .

Assignment details

As discussed earlier, here are the main program steps:

Load map into xmldoc.
Read nodes.
Read footways.
Read buildings.
Add nodes as vertices.
Add edges based on footways.
Input start and destination buildings, locate on map.
Search the footways and find the nearest nodes to the start and destination buildings; these become the start and dest nodes.
Run Dijkstras algorithm from the start node.
Output the distance and path from start node to destination node. If no path exists, output Sorry, destination unreachable.
Repeat with another pair of buildings.

A main program is provided in main.cpp, and the provided code implements steps 1 4. Your assignment are steps 5 11, which can be done completely in main.cpp. Youll need your implementation of Dijkstras algorithm from HW #17, which youll need to modify to compute the predecessors. The topic of predecessors was discussed in class on Friday 4/24 (day 38). For this problem the graph type is now

graph<long long, double> G; // vertices are nodes, weights are distances

Here are more details about each step:

Add nodes as vertices. Self-explanatory, add each node to the graph.
Add edges based on footways. A footway is a vector of nodes, defining points along the footway. Lets suppose the footway is {N1, N2, N3, N4}. Then you add edges in both directions between N1-N2, N2-N3, and N3-N4. A footway contains at least 2 nodes.
Input start and destination buildings, locate on map. Code is provided to do the input, your job is to find the buildings in the Buildings vector. Note that the user can enter multiple words (e.g. Thomas Beckham or Henry Hall), and the input can denote a full building name, some part of the name, or an abbreviation (e.g. SEO, LCA, or SCE). Unfortunately, some abbreviations overlap, e.g. BH and TBH, so if you only search for partial matches, you might find TBH instead of BH. The simplest solution is the following: Search by abbreviation first
If not found, then search the fullname for a partial match (use .find?).

If the start building is not found, output Start building not found, skip steps 8-10, and get another pair of inputs. Likewise if the dest building is not found, output Destination building not found.

Search the footways for the nearest start and dest nodes. Assuming the start and destination buildings were found, you have the start and destination coordinates. The problem is that the buildings are *not* on

the footways, so theres no path between buildings. The solution were going to take is to search through the Footways, and find the nearest footway node to the start building. Likewise search and find the nearest footway node to the destination building. How? Call the distBetween2Points() function (provided in dist.cpp), and remember the node with the smallest distance; when you call the function, use the buildings (lat, lon) as the first parameter. If two nodes have the same distance, use the first one you encounter as you search through the Footways. [ This is basically a find the min algorithm. ]

Run Dijkstras algorithm. Dont forget to redefine double INF = numeric_limits<double>::max();
Output distance and path to destination. Dijkstras algorithm returns the distances (as a map), and the predecessors (however you want). If the destination is unreachable (which can happen, e.g. SEO to SSB is unreachable), output Sorry, destination unreachable. Otherwise output the distance and path as shown in the screenshots.
Repeat with another pair of buildings.

Requirements

You must solve the problem as intended, i.e. build a graph from the map data, and use Dijkstras algorithm to find the shortest weighted path.
The graph class must be the same graph class submitted for part 1. Do not modify the graph class in order to create a custom class for the purpose of solving this particular assignment.
Dijkstras algorithm should be your solution from HW #17, modified as needed for this assignment (i.e. predecessors, different graph type).
No global variables.

Grading, electronic submission, and Gradescope

Submission: all .cpp and .h files required to compile your program

Your score on this project is based on two factors: (1) correctness as determined by Gradescope, and (2) manual review of program files for commenting, style, and approach (e.g. adherence to requirements). Since part 2 is longer than part 1, it is worth 100 points for correctness, and 40 points for manual review of commenting, style and overall approach / efficiency. In this class we expect all submissions to compile, run, and pass at least some of the test cases; do not expect partial credit with regards to correctness. Example: if you submit to Gradescope and your score is a reported as a 0, then thats your correctness score. The only way to raise your correctness score is to re-submit.

In this project, your program will be allowed 12 free submissions. After 12 submissions, each additional submission will cost 1 point. Example: suppose you score 100 after 15 submissions, and you activate this submission for grading. Your autograder score will be 97: 100 3 extra submissions. Note that you cannot use another students account to test your work; this is considered academic misconduct because you have given your code to another student for submission on their account.

Policy

Late work *is* accepted. You may submit as late as 1 week after the deadline for a penalty of 10%. After late period has expired, no submissions will be accepted.

https://dos.uic.edu/conductforstudents.shtml .

Appendix: data structures

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Whatsapp Us

[Solved] CS251 : Data Structures Project #07: Part 1 and 2: updated graph class

Grading, electronic submission, and Gradescope

Policy

Assignment

From XML to data structures

Getting started

Assignment details

Requirements

Grading, electronic submission, and Gradescope

Policy

Appendix: data structures

Reviews

Related products

[Solved] CS 251 : Data Structures Project #02:mymatrix

[Solved] CS251 : Data Structures Project #05:Threaded AVL: avlt

[Solved] CS251-Assignment 1-AWK script along with a bash script

[Solved] CS251-Assignment 7-GPU programming using CUDA

[Solved] CS251-Assignment 5-Git project

[Solved] CS 251 Project 3: Hashtables and Heap