redundant paths

c pgm to find redundant paths in a graph.Many fault-tolerant network algorithms rely on an underlyin

Redundant Paths. Many fault-tolerant network algorithms rely on an underlying assumption that there are possibly distinct network paths between a source-destination pair. Given a directed graph as input, write a program that uses depth-first search to determine all such paths. Note that, these paths are not vertex-disjoint i.e., the vertices may repeat but they are all edge-disjoint i.e., no two paths have the same edges. The input is the adjacency matrix of a directed acyclic graph and a pair(s) of source and destination vertices and the output should be the number of such disjoint paths and the paths themselves on separate lines. In case of multiple paths the output should be in order of paths with minimum vertices first. In case of tie the vertex number should be taken in consideration for ordering.
Input:
3
0 1 1
0 0 1
0 0 0
2
1 2
1 3
Output:
1
1 -> 2
2
1 -> 3
1 -> 2 -> 3

solution

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

struct Stk
{
int* q;
int top;
};

struct Node
{
int sz;
struct Stk *st;
struct Node *next;
};

struct Stk *st=NULL;
struct Node *nd = NULL;
struct Node *head = NULL;

void push(int i, int n)
{
/*printf("inside push %d \n",i);*/
if(isempty()==-1)
{
st->q= (int*)malloc(sizeof(int)*n);

}
st->top++;
st->q[st->top]=i;
}

int pop()
{

int res;
/*printf("inside pop ");;*/
if(isempty()==-1)
{
return -1;
}
res = st->q[st->top];
/*printf("%d\n",res);*/
st->top--;
return res;

}

int isempty()
{
if(st->top==-1)
return -1;
else
return 0;
}

void copyStk(struct Stk* t, struct Stk* st, int n)
{
int i;
/*printf("inside copystk\n");*/


t->q = (int*)malloc(sizeof(int)*n);
for(i=0;i<=st->top;i++)
{
t->q[i]=st->q[i];
}
t->top= st->top;
/*printf("t->top is %d\n",t->top);*/
}
void printq(int n )
{
int i,setval,cnt;
struct Node* nd1;
struct Node* prev;

prev= NULL;
nd1=NULL;

setval=0;
if (nd==NULL)
{
/*printf("inside if printq\n");*/
nd=(struct Node*)malloc(sizeof(struct Node));
head = nd;
/*printf("st->top is %d\n",st->top);*/
nd->sz = (st->top)+1;
/*nd->st = st;*/
nd->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd->st,st,n);
/*printf("nd->st->top is %d\n",nd->st->top);*/
}
else
{
/*printf("inside else printq\n");*/
nd = head;
cnt = st->top;
/*printf("cnt is %d\n",cnt);*/
prev = head;
while(nd != NULL)
{
if(cnt < nd->sz)
{
nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->sz = st->top+1;
/*printf("st->top is %d\n",st->top);*/
/*nd1->st = st;*/
nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
nd1->next = nd;

if(head==nd)
head = nd1;
else
prev->next=nd1;

setval=1;
break;
}
if(cnt>=nd->sz)
{
prev=nd;
nd = nd->next;
}
}

if(setval==0)
{
/*printf("inside setval printq\n");*/
nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->sz = st->top+1;
printf("st->top is %d\n",st->top);
/*nd1->st = st;*/
nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
prev->next=nd1;
}


}


}

/*void reset(int arr[][3],int n)*/
void reset(int** arr,int n)
{
int i,j;
i=j=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j]==-1)
arr[i][j]=1;
}

}
free(st->q);
st->top=-1;
head=NULL;
nd = NULL;
}

/*int dfs(int src,int dest, int arr[][3], int n, int cnt)*/
int dfs(int src,int dest, int** arr, int n, int cnt)
{
int i;


for(i=0;i<n;i++)
{

if(arr[src][i]==1)
{
push(i,n);
arr[src][i]=-1;
if(i==dest)
{
cnt++;
/*printf("%d\n",cnt); */
printq(n);
}
else
cnt = dfs(i,dest,arr,n,cnt);

pop();
}
}
return cnt;


}

int main()
{
int notestcases;
int src,dest, i,j,n,cnt;
int** arr;
int* srcArr;
int* destArr;
/*int arr[][3] = {{0,1,1},{0,0,1},{0,0,0}};*/
i=0;j=0;

st= (struct Stk *)malloc(sizeof(struct Stk));
st->top=-1;

scanf("%d",&n);
getchar();
if(n > 0)
{
arr = (int**) malloc(sizeof(int*)*(n));


for(i=0;i<n+1;i++)
arr[i]=(int*)malloc(sizeof(int)*(n));


for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{

scanf("%d",&arr[i][j]);

}

}


scanf("%d",&notestcases);
getchar();

if(notestcases >0)
{
i=0;
srcArr = (int*)malloc(sizeof(int)*notestcases);
destArr = (int*)malloc(sizeof(int)*notestcases);
while(i<notestcases)
{
scanf("%d %d",&srcArr[i], &destArr[i]);
i++;
}
cnt = 0 ;
for(j=0;j<notestcases;j++)
{
src = srcArr[j]-1; dest = destArr[j]-1;
if (src == dest)
{
printf("%d\n",src);
continue;
}
push(src,n);
cnt  = dfs(src,dest,arr,n,0);

printf("%d\n",cnt);
nd = head;
while(nd != NULL)
{
/*printf("after dfs %d\n",nd->st->top);*/
for(i=0;i<=nd->st->top;i++)
{
printf("%d",(nd->st->q[i])+1);
if(i < nd->st->top)
printf("->");
}
printf("\n");

nd=nd->next;
}


reset(arr,n);


}
}/*if notestcases>0*/
}/*if n>0*/

return 0;
}