Code:
#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <conio.h>
#include <windows.h>
using namespace std;
//#define MAX 100
//template <class V, class W> // V is the vertex class; W is edge weight class
struct Edge {
string name; // Vertex name
int weight; // Edge weight
Edge *pNextEdg;
Edge();
~Edge() {};
Edge (Edge& edg);
Edge& operator< (Edge& edg);
Edge& operator> (Edge& edg);
bool operator== (Edge& edg);
Edge& operator= (Edge& edg);
};
//typedef edgeRep<string,int> Edge; // simplifies type-name
//template <class V, class W>
Edge::Edge()
{
weight = 0;
}
//template <class V, class W>
Edge::Edge(Edge& edg)
{
name = edg.name;
weight = edg.weight;
}
//template <class V, class W>
Edge& Edge::operator< (Edge& edg)
{
this->name < edg.name;
this->weight < edg.weight;
return *this;
}
//template <class V, class W>
Edge& Edge::operator> (Edge& edg)
{
this->name > edg.name;
this->weight > edg.weight;
return *this;
}
//template <class V, class W>
Edge& Edge::operator= (Edge& edg)
{
name = edg.name;
weight = edg.weight;
return *this;
}
//template <class V, class W>
bool Edge::operator== (Edge& edg)
{
return (this->name == edg.name && this->weight == edg.weight);
}
/********************************************************************************/
//template <class V, class W>
struct Vertex { // Array cell structure for graph
string name; // Vertex name
int visited; // Used during traversal, Breadth-First or Depth-First
list<Edge> edgelist; // Pointer to edge list
Vertex *pNextVert;
Vertex (Vertex& vert);
int inDegree;
int outDegree;
Edge *edgPtr;
Vertex();
~Vertex();
};
//template <class V, class W>
Vertex/*<V,W>*/::Vertex()
{
visited = 0;
}
//template <class V, class W>
Vertex/*<V,W>*/::~Vertex()
{
}
//template <class V, class W>
Vertex/*<V,W>*/::Vertex(Vertex& vert)
{
name = vert.name;
visited = 0;
}
//typedef vertex<string,int> Vertex ;
/********************************************************************************/
//template <class V, class W>
class Graph {
protected:
list<Vertex> g; // Main graph array for adjacency list representation
Vertex *first;
int count;
string inFileName;
ifstream inFile;
//. . . protected member functions
public:
Graph(); // Constructor
// . . . other constructors
~Graph(); // Destructor
//Predicates:
void FVert();
int isVertex(string &v); // Tests whether v is a vertex in the graph
//list<Vertex>::iterator isVertex(string &v); // Tests whether v is a vertex in the graph
int isUniEdge(string &v1, string &v2); // Tests whether edge <v1,v2> in graph
int isBiDirEdge(string &v1, string &v2);// Tests whether edge (v1,v2) in graph
// The following functions return -1 for failure, non-neg for success
int AddVertex(string &v);
// Adds vertex with name v to the graph, if v is not already in
// graph, and returns the index where the vertex is stored.
int DeleteVertex(string &v);
// Deletes vertex with name v from the graph, if v is in the graph.
// If there are any edges incident on the vertex, these edges
// are deleted also.
int AddUniEdge(string &v1, string &v2, int &wt);
// Adds the directed edge <v1,v2,wt> to the graph; adds the vertices
// to the graph if the vertices are not already part of the graph
int DeleteUniEdge(string &v1, string &v2);
// Deletes the directed edge <v1,v2> (any weight) from the graph, if
// it is in the graph. The vertices are not deleted from the graph,
// only the edge.
int AddBiDirEdge(string &v1, string &v2, int &wt);
// Adds the bi-directional edge (v1,v2,wt) to the graph; adds the
// vertices to the graph if the vertices are not already part of
// the graph
int DeleteBiDirEdge(string &v1, string &v2);
// Deletes the bi-directional edge (v1,v2) (any weight) from the
// graph, if it is in the graph. The vertices are not deleted from
// the graph, only the edge.
void SimplePrintGraph();
// Prints the list of vertices in the graph, and for each vertex,
// prints the list of edges in proper parenthesized notation, namely
// (v1,v2,wt) or <v1,v2,wt>. NOTE: This is not a traversal.
void DFT();
void DFTraversal(string &v);
// DepthFirstTraversal: Performs a recursive Depth First Traversal of
// the graph starting at the specified vertex (parameter); prints trace
// information: This traversal requires a stack.
void GetGraph();
//Retrieves a graph from a special disk file and sets up the adjacency
//list for the graph. I am supplying 3 such files.
/* void ShortestPaths(V &v); (for Project 3)
// Determines the shortest paths to all other vertices from the
// specified vertex.
// Must be implemented using Ford's algorithm and a 'DeQ' ADT for
// processing the vertices. Trace information must be displayed,
// i.e. the DeQ after each iteration.
// When done, display the distances and the previous vertex for each
// vertex in the graph.*/
};
Graph::Graph()
{
//VertNum = 0;
}
Graph::~Graph()
{
}
void Graph::FVert()
{
string SearchVert;
cout << "What city would you like to find? " << endl;
cin >> SearchVert;
isVertex(SearchVert);
}
int Graph::isVertex(string &v)
{
//Vertex *walker;
Vertex *ptr;
if(!first)
{
cout << "There is no Graph" << endl;
return -2;
}
ptr = first;
while(!ptr && (v > ptr->name))
ptr = ptr->pNextVert;
if(v == ptr->name)
{
cout << "City found" << endl;
return 1;
}
else
{
cout << "City not found" << endl;
return -2;
}
}
int Graph::isUniEdge(string &v1,string &v2)
{
return -1;
}
int Graph::isBiDirEdge(string &v1, string &v2)
{
return -1;
}
int Graph::AddVertex(string &v)
{
Vertex *ptr;
Vertex *locPtr;
Vertex *predPtr;
ptr = new Vertex;
ptr->name = v;
if(ptr)
{
ptr->pNextVert = NULL;
ptr->name = v;
ptr->inDegree = 0;
ptr->outDegree = 0;
count++;
}
else
return -1;
locPtr = first;
if(!locPtr)
first = ptr;
else
{
predPtr = NULL;
while(locPtr && v < locPtr->name) //????????????
{
predPtr = locPtr;
locPtr = locPtr->pNextVert;
}
if(!predPtr)
first = ptr;
else
predPtr->pNextVert = ptr;
ptr->pNextVert = locPtr;
}
return 1;
}
int Graph::DeleteVertex(string &v)
{
Vertex *ptr;
Vertex *walker;
if(!first)
{
cout << "There is no Graph" << endl;
return -2;
}
ptr = NULL;
walker = first;
while(walker && v != walker->name) //?????????
{
ptr = walker;
walker = walker->pNextVert;
}
if(!walker || v != walker->name)
return -2;
if((walker->inDegree > 0) || (walker->outDegree > 0))
return -1;
if(!ptr)
first = walker->pNextVert;
else
ptr->pNextVert = walker->pNextVert;
count--;
delete walker;
return 1;
}
int Graph::AddUniEdge(string &v1, string &v2, int &wt)
{
Edge *ptr;
Edge *walker;
Edge *edgeptr;
Vertex *v1ptr;
Vertex *v2ptr;
ptr = new Edge;
if(!ptr)
{
cout << "error" << endl;
return -1;
}
/********************find v1*****************************/
v1ptr = first;
while(v1ptr && (v1 > v1ptr->name))
v1ptr = v1ptr->pNextVert;
if(!v1ptr || v1 != v1ptr->name)
{
cout << "key not found" << endl;
return -2;
}
/***********************find v2****************************/
v2ptr = first;
while(v2ptr && (v2 > v2ptr->name))
v2ptr = v2ptr->pNextVert;
if(!v2ptr || v2 != v2ptr->name)
{
cout << "key not found" << endl;
return -3;
}
/*************************************************/
++v1ptr->outDegree;
++v2ptr->inDegree;
if(!v1ptr->edgPtr)
{
v1ptr->edgPtr = ptr;
ptr->pNextEdg = NULL;
return 1;
}
edgeptr = NULL;
walker = v1ptr->edgPtr;
while(walker && v2 >= v2ptr->name)
{
edgeptr = walker;
walker = walker->pNextEdg;
}
if(!edgeptr)
v1ptr->edgPtr = ptr;
else
edgeptr->pNextEdg = ptr;
ptr->pNextEdg = walker;
return 1;
}
int Graph::DeleteUniEdge(string &v1, string &v2)
{
Vertex *v1ptr;
Vertex *v2ptr;
Edge *edgeptr;
Edge *walker;
/******************************************************/
if(!first)
{
cout << "no graph" << endl;
return -2;
}
v1ptr = first;
while (v1ptr && v1 > v1ptr->name)
v1ptr = v1ptr->pNextVert;
if(!v1ptr || v1 != v1ptr->name)
{
cout << "error" << endl;
return -2;
}
/*********************************************************/
if(!v1ptr->edgPtr)
return -3;
edgeptr = NULL;
walker = v1ptr->edgPtr;
while(walker && v2 > walker->name)
{
edgeptr = walker;
walker = walker->pNextEdg;
}
if(!walker || v2 != walker->name)
return -3;
return -1;
}
int Graph::AddBiDirEdge(string &v1, string &v2, int &wt)
{
return -1;
}
int Graph::DeleteBiDirEdge(string &v1, string &v2)
{
return -1;
}
void Graph::SimplePrintGraph()
{
}
void Graph::DFT()
{
string start;
cout << "Enter Starting Point" << endl;
cin >> start;
DFTraversal(start);
}
void Graph::DFTraversal(string &v)
{
Vertex *walker;
if(!first)
{
cout << "No Graph" << endl;
return;
}
walker = first;
while(walker)
{
walker->visited = 0;
walker = walker->pNextVert;
}
walker = first;
while(walker)
{
if(walker->visited < 2)
{
if(walker->visited < 1)
{
}
}
}
}
//template <class V, class W>
void Graph::GetGraph()
{
Edge edge;
Vertex V;
string vName;
cout << "Enter the the file location" << endl;
cin >> inFileName;
inFile.open(inFileName.c_str());
if (!inFile.is_open()) //test for file
{
cerr << "Cannot open file: " << inFileName << endl;
getche();
return;
}
while(!inFile.eof()) //loop through untill end of file
{ //cout << "hi" << endl;
inFile >> V.name;
g.push_front(V);
// Loop until # is inFiled - the next inFile will either be another V or eof
}// end obtain info
//cout << "hi" << endl;
inFile.close();
inFile.clear();
// Reopen file - load edges
inFile.open(inFileName.c_str());
if (!inFile.is_open()) //test for file
{
cerr << "Cannot open file: " << inFileName << endl;
getche();
}
while(!inFile.eof())
{
inFile >> vName;
// Find matching Vertex V
// Find the ptr to Vert
// Loop thru edge-list
inFile >> edge.name;
inFile >> edge.weight;
V.edgelist.push_front(edge);
}
inFile.close();//close infile
}
void main()
{
Graph g;
}
CornedBee
Originally Posted by Daved
