nicholas_502

graphType.h

#ifndef H_graph
#define H_graph

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include "linkedList.h"
#include "linkedListForGraph.h"
#include "queuelinked.h"


const int infinity = 10000000; //This will be used in later
//parts of this chapter, when
//we discuss weighted graphs.

template <class vertexType, int size>
class graphType
{
public:
bool isEmpty();
//Returns true if the graph is empty;
//otherwise, returns false.
void createGraph();
//The graph is created using the adjacency list
//representation.
void clearGraph();
//The memory occupied by each vertex is deallocated.
void printGraph() const;
//The graph is printed.

void depthFirstTraversal();
//The function to perform the depth first traversal of
//the entire graph.
void dftAtVertex(vertexType vertex);
//The function to perform the depth first traversal of
//the graph at a node specified by the parameter vertex.

void breadthFirstTraversal();
//The function to perform the breadth first traversal of
//the entire graph.

graphType();
//default constructor
//The graph size is set to 0, that is, gSize = 0;
//maxSize = size

~graphType();
//destructor
//The storage occupied by the graph is deallocated.

protected:
int maxSize; //maximum number of vertices
int gSize; //current number of vertices
linkedListGraph<vertexType> *graph; //array of pointers
//to create adjacency lists (linked lists)

private:
void dft(vertexType v, bool visited[]);
//The function to perform the depth first traversal of
//the graph at a particular node.
};


template <class vType, int size>
bool graphType<vType,size>::isEmpty()
{
return (gSize == 0);
}

template <class vType, int size>
void graphType<vType,size>::createGraph()
{
ifstream infile;
char fileName[50];

int index;
vertexType vertex;
vertexType adjacentVertex;

if(gSize != 0) //if the graph is not empty, make it empty
clearGraph();


cout<<"Enter input file name: ";
cin>>fileName;
cout<<endl;

infile.open(fileName,ios::nocreate);

if(!infile)
{
cout<<"Cannot open input file"<<endl;
return;
}

infile>>gSize; //get the number of vertices

for(index = 0; index < gSize; index++)
{
infile>>vertex;
infile>>adjacentVertex;
while(adjacentVertex != -999)
{
graph[vertex].insertLast(adjacentVertex);
infile>>adjacentVertex;
} //end while
} // end for

infile.close();
} //end createGraph


template <class vType, int size>
void graphType<vType, size>::clearGraph()
{
int index;

for(index = 0; index < gSize; index++)
graph[index].destroyList();
gSize = 0;
}

template <class vType, int size>
void graphType<vType, size>::printGraph() const
{
int index;

for(index = 0; index < gSize; index++)
{
cout<<index<<" ";
graph[index].printList();
cout<<endl;
}

cout<<endl;

}

template <class vType, int size>
void graphType<vType, size>::depthFirstTraversal()
{
bool *visited; //array to keep track of the visited vertices
visited = new bool[gSize];

int index;

for(index = 0; index < gSize; index++)
visited[index] = false;

for(index = 0; index < gSize; index++) //for each vertex
if(!visited[index]) //that is not visited
dft(index,visited); //do a depth first
//traverssal
delete [] visited;
} //end depthFirstTraversal



template<class vType, int size>
void graphType<vType,size>::dft(vType v, bool visited[])
{
vType w;

vType *adjacencyList; //array to retrieve
//the adjacent vertices
adjacencyList = new vType[gSize];

int alLength = 0; //the number of adjacent vertices

visited[v] = true;
cout<<" "<<v<<" "; //visit the vertex

graph[v].getAdjacentVertices(adjacencyList, alLength);
//retrieve the adjacent vertices into adjacencyList

for(int index = 0; index < alLength; index++) //for each
{ //vertex adjacent to v
w = adjacencyList[index];
if(!visited[w])
dft(w,visited);
} //end while

delete [] adjacencyList;
} //end dft

template <class vType, int size>
void graphType<vType, size>::dftAtVertex(vertexType vertex)
{
bool *visited;

visited = new bool[gSize];

for(int index = 0; index < gSize; index++)
visited[index] = false;

dft(vertex,visited);

delete [] visited;

} // end dftAtVertex


template <class vType, int size>
void graphType<vType, size>::breadthFirstTraversal()
{
linkedQueueType<vType> queue;

vType u;

bool *visited;
visited = new bool[gSize];

for(int ind = 0; ind < gSize; ind++)
visited[ind] = false; //initialize the array
//visited to false

vType *adjacencyList;

adjacencyList = new vType[gSize];

int alLength = 0;


for(int index = 0; index < gSize; index++)
if(!visited[index])
{
queue.addQueue(index);
visited[index] = true;
cout<<" "<<index<<" ";

while(!queue.isEmptyQueue())
{
queue.deQueue(u);
graph[u].getAdjacentVertices(adjacencyList, alLength);
for(int w = 0; w < alLength; w++)
if(!visited[adjacencyList[w]])
{
queue.addQueue(adjacencyList[w]);
visited[adjacencyList[w]] = true;
cout<<" "<<adjacencyList[w]<<" ";
}
} //end while
}

delete [] visited;
delete [] adjacencyList;
} //end breadthFirstTraversal


template <class vType, int size>
graphType<vType,size>::graphType()
{
maxSize = size;
gSize = 0;
graph = new linkedListGraph<vType>[maxSize];
}

template <class vType,int size>
graphType<vType,size>::~graphType()
{
clearGraph();

delete [] graph;
}

#endif

nicholas_502

linkedListType.h


#ifndef H_LinkedListType
#define H_LinkedListType

#include <iostream.h>


//Definition of the node

template <class Type>
class nodeType
{
public:
Type info;
nodeType<Type> *link;
};


template<class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=(const linkedListType<Type>&);
// overload the assignment operator
void initializeList();
// initialize list to an empty state
// Postcondition: first = NULL, last = NULL
bool isEmptyList();
// Function returns a nonzero value (TRUE) if the list
// is empty, otherwise it returns the value 0 (FALSE)
bool isFullList();
// Function returns a nonzero value (TRUE) if the list
// is full, otherwise it returns the value 0 (FALSE)
void printList();
// Output the info contained in each node.
// Precondition: List must exist
// Postcondition: None
void destroyList();
// Delete all nodes from the list
// Postcondition: first = NULL, last = NULL
void retrieveFirst(Type& firstElement);
// Return the info contained in the first node of the list
// Postcondition: firstElement = first element of the list
void search(Type searchItem);
// Outputs "item is found" if searchItem is in the list,
// otherwise outputs "item not in the list"
void insertFirst(Type newItem);
// newItem is inserted in the list
// Postcondition: first points to the new list and the
// newItem inserted in the beginning of the list
void insertLast(Type newItem);
// newItem is inserted in the list
// Postcondition: first points to the new list and the
// newItem is inserted at the end of the list.
// last points to the last node in the list
void deleteNode(Type deleteItem);
// if found, the node containing the deleteItem is deleted
// from the list
// Postcondition: first points to the first node and
// last points to the last node of the updated list.
linkedListType();
// default constructor
// Initializes the list to an empty state.
// Postcondition: first = NULL, last = NULL
linkedListType(const linkedListType<Type>& otherList);
// copy constructor
~linkedListType();
// destructor
// delete all nodes from the list
// Postcondition: list object is destroyed
protected:
nodeType<Type> *first; //pointer to the first node of the list
nodeType<Type> *last; //pointer to the last node of the list
};


template<class Type>
linkedListType<Type>::linkedListType() // default constructor
{
first = NULL;
last = NULL;
}


template<class Type>
bool linkedListType<Type>::isEmptyList()
{
return(first == NULL);
}

template<class Type>
bool linkedListType<Type>::isFullList()
{
return 0;
}

template<class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp; // pointer to deallocate the memory
// occupied by the node.
while(first != NULL) // while there are nodes in the list
{
temp = first; // set temp to the current node
first = first->link; // advance first to the next node
delete temp; // deallocate memory occupied by temp
}
last = NULL; // initialize last to null. First has already been set to null by the while loop
}

template<class Type>
void linkedListType<Type>::initializeList()
{
destroyList(); //if there are nodes in the list, delete them
}

template<class Type>
void linkedListType<Type>::printList()
{
nodeType<Type> *current; //pointer to traverse the list

current = first; //Set current so that it points to the first node
while(current != NULL) // while more data to print
{
cout<<current->info<<" ";
current = current->link;
}
}//end printList


template<class Type>
void linkedListType<Type>::retrieveFirst(Type& firstElement)
{
firstElement = first->info; //copy the info of the first node
}//end retrieveFirst


template<class Type>
void linkedListType<Type>::search(Type item)
{
nodeType<Type> *current; //pointer to traverse the list
int found;

if(first == NULL) // list is empty
cout<<"Cannot search an empty list. "<<endl;
else
{
current = first; // set current point to first node in the list.
found = 0; // set found to false

while(!found && current != NULL) //search the list
if(current->info == item) //item is found
found = 1;
else
current = current->link; //make current point to the next node

if(found)
cout<<"Item is found in the list."<<endl;
else
cout<<"Item is not in the list."<<endl;
} //end else
}//end search


template<class Type>
void linkedListType<Type>::insertFirst(Type newItem)
{
nodeType<Type> *newNode; // pointer to create the new node

newNode = new nodeType<Type>; // create the new node
newNode->info = newItem; // store the new item in the node
newNode->link = first; // insert new node before first
first = newNode; // make first point to the actual first node

if(last == NULL) // if the list was empty, newNode is also the last node in the list
last = newNode;
}


template<class Type>
void linkedListType<Type>::insertLast(Type newItem)
{
nodeType<Type> *newNode; // pointer to create the new node

newNode = new nodeType<Type>; // create the new node
newNode->info = newItem; // store the new item in the node
newNode->link = NULL; // set the link field of new node to null

if(last == NULL) //if list is empty new node is the first and the last node
{
first = newNode;
last = newNode;
}
else //list is not empty insert new node after last
{
last->link = newNode; // insert new node after last
last = newNode; // make last point to the actual last node
}
}//end insertLast


template<class Type>
void linkedListType<Type>::deleteNode(Type deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
int found;

if(first == NULL) // Case 1. list is empty.
cout<<"Can not delete from an empty list.\n";
else
{
if(first->info == deleteItem) // Case 2. first node is the node
// with the given info.
{
current = first;
first = first ->link;
if(first == NULL) // list had only one node
last = NULL;
delete current;
}
else // search the list for the node with the given info
{
found = 0;
trailCurrent = first; // set trailCurrent to point to the first node
current = first->link; // set current to point to the second node

while((!found) && (current != NULL))
{
if(current->info != deleteItem)
{
trailCurrent = current;
current = current-> link;
}
else
found = 1;
} // end while

if(found) // Case 3. if found, delete the node.
{
trailCurrent->link = current->link;
if(last == current) // node to be deleted was the last node
last = trailCurrent; // update the value of last
delete current; // delete the node from the list
}
else
cout<<"Item to be deleted is not in the list."<<endl;
} // end else
} // end else
} // end deleteNode



template<class Type>
linkedListType<Type>::~linkedListType() // destructor
{
nodeType<Type> *temp;

while(first != NULL) //while there are nodes left in the list
{
temp = first; //set temp point to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate memory occupied by temp
}//end while

last = NULL; // initialize last to null. First already null.
}//end destructor

//copy constructor
template<class Type>
linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list

if(otherList.first == NULL) // otherList is empty
{
first = NULL;
last = NULL;
}
else
{
current = otherList.first; // current points to the list to be copied

//copy the first node
first = new nodeType<Type>; // create the node
first->info = current->info; // copy info
first->link = NULL; // set the link field of the node to null
last = first; // make last point to the first node
current = current->link; //make current point to the next node

//copy the remaining list
while(current != NULL)
{
newNode = new nodeType<Type>; //create new node
newNode->info = current->info; //copy info
newNode->link = NULL; //set link of the new node to null
last->link = newNode; //attach newNode after last
last = newNode; //make last point to the actual last node
current = current->link; //make current point to the next node
}//end while
}//end else
}//end function

//overload the assignment operator
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list.

if(this != &otherList) //avoid self copy
{
if(first != NULL) // if list is not empty, destroy the list
destroyList();

if(otherList.first == NULL) // otherList is empty
{
first = NULL;
last = NULL;
}
else
{
current = otherList.first; //current points to the list to be copied

//copy the first element
first = new nodeType<Type>; // create the node
first->info = current->info; // copy info
first->link = NULL; // set the link field of the node to null
last = first; // make last point to the node
current = current->link; // make current point to the next node

//copy the remaining list
while(current != NULL)
{
newNode = new nodeType<Type>;
newNode->info = current->info;
newNode->link = NULL;
last->link = newNode;
last = newNode;
current = current->link;
}//end while
}//end else
}//end else

return *this;
}


#endif

nicholas_502

linkedListGraph.h
#ifndef H_LinkedListForGraph
#define H_LinkedListForGraph
#include "linkedList.h"

template<class vType>
class linkedListGraph: public linkedListType<vType>
{
public:
void getAdjacentVertices(vType adjacencyList[],
int& length);
//The vertices adjacent to a given vertex from the
//linked list are retrieved in the array adjacencyList.
//The parameter length specifies the number of vertices
//adjacent to given vertex.
};


template<class vType>
void linkedListGraph<vType>::getAdjacentVertices(
vType adjacencyList[], int& length)
{
nodeType<vType> *current;

length = 0;
current = first;

while(current != NULL)
{
adjacencyList[length++] = current->info;
current = current->link;
}
}

#endif

nicholas_502

msTreeType.h
#ifndef H_msTree
#define H_msTree

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include "graphType.h"

template <class vType, int size>
class msTreeType: public graphType<vType, size>
{
public:
void createSpanningGraph();
//This function creates the graph and the weight matrix
void minimalSpanning(vType sVertex);
//This function creates the edges of the minimal
//spanning tree. The weight of the edges is also
//saved in the array edgeWeights
void printTreeAndWeight();
//This function outputs the edges of the minimal
//spanning tree and the weight of the minimal
//spanning tree

protected:
vType source;
int weights[size][size];
int edges[size];
int edgeWeights[size];
};



template <class vType, int size>
void msTreeType<vType, size>::createSpanningGraph()
{
cout<<"Write the definition createSpanningGraph"<<endl;

} //createWeightedGraph

template <class vType, int size>
void msTreeType<vType, size>::minimalSpanning(vType sVertex)
{
int i,j,k;
vType startVertex, endVertex;
int minWeight;

source = sVertex;

bool mstv[size];

for(j = 0; j < gSize; j++)
{
mstv[j] = false;
edges[j] = source;
edgeWeights[j] = weights[source][j];
}

mstv[source] = true;
edgeWeights[source] = 0;

for(i = 0; i < gSize - 1; i++)
{
minWeight = infinity;

for(j = 0; j < gSize; j++)
if(mstv[j])
for(k = 0; k < gSize; k++)
if(!mstv[k] && weights[j][k] < minWeight)
{
endVertex = k;
startVertex = j;
minWeight = weights[j][k];
}
mstv[endVertex] = true;
edges[endVertex] = startVertex;
edgeWeights[endVertex] = minWeight;
} //end for
} //end minimalSpanning

template <class vType, int size>
void msTreeType<vType, size>::printTreeAndWeight()
{
int treeWeight = 0;

cout<<"Source Vertex: "<<source<<endl;
cout<<"Edges Weight"<<endl;

for(int j = 0; j < gSize; j++)
{
if(edges[j] != j)
{
treeWeight = treeWeight + edgeWeights[j];
cout<<"("<<edges[j]<<", "<<j<<") "
<<edgeWeights[j]<<endl;
}
}

cout<<endl;
cout<<"Minimal Spanning Tree Weight: "<<treeWeight<<endl;
} //end printTreeAndWeight



#endif

nicholas_502

linkedQueueType.h

//Queue derived from linked list. Header file: queueLinked.h
#ifndef H_QueueType
#define H_QueueType

#include <iostream.h>
#include "linkedList.h"

template<class Type>
class linkedQueueType: public linkedListType<Type>
{
public:
bool isEmptyQueue();
bool isFullQueue();
void destroyQueue();
void initializeQueue();
void addQueue(Type newElement);
void deQueue(Type& deqElement);
};

template<class Type>
void linkedQueueType<Type>::initializeQueue()
{
linkedListType<Type>::initializeList();
}

template<class Type>
void linkedQueueType<Type>::destroyQueue()
{
linkedListType<Type>::destroy();
}

template<class Type>
bool linkedQueueType<Type>::isEmptyQueue()
{
return linkedListType<Type>::isEmptyList();
}

template<class Type>
bool linkedQueueType<Type>::isFullQueue()
{
return linkedListType<Type>::isFullList();
}

template<class Type>
void linkedQueueType<Type>::addQueue(Type newElement)
{
linkedListType<Type>::insertLast(newElement);
}

template<class Type>
void linkedQueueType<Type>::deQueue(Type& deqElement)
{
nodeType<Type> *temp;

deqElement = first->info; // copy the info of the first element
temp = first; // make temp point to the first node
first = first->link; // advance front to the next node
delete temp; // delete the first node
if(first== NULL) // if after deletion queue is empty
last = NULL;
}

#endif

nicholas_502

#include <iostream.h>
#include "minimalSpanTreeType.h"


int main()
{
cout<<"See Programming Exercise 4"<<endl;

return 0;
}



what should i put at here plz help me

johnwill

You might start by telling us what the problem is, instead of just posting a program source file.

nicholas_502

i have problem is how to give the program work ....

nicholas_502

plz help me solve the problem thx......
my email adderess is nicholas_502@yahoo.com

ricer333

See TITLE

johnwill

I give up.

ricer333

You know, maybe we should have some basic rules that some of the newbies should and could read. Like Rule 1: don't just post code or HW problems looking for solutions. Questions should be specific. We're not here to do your HW. Lord knows, that I did enough HW in the past 6 years to choak a small horse! Moderator, you can use that 'small horse' line if you want. I give permission!

common

do you need a program to COMPILE all that stuff to make it workie ???

johnwill

I think he just needs someone to do his homework.

elf

Well he has it mostly done...it seems to me all he needs is help ridding his prog. of errors. If I had a compiler handy I would help, but I don't

johnwill

Well, for someone that can't be bothered to do some of the work, and to show some interest in the process, I sure am not going to invest any effort.