Hey Guys,
I'm working on a C++ program for school. Basically the Program inputs a file of points and outputs an svg file that contains the Graph with the least number of edges. We need to implement this with the Kruskal and Prim algorithm, and the algorithm needs to be chosen dynamically at run time. There is also different sorting techniques used which need to be dynamically chosen at run time aswell.
I have an algorithm class that the Kruscal and Prim classes both extend which has a virtual execute function. And a similar architecture for the sorting algorithms.
My problem is when I create the algorithm needed (this is passed in by command line) and pass it to my Graph constructor which contains an Algorithm type object something goes wrong. When I try to use the algorithm function though the graph object it always goes to the base class execute function which does nothing.
Main.cpp
#include <cstdlib>
#include "graph.h"
#include "utils.h"
int main(int argc, char **argv)
{
if (argc != 4)
{
std::cout << "Usage: exe filename algorithm data_structure\n";
return EXIT_SUCCESS;
}
int iType = toInt(argv[2]);
int sType = toInt(argv[3]);
Graph graph;
if (iType == 1)
{
if (sType == 0) {
Heap queue(1);
Prim prim(queue);
Graph graph = Graph(prim); // Heap
}
else if (sType == 1) {
UnorderedArray queue;
Prim prim(queue);
Graph graph = Graph(prim); // Unordered
}
else {
StdPQueue queue;
Prim prim(queue);
Graph graph = Graph(prim); // Std;
}
}
else
{
if (sType == 0) {
HeapSort sort;
Kruskal krus(sort);
Graph graph = Graph(krus); // heapsort;
}
else if (sType == 1) {
MergeSort sort;
Kruskal krus(sort);
Graph graph = Graph(krus); // mergesort;
}
else if (sType == 2) {
BubbleSort sort;
Kruskal krus(sort);
Graph graph = Graph(krus); // bubblesort;
}
else {
StdSort sort;
Kruskal krus(sort);
Graph graph = Graph(krus); // stdsort;
}
}
// This would be a more appropriate use of the tokenizer, as splitting streams
// based on tokens to get part of a string can be tricky if multiple different
// character tokens are required (stream functions only accept a single character
// token)
std::string plName = argv[1];
std::vector<std::string> t = tokenize(plName, "-.");
int size = toInt(t.at(t.size() - 2));
std::stringstream mss;
mss << "mst-" << size << ".svg";
std::string mstName = mss.str();
graph.loadPoints(plName);
graph.calculateMST();
graph.saveMST(mstName);
return EXIT_SUCCESS;
}Graph.cpp
void Graph::calculateMST()
{
beginTimer();
algo.execute(size, vertexArray, edgeList);
endTimer();
std::cout << "MST computation time: " << getTime() << " s\n";
}Graph.h
#ifndef GRAPH_H
#define GRAPH_H
#include "utils.h"
#include "list.h"
#include "algorithm.h"
#include "prim.h"
#include "kruskal.h"
#include "mergesort.h"
#include "bubblesort.h"
#include "heapsort.h"
#include "stdsort.h"
#include "stdqueue.h"
#include "unordered.h"
#include "heap.h"
using namespace std;
class Graph
{
private:
int size;
Algorithm algo;
List edgeList;
vector<Vertex> vertexArray;
public:
Graph(Algorithm a) : size(0), algo(a), vertexArray(), edgeList() {}
Graph() : size(0), vertexArray(), edgeList() {}
~Graph() { }
void getAlgoType() {algo.getAlgotype();};
void generatePoints(const std::string &filename, int size);
void savePoints(const std::string &filename);
void loadPoints(const std::string &filename);
void calculateMST();
void saveMST(const std::string &filename);
};
#endifI can post other code if you think necessary.
Thanks for any help. I'm really confused by this.
Matt
