cycleDetection

Detect cycles in graphs
Log | Files | Refs | README

cycleDetection.c (2736B)

      1 #include "cycleDetection.h"
      2 #include "LinkedList.h"
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 #include <stdbool.h>
      6 
      7 void cycleDetection( Graph *g ) {
      8         LinkedList *L = LinkedList_new(); // Empty list of vertiecs
      9         LinkedList *S = LinkedList_new(); // A set of all vertices of g with no incoming edges
     10         for ( int i = 0; i < g->numVertices; i += 1 )
     11                 if ( g->vertices[i].inNeighbours->size == 0 )
     12                         LinkedList_append( S, &g->vertices[i] );
     13 
     14         // print S
     15         /*
     16         LinkedListNode *n = S->head;
     17         while ( n ) {
     18             Vertex *v = n->data;
     19             printf( "S: %i\n", v->id );
     20             n = n->prev;
     21         }*/
     22             
     23 
     24         //printf( "S size: %i\n", S->size );
     25         while ( S->size > 0 ) { // While s is non-empty 
     26 
     27                 Vertex *u = LinkedList_popFront( S ); // A node removed from S
     28                 LinkedList_append( L, u ); // Append u to the tail of L
     29                 // printf( "L->size: %i\n", L->size );
     30                 // printf( "u out: %i\n", u->outNeighbours->size );
     31 
     32                 while ( u->outNeighbours->size > 0 ) { // For each vertex v in g with an edge from u to v
     33                         Vertex *v = LinkedList_popFront( u->outNeighbours ); 
     34                         // printf( "v: %i\n", v->id );
     35                         if ( v->inNeighbours->size == 1 ) { // If v has no other incoming edges than e
     36                                 LinkedList_append( S, v ); // Insert v in S
     37                                 // printf( "no other in e: %i\n", v->id );
     38                         }
     39                         // Remove edge from graph
     40                         // v already popped from u->outneighbours
     41                         LinkedListNode *n = LinkedList_find( v->inNeighbours, u );
     42                         LinkedList_remove( v->inNeighbours, n );
     43                 }
     44         }
     45 
     46         bool noEdges = true;
     47         int i = 0;
     48         while ( i < g->numVertices && noEdges ) {
     49                 Vertex v = g->vertices[i];
     50                 // printf( "in: %i, out: %i\n", v.inNeighbours->size, v.outNeighbours->size );
     51                 if ( v.inNeighbours->size > 0 || v.outNeighbours->size > 0 )
     52                         noEdges = false;
     53                 i = i + 1;
     54         }
     55 
     56         if ( !noEdges )
     57                 printf( "CYCLE DETECTED!\n" );
     58         else {
     59                 Vertex *v = LinkedList_popFront( L );
     60                 printf( "%i", v->id );
     61                 while ( L->size > 0 ) {
     62                         v = LinkedList_popFront( L );
     63                         printf( ", %i", v->id );
     64                 }
     65                 printf( "\n" );
     66         }
     67 
     68         LinkedList_delete( S );
     69         LinkedList_delete( L );
     70 }