/** @file Graph.h */
#ifndef GRAPH_FLIGHTFINDER
#define GRAPH_FLIGHTFINDER
#include <iostream>
#include <fstream>
#include <sstream>
using namespace std;
//graph implementation
class FlightGraph
{
//A Node class to create pointer for graph implementation
class Node
{
public :
string name;
double cost;
Node * next;
// constructor
Node()
{
name=" ";
next=NULL;
}
};
int vertices;
int edges;
//vertex column pointer
Node * columns;
public :
//FlightGraph();
FlightGraph(int size);
~FlightGraph();
int getVertexNumbers();
bool isEmpty();
string ReturnName(int index);
int ReturnIndex(string name);
int ReturnWeight(double cost);
bool isVertex (string name);
bool isEdge (string name1, string name2);
void AddVertex(string name);
void DeleteVertex(string name);
void AddEdge(string name1, string name2);
void AddWeight(string name1, string name2, double cost);
void DeleteEdge(string name1, string name2);
void ModifyVertex(string name1, string name2);
void SaveRecord(string file);
void LoadRecord(string file);
void DisplayGraph();
};
#endif
#include "FlightFinderGraph.h"
//FlightGraph :: FlightGraph(){}
//overloaded constructor
FlightGraph :: FlightGraph(int size)
{
vertices=size;
edges=0;
columns = new Node[vertices];
cout << "" << endl;
}
//destructor
FlightGraph :: ~FlightGraph()
{
for (int i=0 ; i<vertices ; i++)
{
Node * cur = columns[i].next;
Node * temp = cur;
while(temp != NULL)
{
cur = temp;
temp = cur -> next;
delete cur;
}
delete [] columns;
columns = NULL;
cout <<"Destructor -> Flight Finder Graph is destroyed." << endl;
}
}
int FlightGraph :: getVertexNumbers()
{
return vertices;
}
bool FlightGraph :: isEmpty()
{
if (vertices == 0)
return true;
else
return false;
}
string FlightGraph :: ReturnName(int index)
{
if(columns[index].name!="")
return columns[index].name;
else
return "";
}
int FlightGraph :: ReturnIndex(string name)
{
for (int i=0; i<vertices; i++)
{
if (columns[i].name == name)
return i;
}
return -1;
}
/*int FlightGraph :: ReturnWeight(double cost)
{
for (int i=0; i<vertices; i++)
{
if (columns[i].cost == cost)
return i;
}
return -1;
} */
bool FlightGraph :: isVertex(string name)
{
for (int i=0; i< vertices; i++)
{
if (columns[i].name == name)
return true;
}
return false;
}
bool FlightGraph :: isEdge(string name1, string name2)
{
if (isVertex (name1) && isVertex (name2))
{
for (int i=0; i< vertices; i++)
{
if (columns[i].name == name1)
{
if (columns[i].next != NULL)
{
Node * cur = columns[i].next;
while(cur != NULL)
{
if(cur -> name == name2)
return true;
cur = cur -> next;
}
}
}
}
}
return false;
}
void FlightGraph :: AddVertex(string name)
{
vertices++;
Node * newColumn = new Node [vertices];
for (int i =0; i< vertices-1; i++)
{
newColumn[i].next = columns[i].next;
newColumn[i].name = columns[i].name;
}
newColumn[vertices-1].name = name;
Node * tempColumn = columns;
columns = newColumn;
newColumn = tempColumn;
delete [] newColumn;
newColumn = NULL;
cout <<"The departure is added."<< endl;
}
void FlightGraph :: DeleteVertex(string name)
{
// if there is not the vertex
if (!isVertex(name))
{
cout << "The departure does not exist!" << endl;
return;
}
// delete the edges first
for (int i=0; i<vertices; i++)
{
if (isEdge(columns[i].name,name))
DeleteEdge(columns[i].name,name);
if (isEdge(name,columns[i].name))
DeleteEdge(name,columns[i].name);
}
// a new coloumn
vertices--;
Node * newColumn = new Node[vertices];
// copy the column to new column
for (int i=0, j=0; i<=vertices; i++)
{
// skip the deleted node
if (columns[i].name!=name)
{
newColumn[j].next=columns[i].next;
newColumn[j].name=columns[i].name;
j++;
}
}
// swap the content of the columns
Node * tempColumn = columns;
columns = newColumn;
newColumn = tempColumn;
// delete the newColumn
delete[] newColumn;
newColumn = NULL;
cout << "Departure is deleted." << endl;
}
void FlightGraph :: AddEdge(string name1, string name2)
{
bool EdgeExists = false;
for (int i = 0; i< vertices; i++)
{
if (columns[i].name == name2)
{
EdgeExists = true;
}
}
if (EdgeExists == false)
{
cout << "The flight does not exist! " << endl;
return;
}
for (int i=0; i< vertices; i++)
{
if (columns[i].name == name1)
{
Node * newEdge = new Node;
newEdge->name=name2;
if(columns[i].next == NULL)
{
columns[i].next=newEdge;
}
else
{
Node * cur = columns[i].next;
while(cur -> next !=NULL)
cur = cur -> next;
cur -> next = newEdge;
}
edges++;
cout << "The flight is added!" << endl;
return;
}
}
}
void FlightGraph :: DeleteEdge(string name1, string name2)
{
bool ifEdgeExists=0;
// check if the second edge exists
for (int i=0; i<vertices; i++)
{
if (columns[i].name == name2)
{
ifEdgeExists=1;
}
}
// if it is not in the list
if (ifEdgeExists==0)
{
cout << "The flight does not exist!" << endl;
return;
}
for (int i=0; i<vertices; i++)
{
// find the name1 in the column
if (columns[i].name == name1)
{
// if the list is empty
if (columns[i].next == NULL)
{
cout << "The flight does not exist!" << endl;
return;
}
// use two pointers
Node * current = columns[i].next;
Node * previous = columns[i].next;
// for the first edge
if (current->name == name2)
{
current = current->next;
columns[i].next=current;
delete previous;
previous = NULL;
edges--;
cout << "The flight is deleted." << endl;
return;
}
// for other edges
else
{
current = current->next;
while (current != NULL)
{
// check the name is found
if (current->name == name2)
{
previous->next = current->next;
delete current;
current = NULL;
edges--;
cout << "The flight is deleted." << endl;
return;
}
// go one more node ahead
previous = current;
current = current->next;
}
}
}
}
// if it is not in the list
cout << "The flight does not exist!" << endl;
}
// modify vertex name with the name
void FlightGraph :: ModifyVertex(string name1, string name2)
{
Node * cur;
bool VertexExists=false;
// check the first name is valid
for (int i=0; i<vertices; i++)
{
if (columns[i].name == name1)
VertexExists=true;
}
// if the vertex is not found
if (VertexExists == false)
{
cout << "The first name is not valid!" << endl;
return;
}
// check the second name is not repeated
for (int i=0; i<vertices; i++)
{
if (columns[i].name == name2)
{
cout << "The second name is repeated!" << endl;
return;
}
}
// look for the name in all indices
for (int i=0; i<vertices; i++)
{
// check if there is any edge
if (columns[i].next != NULL)
{
cur = columns[i].next;
// go to all the edges
while (cur != NULL)
{
// change the edge name
if (cur->name == name1)
cur->name = name2;
// go to next edge
cur = cur->next;
}
}
if (columns[i].name == name1)
{
columns[i].name = name2;
cout << "The departure name changed to " << name2 << endl;
}
}
}
void FlightGraph :: SaveRecord(string file)
{
ofstream outfile;
outfile.open(file.c_str());
//save the vertices number
outfile << vertices;
outfile << endl << endl;
//save the vertices
for (int i=0; i< vertices; i++)
{
outfile << i << ' ' ;
outfile << columns[i].name << endl;
}
//save the edges
for(int i=0;i<vertices;i++)
{
outfile << i << ' ';
if (columns[i].next != NULL)
{
Node * cur = columns[i].next;
while (cur != NULL)
{
outfile << ReturnIndex(cur -> name) << ' ';
cur = cur -> next;
}
}
outfile << endl;
}
outfile.close();
cout << "The Flight Grpah is saved. " << endl;
}
void FlightGraph :: LoadRecord(string file)
{
ifstream infile;
int size,index;
string input;
infile.open(file.c_str());
if (infile.is_open())
{
infile>>size;
getline(infile,input);
getline(infile,input);
//loading the vertices
for(int i=1;i<size;i++)
{
getline(infile,input);
input = input.substr(2);
if(input[1] == ' ')
input = input.substr(2);
AddVertex(input);
}
getline(infile,input);
// loading the edges
for(int i=1; i<vertices; i++)
{
getline(infile, input);
stringstream ss(input);
ss >> size;
// add edge to the graph
while(ss >> index)
{
AddEdge(ReturnName(i), ReturnName(index));
}
}
}
else
{
cout << "Error opening file.";
return;
}
infile.close();
cout << "The graph is loaded." << endl;
}
void FlightGraph :: DisplayGraph()
{
Node * cur;
cout <<endl;
cout <<"---------------------------------"<<endl;
cout <<" Departure List "<<endl;
cout <<"---------------------------------"<<endl;
for (int i=0; i<vertices; i++)
{
cout << i << " " << columns[i].name << endl;
}
cout << "--------------------------------"<<endl<<endl;
cout << endl;
cout << "================================"<<endl;
cout << " Flight List "<<endl;
cout << "================================"<<endl;
cout << "Number of Countries served : " << getVertexNumbers() <<endl;
for (int i=0; i<vertices; i++)
{
cout << columns[i].name;
// show the edges if it is not empty
if (columns[i].next !=NULL)
{
cur = columns[i].next;
while (cur != NULL)
{
// show all the edges
cout << " --- " << cur->name;
cur = cur->next;
}
}
cout << endl;
}
cout << "================================" << endl << endl;
}
jingxian.fs 0 Newbie Poster
jingxian.fs 0 Newbie Poster
sfuo 111 Practically a Master Poster
Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster
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.