// This is a assignment to find the Bridge from a Directed
Graph
// Theis program is not star perfect.A bug has found and
trying to remove that.Better algorithm can be build-up.
// This program will take (O(V)+O(V+E)).
// This Program is compiled by Dev-C++ 4.9.4.0.
// for further information please contact with:
// Bappi Nath
// ID:
01201026
// Fall'01
// Computer
Science and Engineering
// BRAC
University
// Cell:
88-018111757
// email:
bappinath@hotmail.com
#include<stdio.h>
#include<conio.h>
#include<string.h>
////some global variable
int len,neel_nod=0;
char
arr[1024][1024],que[1024],black[1024],cycle[1024],bridge[1024];
///general declaration of some function
void QueIn(char c);
char QueOut();
void Do_Black(char c);
int Already_Black(char c);
int Check_Size();
void PrintStatus();
void FindBridge();
void Seperate_Cycle(char c);
void Set_Bridge();
//body of QueIn(char c) func
void QueIn(char c)
{
int size=0;
for(;;)
{
if(que[size]=='#') break;
size++;
}
que[size]=c;
que[size+1]='#';
}
///body of QueOut() func
char QueOut()
{
char temp=que[0];
int i = 0;
for(;;)
{
que[i]=que[i+1];
if(que[i+1]=='#')
break;
i++;
}
Do_Black(temp);
return temp;
}
///body of Already_Black(char c) func
int Already_Black(char c)
{
int size=0;
while(black[size]!='#')
{
if
(black[size]==c) return 1;
size++;
}
return 0;
}
///body of Do_Black(char c) func
void Do_Black(char c)
{
int size=0;
while(black[size]!='#')
{
size++;
}
black[size]= c;
black[size+1]= '#';
}
///body of Check_Size() func
int Check_Size()
{
int i=0;
while(black[i]!='#')
{
i++;
}
return i;
}
////body of func Already_Exist_In_Que(char c)
int Already_Exist_In_Que(char c)
{
int size=0;
while(que[size]!='#')
{
if (que[size]==c)
return 1;
size++;
}
return 0;
}
////////body of print function
void PrintStatus()
{
int i,j;
for(i=0;i<=len;i++)
{
for(j=0;j<=len;j++)
{
printf("%c ",arr[i][j]);
}
printf("\n");
}
printf("\n\n");
}
////here is the body of void Seperate_Cycle() func
void Seperate_Cycle(char c)
{
int i=0;
while(black[i]!=c)
{
i++;
}
while(black[i]!='#')
{
cycle[neel_nod]=black[i];
i++;
neel_nod++;
}
cycle[neel_nod]='#';
neel_nod++;
}
///here is the body of void Set_Bridge() func
void Set_Bridge()
{
int i=0,flag1=0,flag2=0;
int size=0;
while(i<(len-1))
{
char
check1=black[i],check2=black[i+1];
char
temp[1024];
//....................
int k=0;
while(cycle[k]!='$')
{
int
t=0;
while(cycle[k]!='#')
{
temp[t]=cycle[k];
t++;
k++;
if(cycle[k]=='$') break;
}
temp[t]='#';
//....................
t=0;
while(temp[t]!='#')
{
if(temp[t]==check1)
{
flag1=1;
int p=0;
while(temp[p]!='#')
{
if(temp[p]==check2)
flag2=1;
p++;
}
}
t++;
if(flag1==1) break;
}
if(flag1==1) break;
k++;
}
///..........................
if(flag1==0 || flag2==0)
{
bridge[size]=check1;
size++;
bridge[size]=check2;
size++;
}
i++;k++;
flag1=0;flag2=0;
}
bridge[size]='#';
}
///here is the body of FindBridge() func
void FindBridge()
{
black[0]='#';
que[0]='#';
int i=1,j;
char Out_from_Que;
QueIn(arr[1][0]);
while(Check_Size()!=len)
{
Out_from_Que=QueOut();
i=1;
while(arr[i][0]!=Out_from_Que)
{
i++;
}
for(j=1;j<=len;j++)
{
if(arr[i][j]=='1')
{
if(Already_Black(arr[0][j])==1)
{
Seperate_Cycle(arr[0][j]);
}
if(Already_Black(arr[0][j])==0 &&
Already_Exist_In_Que(arr[0][j])==0)
{
QueIn(arr[0][j]);
}
}
}
}///end of
the while loop
if(neel_nod!=0)
{
cycle[(neel_nod-1)]='$';
}else
{cycle[neel_nod]='$';
}
Set_Bridge();
}///end of the func
/////here is the body of PrintBridge() func
void PrintBridge()
{
int i=0;
printf("\nThe Bridge has given bellow:\n");
while(bridge[i]!='#')
{
printf("%c",bridge[i]);
printf("->%c\n",bridge[i+1]);
i=i+2;
}
}
int main()
{
///////////////////build the array according to
lebeling////////////////////////////////
int i,j;
char lebel[1024];
printf("\t\t
----------------------------------");
printf("\n\n\t\t\t Algorithm (CSE 221)\n");
printf("\t\t
Take Home Lab Assignment: 03\n\n");
printf("\t\t
----------------------------------\n");
printf("\t\t\t\t Prepared by:\n");
printf("\t\t\t\t\t
Promila Kanti Nath\n");
printf("\t\t\t\t\t
ID:01201026\n");
printf("\t\t\t\t\t
Computer Science & Engineering\n");
printf("\t\t\t\t\t
BRAC University.\n\n\n\n");
printf(" Input The Graph G by Adjacent
Matrix:\n");
printf("______________________________________\n\n");
printf(" Enter the lebel of the vertices without
seperatiing by space: ");
scanf("%s",&lebel);
len=strlen(lebel);
/////////////////implimentation////////////////////
int k;
for(k=1;k<=len;k++)
{
arr[k][0]=lebel[k-1];
}
for(k=1;k<=len;k++)
{
arr[0][k]=lebel[k-1];
}
///////////////////////initilize by
zero/////////////////////
for(i=1;i<=len;i++)
{
for(j=1;j<=len;j++)
{
arr[i][j]='0';
}
}
//////////////////////////////////////////////////////////
//////////////////////////print the current
status///////////////////////
printf("\n\nThis is the current situation of the
Adjacency Matrix: \n\n\n");
PrintStatus();
/////////////////////////////////////////////////////////////////////////////
////////////////get the value//////////////////
char ch='y';
while(ch=='y')
{
printf("\n\nPlease, Enter the Row and Colomn that have
value One: ");
scanf("%d %d",&i,&j);
arr[i][j]='1';
printf("\nDo u wanna enter any more?(y/n) :");
ch=getche();
}
//////print the current status//////
printf("\n\nThis is the current situation of the
Adjacency Matrix: \n\n\n");
PrintStatus();
/////here we start the find program for strongly connected
components
printf("\n\n\n Answer To The Problem Statement:
B\n");
printf("_____________________________________\n\n");
FindBridge();
PrintBridge();
getch();
getch();
}
