//graphs.c(1780 lines of compiled code)@standard c library(*SCL*) by ASHISH TIWARI
/*
You may print, store code from this program for your personal,
noncommercial use. By accessing this code, you agree not to reproduce, distribute,
display or transmit information from this code in any form or by any means without
the permission of ASHISH TIWARI, with this exception: You may occasionally reproduce,
distribute, display or transmit an insubstantial portion of the information, for a
noncommercial purpose, to a limited number of individuals. ASHISH TIWARI does not warrant
the accuracy, completeness, timeliness, merchantability or fitness for a particular purpose
of the cose,though every care has been taken in making this code and has been compiled
on standard gcc compiler provided by GNU. ASHISH TIWARI shall not be liable for any
errors or omissions in the information or decisions made or actions taken in reliance
on the code.

"*SCL*" is a registered trademark of ASHISH TIWARI, IITKGP.
All contents of "*SCL*" is copyright ©2000-.... ,ASHISH TIWARI, IITKGP
unless otherwise noted. Reproduction in part or in whole without
permission is expressly prohibited.
*/

#include<stdio.h>
#include<stdlib.h>

#define l 2*i
#define r 2*i+1
#define NIL 0
#define INF 100000
#define NONE 8000
#define start 1 //for printpath
#define end 3



struct name{
int key;
int index;
};
typedef struct name mst;

struct tag{
int data;
struct tag* link;
};
typedef struct tag node;

int** flow;
node* path;
int** adjmatrix;
int** john_adjmatrix;
node* adj_list;
node* john_adj_list;
char* color;
int* parent;
int* john_parent;
int* dist;
int no_nodes;//4 list
int no_vertice;//4 matrix
int* d;
int* f;
int time;
int no_backedge;
int counter;
node* linklist;
int *temp;
int repeat;
int chotu;
mst* arr;
int* distance;
int* john_distance;
int* set;
int* parent_dag;
int count;
int** result;
int min;
int chutia;
int breaker;
int** bi_adjmatrix;



void adjmatrix2list_directed();//converts directed adjmat to adjlist
void john_adjmatrix2list_directed();//in caseofjohnson graph
void adjmatrix2list_undirected();//converts undirected adjmat to adjlist
void inputadjmatrix(FILE* ash);//input from a file having adj mat graph
void inputadjmatrixversion2(FILE* ash);//anotherversion
void init_matrix_list();//initialise adjlist in case of adjmatrix
void getno_nodes_mat(FILE* cash);//no_vertice get in case of matrix
void get_no_nodes(FILE* cash); //incase oflist
void init();//initialise adj_list
node* def_node(node* s,int i);//define new node
void insert_adj_list(int index,node* new);//insert in adj_list
void append(node* s,int data);//supportingfunc forinsert
void print(node* s);//prints the adj_list rowwise
void bfs(int source);//shortest paths on unweighted graphs
node* addq(node* s,int data);
node* delq(node* s,int* i);
int isempty(node* s);
void printpath(int source,int destination);
void dfs(int source);//gives b,f,c edges aswell
void dfsvisit(int u);
void predecessor_bfssubgraph(int source);
int descendant_dfs(int source,int destination);

int cycledetection();//reports if a graph has cycle,used in toposortas well
void forstronglyconnected_dfs(int source);//for identifying strongly connected
void forstrong_dfsvisit(int u);//components
void stronglyconnected_dfs();//for identifying strongly connected
void stronglyconnected_dfsvisit(int u);//components
int getmax_f();//maxvalueof late timestamp f[u]
void stronglyconnected();//strongly connected components caller
void transpose_adjmatrix();//generatestranspose of adj matrix
void printdfstree(int source);//prints trees in dfs
int singlyconnected();//for graph singly connected detection
void topological_sort();//just mention toposort n u will get it
node* add8beg(node* s,int data);//for toposort
void topo_dfs(int source);//for topo sort
void topo_dfsvisit(int u);//fortopo sort
void reachibility();//generatessetof min tag vertice reachable
void reach_dfs(int source);
void getmin();//for reachibility
void primmst(int source);//for undirected weighted graphs mst generation
void buildheap(int size);//mst
void heapify(int size,int i);//mst
void swap(int p,int q);//mst
int extractmin(int *size);//mst
int isinq(int match,int size);//mst
void init_single_source(int source);//initialises distances andparents
void relax(int u,int v);//gets an upperbound ondistance
void dag(int source);//single source shortest path in dag.O(V+E)
void djkstra(int source);//shortest path for non negative graphs,O((V+E)logV)
int bellmanford(int source);//solve single source shortest path in case of
//-ve edges aswell and returns 0 incaseof-vecycle
//O(VE)
void init_single_source_dag(int source);//initialises distances andpa
void relax_dag(int u,int v);//gets an upperbound ondistance

void john_init_single_source(int source);//initialises distances andparents
void john_relax(int u,int v);//gets an upperbound ondistance
void john_init();
void john_bellmanford(int source);
void johnson();
void ford_fulkerson(int source,int sink);
void path_exist(int source,int destination);
int calculatemin();
void delete(node* s,int num);
int search(node* s,int data);
void max_flow(int source,int destination);//for calc maxflowina graph
void max_bipartite_matching(FILE* ash,int a);
void bi_inputadjmatrixversion2(FILE* ash);



/*main(int argc,char** argv)//main incase of input format for adjlist
{
node* new;
int data;
int vertice;
int i;

if(argc==1)
{
printf("Please use format: run filename1 filename2...\n");
}
FILE* ash;

for(i=1;i<argc;i++)



{

ash=(FILE*)fopen(argv[i],"r");
if(ash==NULL)
printf("nochance\n"),exit(1);

get_no_nodes(ash); //no_vertice=0;no_vertice=getno_nodes_mat(ash);
init();//just do inputadjmatrix
ash=(FILE*)fopen(argv[i],"r");//inputadjmatrix(ash);
while((fscanf(ash,"%d %d",&vertice,&data))!=EOF)
{

new=def_node(new,data);
insert_adj_list(vertice,new);
}
fclose(ash);
parent=(int*)malloc(no_nodes*sizeof(int));
color=(char*)malloc(no_nodes*sizeof(char));
for(i=0;i<no_nodes;i++)
print(adj_list+i);
reachibility();
topological_sort();
bfs(0);
for(i=0;i<no_nodes;i++)
printf("%d%c\n",dist[i],color[i]);
}
dfs(0);
for(i=0;i<no_nodes;i++)
printf("%d %d %c\n",d[i],f[i],color[i]);

if(descendant_dfs(start,end))
printf("yes %d is an ancestor of %d",start,end);


}
}
*/

main(int argc,char** argv)//main incase of input ofform adjmat
{
node* new;
int data;
int vertice;
int i,j;
int u,v;node* temp;//for johnson
if(argc==1)
{
printf("Please use format: run filename1 filename2...\n");
}
FILE* ash;

for(i=1;i<argc;i++)



{

ash=(FILE*)fopen(argv[i],"r");
if(ash==NULL)
printf("nochance\n"),exit(1);

no_vertice=0;
// getno_nodes_mat(ash);
//printf("%d\n",no_vertice);
ash=(FILE*)fopen(argv[i],"r");

/* inputadjmatrixversion2(ash);
printf("NO OF NODES\n");
printf("%d\n",no_vertice);
no_nodes=no_vertice;
printf("THE INPUT MATRIX\n");
for(i=0;i<no_vertice;i++)
{
for(j=0;j<no_vertice;j++)
{
printf("%d ",adjmatrix[i][j]);
}
printf("\n");
}
adjmatrix2list_directed();
printf("THE INPUT ADJ_LIST\n");
for(i=0;i<no_vertice;i++)
print(adj_list+i);
*/
max_bipartite_matching(ash,5);


/*
parent=(int*)malloc(no_nodes*sizeof(int));
color=(char*)malloc(no_nodes*sizeof(char));
topological_sort();*/
/* dfs(0);
for(i=0;i<no_nodes;i++)
printf("%d %d %c\n",d[i],f[i],color[i]);

if(descendant_dfs(start,end))
printf("yes %d is an ancestor of %d",start,end);*/
}

}
void max_bipartite_matching(FILE* ash,int a)
{
int i,j;

bi_inputadjmatrixversion2(ash);
printf("NO OF NODES\n");
printf("%d\n",no_vertice+2);
no_nodes=no_vertice;
no_nodes=no_nodes+2;
adjmatrix=(int**)calloc(no_nodes,sizeof(int*));
for(i=0;i<no_nodes;i++)
adjmatrix[i]=(int*)calloc(no_nodes,sizeof(int));
for(i=0;i<no_nodes-2;i++)
for(j=0;j<no_nodes-2;j++)
{
if(bi_adjmatrix[i][j]==1)
adjmatrix[i+1][j+1]=1;
}
for(i=1;i<=a;i++)
adjmatrix[0][i]=1;
for(i=a+1;i<=no_nodes-2;i++)
adjmatrix[i][no_nodes-1]=1;
for(i=0;i<no_nodes;i++)
{
for(j=0;j<no_nodes;j++)
{
printf("%d ",adjmatrix[i][j]);
}
printf("\n");
}
adjmatrix2list_directed();
printf("THE INPUT ADJ_LIST\n");
for(i=0;i<no_nodes;i++)
print(adj_list+i);
max_flow(0,no_nodes-1);
printf("THE BIPARTITE MATCHING GROUPS\n");
for(i=1;i<=a;i++)
for(j=a+1;j<=no_nodes-2;j++)
{
if(flow[i][j]==1)
printf("%d->%d\n",i,j);
}
}

void max_flow(int source,int destination)//for calc maxflowina graph
{
int i,j,maxflow=0;
ford_fulkerson(source,destination);
printf("THE RESIDUAL CAPACITIES\n");
for(i=0;i<no_vertice;i++)
{
for(j=0;j<no_vertice;j++)
{
printf("%d ",adjmatrix[i][j]);
}
printf("\n");
}
printf("THE MAX FLOWS IN (U,V) OR (V,U)\n");;
for(i=0;i<no_vertice;i++)
{
for(j=0;j<no_vertice;j++)
{
printf("%d ",flow[i][j]);
}
printf("\n");
}
printf("THE RESIDUAL NETWORK LEFT\n");
for(i=0;i<no_vertice;i++)
print(adj_list+i);
printf("THE MAX FLOW IN THIS GRAPH\n");
for(i=0;i<no_nodes;i++)
maxflow+=flow[0][i];
printf("maxflow=%d\n",maxflow);
}


void johnson()
{int i,j,u,v;
node* temp;
john_adjmatrix=(int**)calloc((no_nodes-1),sizeof(int*));
for(i=0;i<no_nodes-1;i++)
john_adjmatrix[i]=(int*)calloc((no_nodes-1),sizeof(int));
result=(int**)malloc((no_nodes-1)*sizeof(int*));
for(i=0;i<no_nodes-1;i++)
result[i]=(int*)malloc((no_nodes-1)*sizeof(int));
john_adjmatrix2list_directed();
for(i=0;i<no_vertice;i++)
print(adj_list+i);
if(!bellmanford(0))
{
printf("the input graph has a -ve cycle\n");exit(1);
}
else
{
for(j=1;j<no_nodes;j++)
{
u=j;
temp=adj_list+j;
temp=temp->link;
while(temp!=NULL)
{
v=temp->data;
john_adjmatrix[u-1][v-1]=adjmatrix[u][v]+distance[u]-distance[v];
temp=temp->link;
}
}
}
for(i=0;i<no_nodes-1;i++)
{
for(j=0;j<no_nodes-1;j++)
{
printf("%d ",john_adjmatrix[i][j]);
}
printf("\n");
}

no_nodes=no_nodes-1;

john_init();
for(i=0;i<no_nodes;i++)
{
john_adj_list[i].link= adj_list[i+1].link;
}
for(i=0;i<no_nodes;i++)
print(john_adj_list+i);
for(j=0;j<no_nodes;j++)
{
u=j;
john_bellmanford(u);
for(i=0;i<no_nodes;i++)
{
v=i;
result[u][v]=john_distance[v]+distance[v+1]-distance[u+1];
}
}
for(i=0;i<no_nodes;i++)
{
for(j=0;j<no_nodes;j++)
{
printf("%d ",result[i][j]);
}
printf("\n");
}

}
void adjmatrix2list_directed()
{
int i,j,vertice,data;
node* new;
init_matrix_list();

for(i=0;i<no_nodes;i++)
for(j=0;j<no_nodes;j++)
{
if(adjmatrix[i][j]!=0)
{
vertice=i;
data=j;
new=def_node(new,data);
insert_adj_list(vertice,new);
}
}
}



void john_adjmatrix2list_directed()
{
int i,j,vertice,data;
node* new;
init_matrix_list();
for(i=1;i<no_nodes;i++)
{
new=def_node(new,i);
insert_adj_list(0,new);
}
for(i=1;i<no_vertice;i++)
for(j=0;j<no_vertice;j++)
{
if(adjmatrix[i][j]!=0)
{
vertice=i;
data=j;
new=def_node(new,data);
insert_adj_list(vertice,new);
}
}
}


void adjmatrix2list_undirected()
{
int i,j,vertice,data;
node* new;
init_matrix_list();
for(i=0;i<no_vertice;i++)
for(j=0;j<=i;j++)
{
if((adjmatrix[i][j]!=0) && (i==j))
{
vertice=i;
data=j;
new=def_node(new,data);
insert_adj_list(vertice,new);

}
if((adjmatrix[i][j]!=0) && (i!=j))
{
vertice=i;
data=j;
new=def_node(new,data);
insert_adj_list(vertice,new);

vertice=j;
data=i;
new=def_node(new,data);
insert_adj_list(vertice,new);

}
}
}



void inputadjmatrix(FILE* ash)//call to get no_vertice needed
{
FILE* cash;
int i,j;
char reader;
cash=ash;
adjmatrix=(int**)malloc(no_vertice*sizeof(int*));
for(i=0;i<no_vertice;i++)
adjmatrix[i]=(int*)malloc(no_vertice*sizeof(int));
for(i=0;i<no_vertice;i++)
for(j=0;j<no_vertice;j++)
fscanf(ash,"%d",&adjmatrix[i][j]);
reader=getc(ash);
if(reader==EOF)
return;
reader=getc(ash);
if(reader!=EOF || reader!=' ' || reader!='\n')
printf("adj_matrix is faulty\n"),exit(1);
}

void inputadjmatrixversion2(FILE* ash)//no need to get no_vertice
{
FILE* cash;
int i,j;
char reader;
cash=ash;
fscanf(ash,"%d",&no_vertice);
adjmatrix=(int**)malloc(no_vertice*sizeof(int*));
for(i=0;i<no_vertice;i++)
adjmatrix[i]=(int*)malloc(no_vertice*sizeof(int));
for(i=0;i<no_vertice;i++)
for(j=0;j<no_vertice;j++)
fscanf(ash,"%d",&adjmatrix[i][j]);
reader=getc(ash);if(reader==EOF)return;
if(getc(ash)!='\n' || getc(ash)!=' ' || getc(ash)!=EOF)
printf("adj_matrix is faulty\n");//,exit(1);
}
void bi_inputadjmatrixversion2(FILE* ash)//no need to get no_vertice
{
FILE* cash;
int i,j;
char reader;
cash=ash;
fscanf(ash,"%d",&no_vertice);
bi_adjmatrix=(int**)malloc(no_vertice*sizeof(int*));
for(i=0;i<no_vertice;i++)
bi_adjmatrix[i]=(int*)malloc(no_vertice*sizeof(int));
for(i=0;i<no_vertice;i++)
for(j=0;j<no_vertice;j++)
fscanf(ash,"%d",&bi_adjmatrix[i][j]);
reader=getc(ash);if(reader==EOF)return;
if(getc(ash)!='\n' || getc(ash)!=' ' || getc(ash)!=EOF)
printf("adj_matrix is faulty\n");//,exit(1);
}


void init_matrix_list()//for matrix2list list init
{
int i;
adj_list=(node*)malloc(no_nodes*sizeof(node));
for(i=0;i<no_nodes;i++)
{
adj_list[i].data=i;
adj_list[i].link=NULL;
}
}

void getno_nodes_mat(FILE* cash)
{

FILE* ash;
ash=cash;
char reader;
if(ash==NULL)
printf("nochance\n"),exit(1);
while((reader=getc(ash))!='\n')
{
if(reader==' ')
continue;
else
no_vertice++;
}
fclose(ash);
}

void get_no_nodes(FILE* cash) //incase oflist
{
FILE* ash;
ash=cash;
if(ash==NULL)
printf("nochance\n"),exit(1);
int* count;
int vertice,i,condi,data;
no_nodes=1;
count=(int*)malloc(no_nodes*sizeof(int));
if((fscanf(ash,"%d %d",&vertice,&data))!=EOF)
count[0]=vertice;

while((fscanf(ash,"%d %d",&vertice,&data))!=EOF)
{
for(i=0;i<no_nodes;i++)
{
if(vertice!=count[i])
continue;
else
break;
}
if(i==no_nodes)
condi=1;
else
condi=0;
if(condi==1)
{
++no_nodes;
count=(int*)realloc(count,no_nodes*sizeof(int));
count[i]=vertice;
}
}
fclose(ash);



}


void init()
{
int i;
adj_list=(node*)malloc(no_nodes*sizeof(node));
for(i=0;i<no_nodes;i++)
{
adj_list[i].data=i;
adj_list[i].link=NULL;
}
}
void john_init()
{
int i;
john_adj_list=(node*)malloc(no_nodes*sizeof(node));
for(i=0;i<no_nodes;i++)
{
john_adj_list[i].data=i;
john_adj_list[i].link=NULL;
}
}


node* def_node(node* s,int i)
{
s=(node*)malloc(sizeof(node));
s->data=i;
s->link=NULL;
return(s);
}



void insert_adj_list(int hash,node* new)
{
if(adj_list[hash].link==NULL)
adj_list[hash].link=new;
else
append(adj_list+hash,new->data);
}


void append(node* s,int data)
{
node* temp;
node* new;
temp=s;

if(temp==NULL)
{
temp=def_node(temp,data);
return;
}
while(temp->link!=NULL)
temp=temp->link;
new=def_node(new,data);
temp->link=new;
}


void print(node* s)//forprinting of adj_list row wise
{
node* temp;
temp=s;
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->link;
}
printf("\n");
}

void bfs(int source)
{

node* s;
int u;
node* temp;
int i;
dist=(int*)malloc(no_nodes*sizeof(int));
parent=(int*)malloc(no_nodes*sizeof(int));
color=(char*)malloc(no_nodes*sizeof(char));

for(i=0;i<no_nodes;i++)
{
if(i==source)
continue;
else
{
parent[i]=NONE;
color[i]='w';
dist[i]=INF;
}
}

dist[source]=NIL;
color[source]='g';
parent[source]=NONE;
s=def_node(s,source);
while(!isempty(s))
{
s=delq(s,&u);
temp=(adj_list+u);
temp=temp->link;
while(temp!=NULL)
{

if(color[temp->data]=='w')
{
color[temp->data]='g';
dist[temp->data]=dist[u]+1;
parent[temp->data]=u;
s=addq(s,temp->data);

}
temp=temp->link;
}
color[u]='b';
}
}



node* addq(node* s,int data)
{
node* temp;
node* new;
temp=s;

if(temp==NULL)
{
temp=def_node(temp,data);
s=temp;
return(s);
}
while(temp->link!=NULL)
temp=temp->link;
new=def_node(new,data);
temp->link=new;
return(s);
}





node* delq(node* s,int* i)
{
node* temp;
temp=s;
if(isempty(s))
{
printf("underflow\n");
exit(1);
}

else
{
(*i)=temp->data;
s=temp->link;
free(temp);
return(s);
}
}



int isempty(node* s)
{
if(s==NULL)
return(1);
else
return(0);
}


void printpath(int source,int destination)// can b usedtoprint dfs/bfs path
{
int count=0;
if(destination==source )
{
if(count++!=0)
printf("%d ",source);
}
else
{
if(parent[destination]==NONE)
printf("no path from '%d' to '%d' exists\n");
else
printpath(source,parent[destination]);
}
printf("%d ",destination);

}


void dfs(int source)
{
int i,count=0;
counter=-1;
d=(int*)malloc(no_nodes*sizeof(int));
f=(int*)malloc(no_nodes*sizeof(int));
for(i=0;i<no_nodes;i++)
{
d[i]=NIL;
f[i]=NIL;
}
for(i=0;i<no_nodes;i++)
{
color[i]='w';
parent[i]=NONE;
}
time=0;
i=source;
while(count<no_nodes)
{
if(color[i]=='w')
{
counter++;
dfsvisit(i);
}
i++;
i=i%no_nodes;
count++;
}
}

void dfsvisit(int u)
{
int v,copy;
node* temp;node* new;
no_backedge=0;
color[u]='g';
time=time+1;
d[u]=time;

temp=(adj_list+u);
temp=temp->link;
while(temp!=NULL)
{
v=temp->data;
if(color[v]=='w')
{
parent[v]=u;
dfsvisit(v);
}
if(color[v]=='g')
{
if(chotu>v)
chotu=v;

no_backedge++;
printf("backedge=edge(%d,%d)\n",u,v);
}
if(color[v]=='b' && d[u]>d[v])
{
if(chotu>v)
chotu=v;
printf("crossedge=edge(%d,%d)\n",u,v);
}
temp=temp->link;
}
color[u]='b';
new=adj_list+u;
new=new->link;
{
while(new!=NULL)
{
copy=new->data;
if(d[copy]-d[u]>1)
printf("fowardedge=edge(%d,%d)\n",u,v);
new=new->link;
}
}
time=time+1;
f[u]=time;

}



void predecessor_bfssubgraph(int source)
{
int* vpi;int k=1;
int n,i;
vpi=(int*)malloc(k*sizeof(int));
vpi[0]=source;
for(i=0;i<no_nodes;i++)

{ printf("p=%d\n",parent[i]);
if(parent[i]!=NONE)
{
vpi=(int*)realloc(vpi,(++k)*sizeof(int));
vpi[k-1]=i;
}
}
for(n=1;n<k;n++)
{
printf("%d->%d\n",parent[vpi[n]],vpi[n]);
}
}

int descendant_dfs(int source,int destination)//checks ancestor-decendant reln
{
if((d[source]<d[destination])&&
(d[destination]<f[destination])&&
(d[destination]<f[source])
)
return(1);
else
return(0);
}



void stronglyconnected()
{
int i,j;
forstronglyconnected_dfs(0);
temp=(int*)malloc(no_nodes*sizeof(int));
for(i=0;i<no_nodes;i++)
temp[i]=f[i];

transpose_adjmatrix();

adjmatrix2list_directed();

stronglyconnected_dfs();
}

void transpose_adjmatrix()
{
int i,j,swap;
for(i=0;i<no_vertice;i++)
for(j=i;j<no_vertice;j++)
{
if(i!=j)
{
swap=adjmatrix[i][j];
adjmatrix[i][j]=adjmatrix[j][i];
adjmatrix[j][i]=swap;
}
}
}



int cycledetection()
{
no_backedge=0;
forstronglyconnected_dfs(0);
if(no_backedge==0)
return(0);
else
return(1);
}



void printdfstree(int source)
{
int index=0;

if(repeat==0)
printf("%d->",source);
repeat++;
while(parent[index]!=source)

{
index++;
if(index==no_nodes)return;
}

printf("%d->",index);


printdfstree(index);
}



int singlyconnected()
{
int i;
for(i=0;i<no_nodes;i++)
{

forstronglyconnected_dfs(i);
if(counter==0)
continue;
else
break;
}
if(counter==0)
return(1);
else
return(0);
}

void stronglyconnected_dfs()
{
int i,count,group=0;
counter=-1;
d=(int*)malloc(no_nodes*sizeof(int));
f=(int*)malloc(no_nodes*sizeof(int));
for(i=0;i<no_nodes;i++)
{
d[i]=NIL;
f[i]=NIL;
}
for(i=0;i<no_nodes;i++)
{
color[i]='w';
parent[i]=NONE;
}
time=0;

for(count=0;count<no_nodes;count++)
{
i=getmax_f();

if(color[i]=='w')
{
counter++;
stronglyconnected_dfsvisit(i);
printf("\ngroup(%d)\n",++group);
repeat=0;
printdfstree(i);
printf("\n\n");
}

}
}

void stronglyconnected_dfsvisit(int u)
{
int v,copy;
node* temp;node* new;
no_backedge=0;
color[u]='g';
time=time+1;
d[u]=time;
temp=(adj_list+u);
temp=temp->link;
while(temp!=NULL)
{
v=temp->data;
if(color[v]=='w')
{
parent[v]=u;
stronglyconnected_dfsvisit(v);
}
temp=temp->link;
}
color[u]='b';
new=adj_list+u;
new=new->link;
{
while(new!=NULL)
{
copy=new->data;

new=new->link;
}
}
time=time+1;
f[u]=time;

}
int getmax_f()
{
int i,max=0,tag;

for(i=0;i<no_nodes;i++)
{
if(temp[i]>max)
{
max=temp[i];
tag=i;
}

}
temp[tag]=0;

return(tag);

}



void forstronglyconnected_dfs(int source)
{
int i,count=0;
counter=-1;
d=(int*)malloc(no_nodes*sizeof(int));
f=(int*)malloc(no_nodes*sizeof(int));
for(i=0;i<no_nodes;i++)
{
d[i]=NIL;
f[i]=NIL;
}
for(i=0;i<no_nodes;i++)
{
color[i]='w';
parent[i]=NONE;
}
time=0;
i=source;
while(count<no_nodes)
{
if(color[i]=='w')
{
counter++;
forstrong_dfsvisit(i);
}
i++;
i=i%no_nodes;
count++;
}
}

void forstrong_dfsvisit(int u)
{
int v,copy;
node* temp;node* new;
no_backedge=0;
color[u]='g';
time=time+1;
d[u]=time;
temp=(adj_list+u);
temp=temp->link;
while(temp!=NULL)
{
v=temp->data;
if(color[v]=='w')
{
parent[v]=u;
forstrong_dfsvisit(v);
}
if(color[v]=='g')
{
no_backedge++;
/* printf("backedge=edge(%d,%d)\n",u,v)*/;
}
/* if(color[v]=='b' && d[u]>d[v])
printf("crossedge=edge(%d,%d)\n",u,v);*/
temp=temp->link;
}
color[u]='b';
new=adj_list+u;
new=new->link;
{
while(new!=NULL)
{
copy=new->data;
/*if(d[copy]-d[u]>1)
printf("fowardedge=edge(%d,%d)\n",u,v);*/
new=new->link;
}
}
time=time+1;
f[u]=time;

}

void topological_sort()
{

if(cycledetection())
printf("no toposort ispossible since graph isnot dag\n"),exit(1);
else
{
topo_dfs(0);
print(linklist);
}
}


node* add8beg(node* s,int data)
{
node* new;
new=def_node(new,data);
new->link=s;
s=new;
return(s);
}

void topo_dfs(int source)
{
int i,count=0;
counter=-1;
d=(int*)malloc(no_nodes*sizeof(int));
f=(int*)malloc(no_nodes*sizeof(int));
for(i=0;i<no_nodes;i++)
{
d[i]=NIL;
f[i]=NIL;
}
for(i=0;i<no_nodes;i++)
{
color[i]='w';
parent[i]=NONE;
}
time=0;
i=source;
while(count<no_nodes)
{
if(color[i]=='w')
{
counter++;
topo_dfsvisit(i);
}
i++;
i=i%no_nodes;
count++;
}
}

void topo_dfsvisit(int u)
{
int v,copy;
node* temp;node* new;
no_backedge=0;
color[u]='g';
time=time+1;
d[u]=time;
temp=(adj_list+u);
temp=temp->link;
while(temp!=NULL)
{
v=temp->data;
if(color[v]=='w')
{
parent[v]=u;
topo_dfsvisit(v);
}
temp=temp->link;
}
color[u]='b';
new=adj_list+u;
new=new->link;
{
while(new!=NULL)
{
copy=new->data;

new=new->link;
}
}
time=time+1;
f[u]=time;
linklist=add8beg(linklist,u);
}


void reachibility()//generatessetof min tag vertice reachable
{
int i;
for(i=0;i<no_nodes;i++)
{
chotu=NONE;
reach_dfs(i);
printf("vertice=%d=>minimum tag vertice reachable=%d\n",i,chotu);
}
}





void reach_dfs(int source)
{
int i,count;

d=(int*)malloc(no_nodes*sizeof(int));
f=(int*)malloc(no_nodes*sizeof(int));
for(i=0;i<no_nodes;i++)
{
d[i]=NIL;
f[i]=NIL;
}
for(i=0;i<no_nodes;i++)
{
color[i]='w';
parent[i]=NONE;
}
time=0;
i=source;
if(color[i]=='w')
{
dfsvisit(i);
getmin(i);
}
}


void getmin(int source)
{
int index=0;
while(parent[index]!=source)

{
index++;
if(index==no_nodes)return;
}
if(chotu>index)
chotu=index;

getmin(index);


}

void primmst(int source)//for undirectedweigthed graph's mst generation
{

int* parent;
node* temp;
int i,u,v,size;
size=no_nodes+1;
arr=(mst*)malloc(size*sizeof(mst));
parent=(int*)malloc(size*sizeof(int));

for(i=1;i<size;i++)
{
arr[i].key=INF;
arr[i].index=i;
parent[arr[i].index]=NIL;
}
arr[source+1].key=0;
buildheap(size);


for(i=1;i<no_nodes+1;i++)
{
u=extractmin(&size);
temp=(adj_list+u-1);
temp=temp->link;
while(temp!=NULL)
{
v=(temp->data)+1;
if((isinq(v,size)) && adjmatrix[u-1][v-1]<arr[v].key)
{
parent[v]=u;
arr[v].key=adjmatrix[u-1][v-1];
}
temp=temp->link;
}
}

for(i=1;i<no_nodes+1;i++)
printf("%d->%d\n",i-1,parent[i]-1);
}


void buildheap(int size)
{
int i;

for(i=(size)/2;i>=1;i--)
{
heapify(size,i);

}

}


void heapify(int size,int i)
{
int smallest;

if(arr[i].key>arr[l].key && l<=size-1)
smallest=l;
else
smallest=i;
if(arr[smallest].key>arr[r].key && r<=size-1)
smallest=r;

if(i!=smallest)
{
swap(i,smallest);
heapify(size,smallest);
}
}


void swap(int p,int q)
{
int temp;

temp=arr[q].key;
arr[q].key=arr[p].key;
arr[p].key=temp;

}


int extractmin(int *size)
{
int min;
if(*size-1<1)
{
printf("heap has no more elements\n");
exit(1);
}
else
{
min=arr[1].index;
arr[1].key=arr[*size-1].key;
arr[1].index=arr[*size-1].index;
(*size)--;
heapify(*size,1);
}
return(min);
}

int isinq(int match,int size)
{
int i;
for(i=1;i<size;i++)
{
if(arr[i].index==match)
return(1);
else
continue;
}
if(i==size-1)
return(0);
}


void init_single_source(int source)//initialises distances andparents
{
int v;
distance=(int*)malloc(no_nodes*sizeof(int));
parent=(int*)malloc(no_nodes*sizeof(int));
for(v=0;v<no_nodes;v++)
{
distance[v]=INF;
parent[v]=NIL;
}

distance[source]=0;
}

void relax(int u,int v)//gets an upperbound ondistance
{
if(distance[v]>(distance[u]+adjmatrix[u][v]))
{
distance[v]=distance[u]+adjmatrix[u][v];
parent[v]=u;
}
}
void init_single_source_dag(int source)//initialises distances andparents
{
int v;
distance=(int*)malloc(no_nodes*sizeof(int));
parent_dag=(int*)malloc(no_nodes*sizeof(int));
for(v=0;v<no_nodes;v++)
{
distance[v]=INF;
parent_dag[v]=NIL;
}

distance[source]=0;
}

void relax_dag(int u,int v)//gets an upperbound ondistance
{
if(distance[v]>(distance[u]+adjmatrix[u][v]))
{
distance[v]=distance[u]+adjmatrix[u][v];
parent_dag[v]=u;
}
}


void dag(int source)//single source shortest path in dag.O(V+E)
{int i;
node* temp;
node* temp1;
int u,v;

topological_sort();
init_single_source_dag(source);
temp=linklist;
while(temp!=NULL)

{
u=temp->data;

temp1=(adj_list+u);
temp1=temp1->link;
while(temp1!=NULL)
{
v=temp1->data;
relax_dag(u,v);
temp1=temp1->link;
}


temp=temp->link;
}
}

void djkstra(int source)//shortest path for non negative graphs,O((V+E)logV)
{
int i,junk=0;
node* temp;
int u,v,size;
size=no_nodes+1;
arr=(mst*)malloc(size*sizeof(mst));
set=(int*)malloc(no_nodes*sizeof(int));
init_single_source(source);

for(i=0;i<no_nodes;i++)
set[i]=NIL;

for(i=1;i<size;i++)
{
arr[i].key=distance[i-1];
arr[i].index=i;
}
buildheap(size);


for(i=1;i<no_nodes+1;i++)
{
u=extractmin(&size);
set[junk++]=u-1;
temp=(adj_list+u-1);
temp=temp->link;
while(temp!=NULL)
{
v=(temp->data)+1;
relax(u-1,v-1);
temp=temp->link;
}
}

}

int bellmanford(int source)//solve single source shortest path in case of
{ //-ve edges aswell and returns 0 incaseof-vecycle
int i,j,v,u;
node* temp; //O(VE)
init_single_source(source);
for(i=1;i<no_nodes;i++)
{
for(j=0;j<no_nodes;j++)// for(j=0;j<no_nodes;j++)
{ //for(k=0;k<no_nodes;j++)
temp=adj_list+j;//{if(adjmatrix[j][k]!=0)
temp=temp->link;//relax(j,k);
while(temp!=NULL)//}
{
v=temp->data;
relax(j,v);
temp=temp->link;
}
}
}

for(j=0;j<no_nodes;j++)// for(j=0;j<no_nodes;j++)
{
u=j;//for(k=0;k<no_nodes;j++)
temp=adj_list+j;//{if(adjmatrix[j][k]!=0)
temp=temp->link;//{if(distance[k]>distance[j]+adjmatrix[j][k])
while(temp!=NULL)//return(0);
{
v=temp->data;
if(distance[v]>(distance[u]+adjmatrix[u][v])) //}
return(0);
temp=temp->link;
} //}
}


return(1);
} //return(1);


void john_init_single_source(int source)//initialises distances andparents
{
int v;
john_distance=(int*)malloc(no_nodes*sizeof(int));
john_parent=(int*)malloc(no_nodes*sizeof(int));
for(v=0;v<no_nodes;v++)
{
john_distance[v]=INF;
john_parent[v]=NIL;
}

john_distance[source]=0;
}

void john_relax(int u,int v)//gets an upperbound ondistance
{
if(john_distance[v]>(john_distance[u]+john_adjmatrix[u][v]))
{
john_distance[v]=john_distance[u]+john_adjmatrix[u][v];
john_parent[v]=u;
}
}


void john_bellmanford(int source)//solve single source shortest path in case of
{ //-ve edges aswell and returns 0 incaseof-vecycle
int i,j,v,u;
node* temp; //O(VE)
john_init_single_source(source);
for(i=1;i<no_nodes;i++)
{
for(j=0;j<no_nodes;j++)// for(j=0;j<no_nodes;j++)
{ //for(k=0;k<no_nodes;j++)
temp=john_adj_list+j;//{if(adjmatrix[j][k]!=0)
temp=temp->link;//relax(j,k);
while(temp!=NULL)//}
{
v=temp->data-1;
john_relax(j,v);
temp=temp->link;
}
}
}


}



void ford_fulkerson(int source,int sink)
{
int i,residual_flow,u,v,k;
node* temp;int ni=0;;
breaker=0;
flow=(int**)calloc(no_nodes,sizeof(int*));
for(i=0;i<no_nodes;i++)
flow[i]=(int*)calloc(no_nodes,sizeof(int));

while(breaker!=1)
{breaker=0;

bfs(source);
count=0;
chutia=0;
path_exist(source,sink);
if(breaker==1)return;
residual_flow=calculatemin();

temp=path;
printf("path:(%d)\n",++ni);
print(temp);
//while(temp!=
for(k=1;k<=chutia;k++)
{
u=temp->data;
v=temp->link->data;
adjmatrix[u][v]=adjmatrix[u][v]-residual_flow;
flow[u][v]=flow[u][v]+residual_flow;
flow[v][u]=-flow[u][v];
temp=temp->link;

}

}

}



void path_exist(int source,int destination)
{


node* new;
if(destination==source )
{

path=def_node(path,source);


}
else
{
if(parent[destination]==NONE)
{breaker=1;return;}
else
path_exist(source,parent[destination]);

}
if(destination!=0)
{
chutia++;
append(path,destination);
}
}


int calculatemin()
{
node* temp;

int u,v,i,j,k;

int min=INF;
temp=path;

//while(temp!=NULL)
for(k=1;k<=chutia;k++)
{
u=temp->data;
v=temp->link->data;
if(!search(adj_list+v,u))
append(adj_list+v,u);
if(min>adjmatrix[u][v])
{
min=adjmatrix[u][v];
i=u;
j=v;
}
temp=temp->link;
}
delete(adj_list+i,j);


return(min);
}
void delete(node* s,int num)
{
node* temp;
node* pre;
temp=s;
while(temp!=NULL)
{
if(s->data==num)
{
s=temp->link;
free(temp);
return;
}
else if(temp->data==num)
{
pre->link=temp->link;
free(temp);
return;
}
pre=temp;
temp=temp->link;
}
printf("element to b deleted not found\n");
}
int search(node* s,int data)
{
node*temp;
temp=s;
while(temp->data!=data)
{
if(temp->link==NULL)
{
return(0);
}
temp=temp->link;
}
return(1);
}