QuestionQuestion

For our final program we are going to visit the stars (virtually). We have gathered all the data we need, and now we are going to visit each planet that contains life; however, our craft is very simple and cannot travel too far without refueling, so we will have to plot our course as efficiently as possible. You are going to create a library that reads in a file with a list a planets and their coordinates in space. The driver code will input a starting planet and destination planet, and you will return the shortest path between the two as a vector of planet names along with the path. Then we are going to test the performance of your path finding algorithm, and possibly give you extra credit.

## Part A: Making a Graph

For Part A you will read in a text containing planets and their x, y, and z coordinates in 3 dimensional space. The file format will be as follows:

```
Kepler-1049b -25 13 8
HAT-P-27b 8 27 23
HD116029b 9 -35 -5
```

Planet names will not contain whitespace and will be uniquely named. Input files will be well-formed (no need for error checking). You will need to build an undirected, weighted graph using the x, y, and z coordinates.

Each planet will have 4 adjacent planets. These should be the 4 closest planets in space. Not all adjacencies will be symmetric. This means the graph is a directed graph. So the algorithm for building the adjacency list will be to find the distance for all planets, but set only the 4 closest as adjacent.

You should use an array or vector to store the planets. To hold edges you will need to implement an adjacency list or an adjacency matrix (you may use the STL list or vector class).

To help you visualize the graph, I have created the following:
[planetsB.dat](http://graphonline.ru/en/?graph=CkibCDSMVdSIOfrV)

### Planet Public Interface
* `Planet(string planetName, long xCoor, long yCoor, long zCoor)`
* `std::string getName()`
    * Returns the planet name
* `int getXCoor()`
    * Returns the x coordinate
* `int getYCoor()`
    * Returns the y coordinate
* `int getZCoor()`
      * Returns the z coordinate
* `list<Planet*> getAdjacent()`
    * Returns an adjacency list for the planet

### Galaxy Public Interface
* `Galaxy(string filename)`
    * Takes in a filename and build a list of planets with adjacencies
* `unsigned int size()`
    * The number of planets currently contained in the galaxy
* `Planet* findByName(std::string planetName)`
    * Returns the planet object with the associated name

__Show your TA your working Part A code by the end of lab on May 2nd.__

_You may continue to work on the remainder of the project on your own time or in lab_

## Part B: Finding the Shortest Path

In order to travel between planets, we have to stop at nearby planets to refuel. You will need to implement Dijkstra’s shortest path algorithm to determine the shortest path between two planets. If you want to implement a different shortest path algorithm, you must clear it with me first. You must use only "adjacent" planets when finding the path. In other words, planetA may have 4 adjacencies, but also may not be an adjacent to any other planet. That means there is no path to planetA.

You should add the following public method to your Galaxy class:
* `vector<Planet *> shortestPath(Planet * start, Planet * dest)`
    * The method should return the shortest path between two planets by returning a list of the planets you will need to travel through in order.

You will also need a second method that gives the distance (in light years) between two planets on the graph:
* `double pathDistance(Planet * start, Planets * dest)`
    * The method should return the total distance (based on the path you must take) between the two planets.
    * The method should return `inf` if there is no path.
       * take a look at [LDBL_MAX](http://www.cplusplus.com/reference/cfloat/), which is equal to `inf`

## Part C - EXTRA CREDIT: Optimizing Dijkstra's Algorithm

Part of the complexity of Dijkstra's algorithm comes from finding the next closest, unvisited vertex. Typically, you can increase the speed of Dijkstra's shortest path algorithm by storing the data in a simple priority queue, such as a heap.

There are several other ways we can improve performance, which I will leave up to you. The top 3 best performance times as measured by test 13 will receive 10 points extra credit.

## Part D: Code Organization and Submission
* Required code organization:
    * program3.cpp
    * Planet.h/.cpp
    * Galaxy.h/.cpp
    * makefile
       * executable should be called: program3
       * You must have the following targets in your makefile:
            * `program3` - only compiles your source code using separate compilation for each .cpp file
            * `clean` - removes all object files and binary executables
            * `run` - compiles if necessary and runs your executable
            * `memcheck` - compiles your source if necessary, then runs your executable with valgrind
       * `program3.cpp` is set up to allow you to skip specified tests. To select tests to skip, you should set a preprocessor define directive in your makefile, using the -D flag. This sets the preprocessing variable in your makefile when you compile `program3.cpp` to an object file. Below is an example of skipping tests 4-11:
            * `g++ -g -std=c++14 -c -D TEST4 -D TEST5 -D TEST6 -D TEST7 -D TEST8 -D TEST9 -D TEST10 -D TEST11 program3.cpp -o program3.o`

Below is just a reminder of the commands you should use to submit your code. If you cannot remember the exact process, please review lab 1.

_These commands all presume that your current working directory is within the directory tracked by `git`._

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#include "Planet.h"
#include <cmath>

using namespace std;

Planet::Planet(std::string planetName, long xCoor, long yCoor, long zCoor) {
name = planetName;
x = xCoor;
y = yCoor;
z = zCoor;
}

std::string Planet::getName() {
return name;
}

int Planet::getXCoor() {
return x;
}

int Planet::getYCoor() {
return y;
}

int Planet::getZCoor() {
return z;
}...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$33.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats