Hi Zach
My program seems to being running ok the removeEdge is working as far as I can tell...I dont understand why though when the gPrint is called it says that I have no edges. When I run the program it says that the edges I have read from the file have been inserted, but when the gPrint function gets ahold of it, it comes up no edges. Can you see why? I'm in the middle of working on ..so some functions are only half there. Sorry It's long but I didnt know if you had to see the whole thing or just the function.
Code:
#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>
const long Infinity = 12345; // all weights need to be less than this
const int VISITED = 1;
const int UNVISITED = 0;
const int NOEDGE = -1;
class EdgeClass {
public:
int v1, v2;
EdgeClass(int in1, int in2) { v1 = in1; v2 = in2; }
};
typedef EdgeClass* Edge;
class Graph { // Graph class: Adjacency matrix
private:
int** matrix; // The edge matrix
int numVertex; // Number of vertices
int numEdge; // Number of edges
bool* Mark; // The mark array
friend bool createGraph(Graph&, FILE*);
friend void Gprint(Graph&);
public:
Graph(); // Constructor
Graph(int NumVerts); // Constructor
~Graph(); // Destructor
int n() { return numVertex; }
int e() { return numEdge; }
bool insertEdge (Edge); // Insert an edge into the graph
bool insertEdge (Edge, int); // insert an edge and its weight
bool removeEdge (Edge); // remove an edge from the graph
Edge first(int); // Get the first edge for a vertex
bool isEdge(Edge); // true if this is an edge
Edge next(Edge); // Get next edge for a vertex
int v1(Edge w) { return w->v1; } // Vertex edge comes from
int v2(Edge w) { return w->v2; } // Vertex edge goes to
int weight(int, int); // Return weight of edge
int weight(Edge); // Return weight of edge
bool getMark(int v) { return Mark[v]; }
void setMark(int v, bool val) { Mark[v] = val; }
};
Graph::Graph() { // Constructor
Mark = NULL; matrix = NULL; numVertex = numEdge = 0;
}
Graph::Graph( int NumVerts) { // Constructor
numVertex = NumVerts;
numEdge = 0;
Mark = new bool[numVertex];
matrix = new (int*)[numVertex];
for (int i = 0; i < numVertex; i++) {
matrix[i] = new int[numVertex];
Mark[i] = false;
for (int j = 0; j < numVertex; j++)
matrix[i][j] = NOEDGE;
}
}
Graph::~Graph() { // Destructor: return allocated space
if (Mark != NULL) delete [] Mark;
if (matrix != NULL) delete [] matrix; //code to "destroy" the graph
}
bool Graph::insertEdge (Edge E, int weight)
{ // insert an edge and its weight
if((matrix[E->v1][E->v2]) != VISITED || (matrix[E->v1][E->v2]))
{
matrix[E->v1][E->v2] = weight;
return(true);
}
else
return(false);
}
bool Graph::insertEdge (Edge E) { // insert an edge into the graph
// and
return insertEdge (E, Infinity); // give it an infinite weight
}
bool Graph::removeEdge (Edge E) { // remove an edge from the graph
// If remove is successful, return true;
// else return false
if (matrix[E->v1][E->v2] != NOEDGE)
{
matrix[E->v1][E->v2] = UNVISITED;
return(true);
}
else
return(false);
}
Edge Graph::first(int v) { // Get the first edge for a vertex
for (int i=0; i<numVertex; i++)
if (matrix[v][i] != NOEDGE) return new EdgeClass(v, i);
return NULL;
}
bool Graph::isEdge(Edge w) // true if this is an edge
{ return (w != NULL) && (matrix[w->v1][w->v2] != NOEDGE); }
Edge Graph::next(Edge w) { // Get next edge for a vertex
for (int i=w->v2+1; i<numVertex; i++)
if (matrix[w->v1][i] != NOEDGE)
return new EdgeClass(w->v1, i);
return NULL;
}
int Graph::weight(int i, int j) { // Return weight of edge
if (matrix[i][j] == NOEDGE) return Infinity;
else return matrix[i][j];
}
int Graph::weight(Edge w) { // Return weight of edge
if ((w == NULL) || (matrix[w->v1][w->v2] == NOEDGE))
return Infinity;
else return matrix[w->v1][w->v2];
}
void gPrint(Graph& G) {
int i, j;
if (G.n() == 0) return;
cout << "Number of vertices is " << G.n() << "\n";
cout << "Number of edges is " << G.e() << "\n";
cout << "Matrix is:\n";
for (i=0; i<G.n(); i++) {
for(j=0; j<G.n(); j++)
cout << setw(4) << G.weight(i,j) << " ";
cout << "\n";
}
}
// Return true if there is a path from from to to; false otherwise
bool isThereAPath (Graph &G, int from, int to) {
int a,isEdge(from);
return(true);
}
//Return true if graph G is connected; false otherwise
bool isConnected (Graph &G) {
}
int main() {
char fileName[100];
int numVertices, fromVert, toVert;
char command;
cout << "Please enter the name of the graph data file: ";
cin>> fileName;
// Try to open the file; terminate if unsuccessful
ifstream datumsIn (fileName);
if (!datumsIn) {
cerr << "Could not open " << fileName << endl;
cin >> fileName; // just to keep window open
return -1;
}
// Read the number of vertices and create the graph
datumsIn >> numVertices;
Graph G(numVertices);
// Process the commands in the file
while (datumsIn >> command)
switch (command) {
case 'a': // Add an edge to the graph
case 'A': datumsIn >> fromVert >> toVert;
if (G.insertEdge (new EdgeClass (fromVert, toVert)))
cout << "edge (" << fromVert << ',' << toVert
<< ") was added to the graph." << endl;
else
cout << "edge (" << fromVert << ',' << toVert
<< ") was NOT added to the graph." << endl;
break;
case 'r': // Remove an edge from the graph
case 'R': datumsIn >> fromVert >> toVert;
if (G.removeEdge (new EdgeClass (fromVert, toVert)))
cout << "edge (" << fromVert << ',' << toVert
<< ") was removed to the graph." << endl;
else
cout << "edge (" << fromVert << ',' << toVert
<< ") was NOT removed to the graph." << endl;
break;
case 'c': // Check if the graph is connected
case 'C': if (isConnected (G))
cout << "The graph is connected" << endl;
else
cout << "The graph is NOT connected" << endl;
break;
case 'd': // Display the graph
case 'D': gPrint (G);
break;
case 'p': // Check if a path exists between two vertices
case 'P': datumsIn >> fromVert >> toVert;
if (isThereAPath (G, fromVert, toVert))
cout << "There is a path from "
<< fromVert << " to " << toVert << endl;
else
cout << "There is NOT a path from "
<< fromVert << " to " << toVert << endl;
break;
default: cout << "Bad command: " << command << endl;
} // switch
cout << "All done!" << endl;
char s;
cin >> s ;
return 0;
}