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);
};

#endif

I can post other code if you think necessary.
Thanks for any help. I'm really confused by this.

Matt

I think the problem si simply this:
In line 16 you create a Graph object :

Graph graph;

Then in lines 23,28,33,41,46,51,56 another local object with the same name .
Then in line 72 you use the original object:

graph.loadPoints(plName);//this is graph at line 16

You can fix simply this way(I modified only lines mentioned ):

#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(prim); // Heap
		}
		else if (sType == 1) {
			UnorderedArray queue;
			Prim prim(queue);
			graph = Graph(prim); // Unordered
		}
		else {
			StdPQueue queue;			
			Prim prim(queue);
			graph = Graph(prim); // Std;
		}
	}
	else
	{
		if (sType == 0) {
			HeapSort sort;			
			Kruskal krus(sort);
			graph = Graph(krus); // heapsort;
		}
		else if (sType == 1) {
			MergeSort sort;
			Kruskal krus(sort);
			graph = Graph(krus); // mergesort;
		}
		else if (sType == 2) {
			BubbleSort sort;
			Kruskal krus(sort);
			graph = Graph(krus); // bubblesort;
		}
		else {
			StdSort sort;
			Kruskal krus(sort);
			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;
}

This results in exactly the same output. Still accessing the Base algorithm object rather than the specified Prim or Kruscal.

Your Algorithm object in your Graph class needs to be a pointer, not an actual Algorithm object. For polymorphism to work properly, you need to use pointers.

I also notice that your non-default Graph constructor is designed to pass your Algorithm object by value; this is not only slow, because you have to copy the object, but dangerous because it opens the door to losing information. It really should be designed to pass by constant reference.

In other words, take a closer look at your constructor(s).

Edited 5 Years Ago by Fbody: n/a

This question has already been answered. Start a new discussion instead.