Last active
September 26, 2019 07:25
-
-
Save thasan3003/cb1787c4b3959271ee692e8c79364bc3 to your computer and use it in GitHub Desktop.
This algorithm finds blocks in a graph. Detailed description is given in code as comment.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
==================================================== | |
################## Code Author ################## | |
==================================================== | |
Md. Tahmid Hasan | |
#tahmidhasan3003 | |
==================================================== | |
Code Title: Finding Block in a Graph.cpp | |
==================================================== | |
############## Algorithm Reference ############## | |
==================================================== | |
Book Title: Introduction to Graph Theory (2nd ed.) | |
Author: Douglas B. West | |
ISBN: 978-81-7758-741-8 | |
==================================================== | |
4.1.23.* Algorithm. (Computing the blocks of a graph) | |
Input: A connected graph G. (The blocks of a graph are the blocks of its components, which can be found by depth-first search, so we may assume that G is connected.) | |
Idea: Build a depth-first search tree T of G, discarding portions of T as blocks are identified. Maintain one vertex called ACTIVE. | |
Initialization: Pick a root x ∈ V(H); make x ACTIVE; set T = {x}. | |
Iteration: Let v denote the current active vertex. | |
1) If v has an unexplored incident edge vw, then | |
1A) If w ∉ V(T), then add vw to T, mark vw explored, make w ACTIVE. | |
1B) If W ∈ V(T), then w is an ancestor of v; mark vw explored. | |
2) If v has no more unexplored incident edges, then | |
2A) If v ≠ x, and w is the parent of v, make w ACTIVE. If no vertex in the current subtree T' rooted at v has an explored edge to an ancestor above w, then V(T') ∪ {w} is the vertex set of a block, record this information and delete V(T') from T. | |
2B) If v = x, terminate. | |
==================================================== | |
################ Important Notice ################ | |
==================================================== | |
Input Details:- | |
1st line: total number of vertex (V) | |
2nd line: total number of edges (E) | |
Next E lines: vertex of edges (u v) | |
Last line: start vertex (root) | |
(Here is given a sample) | |
==================================================== | |
filename: input.txt | |
(Put this .txt file in the same directory of source code. Content is given below.) | |
==================================================== | |
11 | |
13 | |
0 1 | |
0 3 | |
0 4 | |
0 8 | |
0 10 | |
1 2 | |
2 3 | |
4 5 | |
4 7 | |
4 10 | |
5 6 | |
6 7 | |
9 10 | |
10 | |
==================================================== | |
################## Coding Start ################## | |
==================================================== | |
*/ | |
#include<bits/stdc++.h> | |
using namespace std; | |
bool findConnection(int *adjMatrix, int *parentArray, int totalV, int node, int parent) //search connection to ancestor | |
{ | |
int ancestor = parentArray[parent]; | |
while(ancestor != -1) | |
{ | |
if(adjMatrix[ancestor*totalV+node] == 2) //2 means explored edge | |
return true; | |
ancestor = parentArray[ancestor]; | |
} | |
return false; | |
} | |
bool findBlock(int *adjMatrix, int *parentArray, int totalV, int root, int parent, stack<int>* blockPoints) | |
{ | |
if(findConnection(adjMatrix, parentArray, totalV, root, parent)) //find connection to ancestor | |
return true; | |
for(int i=0; i<totalV; i++) //find vertex in tree of root | |
if(parentArray[i] == root) //child found of root | |
if(findBlock(adjMatrix, parentArray, totalV, i, parent, blockPoints)) //call for child i | |
return true; | |
(*blockPoints).push(root); //consider as block point | |
parentArray[root] = -1; //parent -1 means not parent means delete from tree | |
return false; | |
} | |
int main() | |
{ | |
freopen("input.txt","r",stdin); | |
int totalV, totalE, totalBlocks=0, rootX, activeV, associateW, tempU, tempV, *adjMatrix, *parentArray, *cutVertexArray; | |
bool hasUnexploredE, isElement; | |
stack <int> blockPoints; | |
cin>>totalV>>totalE; //total no of vertex and edges | |
adjMatrix = (int*)malloc(sizeof(int)*totalV*totalV); //creating adjacent matrix | |
parentArray = (int*)malloc(sizeof(int)*totalV); //creating parent container | |
cutVertexArray = (int*)malloc(sizeof(int)*totalV); //creating cut vertex container | |
memset(adjMatrix, 0, sizeof(int)*totalV*totalV); //set all value to 0 | |
memset(parentArray, -1, sizeof(int)*totalV); //set all value to -1 | |
memset(cutVertexArray, 0, sizeof(int)*totalV); //set all value to 0 | |
for(int i=0; i<totalE; i++) | |
{ | |
cin>>tempU>>tempV; //input space separated u,v vertex of an edge | |
adjMatrix[tempU*totalV+tempV] = adjMatrix[tempV*totalV+tempU] = 1; | |
} | |
cin>>rootX; //root vertex | |
activeV = rootX; //set active | |
parentArray[rootX] = -1; //no parent | |
while(1) | |
{ | |
hasUnexploredE = false; | |
for(int i=0; i<totalV; i++) //unexplored edges checking | |
{ | |
if(*(adjMatrix+activeV*totalV+i) == 1) | |
{ | |
hasUnexploredE = true; | |
associateW = i; | |
break; | |
} | |
} | |
if(hasUnexploredE) //condition 1 | |
{ | |
isElement = false; | |
if((associateW == rootX) || (parentArray[associateW] != -1)) | |
isElement = true; | |
if(!isElement) //Condition 1A | |
{ | |
parentArray[associateW] = activeV; //set a parent means added to tree | |
adjMatrix[activeV*totalV+associateW] = adjMatrix[associateW*totalV+activeV] = 2; //mark explored | |
activeV = associateW; //change active vertex | |
} | |
else //condition 1B | |
adjMatrix[activeV*totalV+associateW] = adjMatrix[associateW*totalV+activeV] = 2; //mark explored | |
} | |
else //condition 2 | |
{ | |
if(activeV != rootX) //condition 2A | |
{ | |
associateW = parentArray[activeV]; //pick parent of activeV | |
if(!findBlock(adjMatrix, parentArray, totalV, activeV, associateW, &blockPoints)) //no vertex has explored edge to ancestor | |
{ | |
totalBlocks++; | |
cutVertexArray[associateW] = 1; | |
cout<<"Block "<<totalBlocks<<": "<<associateW<<" "; //show block points | |
while(!blockPoints.empty()) | |
{ | |
cout<<blockPoints.top()<<" "; | |
blockPoints.pop(); | |
} | |
cout<<endl; | |
} | |
activeV = associateW; //make parent active | |
} | |
else //condition 2B | |
break; | |
} | |
} | |
cout<<endl<<"Total Blocks: "<<totalBlocks<<endl; //total blocks | |
cout<<"Articulation Points: "; //cut vertex | |
for(int i=0; i<totalV; i++) | |
if(cutVertexArray[i]) | |
cout<<i<<" "; | |
cout<<endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment