In this program, you create a map and find the route from a source location to a

Question

In this program, you create a map and find the route from a source location to a destination location. You will use structure(s), pointers) and class(es) to accomplish this task. Let's begin by looking at the following map: The letters of the alphabet represent the locations. Each line represents a highway and each location has one exit highway and one entry highway. You may only leave a location through its exit highway and enter it through its entry highway. (For example The route from location A to D using this map is A- > E- > C- > B- > D) Your code will implement this. First, you will begin by creating the map above in your code using class(es), structure(s), pointers) and anything else you may want to use. Once you have the map, you will prompt the user to enter new names for the locations represented by A, B, C, D, E, above. Once you have accomplished that, you have created your map. Next, you will prompt the user for the starting location and destination location. You will use the map to figure out and then display the route from the starting location to the destination location. You must keep track of how many times a location is chosen as a destination. You must, then, display the following menu and continue to do so until the user decides to exit the program: C - to enter another source & destination pair P - to see the most popular destination locations E - to exit If the user enters P, you must display the locations from most popular (chosen the most number of times as destination) to least popular. If two or more locations have been chosen as the destination the same number of times, list them in alphabetical order. Please remember to place appropriate error checks.

Explanation / Answer

#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// definging pair shortcut
typedef PAIR<int, int> treePair;

// Struct defining for graph
struct TreeGraph
{
int VERTEX, EDGE;
vector< PAIR<int, treePair> edges;
// defining constructor here
TreeGraph(int VERTEX, int EDGE)
{
this->VERTEX = VERTEX;
this->EDGE = EDGE;
}

// function to add the edge to grapg
void addEdgeToGraph(int a, int b, int weight)
{
edges.push_back({weight, {a, b}});
}

int GetMinimumSpanningTree();
};

// disjoing sets
struct GraphDisjointSets
{
int *root, *rank;
int _n;

// defining constructor here
GraphDisjointSets(int _n)
{
// memory allocation
this->_n = _n;
root = new int[_n+1];
rank = new int[_n+1];

// initialize ranks with 0
for (int i = 0; i <= _n; i++)
{
rank[i] = 0;
root[i] = i;
}
}

// function to find root
int findRoot(int a)
{
if (a != root[a])
root[a] = findRoot(root[a]);
return root[a];
}

// merge by rank
void Union(int z, int w)
{
z = findRoot(z), w = findRoot(w);

if (rank[z] > rank[w])
root[w] = z;
else // rank(z) <= rank(w)
root[z] = w;

if (rank[z] == rank[w])
rank[w]++;
}
};



int TreeGraph::GetMinimumSpanningTree()
{
int _weight = 0; // Initialize result

// not sort the edges according to weight
sort(edges.begin(), edges.end());

// now disjoint sets
GraphDisjointSets dis_sets(VERTEX);

// loop on edges which are already sorted
vector< PAIR<int, treePair>::iterator it;
for (it=edges.begin(); it!=edges.end(); it++)
{
int a = it->second.first;
int b = it->second.second;

int set_u = dis_sets.findRoot(a);
int set_v = dis_sets.findRoot(b);

// checking for cycles
if (set_u != set_v)
{
// this edge is in minimum spanning tree, so print it
cout << a << " - " << b << endl;

// storing weight
_weight += it->first;

// Merging the sets
dis_sets.Union(set_u, set_v);
}
}
return _weight;
}

// main to test
int main()
{
int VERTEX = 9, EDGE = 14;
TreeGraph g(VERTEX, EDGE);

// making graph graph
g.addEdgeToGraph(0, 1, 4);
g.addEdgeToGraph(0, 7, 8);
g.addEdgeToGraph(1, 2, 8);
g.addEdgeToGraph(1, 7, 11);
g.addEdgeToGraph(2, 3, 7);
g.addEdgeToGraph(2, 8, 2);
g.addEdgeToGraph(2, 5, 4);
g.addEdgeToGraph(3, 4, 9);
g.addEdgeToGraph(3, 5, 14);
g.addEdgeToGraph(4, 5, 10);
g.addEdgeToGraph(5, 6, 2);
g.addEdgeToGraph(6, 7, 1);
g.addEdgeToGraph(6, 8, 6);
g.addEdgeToGraph(7, 8, 7);

cout << "Minimum Spanning tree edges: ";
int _weight = g.GetMinimumSpanningTree();
cout<<endl;
cout << "Total weight " << _weight;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.