Member Avatar for JustLearning

I am having a problem writing the last part of my code for this program.
There is a DFS function that I need to write that is included in the header file of the graph.h my program.

Here is the sample of code that my instructor gave me.

template<class VertexType>
void DepthFirstSearch(GraphType<VertexType> graph,
VertexType startVertex, VertexType endVertex)
// Assumes VertexType is a type for which the “==“ and "<<"
// operators are defined
{
using namespace std;
StackType<VertexType> stack;
QueType<VertexType> vertexQ;
bool found = false;
VertexType vertex;
VertexType item;
graph.ClearMarks();
stack.Push(startVertex);
do
{
stack.Pop(vertex);
if (vertex == endVertex)
{
cout << vertex);
found = true;
}
else
{
if (!graph.IsMarked(vertex))
{
graph.MarkVertex(vertex);
cout << vertex;
graph.GetToVertices(vertex, vertexQ);
while (!vertexQ.IsEmpty())
{
vertexQ.Dequeue(item);
if (!graph.IsMarked(item))
stack.Push(item);
}
}
}
} while (!stack.IsEmpty() && !found);
if (!found)
cout << "Path not found." << endl;
}

But when I try to write it I keep getting errors when it compiles.

This is his email to us the students on the DFS function.

DepthFirstSearch() tasks
- DFS requires one stack (static), one queue (static), and one queue (dynamic) to hold the path. Instead of printing out each vertex on the path, DFS queues them by name in the dynamic queue. When DFS ends, it must return the address of the dynamic queue to main() so that main() can complete its tasks. Otherwise, the DFS algorithm follows that presented in the book/notes.

This function is in the graph.cpp file.
I have attached all the files that are used in this program.
What an I doing wrong on this function?

#include <iostream>
#include <new>
#include <cstddef>
#include <string>
#include "graph.h"
#include "queue.h"
#include "stack.h"

using namespace std;

Graph::Graph(int num):vertices(NULL),numV(num)
{
	if (num) {
		vertices = new VertexNode[num];
	}
}

Graph::~Graph()
{
	delete [] vertices;
}

void Graph::DeleteAllEdges()
{
	VertexNode* temp = NULL;
}

bool Graph::IsEmpty()
{
	return(numV == 0);
}

bool Graph::IsFull()
{
	return(numV != 0);
}

void Graph::AddVertex(string v)
{
	for(int numNodes = 0; numNodes <= numV; numNodes++)
	{
		if (vertices[numNodes].vname.empty()) {
			vertices[numNodes].vname = v;
			vertices[numNodes].edgePtr = NULL;
			vertices[numNodes].mark = false;
			break;
		}
		//Graph::AddVertex(string v);
	}
}

void Graph::AddEdge(string s, string d, int w)
{
 	int sV = IndexIs(s);
	int dV = IndexIs(d);

            EdgeNode *edge = vertices[sV].edgePtr;
                vertices[sV].edgePtr = new EdgeNode;
				vertices[sV].edgePtr->nextPtr = edge;
				vertices[sV].edgePtr->weight = w;
                vertices[sV].edgePtr->destination = dV;

}

int Graph::IndexIs(string v)
{
	for(int numNodes = 0; numNodes <= numV; numNodes++)
	{
		if (vertices[numNodes].vname == v) {
			return numNodes;
		}
	}
	return -1;
}

int Graph::WeightIs(string s, string d)
{
	int sV = IndexIs(s);
	int dV = IndexIs(d);

    EdgeNode *edge = vertices[sV].edgePtr;
    while (edge) {
    	if (edge->destination == dV) {
			return edge->weight;
		}
		edge = edge->nextPtr;
	}
	return -1;
}

void Graph::GetToVertices(string s, Queue& q)
{
	int sV = IndexIs(s);

    EdgeNode *edge = vertices[sV].edgePtr;
    while (edge) {
		q.Enqueue(s);
		edge = edge->nextPtr;
	}
}

void Graph::ClearMarks()
{
	for(int numNodes = 0; numNodes <= numV; numNodes++)
	{
		if (vertices[numNodes].mark) {
			vertices[numNodes].mark = false;
		}
    }
}

void Graph::MarkVertex(string v)
{
	bool mV = IndexIs(v);
	vertices[mV].mark = true;
	
}

bool Graph::IsMarked(string v)
{
    bool mV = IndexIs(v);
	return (vertices[mV].mark);
}

void Graph::Print()
{
    
	for (int node = 0; node <+ numV; node++){
		cout << "     " << vertices[node].vname << " : ";
		if (!vertices[node].edgePtr){
		cout << endl;
			continue;
			
		}
		EdgeNode *edge = vertices[node].edgePtr;
        while (edge) {
			cout << vertices[edge->destination].vname << edge->weight <<" ";
			edge = edge->nextPtr;
		}
		cout << endl;
 }
	

}

Queue* DepthFirstSearch(string startVertex, string endVertex)
{
 bool found = false;

	string vertex, item;
	Stack stack;
	Queue queue;
	
	stack.Push(startVertex);

	do
	{
  		stack.Pop();
		if (vertex == endVertex)
		{
			cout << vertex;
			found = true;
		}
		else
		{
			if(!Graph::IsMarked(vertex))
			{
				Graph::MarkVertex(vertex);
				queue.Enqueue(vertex);
				Graph::GetToVertices(vertex, queue);
				while (!queue.IsEmpty());
				{
					queue.Dequeue(item);
					if(!Graph.IsMarked(item))
					{
						stack.push(item);
					}
				}
			}
		}
	}while (!Stack.IsEmpty() && !found);
	if(!found)
	cout << "Path not found" << endl;
}
//
// graph.h
// -- adjacency list representation of a weighted graph
//

#ifndef GRAPH_H

#define GRAPH_H

#include <string>
#include "queue.h"
using namespace std;


class FileOpenError                                 // Exception class -- cannot open input file
{
};

struct EdgeNode										// Structure representing an edge
{
  int			destination;						// Index of destination vertex
  int			weight;								// Edge weight
  EdgeNode*		nextPtr;							// Next edge pointer
};

struct VertexNode									// Structure representing a vertex
{
  string		vname;								// Name of vertex
  bool			mark;								// Marked flag
  EdgeNode*		edgePtr;							// Pointer to list of edges
};


class Graph											// Graph ADT using adjacency list representation
{
 private:		//***** Private class members below *****//
  VertexNode*	vertices;							// Array of vertex nodes
  int			numV;								// Number of vertices

 public:		//***** Public members below *****//
  Graph(int num);									// Constructor - creates graph with num vertices
  ~Graph();											// Destructor - deallocates all edge nodes and the vertex list
  void DeleteAllEdges();							// Deallocates all edge nodes from all vertices
  bool IsEmpty();									// Returns true if graph empty, false otherwise
  bool IsFull();									// Returns true if graph full, false otherwise
  void AddVertex(string v);							// Adds vertex to graph assuming vertex not already present
  void AddEdge(string s, string d, int w);	        // Adds edge from source S  to destination D with specified weight W
  int IndexIs(string v);							// Returns index of edge from S to D; -1 if not present
  int WeightIs(string s, string d);					// Returns weight of vertex V -- assumes V is in graph
  void GetToVertices(string s, Queue& q);			// Returns a queue Q of vertices adjacent to vertex V
  void ClearMarks();								// Clears vertex marks
  void MarkVertex(string v);						// Marks vertex V
  bool IsMarked(string v);							// Returns true if vertex V is marked, false otherwise
  void Print();										// Write graph to stdout
  Queue* DepthFirstSearch(string startVertex, string endVertex);  // Returns ptr to queue containing path or NULL if none
}; 

  void Load(string filename, Graph*& g, string& startVertex, string& endVertex);  	
  // Load graph from named file and values of start and end vertices
  // Note: this file attempts to open the named file for input and input all information.  
  // If the file fails to open, Load throws the FileOpenError exception

#endif
#include "queue.h"
#include "stack.h"
#include <string>
#include <cmath>
#include <fstream>
#include <iostream>
#include <new>
#include <cstddef>
#include "graph.h"

using namespace std;

int main(int argc, char * const argv[])
{
	
	char command;
	if (argc !=2){
		cout << "Usage :\n program08 <inputfile>\n";
		return 1;
	}
	
    string fInputs = argv[1];

	string startVert, endVert;
	Graph* thegraph = NULL;
	try{
        Load(fInputs, thegraph, startVert, endVert);
	}
	catch(...)
	{
		cout << "Exception caught" << endl;
		throw;
	}
	
	cout << "******************************" << endl;
	cout << "Vertex : Adjacent Vertices" << endl;
	cout << "------------------------------" << endl;
		thegraph->Print();
    cout << "******************************" << endl;
	
	
  	system("pause");
	return 1;
}

void Load(string fileName, Graph*& g, string& startVertex, string& endVertex)
{
 	ifstream theFile;
  	theFile.open(fileName.c_str());
  	if (!theFile)                    // Check to see if file is open
    {
		cout << "Unable to open file" << endl;  // Error message informing user that file was not opened
		return;
    }
    
  	int num;
  	int weight;

  	char command;
  	string vertName;
  	string edge, edge2;
  	
  	theFile >> num;
  	g = new Graph(num);
  	
  	theFile >> command;
  	
  	while(!theFile.eof())
  	{
		switch (command)
		{
			case 'v':
				theFile >> vertName;
				g->AddVertex(vertName);
				break;
				
			case 'd':
				theFile >> edge;
				theFile >> edge2;
				theFile >> weight;
				g->AddEdge(edge, edge2, weight);
    			break;

			case 'u':
				theFile >> edge;
				theFile >> edge2;
				theFile >> weight;
				g->AddEdge(edge, edge2, weight);
   				g->AddEdge(edge2, edge, weight);
				break;
			case 's':
				theFile >> startVertex;
				break;
			case 'e':
                theFile >> endVertex;
				
            default:                                // Default case should not happen
				cout << "";
		}
		theFile >> command;
	}
	
	
	

}
#include <string>
#include <new>
#include <cstddef>
#include <iostream>
#include "queue.h"

using namespace std;

Queue::Queue()
{
	frontPtr = NULL;
	rearPtr = NULL;
}

void Queue::Enqueue(string v)
{
	if(IsFull())
	    throw FullQueue();
	else if (frontPtr != NULL)
	{
		rearPtr->nextPtr = new QueueNode;
		rearPtr = rearPtr->nextPtr;
		rearPtr->data = v;
		rearPtr->nextPtr = NULL;
	}
	else
	{
        rearPtr = new  QueueNode;		// Initilize a new node for queue
		rearPtr->data = v;					// Point rear ptr to the data
		rearPtr->nextPtr = NULL;					// Set rear pointer to null
		frontPtr = rearPtr;						// In this case rear ptr  equals front ptr
	}
}

string Queue::Dequeue()
{
	if (IsEmpty())
	    throw EmptyQueue();
	else
	{
		QueueNode *DequeueNode = frontPtr;
		string removeData = frontPtr->data;
		
		frontPtr = frontPtr->nextPtr;
		delete DequeueNode;
		if (frontPtr == NULL)
		    rearPtr = NULL;

		return removeData;
	}
}

void Queue::Print()
{
    if (IsEmpty())
	    throw EmptyQueue();
	else
	{
        QueueNode *printPtr = frontPtr;
        while (printPtr != rearPtr)
        {
			cout << printPtr->data;
			printPtr = printPtr->nextPtr;
		}
        cout << printPtr->data << endl;
	}
}

Queue::~Queue()
{
    QueueNode *DequeueNode;
    while(frontPtr != NULL)
	{
		DequeueNode = frontPtr;
  		frontPtr = frontPtr->nextPtr;
		delete DequeueNode;
		if (frontPtr == NULL)
		    rearPtr = NULL;
	}
	
}

bool Queue::IsEmpty()
{
	return (frontPtr == NULL);
}


bool Queue::IsFull()
{
	QueueNode * tempPtr;
	try
	{
		tempPtr = new QueueNode;
		delete tempPtr;
		return false;
	}
	catch (std::bad_alloc)
	{
		return true;
	}
}
//
// queue.h
// -- linked list implementation of a queue
//

#ifndef QUEUE_H

#define QUEUE_H

#include <string>
using namespace std;

class FullQueue										// Exception class for full queue
{
};

class EmptyQueue									// Exception class for empty queue
{
};

struct QueueNode									// Structure representing an edge
{
  string		data;								// Vertex name
  QueueNode*	nextPtr;							// Next edge pointer
};


class Queue											// Queue ADT using linked list representation
{
 private:		//***** Private class members below *****//
  QueueNode*	frontPtr;							// Points to front of queue
  QueueNode*	rearPtr;							// Points to rear of queue

 public:		//***** Public members below *****//
  Queue();											// Default constructor
  ~Queue();											// Destructor
  void Enqueue(string v);							// Add named vertex to queue
  string Dequeue();									// Deletes next vertex from queue, returning its value
  bool IsFull();									// true if queue full, false otherwise
  bool IsEmpty();									// true if queue empty, false otherwise
  void Print();										// Prints queue contents
}; 

#endif
#include <iostream>
#include <cstddef>										// For NULL
#include <new>											// For bad_alloc
#include "stack.h"

using namespace std;

Stack::Stack()
{
	topPtr = NULL;
}

void Stack::Push(string s)
{
	StackNode * tempPtr = new StackNode;
	tempPtr->data = s;
	tempPtr->nextPtr = topPtr;
	topPtr = tempPtr;
}

string Stack::Pop()
{
 	string remove;
	StackNode * tempPtr;
	if (IsEmpty())
  	throw string("empty stack");
	else
	{
    	remove = topPtr->data;
		tempPtr = topPtr;
		topPtr = topPtr->nextPtr;
		delete tempPtr;
 		return remove;
	}
}

bool Stack::IsEmpty() const
{
	return (topPtr == NULL);
}

bool Stack::IsFull() const
{
	StackNode * tempPtr;
	try
	{
		tempPtr = new StackNode;
	}
	catch ( bad_alloc )
	{
    	return true;
	}
	delete tempPtr;
	return false;
}

Stack::~Stack()
{
	while(!IsEmpty())
	{
        StackNode * tempPtr;
        
        tempPtr = topPtr;
        topPtr = topPtr->nextPtr;
        delete tempPtr;
	}

}
//
// stack.h
// -- linked list implementation of a stack
//

#ifndef STACK_H

#define STACK_H

#include <string>
using namespace std;


struct StackNode									// Structure representing a stack node
{
  string		data;								// Index of destination vertex
  StackNode*	nextPtr;							// Next stack node pointer
};


class Stack											// Stack ADT using linked list representation
{
 private:		//***** Private class members below *****//
  StackNode* topPtr;								// Points to top of stack

 public:		//***** Public members below *****//
  Stack();											// Constructor - creates empty stack
  ~Stack();											// Deallocates all stack nodes
  void Push(string s);								// Push vertex name S onto top of stack
  string Pop();										// Pop and return top vertex from top of stack
  bool IsFull() const;								// Returns true if stack is full, false otherwise
  bool IsEmpty() const;								// Returns true if stack is empty, false otherwise
}; 

#endif
  • 4 Contributors
  • 7 Replies
  • 182 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by JustLearning
Member Avatar for Clockowl

Narrow the problem down a bit and you'll recieve more help.

Member Avatar for JustLearning

I don't understand what I am doing wrong in the DFS function. Since the DFS function is is declared in the graph.h file and it is part of the class in the definition, why can't I just call the function in the implementation of the DFS function?
Example: if(!IsMarked(vertex)) Why can't I do this? I have also attached my graph.cpp file. What do I need to do?

Member Avatar for james_zheng

you need to have the concept of 'object oriented programing' . A behavior(function) is belong to a object, it can not exist seprately. just like a hand can not do anything if it is not a part of a body....
Thinking in this way you 'll get the idea.
if you still want to use it in traditional way, you can not declare the function in a class.

Member Avatar for Alex Edwards

you need to have the concept of 'object oriented programing' . A behavior(function) is belong to a object, it can not exist seprately. just like a hand can not do anything if it is not a part of a body....
Thinking in this way you 'll get the idea.
if you still want to use it in traditional way, you can not declare the function in a class.

Not quite.

You can have behavior functions via the 2nd and 3rd levels of polymorphism also.

The 3 (or maybe '4') levels of Polymorphism that I know of are-

1.) Virtual
2.) Static
3.) Callback
[4.) Delegation]

- the 4th is questionable since I've only recently heard about it and it seems to be an implementation in only a select few languages @_@.

You can have a Callback method that uses polymorphism via calling some function that meets the required signature (return, parameters, and class/nonclass info, and any other info regarding if the method is meant for const and non-const objects or just non-const objects... possibly even calling convention... possibly even the restriction of the scope of the function (though I don't think I've encountered that issue), etc). Of course the method may not have the same name as another but it will have enough similar traits to be invoked as a generalized type at run-time.

There's also Static polymorphism. This is typical with template-types where method and member lookup for an object is resolved at compile time. I'm still a bit fuzzy on this topic, but from what I understand you can use any class as a template argument for a class so long as it meets the minimum requirements of operations used on the template. For example, if the generalized-type is constructed anywhere as a temporary reference for the execution of a method, the class argument that is standing in place of the templated type must have its default constructor defined... etc.

Delegation is a topic I can't explain >_<. You'd have to look it up, and potentially experiment with it to understand it @_@.

So in a nutshell you can have multiple objects with the same behavior functions without using the virtual mechanism, but instead either the static mechanism (which is popular in C++), or the traditional callback mechanism (which was the solution for C-based polymorphism).


@JustLearning

To save us some document-sifting, can you be more elaborate as to what type of error you're getting? What does it say when you try to compile?

Member Avatar for james_zheng

Maybe you didnt understand what i mean,
A behavior(function) is belong to a object, it can not exist seprately.
In the situation of this problem, it is definitely correct.

1.) Virtual
2.) Static
3.) Callback
4.) Delegation
the Polymorphism features you mentioned above are also defined in 'object' scope or 'class' scope(e.g.static).
1) virtual function , even if it is a virtual method, its behavior can be overridden within an inheriting class by a function with the same signature. this function must have specific behavior in runtime, at that time , it must belong to a specific object .
2) Static. in this case, a behavior is belong to the whole class , and every object of this class shares this behavior. Although it is not belong to a single object , it BELONG TO a class. it can not exist separately ,either.
3) Callback. Strictly speaking, i dont think callback belongs to OOP, any executable code that is passed as an argument to other code can be a type of callback.
4) Delegation. in c# programing, you can easily find this feature . it seems like a pointer of a function in c/c++. And also, i don't think it contains any OOP features.

Member Avatar for Alex Edwards

Maybe you didnt understand what i mean,
A behavior(function) is belong to a object, it can not exist seprately.
In the situation of this problem, it is definitely correct.

1.) Virtual
2.) Static
3.) Callback
4.) Delegation
the Polymorphism features you mentioned above are also defined in 'object' scope or 'class' scope(e.g.static).
1) virtual function , even if it is a virtual method, its behavior can be overridden within an inheriting class by a function with the same signature. this function must have specific behavior in runtime, at that time , it must belong to a specific object .
2) Static. in this case, a behavior is belong to the whole class , and every object of this class shares this behavior. Although it is not belong to a single object , it BELONG TO a class. it can not exist separately ,either.
3) Callback. Strictly speaking, i dont think callback belongs to OOP, any executable code that is passed as an argument to other code can be a type of callback.
4) Delegation. in c# programing, you can easily find this feature . it seems like a pointer of a function in c/c++. And also, i don't think it contains any OOP features.

Static isn't defined strictly for classes. Static implies that something is resolved at compile-time (or in Java, something is used for the first time (Static Fields)). If this is hard to believe, refer to the use of static in C, a non object-oriented language where static referred to (in short) 'as part of this file' and not a shared member of instances of an object of the class-type.

It is possible to use different functions (different behavior) from different files (non-class types, but the concept is similar) using a combination of Static and Callback polymorphism with functions (behavior in other files) that can both resolve the type at compile time and use the type abstractly in a way that the behavior can still differ among types without the use of classes.

I'd have to do some research on statically calling storage-type members of a namespace via the static mechanism. I wonder if that is also possible (in theory it should be)?

Oh and here's a question for you. Why do you think a Callback is not a valid form of OOP? The virtual mechanism is very similar, except you are relying on a virtual table of a class instead of a reference to a function with the same signature.

I'm honestly not convinced that Polymorphism belongs only to OOP.

Member Avatar for JustLearning

I found out what I was doing wrong I put the function heading like this

Queue* DepthFirstSearch(string startVertex, string endVertex);

instead of like this

Queue* Graph::DepthFirstSearch(string startVertex, string endVertex);
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.