Problem Statement:- Write a C++ program to implement topological sorting on graph using object-oriented programming features. Design necessary class (Use of Graph).
Note:- Scroll horizontally to see the full line of code.
#include <iostream>
using namespace std;
class flagarray {
char data;
int flag;
public:
flagarray() {
this->data = '*';
this->flag = 0;
}
flagarray(char data, int flag) {
this->data = data;
this->flag = flag;
}
friend class node;
friend class graph;
friend class stack;
};
class stack {
int top = -1;
char arr[30];
public:
bool isFull();
bool isEmpty();
void push(char data);
char Top();
char pop();
};
void stack::push(char data) {
if (!isFull()) {
top++;
arr[top] = data;
} else {
cout << "Stack is full!!! in push" << endl;
}
}
char stack::Top() {
if (!isEmpty()) {
return arr[top];
} else {
cout << "Stack is Empty!!!" << endl;
return '*';
}
}
bool stack::isFull() {
return (top >= 29);
}
bool stack::isEmpty() {
return (top == -1);
}
char stack::pop() {
if (!isEmpty()) {
return arr[top--];
} else {
cout << "Stack is Empty!!!" << endl;
return '*';
}
}
class node {
char data;
node *next;
public:
node(char data) {
this->data = data;
next = NULL;
}
friend class graph;
};
class graph {
node **head;
flagarray *visited;
int indexForVisited = -1;
int vertexCount;
stack nodeStack;
public:
graph(int vertexCount) {
this->vertexCount = vertexCount;
head = new node*[vertexCount];
visited = new flagarray[vertexCount];
for (int i = 0; i < vertexCount; i++) {
head[i] = NULL;
}
}
void createGraph();
int indexInVisited(char data);
void displayGraph();
void topological();
void topologicalSort(char v);
int indexInHead(char data);
void printVisited();
};
void graph::printVisited() {
for (int i = 0; i < vertexCount; i++) {
cout << visited[i].data << " : " << visited[i].flag << endl;
}
}
int graph::indexInHead(char data) {
for (int i = 0; i < vertexCount; i++) {
if (head[i]) {
if (head[i]->data == data) {
return i;
}
}
}
return -1;
}
int graph::indexInVisited(char data) {
for (int i = 0; i < vertexCount; i++) {
if (visited[i].data == data) {
return i;
}
}
return -1;
}
void graph::createGraph() {
int n;
cout << "Enter the no. of Edges: ";
cin >> n;
for (int i = 0; i < n; i++) {
cout << "Edge " << i + 1 << " : " << endl;
char src, dest;
cout << "Enter source node of edge: ";
cin >> src;
cout << "Enter destination node of edge: ";
cin >> dest;
if (!head[0]) {
head[0] = new node(src);
visited[++indexForVisited].data = src;
head[0]->next = new node(dest);
visited[++indexForVisited].data = dest;
} else {
int index1 = -1;
int index = 0;
while (head[index] && index < vertexCount) {
if (head[index]->data == src) {
index1 = index;
}
index++;
}
if (index1 == -1) {
int j = 0;
while (head[j]) {
j++;
}
head[j] = new node(src);
if (indexInVisited(src) == -1) {
visited[++indexForVisited].data = src;
}
head[j]->next = new node(dest);
if (indexInVisited(dest) == -1) {
visited[++indexForVisited].data = dest;
}
} else {
node *current = head[index1];
while (current->next) {
current = current->next;
}
current->next = new node(dest);
if (indexInVisited(dest) == -1) {
visited[++indexForVisited].data = dest;
}
}
}
}
}
void graph::displayGraph() {
if (head[0]) {
for (int i = 0; i < vertexCount; i++) {
if (head[i]) {
node *current = head[i];
cout << current->data;
if (current->next) {
current = current->next;
}
while (current) {
cout << " --> " << current->data;
current = current->next;
}
cout << endl;
}
}
} else {
cout << "Graph is Empty!!!" << endl;
}
}
void graph::topological() {
for (int i = 0; i < vertexCount; i++) {
if (visited[i].flag == 0) {
topologicalSort(visited[i].data);
}
}
while (!nodeStack.isEmpty()) {
cout << nodeStack.pop() << " ";
}
}
void graph::topologicalSort(char v) {
visited[indexInVisited(v)].flag = 1;
int index = indexInHead(v);
if (index != -1) {
node *current = head[index];
while (current) {
if (!visited[indexInVisited(current->data)].flag) {
topologicalSort(current->data);
}
current = current->next;
}
}
nodeStack.push(v);
}
int main() {
int n;
cout << "Enter the no. of Vertices: ";
cin >> n;
graph k(n);
k.createGraph();
char cont = 'y';
while (cont == 'y')
{
cout << "<--------Menu-------->" << endl;
cout << "1. Show Adjacency List" << endl;
cout << "2. Show Topological Sort" << endl;
int choice;
cout << "Enter the choice: ";
cin >> choice;
switch (choice)
{
case 1:
cout << "Adjacency List for Graph : " << endl;
k.displayGraph();
break;
case 2:
cout << "Topological Sort : " << endl;
k.topological();
cout << endl;
break;
default:
cout << "Invalid Choice!!!" << endl;
break;
}
cout << "Do you want to continue ? (y/n) : ";
cin >> cont;
}
cout << "Program Ended Successfully!!!" << endl;
}
Comments
Post a Comment