/*
For this program you will implement a graph cycle detector. The program
will
input a directed graph and output all simple cycles (see p88), if any,
that
exist in the graph. Specifically,
1. Your program may use no global variables.
2. Implement a graph data structure (either adjacency matrix or
adjacency
list) to hold the directed graph. The graph must be allocated and
deallocated at runtime. Implement procedures for graph allocation,
graph deallocation, edge addition and edge lookup.
3. Implement procedures for detecting (and outputting) cycles in a
given
graph. A cycle should be output as a directed path starting from
the
smallest vertex number, e.g., '1 -> 2 -> 3 -> 5 -> 1'. Cycles
should be
output in non-decreasing order by their starting vertex, where
cycles
beginning with the same vertex can be output in any order. If the
graph
contains no cycles, then simply output 'No cycles'.
4. The main part of your program will read in data from a file whose
name
is given as the first argument to your executable. The first line
of
the file contains the number of vertices (1-100) and edges (1-1000)
in
the graph. The remaining lines define the edges in the graph in the
form 'e 5 3', which means there is a directed edge in the graph from
vertex 5 to vertex 3. Your main program should read in the graph and
then call your procedure to output any cycles.
*/
/* Anan Tongprasith */
/* Compile: cc graph.c */
/**********************/
#include
#include
/* This program use adjacency matrix */
/************* list of all functions **************/
/* insert a new row in the middle of array ba */
int arrayshift(int ba[100][20],int i,int nodenum);
/* detect a cycle */
int cycledetec(int **A,int startp,int nodenum);
/* add an edge, m=start vertice, n=end vertice */
void graphadd(int **A,int m,int n);
/* allocate memory for the matrix */
int **graphalloc(int nodenum);
/* free memory */
void graphfree(int **A,int nodenum);
/**************************************************/
int main(int argc,char *argv[])
{ FILE *fp;char newline[10],*tempch=" ";
int nodenum,edgenum,i,j,**A,mybegin,myend;
/* open the input file */
fp=fopen(argv[1],"r");
fgets(newline,10,fp);
/* reading # of node */
sscanf(newline,"%i %i",&nodenum,&edgenum);
/* allocating the adjacency matrix */
A=graphalloc(nodenum);
/* reading the input file and adding to the matrix*/
while(fgets(newline,10,fp) != NULL)
{
sscanf(newline,"%s %i %i",tempch,&mybegin,&myend);
graphadd(A,mybegin-1,myend-1);
}
fclose(fp);
j=0;
/* detecting cycle from starting point i (1,2,3,4,5) */
for(i=0;i 4, 3 -> 3 */
if(A[startp][startp]==1) /* mydist=0 */
{ printf("%i -> %i\n",startp+1,startp+1);
cycle=1;
}
/* checking for distance > 1 */
/****** outer loop check from distance = 2 to maximum distance
(when startp=1) ********/
for(mydist=1;mydist=0&&A[bigarray[index][subdist-1]][i]!=0) /****** checking path from last point to current point *****/
{ bigarray[index][subdist]=i;
arrayshift(bigarray,index,nodenum);
index+=1;
bigarray[index][subdist-1]=bigarray[index-1][subdist-1];
}
}
}
/* After reaching the wanted distance, checking path from the
last nodes in all existing path back to the starting point */
for(i=0;i3->3->4 , throw it away*/
for(j=0;j<=mydist;j++)
{ for(k=0;k<=mydist;k++)
{ if(j!=k && bigarray[i][j]==bigarray[i][k])
l+=1;
}
}
/* no repeated node? check for path from */
/* the last node to startp */
if(l==0&&A[bigarray[i][mydist]][startp]==1)
{ for(j=0;j<=mydist;j++)
printf("%i -> ",bigarray[i][j]+1);
printf("%i\n",startp+1);
cycle=1; /* found a cycle */
}
}
}
return cycle;
}
/* making rooms */
int arrayshift(int ba[100][20],int index,int nodenum)
{ int i,j;
for(i=98;i>index;i--)
{ for(j=0;j ( geocities.com/vienna/7079) ( geocities.com/vienna)