Alright guys, I have seen this no where on the internet and I have been trying to figure it out for days. How can I find the MST of a set of coordinates from an input file using Prim's Algorithm. There are a few things about how to go about doing it, but following them along and being new to C++, they aren't much help. Can anyone show me CODE(preferably) on how to solve this issue?
Suppose I have a set of coordinates in an input file "Something.txt" containing:
(N number of nodes/vertices)
(x Coord), (y coord)
etc...
Eg:
9
50 100
100 150
200 150
300 150
350 100
300 50
200 50
100 50
150 100
Given that these points have already been plotted, How would Prim's Algorithm be written? I understand this is a lot, but I'm beyond confused at this point as a new learner to C++. (and yes, I've tried piecing out the code, I've tried looking at other examples and twisting them around to get it to work, I've tried just about everything besides seeing how it's done so I can further understand what I keep missing.)
Thanks in advance.
Edit: The code plotting the points through pygraphics using the argument .txt input file you pass to it, which then goes into a .dat file, which then gets posted through a plotting file pre-created:
class Point
{
public:
// Constructor.
Point()
{
x = 0; y = 0;
} // end constructor
Point(int a, int b, int id)
{
x = a; y = b; pointID = id;
} // end constructor
int getX() { return x; }
int getY() { return y; }
int getID() { return pointID; }
string data;
Point(string x)
{
data = x;
}
private:
int x = 0;
int y = 0;
int v;
int xVert;
int yVert;
int pointID = 0;
list<Point*> pointList;
list<Point*> neighbors;
//vector<Neighbor> myNeighborvector;
//locate point containg value x
Point * findPoint(string x)
{
for(Point * v : pointList)
{
if (v->data == x)
return v;
}
return NULL;
}
//add Neighbor going from x to y
void addDirectedNeighbor(string x, string y)
{
Point * xVert = findPoint(x);
Point * yVert = findPoint(y);
xVert->neighbors.push_back(yVert); //I would think that this should only add y to x's neighbors, but when I try to display I get x as one of y's neighbors
}
void addNeighbor(string x, string y)
{
addDirectedNeighbor(x, y);
addDirectedNeighbor(y, x);
}
}; // end class Point
//--------------------------------------------------------------------------
class Edge
{
public:
// Constructor.
Edge()
{
} // end constructor
Edge(Point ptA, Point ptB)
{
pointA = ptA;
pointB = ptB;
length = sqrt(pow(abs(pointA.getX() - pointB.getX() ), 2) + pow(abs(pointA.getY() - pointB.getY() ), 2) );
} // end constructor
Point getPtA() { return pointA; }
Point getPtB() { return pointB; }
double getLen() { return length; }
int getPtAID() { return pointA.getID(); }
int getPtBID() { return pointB.getID(); }
private:
Point pointA;
Point pointB;
double length;
}; // end class Edge
//--------------------------------------------------------------------------
/*class Neighbor
{
public:
// Constructor.
Neighbor()
{
length = sqrt(pow(abs(pointA.getX() - pointB.getX() ), 2) + pow(abs(pointA.getY() - pointB.getY() ), 2) );
} // end constructor
double getLen() { return length; }
private:
double length;
int pointID = 0;
};*/ // end class Neighbor
vector<Point> myPointvector; // vector will expand as needed
vector<Edge> MinSpanTree;
int main (int argc, char *argv[])
{
ifstream fin;
int coordPairs; // number of coordinate pairs in the file
int ptX, ptY;
int loopCounter;
int pointCounter = 0;
double MSTLength = 0.0;
// Check the number of arguments. Expected: filename of a file
if (argc != 2) // This check is often hardcoded
{ // If failure in parameters, offer advice for correction
cout << "\nThis program uses command-line argument.\n";
cout << "Usage: a.exe <filename>\n";
exit(0);
}
try // All lines within this block are part of the same exception handler
{
fin.open(argv[1]);
}
catch (exception& ex)
{
cout << ex.what(); // display standard explanation of the exception
exit(0); // exit the program
}
// Read from the file, one token at a time. If the type of token is known, it
// can be read into a corresponding variable type, such as
// in >> x; // Read the first item into an integer variable x.
// in >> str; // Read the next item into a string variable str.
// This line provides the graphic window setup.
cout << "800 600 white" << endl;
fin >> coordPairs;
cout << coordPairs << endl;
while (fin >> ptX)
{
// Do something with the element read from the file
// cout << ptX << endl;
fin >> ptY;
// cout << ptY << endl;
cout << "circle " << ptX << " " << ptY << " " << 20 << " seagreen" << endl;
Point dummyPoint(ptX, ptY, pointCounter++);
myPointvector.push_back(dummyPoint); // vector will expand as needed
cout << "Now myPointvector has size " << myPointvector.size() << endl;
} // end while
fin.close();
return 0;
}
This will take a few iterations.
You have Point and vectors. Now write a function to calculate the distance between two Points, and a function to read the data file and produce a vector of Points. Also, write a class Neighbor that holds an ID number and a distance, and give Point a data member which is a vector of Neighbor.
Then give Point some member functions 1) add a Neighbor, 2) remove a Neighbor (specified by ID), and 3) return a copy of the Point's nearest Neighbor.
Once that's done, try popping one Point, A, from the vector, then iterating over the remaining vector, calculating the distance from A to each other Point in turn, and building A's collection of Neighbors.
Put a comment on this answer when all that's working.
EDIT 1:
That's a promising start, but it is vitally important that every iteration of the code be correct. It doesn't have to do everything (or initially anything), but it has to 1) compile and 2) run without crashing. This code does not compile. In Neighbor(), you refer to pointA and pointB without declaring them; they should be arguments to the constructor. In Point, you refer to vertex, findVertex, xvert and neighbors, none of which is defined or even declared. (The Edge class is interesting, but it is not clear how you intend to use it.)
Shore up the Point and Neighbor classes (or abandon Neighbor in favor of Edge) so that they can compile and run, even if they don't accomplish much. I'll check back in a few hours.
EDIT 2:
There are a few features in the latest version of the code that may turn out to be unnecessary, but we shall see.
The idea is to build a tree, so how would that work with these classes? Try writing a small test function that constructs three Points (with hard-coded values) and assembles them into a tree. Once that's working, consider how you would apply Prim's Algorithm to those three points.