There are flight paths between cities. If there is a flight between city A and city B then there is an edge between the cities. The cost of the edge can be the time that flight takes to reach city B from A, or the amount of fuel used for the journey. Represent this as a graph. The node can be represented by airport name or name of the city. Use adjacency list representation of the graph or use adjacency matrix representation of the graph. Justify the storage representation used.(Operation to be performed adding and deleting edge, adding and deleting vertices, calculated in-degree and out-degree for directed graph and and degree of a node for undirected graph, Use any traversal to traverse graph)

	/*
	* Graph.cpp
	*
	* Created on: Mar 17, 2019
	* Author: iamrohitsuthar
	*/
	#include<iostream>
	const int MAX=20;
	using namespace std;
	class Node {
	string city;
	int time;
	Node* next;
	public:
	Node() {
	city="";
	time=0;
	next=NULL;
	}
	Node(string city,int time) {
	this->time=time;
	this->city=city;
	next=NULL;
	}
	friend class Graph;
	};
	class HeadNode {
	string city;
	Node* next;
	HeadNode* down;
	bool visit;
	public:
	HeadNode() {
	city="";
	next=NULL;
	down=NULL;
	visit=false;
	}
	HeadNode(string city) {
	this->city=city;
	next=NULL;
	down=NULL;
	visit=false;
	}
	string getCity() {
	return city;
	}
	friend class Graph;
	};
	class Graph {
	HeadNode* head;
	public:
	Graph() {
	head=NULL;
	}
	HeadNode* getHead() {
	return head;
	}
	void create_city(string city) {
	HeadNode* temp;
	HeadNode* temp1;
	temp=new HeadNode(city);
	if(head == NULL) {
	head=temp;
	}
	else if(head->city == city) {
	return;
	}
	else {
	temp1=head;
	while(temp1->down != NULL && temp1->down->city != city) {
	temp1=temp1->down;
	}
	if(temp1->down == NULL)
	temp1->down=temp;
	}
	cout<<"city added"<<endl;
	}
	void add_flight(string a,string b,int time) {
	HeadNode* main;
	HeadNode* temp1=NULL;
	Node* node;
	if(a==b) {
	cout<<"You cannot add flight between same city"<<endl;
	return;
	}
	main=findCity(a);
	if(main != NULL) {
	temp1=findCity(b);
	if(temp1 != NULL) {
	Node* temp=new Node(b,time);
	if(main->next == NULL) {
	main->next=temp;
	}
	else {
	node=main->next;
	while(node->next !=NULL) {
	node=node->next;
	}
	node->next=temp;
	}
	cout<<"Flight added"<<endl;
	}
	else
	cout<<"city "<<b<<" is not found"<<endl;
	}
	else {
	cout<<"city "<<a<<" is not found"<<endl;
	}
	}
	HeadNode* findCity(string name) {
	HeadNode* temp=head;
	while(temp != NULL) {
	if(temp->city == name) {
	break;
	}
	temp=temp->down;
	}
	return temp;
	}
	Node* findChild(HeadNode* hdnode,string name) {
	Node* temp=hdnode->next;
	while(temp != NULL) {
	if(temp->city == name) {
	break;
	}
	temp=temp->next;
	}
	return temp;
	}
	void DFS(string city) {
	HeadNode* temp;
	Node* child;
	temp=findCity(city);
	cout<<temp->city<<endl;
	temp->visit=true;
	child=temp->next;
	while(child != NULL) {
	if(!findCity(child->city)->visit)
	DFS(child->city);
	child=child->next;
	}
	}
	void traverse() {
	HeadNode* hdnode=head;
	Node* node;
	while(hdnode != NULL) {
	node=hdnode->next;
	while(node != NULL) {
	cout<<hdnode->city<<" "<<node->city<<"\t"<<node->time<<endl;
	node=node->next;
	}
	hdnode=hdnode->down;
	}
	}
	void ResetValues() {
	HeadNode* temp=head;
	while(temp != NULL) {
	temp->visit=false;
	temp=temp->down;
	}
	}
	void delete_flights(Node* node) {
	if(node == NULL)
	return;
	delete_flights(node->next);
	delete node;
	}
	void inDegree(HeadNode* head) {
	while(head != NULL) {
	cout<<head->city<<" : "<<getInDegreeOfNode(head)<<endl;
	head=head->down;
	}
	}
	int getInDegreeOfNode(HeadNode* curr) {
	int count=0;
	HeadNode* hnode=head;
	Node* node;
	while(hnode != NULL) {
	if(hnode->city != curr->city) {
	node=hnode->next;
	while(node != NULL) {
	if(node->city == curr->city)
	count++;
	node=node->next;
	}
	}
	hnode=hnode->down;
	}
	return count++;
	}
	void outDegree(HeadNode* head) {
	while(head != NULL) {
	cout<<head->city<<": "<<getOutDegreeOfNode(head)<<endl;
	head=head->down;
	}
	}
	int getOutDegreeOfNode(HeadNode* curr) {
	int count=0;
	Node* temp;
	if(curr->next != NULL) {
	temp=curr->next;
	while(temp != NULL) {
	count++;
	temp=temp->next;
	}
	}
	return count;
	}
	void delete_city(string city) {
	HeadNode* hnode=head;
	while(hnode != NULL) {
	if(hnode->city==city)
	break;
	hnode=hnode->down;
	}
	cout<<"Found..."<<hnode->city<<endl;
	if(hnode != NULL) {
	//delete all flights first from city which is going to deleted
	delete_flights(hnode->next);
	//delete flights which come to the deleted city from other cities
	delete_incoming_flights(hnode->city);
	if(hnode==head && hnode->down == NULL) {
	delete hnode;
	head=NULL;
	}
	// else if(hnode->down == NULL) {
	// HeadNode* before=findHeadNodeBefore(hnode);
	// delete hnode;
	// before->down=NULL;
	// }
	else if(hnode->down != NULL && hnode==head) {
	head=hnode->down;
	delete hnode;
	}
	else {
	HeadNode* before=findHeadNodeBefore(hnode);
	before->down=hnode->down;
	delete hnode;
	}
	cout<<"city deleted"<<endl;
	}
	else
	cout<<"City not found"<<endl;
	}
	void delete_incoming_flights(string city) {
	HeadNode* hnode=head;
	Node* node;
	while(hnode != NULL) {
	node=hnode->next;
	while(node != NULL) {
	if(node->city == city) {
	delete_flight(hnode->city,node->city);
	}
	node=node->next;
	}
	hnode=hnode->down;
	}
	}
	void delete_flight(string from,string to) {
	HeadNode* main;
	HeadNode* temp1=NULL;
	main=findCity(from);
	if(main != NULL) {
	temp1=findCity(to);
	if(temp1 != NULL) {
	if(main->next == NULL) {
	cout<<"There is no flight from "<<from<<" city"<<endl;
	}
	else {
	Node* child=findChild(main,to);
	if(child == NULL) {
	cout<<"There is no flight from "<<from<<" to "<<to<<endl;
	return;
	}
	if(main->next==child) {
	main->next=child->next;
	delete child;
	}
	// else if(child->next==NULL) {
	// //last node
	// Node* before=findNodeBefore(main,child);
	// delete child;
	// before->next=NULL;
	// }
	// else if(child->next != NULL && main->next == child) {
	// main->next=child->next;
	// delete child;
	// }
	else {
	//middle node
	Node* before=findNodeBefore(main,child);
	before->next=child->next;
	delete child;
	}
	cout<<"Flight deleted"<<endl;
	}
	}
	else
	cout<<"city "<<to<<" is not found"<<endl;
	}
	else
	cout<<"city "<<from<<" is not found"<<endl;
	}
	HeadNode* findHeadNodeBefore(HeadNode* node) {
	HeadNode* temp=head;
	while(temp->down != NULL) {
	if(temp->down == node) {
	break;
	}
	temp=temp->down;
	}
	return temp;
	}
	Node* findNodeBefore(HeadNode* hdnode,Node* node) {
	Node* temp=hdnode->next;
	while(temp->next != NULL) {
	if(temp->next == node)
	break;
	temp=temp->next;
	}
	return temp;
	}
	};
	int main() {
	Graph g;
	int time;
	string city,city1;
	char ch;
	int choice;
	// g.create_city("m");
	// g.create_city("p");
	// g.create_city("a");
	// g.create_city("s");
	// g.create_city("n");
	//
	// g.add_flight("m","p",12);
	// g.add_flight("p","s",45);
	// g.add_flight("s","a",32);
	// g.add_flight("s","n",78);
	// g.add_flight("m","n",79);
	// g.add_flight("n","a",12);
	// g.add_flight("p","a",45);
	// g.add_flight("s","a",32);
	do {
	cout<<"1. Add new city \n";
	cout<<"2. Add Flight \n";
	cout<<"3. DFS \n";
	cout<<"4. Outdegree of all nodes \n";
	cout<<"5. Indegree of all nodes \n";
	cout<<"6. Delete City \n";
	cout<<"7. Delete Flight \n";
	cout<<"8. Outdegree of specific node \n";
	cout<<"9. Indegree of specific node \n";
	cout<<"Enter your choice: ";
	cin>>choice;
	switch(choice) {
	case 1: cout<<"Enter city name: ";
	cin>>city;
	g.create_city(city);
	break;
	case 2: cout<<"Enter source city: ";
	cin>>city;
	cout<<"Enter destination city: ";
	cin>>city1;
	cout<<"Enter required time: ";
	cin>>time;
	g.add_flight(city,city1,time);
	break;
	case 3: g.DFS(g.getHead()->getCity());
	g.ResetValues();
	//g.traverse();
	break;
	case 4: g.outDegree(g.getHead());
	break;
	case 5: g.inDegree(g.getHead());
	break;
	case 6: cout<<"Enter city name to delete: ";
	cin>>city;
	g.delete_city(city);
	break;
	case 7: cout<<"Enter source city: ";
	cin>>city;
	cout<<"Enter destination city: ";
	cin>>city1;
	g.delete_flight(city,city1);
	break;
	case 8: cout<<"Enter city name: ";
	cin>>city;
	cout<<"Outdegree is: "<<g.getOutDegreeOfNode(g.findCity(city))<<endl;
	break;
	case 9: cout<<"Enter city name: ";
	cin>>city;
	cout<<"Indegree is: "<<g.getInDegreeOfNode(g.findCity(city))<<endl;
	break;
	}
	cout<<"Do you want to continue (Y/N): ";
	cin>>ch;
	}while(ch == 'Y' || ch=='y');
	return 0;
	}

view raw Graph.cpp hosted with ❤ by GitHub