Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<stdlib.h>
- #include <iostream>
- #include <fstream>
- #include<math.h>
- #include <bits/stdc++.h>
- using namespace std;
- #define NULL_VALUE -999999
- #define INFINITY 999999
- #define WHITE 1
- #define GREY 2
- #define BLACK 3
- #define MAX_HEAP_SIZE 100000
- #define MAXREAL 999999.0
- class Queue
- {
- int queueInitSize ;
- int queueMaxSize;
- int * data;
- int length;
- int front;
- int rear;
- public:
- Queue();
- ~Queue();
- void enqueue(int item); //insert item in the queue
- int dequeue(); //returns the item according to FIFO
- bool empty(); //return true if Queue is empty
- };
- Queue::Queue()
- {
- queueInitSize = 2 ;
- queueMaxSize = queueInitSize;
- data = new int[queueMaxSize] ; //allocate initial memory
- length = 0 ;
- front = 0;
- rear = 0;
- }
- void Queue::enqueue(int item)
- {
- if (length == queueMaxSize)
- {
- int * tempData ;
- //allocate new memory space for tempList
- queueMaxSize = 2 * queueMaxSize ;
- tempData = new int[queueMaxSize] ;
- int i, j;
- j = 0;
- for( i = rear; i < length ; i++ )
- {
- tempData[j++] = data[i] ; //copy items from rear
- }
- for( i = 0; i < rear ; i++ )
- {
- tempData[j++] = data[i] ; //copy items before rear
- }
- rear = 0 ;
- front = length ;
- delete[] data ; //free the memory allocated before
- data = tempData ; //make list to point to new memory
- }
- data[front] = item ; //store new item
- front = (front + 1) % queueMaxSize ;
- length++ ;
- }
- bool Queue::empty()
- {
- if(length == 0) return true ;
- else return false ;
- }
- int Queue::dequeue()
- {
- if(length == 0) return NULL_VALUE ;
- int item = data[rear] ;
- rear = (rear + 1) % queueMaxSize ;
- length-- ;
- return item ;
- }
- Queue::~Queue()
- {
- if(data) delete[] data; //deallocate memory
- data = 0; //set to NULL
- }
- //****************Queue class ends here************************
- //****************Dynamic ArrayList class based************************
- class ArrayList
- {
- int * list;
- int length ;
- int listMaxSize ;
- int listInitSize ;
- public:
- ArrayList() ;
- ~ArrayList() ;
- int searchItem(int item) ;
- void insertItem(int item) ;
- void removeItem(int item) ;
- void removeItemAt(int item);
- int getItem(int position) ;
- int getLength();
- bool empty();
- void printList();
- } ;
- ArrayList::ArrayList()
- {
- listInitSize = 2 ;
- listMaxSize = listInitSize ;
- list = new int[listMaxSize] ;
- length = 0 ;
- }
- void ArrayList::insertItem(int newitem)
- {
- int * tempList ;
- if (length == listMaxSize)
- {
- //allocate new memory space for tempList
- listMaxSize = 2 * listMaxSize ;
- tempList = new int[listMaxSize] ;
- int i;
- for( i = 0; i < length ; i++ )
- {
- tempList[i] = list[i] ; //copy all items from list to tempList
- }
- delete[] list ; //free the memory allocated before
- list = tempList ; //make list to point to new memory
- };
- list[length] = newitem ; //store new item
- length++ ;
- }
- int ArrayList::searchItem(int item)
- {
- int i = 0;
- for (i = 0; i < length; i++)
- {
- if( list[i] == item ) return i;
- }
- return NULL_VALUE;
- }
- void ArrayList::removeItemAt(int position) //do not preserve order of items
- {
- if ( position < 0 || position >= length ) return ; //nothing to remove
- list[position] = list[length-1] ;
- length-- ;
- }
- void ArrayList::removeItem(int item)
- {
- int position;
- position = searchItem(item) ;
- if ( position == NULL_VALUE ) return ; //nothing to remove
- removeItemAt(position) ;
- }
- int ArrayList::getItem(int position)
- {
- if(position < 0 || position >= length) return NULL_VALUE ;
- return list[position] ;
- }
- int ArrayList::getLength()
- {
- return length ;
- }
- bool ArrayList::empty()
- {
- if(length==0)return true;
- else return false;
- }
- void ArrayList::printList()
- {
- int i;
- for(i=0; i<length; i++)
- printf("%d ", list[i]);
- printf("Current size: %d, current length: %d\n", listMaxSize, length);
- }
- ArrayList::~ArrayList()
- {
- if(list) delete [] list;
- list = 0 ;
- }
- //******************ArrayList class ends here*************************
- //******************Graph class starts here**************************
- class Graph
- {
- public:
- int nVertices, nEdges ;
- bool directed ;
- ArrayList * adjList ;
- //define other variables required for bfs such as color, parent, and dist
- //you must use pointers and dynamic allocation
- int *color;
- int *dist;
- int *parent;
- int time;
- int *discoveryTime;
- int *finishTime;
- int **weightArray;
- int **distance;
- int **path;
- Graph(bool dir = false);
- ~Graph();
- void setnVertices(int n);
- void addEdge(int u, int v);
- void removeEdge(int u, int v);
- bool isEdge(int u, int v);
- int getDegree(int u);
- bool hasCommonAdjacent(int u, int v);
- int getDist(int u, int v);
- void printGraph();
- void bfs(int source); //will run bfs in the graph
- void dfs(); //will run dfs in the graph
- void dfs_visit(int u);
- void makeTranspose();
- void makeUndirected();
- void FloydWarshallAlgo();
- };
- Graph::Graph(bool dir)
- {
- nVertices = 0 ;
- nEdges = 0 ;
- adjList = 0 ;
- directed = dir ; //set direction of the graph
- color = 0;
- dist = 0;
- parent = 0;
- discoveryTime = 0;
- finishTime = 0;
- //define other variables to be initialized
- }
- void Graph::setnVertices(int n)
- {
- this->nVertices = n ;
- if(adjList!=0) delete[] adjList ; //delete previous list
- adjList = new ArrayList[nVertices] ;
- weightArray = (int **) malloc(nVertices * sizeof(int *));
- for (int i = 0; i < nVertices; i++)
- {
- weightArray[i] = (int *) malloc(nVertices * sizeof(int));
- }
- for (int i = 0; i < nVertices; i++){
- for(int j=0;j<nVertices;j++)
- {
- if(i==j) weightArray[i][j] = 0;
- else weightArray[i][j] = 99999;
- }
- }
- distance = (int **) malloc(nVertices * sizeof(int *));
- for (int i = 0; i < nVertices; i++)
- {
- distance[i] = (int *) malloc(nVertices * sizeof(int));
- }
- for (int i = 0; i < nVertices; i++){
- for(int j=0;j<nVertices;j++)
- {
- if(i==j) distance[i][j] = 0;
- else distance[i][j] = 99999;
- }
- }
- path = (int **) malloc(nVertices * sizeof(int *));
- for (int i = 0; i < nVertices; i++)
- {
- path[i] = (int *) malloc(nVertices * sizeof(int));
- }
- for (int i = 0; i < nVertices; i++){
- for(int j=0;j<nVertices;j++)
- {
- path[i][j] = 99999;
- }
- }
- parent = new int[nVertices];
- }
- void Graph::addEdge(int u, int v)
- {
- if(u<0 || v<0 || u>=nVertices || v>=nVertices) return; //vertex out of range
- this->nEdges++ ;
- adjList[u].insertItem(v) ;
- if(!directed) adjList[v].insertItem(u) ; //undirected holee
- }
- void Graph::removeEdge(int u, int v)
- {
- if(u<0 || v<0 || u>=nVertices || v>=nVertices) return; //vertex out of range
- adjList[u].removeItem(v) ;
- this->nEdges-- ;
- if(!directed) adjList[v].removeItem(u) ;
- }
- bool Graph::isEdge(int u, int v)
- {
- //returns true if (u,v) is an edge, otherwise should return false
- if(u<0 || v<0 || u>=nVertices || v>=nVertices) return false; //vertex out of range
- int p = adjList[u].searchItem(v) ;
- int q = adjList[v].searchItem(u) ;
- printf("p= %d and q = %d",p,q);
- if (p==NULL_VALUE && q==NULL_VALUE)
- {
- printf("false\n");
- return false;
- }
- else
- {
- printf("true\n");
- return true;
- }
- }
- int Graph::getDegree(int u)
- {
- if(u<0 || u>=nVertices ) return NULL_VALUE;
- return adjList[u].getLength();
- //returns the degree of vertex u
- }
- bool Graph::hasCommonAdjacent(int u, int v)
- {
- //returns true if vertices u and v have common adjacent vertices
- int N = adjList[u].getLength();
- int a[N];
- for(int j=0; j<adjList[u].getLength(); j++)
- {
- a[j] = adjList[u].getItem(j);
- }
- int c = 0;
- for(int k=0; k<adjList[u].getLength(); k++)
- {
- for(int j=0; j<adjList[v].getLength(); j++)
- {
- if( adjList[u].getItem(k) == adjList[v].getItem(j))
- {
- c++;
- }
- }
- }
- if(c>0) return true;
- else return false;
- }
- void Graph::bfs(int source)
- {
- //complete this function
- //initialize BFS variables
- color = new int[nVertices];
- dist = new int[nVertices];
- parent = new int[nVertices];
- int p;
- for(int i=0; i<nVertices; i++)
- {
- color[i] = WHITE ;
- parent[i] = -1 ;
- dist[i] = INFINITY ;
- }
- Queue q ;
- color[source] = GREY;
- dist[source] = 0 ;
- q.enqueue(source) ;
- while( !q.empty() )
- {
- p = q.dequeue();
- for(int j = 0; j< adjList[p].getLength(); j++)
- {
- if(color[adjList[p].getItem(j)]==WHITE)
- {
- color[adjList[p].getItem(j)] = GREY;
- dist[adjList[p].getItem(j)] = dist[p] + 1;
- parent[adjList[p].getItem(j)] = p;
- q.enqueue(adjList[p].getItem(j)) ;
- }
- color[p] = BLACK;
- }
- }
- for(int i=0; i<nVertices; i++) printf("%d",color[i]);
- }
- void Graph::dfs()
- {
- color = new int[nVertices];
- parent = new int[nVertices];
- discoveryTime = new int[nVertices];
- finishTime = new int[nVertices];
- for(int i=0; i<nVertices; i++)
- {
- color[i] = WHITE ;
- parent[i] = -1 ;
- }
- time = 0;
- for(int u = 0; u< nVertices; u++)
- {
- if(color[u]==WHITE)
- {
- dfs_visit(u);
- }
- }
- for(int i = 0; i< nVertices; i++)
- {
- printf("Vertex: %d ->dist: %d ->finishing time: %d\n",i,discoveryTime[i],finishTime[i]);
- }
- }
- void Graph::dfs_visit(int u)
- {
- //write this function
- time = time + 1 ;
- discoveryTime[u] = time;
- color[u] = GREY;
- for(int j = 0; j< adjList[u].getLength(); j++)
- {
- if(color[adjList[u].getItem(j)]==WHITE)
- {
- parent[adjList[u].getItem(j)] = u;
- dfs_visit(adjList[u].getItem(j));
- }
- }
- color[u] = BLACK;
- time = time +1;
- finishTime[u] = time;
- }
- int Graph::getDist(int u, int v)
- {
- //returns the shortest path distance from u to v
- //must call bfs using u as the source vertex, then use distance array to find the distance
- bfs(u) ;
- return dist[v];
- }
- void Graph::FloydWarshallAlgo(){
- for (int i = 0; i < nVertices ; i++){
- for (int j = 0; j < nVertices; j++){
- distance[i][j] = weightArray[i][j];
- if (distance[i][j] != 99999 && i != j) {
- path[i][j] = i;
- } else {
- path[i][j] = -1;
- }
- }
- }
- for(int k=0; k < nVertices; k++){
- for(int i=0; i <nVertices; i++){
- for(int j=0; j < nVertices; j++){
- if(distance[i][k] == 99999 || distance[k][j] == 99999) {
- continue;
- }
- if(distance[i][j] > distance[i][k] + distance[k][j]){
- distance[i][j] = distance[i][k] + distance[k][j];
- path[i][j] = path[k][j];
- }
- }
- }
- }
- for(int i = 0; i < nVertices; i++) {
- if(distance[i][i] < 0) {
- cout << "Negative cycle present" ;
- }
- }
- for (int i = 0; i < nVertices ; i++){
- for (int j = 0; j < nVertices; j++)
- {
- if(weightArray[i][j]==99999) cout<< "INF" <<" ";
- else
- cout<< weightArray[i][j]<<" ";
- }
- cout <<endl;
- }
- for (int i = 0; i < nVertices ; i++){
- for (int j = 0; j < nVertices; j++)
- {
- if(distance[i][j]==99999) cout<< "INF" <<" ";
- else cout << distance[i][j]<<" ";
- }
- cout << endl;
- }
- for (int i = 0; i < nVertices ; i++){
- for (int j = 0; j < nVertices; j++)
- {
- if(path[i][j]==-1) cout<< "INF" <<" ";
- else
- cout<< path[i][j]+1<<" ";
- }
- cout <<endl;
- }
- int i=0;
- int j=1;
- cout << "path between" << i+1 << " " << j+1<<endl;
- stack <int> Stack;
- Stack.push(j);
- cout << j+1<<" ";
- int a = i;
- int b = j;
- while (true) {
- b = path[a][b];
- if(b == -1) {
- return;
- }
- Stack.push(b);
- cout << b+1<<" ";
- if(b == a) {
- break;
- }
- }
- /// (u,v) edge thaktei hobe
- /// (p,q) er majhe notun path ber korte hobe jetate (u,v) thakbe
- int u=0;
- int v=2;
- int p=0;
- int q=3;
- // for (int i = 0; i < nVertices ; i++){
- // for (int j = 0; j < nVertices; j++){
- // distance[i][j] = weightArray[i][j];
- //
- // }
- //}
- for(int k=0; k < nVertices; k++){
- // if(distance[i][j] > distance[i][p] + distance[p][q]+distance[q][j]){
- distance[p][q] = distance[p][u] + weightArray[u][v]+distance[v][q];
- // path[i][j] = path[k][j];
- }
- cout << "dis: "<<distance[p][q];
- // for(int k=0; k < nVertices; k++){
- // if(distance[p][k] == 99999 || distance[k][q] == 99999) {
- // continue;
- // }
- // if(distance[p][q] > distance[p][u] +distance[u][v]+distance[v][q]){
- // distance[p][q] =distance[p][u] +distance[u][v]+distance[v][q];
- //
- // }
- // }
- // cout << "new dist: "<<distance[i][j];
- // while(!Stack.empty()){
- // int a = Stack.pop();
- // printf("%d ",a);
- // }
- }
- void Graph::printGraph()
- {
- printf("\nNumber of vertices: %d, Number of edges: %d\n", nVertices, nEdges);
- for(int i=0; i<nVertices; i++)
- {
- printf("%d:", i+1);
- for(int j=0; j<adjList[i].getLength(); j++)
- {
- printf(" %d", adjList[i].getItem(j)+1);
- }
- printf("\n");
- }
- }
- Graph::~Graph()
- {
- //write your destructor here
- delete [] color;
- delete [] dist;
- delete [] parent;
- delete [] finishTime;
- delete [] discoveryTime;
- delete [] adjList;
- }
- //**********************Graph class ends here******************************
- //******main function to test your code*************************
- int main(void)
- {
- int n,m;
- ifstream in ("testcasefloyd.txt");
- Graph g(true);
- int u,v,w;
- // scanf("%d", &n);
- in >> n;
- in >> m;
- g.setnVertices(n);
- // g.setnEdges(m);
- for(int i=0; i<m; i++)
- {
- in >> u;
- in >> v;
- in >> w;
- if ( g.weightArray[u-1][v-1]==-1)
- {
- g.weightArray[u-1][v-1] = w;
- if(g.directed==false) g.weightArray[v-1][u-1] = w;
- g.addEdge(u-1,v-1);
- }
- else if(g.weightArray[u-1][v-1]>w)
- {
- g.weightArray[u-1][v-1] = w;
- if(g.directed==false) g.weightArray[v-1][u-1] = w;
- g.addEdge(u-1,v-1);
- }
- }
- g.FloydWarshallAlgo();
- //g.printGraph();
- // Graph MST =
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement