cycleDetection

Detect cycles in graphs
Log | Files | Refs | README

Graph.c (2790B)

      1 #include "cycleDetection.h"
      2 #include "LinkedList.h"
      3 
      4 #include <stdlib.h>
      5 #include <stdio.h>
      6 
      7 Graph *Graph_new( int n ) {
      8         Graph *g = malloc( sizeof( Graph ) );
      9         if ( !g ) // allocation failed
     10                 return NULL;
     11         g->numVertices = n;
     12         g->numEdges = 0;
     13         g->vertices = malloc( sizeof( Vertex[n] ) );
     14         for ( int i = 0; i < n; i = i + 1 ) {
     15                 g->vertices[i].id = i;
     16                 g->vertices[i].outNeighbours = LinkedList_new();
     17                 g->vertices[i].inNeighbours = LinkedList_new();
     18         }
     19         
     20         return g;
     21 }
     22 
     23 void Graph_addEdge( Graph *g, int i, int j ) {
     24         LinkedList_append( g->vertices[i].outNeighbours, &g->vertices[j] );
     25         LinkedList_append( g->vertices[j].inNeighbours, &g->vertices[i] );
     26 }
     27 
     28 void Graph_delete( Graph *g ) {
     29         for ( int i = 0; i < g->numVertices; i += 1 ) {
     30                 Vertex v = g->vertices[i];
     31                 LinkedList_delete( v.outNeighbours );
     32                 LinkedList_delete( v.inNeighbours );
     33         }
     34         free( g->vertices );
     35         free( g );
     36 }
     37 
     38 Graph *Graph_read( const char *filename ) {
     39         FILE *f = fopen( filename, "r" );
     40         size_t n = 1024; // max size of graph is thus 1023 vertices
     41         char *line = malloc( n );
     42         getline( &line, &n, f );
     43 
     44         int size = atoi( line );
     45         Graph *g = Graph_new( size );
     46         if ( !g ) // allocation failed
     47                 return NULL;
     48 
     49         for ( int i = 0; i < size; i += 1 ) {
     50                 getline( &line, &n, f );
     51                 for ( int j = 0; j < size; j += 1 ) {
     52                         if ( line[j] == '1' ) {
     53                                 //printf( "i:%i j:%i\n", i, j );
     54                                 Graph_addEdge( g, i, j );
     55                         }
     56                 }
     57         }
     58         free( line );
     59         fclose( f );
     60         return g;
     61 }
     62 
     63 void Graph_print( Graph *g ) {
     64         for ( int i = 0; i < g->numVertices; i += 1 ) {
     65                 Vertex v = g->vertices[i];
     66                 //printf( "node id %i\tin:%i\tout:%i\n", g->vertices[i].id, g->vertices[i].inNeighbours->size, g->vertices[i].outNeighbours->size );
     67                 printf( "id: %i\n", v.id );
     68                 printf( " out:\n" );
     69                 LinkedListNode *p = v.outNeighbours->tail;
     70                 while ( p ) {
     71                         Vertex *u = p->data;
     72                         printf( "  %i\n", u->id );
     73                         p = p->next;
     74                 }
     75                 printf( " in:\n" );
     76                 p = v.inNeighbours->tail;
     77                 while ( p ) {
     78                         Vertex *u = p->data;
     79                         printf( "  %i\n", u->id );
     80                         p = p->next;
     81                 }
     82                 printf( "\n" );
     83         }
     84 }