| big_k105 |
Dec 9th, 2004 11:13 PM |
really ionly wrote the graph.cpp on this but then again that is the main part i guess :) my instructor wrote the rest but if you want to check it out you can. let me know what you think of it and how i should have writen it ;)
graph.h
:
#ifndef _GRAPH_H
#define _GRAPH_H
#include <string>
#include <iomanip>
#include <iostream>
#include <cstddef>
#include <cassert>
#include "GraphException.h"
using namespace std;
enum graph_type {WEIGHTED,UNWEIGHTED};
enum direction {DIRECTED, UNDIRECTED};
const int maxnodes=100; // if you use an adjacency matrix
template <class VertexType>
class Graph
{
public:
Graph(); // default is UNDIRECTED and UNWEIGHTED
Graph(graph_type,direction=UNDIRECTED);
Graph(direction,graph_type=UNWEIGHTED);
Graph(const Graph&); // copy constructor
void destroy(); // delete all edges and vertices
bool isEmpty() const;
int edgeCount() const;
int vertexCount() const;
virtual void insertVertex(VertexType); // add a new vertext to graph
virtual void insertEdge(VertexType,VertexType, int weight=1);
virtual void deleteEdge(VertexType,VertexType);
virtual void deleteVertex(VertexType); // also delete associated edges
virtual void dump() const; // for debugging purposes only
private:
int edges[maxnodes][maxnodes];
VertexType nodes[maxnodes];
};
#include "graph.cpp"
#endif
graph.cpp
:
//************************************************
// File: graph.cpp
// Author: Kyle Kjorsvik
// Date: 12/04/04
// Class: CSIS 352
//************************************************
#include "graph.h"
#include "GraphException.h"
#include <iomanip>
#include <iostream>
#include <string>
#include <cstddef>
#include <cassert>
using namespace std;
direction dir;
graph_type wei;
template <class VertexType>
Graph<VertexType>::Graph()
{
dir=UNDIRECTED;
wei=UNWEIGHTED;
for(int i = 0;i < maxnodes; i++)
{
nodes[i] = 0;//needs to be changed
for(int j = 0;j < maxnodes; j++)
{
edges[i][j] = 0;
}
}
}
template <class VertexType>
Graph<VertexType>::Graph(graph_type gra,direction dirr)
{
dir=dirr;
wei=gra;
for(int i = 0;i < maxnodes; i++)
{
nodes[i] = 0;//needs to be changed
for(int j = 0;j < maxnodes; j++)
{
edges[i][j] = 0;
}
}
}
template <class VertexType>
Graph<VertexType>::Graph(direction dirr,graph_type gra)
{
dir=dirr;
wei=gra;
for(int i = 0;i < maxnodes; i++)
{
nodes[i] = 0;//needs to be changed
for(int j = 0;j < maxnodes; j++)
{
edges[i][j] = 0;
}
}
}
template <class VertexType>
Graph<VertexType>::Graph(const Graph&)
{
}
template <class VertexType>
void Graph<VertexType>::destroy()
{
int i;
int j;
for(i=0;i<maxnodes;i++)
{
nodes[i] = 0;
for(j=0;j<maxnodes;j++)
{
edges[i][j] = 0;
}
}
}
template <class VertexType>
bool Graph<VertexType>::isEmpty() const
{
return nodes[0] == 0;//needs to be changed
}
template <class VertexType>
int Graph<VertexType>::edgeCount() const
{ // devide by 2 to get actual count :)
int i;
int j;
int totalnodes;
int totaledges = 0;
totalnodes = vertexCount();
if (dir==1) {
for(i=0;i<totalnodes;i++)
{
for(j=0;j<totalnodes;j++)
{
if(edges[i][j] != 0)
totaledges++;
}
}
totaledges = totaledges / 2;
} else if (dir==0) {
for(i=0;i<totalnodes;i++)
{
for(j=0;j<totalnodes;j++)
{
if(edges[i][j] != 0)
totaledges++;
}
}
}
return totaledges;
}
template <class VertexType>
int Graph<VertexType>::vertexCount() const
{
int i;
int j;
int totalnodes;
for(i=0;i<maxnodes;i++)
{
if(nodes[i] == 0)//needs to be changed
break;
}
return i;
}
template <class VertexType>
void Graph<VertexType>::insertVertex(VertexType node)
{
int i;
int j;
int totalnodes;
for(i=0;i<maxnodes;i++)
{
if(nodes[i] == node)
throw GraphException("Vertx already exists in insertVertex Operation");
if(nodes[i] == 0)//needs to be changed
break;
}
totalnodes = i;
nodes[totalnodes] = node;
}
template <class VertexType>
void Graph<VertexType>::insertEdge(VertexType nodeone,VertexType nodetwo, int weight)
{
int i;
int j;
int curnode;
for(i=0;i<maxnodes;i++)
{
if(nodes[i]==nodeone)
break;
}
curnode = i;
if (dir == 1) {
for(i=0;i<maxnodes;i++)
{
if(nodes[i]==nodetwo)
break;
}
if(edges[curnode][i] !=0)
throw GraphException("edge already exist in insertEdge operation");
edges[curnode][i] = weight;
edges[i][curnode] = weight;
} else if (dir==0) {
for(i=0;i<maxnodes;i++)
{
if(nodes[i]==nodetwo)
break;
}
edges[curnode][i] = weight;
}
}
template <class VertexType>
void Graph<VertexType>::deleteEdge(VertexType nodeone,VertexType nodetwo)
{
int i;
int j;
int curnode;
int vertcnt;
vertcnt = vertexCount();
for(i=0;i<vertcnt;i++)
{
if(nodes[i] == nodeone)
break;
if(nodes[i] == 0)//needs to be changed
throw GraphException("non existant edge in deleteEdge operation");
}
curnode = i;
if (dir == 1) {
for(i=0;i<maxnodes;i++)
{
if(nodes[i]==nodetwo)
break;
}
edges[curnode][i] = 0;
edges[i][curnode] = 0;
} else if (dir==0) {
edges[curnode][i] == 0;
}
}
template <class VertexType>
void Graph<VertexType>::deleteVertex(VertexType node)
{
int i;
int j;
int k;
int curvert;
int vertcnt;
vertcnt = vertexCount();
for(i=0;i<vertcnt;i++)
{
if(nodes[i] == node)
{
curvert = i;
break;
}
}
if(nodes[i] != node)
throw GraphException("non existant vertex in deleteVertex operation");
for(i=0;i<vertcnt;i++)
{
edges[curvert][i] = 0;
edges[i][curvert] = 0;
}
vertcnt = vertexCount();
nodes[i] = 0;//needs to be changed
for(j=curvert;j<vertcnt;j++)
{
for(k=0;k<vertcnt;k++)
{
edges[curvert][k] = edges[curvert + 1][k];
}
for(k=0;k<vertcnt;k++)
{
edges[k][curvert] = edges[k][curvert + 1];
}
nodes[curvert] = nodes[curvert + 1];
curvert = curvert + 1;
}
for(k=0;k<vertcnt;k++)
{
edges[curvert][k] = 0;
edges[k][curvert] = 0;
}
nodes[i] = 0;//needs to be changed
}
template <class VertexType>
void Graph<VertexType>::dump() const
{
int vertcnt;
int edgcnt;
vertcnt = vertexCount();
edgcnt = edgeCount();
cout << "dumping graph: vertices: " << vertcnt << " edges: " << edgcnt << endl;
int i;
int j;
int totalnodes;
totalnodes = vertexCount();
if (dir==1) {
if (wei==1) {
for(i=0;i<totalnodes;i++)
{
cout << nodes[i] << " to: ";
for(j=0;j<totalnodes;j++)
{
if(edges[i][j] == 1)
{
cout << nodes[j] << " ";
}
}
cout << endl;
}
} else if (wei==0) {
for(i=0;i<totalnodes;i++)
{
cout << nodes[i] << " to: ";
for(j=0;j<totalnodes;j++)
{
if(edges[i][j] != 0)
{
cout << nodes[j] << "(" << edges[i][j] << ") ";
}
}
cout << endl;
}
}
} else if (dir==0) {
if (wei==1) {
for(i=0;i<totalnodes;i++)
{
cout << nodes[i] << " to: ";
for(j=0;j<totalnodes;j++)
{
if(edges[i][j] == 1)
{
cout << nodes[j] << " ";
}
}
cout << endl;
}
} else if (wei==0) {
for(i=0;i<totalnodes;i++)
{
cout << nodes[i] << " to: ";
for(j=0;j<totalnodes;j++)
{
if(edges[i][j] != 0)
{
cout << nodes[j] << "(" << edges[i][j] << ") ";
}
}
cout << endl;
}
}
}
}
GraphException.h
:
// ********************************************************
// Header file GraphException.h for the ADT Graph.
// ********************************************************
#ifndef _GRAPHEXCEPTION_
#define _GRAPHEXCEPTION_
#include <stdexcept>
#include <string>
using namespace std;
class GraphException: public logic_error
{
public:
GraphException(const string & message = "")
: logic_error(message.c_str())
{ }
}; // end GraphException
#endif
the program i used to test it
main.cpp
:
// ********************************************************
// Header file GraphException.h for the ADT Graph.
// ********************************************************
#ifndef _GRAPHEXCEPTION_
#define _GRAPHEXCEPTION_
#include <stdexcept>
#include <string>
using namespace std;
class GraphException: public logic_error
{
public:
GraphException(const string & message = "")
: logic_error(message.c_str())
{ }
}; // end GraphException
#endif
sh-2.05b$ cat main.cpp
#include <iostream>
#include "graph.h"
using namespace std;
int main()
{
Graph<char> graph(WEIGHTED); // UNDIRECTED and WEIGHTED
char A='A';
char B='B';
char C='C';
char D='D';
char E='E';
try
{
graph.insertVertex(A);
graph.insertVertex(B);
graph.insertVertex(C);
graph.insertVertex(D);
graph.insertVertex(E);
graph.insertVertex(B); // exception, vertex already exists
}
catch (GraphException error)
{
cout << error.what() << endl;
}
try
{
graph.insertEdge(A,D,4);
graph.insertEdge(B,C,3);
graph.insertEdge(B,D,6);
graph.insertEdge(C,D,7);
graph.insertEdge(A,E,2);
graph.insertEdge(D,E,5);
graph.insertEdge(E,C,9);
graph.insertEdge(A,B,8);
graph.insertEdge(D,A,99); // exception, edge already exists
}
catch (GraphException error)
{
cout << error.what() << endl;
}
graph.dump();
try
{
graph.deleteVertex(D);
graph.deleteVertex(D);
}
catch (GraphException error)
{
cout << error.what() << endl;
}
graph.dump();
try
{
graph.deleteVertex(B);
graph.deleteEdge(E,C);
}
catch (GraphException error)
{
cout << error.what() << endl;
}
if (graph.isEmpty())
cout << "graph is empty\n";
else
graph.dump();
return 0;
}
here is the make file :)
makefile
:
OBJECTS=main.o
CC=g++
CFLAGS=
LFLAGS=
prog8: $(OBJECTS)
$(CC) -o prog8 $(OBJECTS) $(LFLAGS)
main.o: main.cpp graph.h graph.cpp GraphException.h
$(CC) -c $(CFLAGS) main.cpp
clean:
rm -rf *.o core.* prog8
on the makefile make sure all the spaces are tabs. it will tell you this but just make sure they are :) |
