#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    2
    Rep Power
    0

    C 2-dimensional arrays and cycle detection in graphs


    Hello,
    I'm quite new in C programming and I have to solve the following problem.

    I'm reading text files that have square matrix in it with ones and zeroes and I have to find out if there are cycles with at least one 0 inside the cycle.

    I'm able to read the files easily but face the following issues:

    1)
    - i'm unable to allocate dynamically 2-dimensional arrays to put the matrix. I tried the following but the compiler still complains that:
    "warning: assignment makes integer from pointer without a cast"

    PHP Code:
    int *array;
    int i;
    int size=20;
    array=(
    int *)malloc(size sizeof(int));
    for(
    i=0;i<size;i++) {
     array[
    i]=(int *)malloc(size sizeof(int));

    2)
    Then I'd like to implement a simple algorithm to detect cycles in the graph derived from the matrix but I don't have any clue how to build a pred table or maybe there are more simple solutions ?


    Any hint would be appreciated !

    "Complete" code:

    PHP Code:
    int exercice3(FILE *file) {
     
    int *array;
     
    int i;
     
    int size;
     
    int row,col;
     
    col=row=0;
     while (!
    feof(file)) { 
      
    fscanf(file,"%c",&c); 
      if(
    c=='0' || c=='1') {
       array[
    row][col]=atoi(c);
       
    col++;
      }
      if(
    c=='\n') {
       
    row++;
       
    col=0;
      }
     }
     array=(
    int *)malloc(size sizeof(int));
     for(
    i=0;i<size;i++) {
      array[
    i]=(int *)malloc(size sizeof(int));
     }
     return 
    findCycle(array);
    }

    int findCycle(int *array) {
    /*???*/

    Example file with cycle:
    PHP Code:
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
    0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
    0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
    0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
    0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
    0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
    0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
    0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
    0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Feb 2001
    Posts
    1,481
    Rep Power
    15
    Hi,

    I don't know anything about malloc(), so I looked up the definition in MSDN, and I came across a function called calloc(), which seems to be similar to the syntax you are using, while malloc() doesn't:


    /* CALLOC.C: This program uses calloc to allocate space for
    * 40 long integers. It initializes each element to zero.
    */
    #include <stdio.h>
    #include <malloc.h>

    void main( void )
    {
    long *buffer;

    buffer = (long *)calloc( 40, sizeof( long ) );
    if( buffer != NULL )
    printf( "Allocated 40 long integers\n" );
    else
    printf( "Can't allocate memory\n" );
    free( buffer );
    }

    Output
    Allocated 40 long integers
    ------------------------

    /* MALLOC.C: This program allocates memory with
    * malloc, then frees the memory with free.
    */

    #include <stdlib.h> /* For _MAX_PATH definition */
    #include <stdio.h>
    #include <malloc.h>

    void main( void )
    {
    char *string;

    /* Allocate space for a path name */
    string = malloc( _MAX_PATH );
    if( string == NULL )
    printf( "Insufficient memory available\n" );
    else
    {
    printf( "Memory space allocated for path name\n" );
    free( string );
    printf( "Memory freed\n" );
    }
    }
  4. #3
  5. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,625
    Rep Power
    4247
    For your first question, you should be declaring your array as int **array instead of int *array. That's why you're getting the warning. See http://www.eskimo.com/~scs/C-faq/q6.16.html for more information.

    7stud - malloc() takes one argument (i.e.) the number of bytes to allocate, whereas calloc() takes two arguments, (i.e) number of objects to allocate and the size of each object. Hence, to allocate say 100 integers, you could say
    int *foo = (int *) malloc (100 * sizeof(int));
    or
    int *foo = (int *)calloc(100, sizeof(int));

    The calls are pretty similar, right? However, calloc() has one additional useful feature -- it also initalizes all the bytes of memory allocated to '\0', which malloc() does not do.
  6. #4
  7. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    2
    Rep Power
    0

    thanks


    Thank you very much for this answer !

    What if I want to pass this array to some function ?

    Fo I have to make:

    1)
    int main{
    [...]
    findCycle(array)
    }

    int findCycle(int *array) {
    [...]
    }

    OR
    2)

    int main{
    [...]
    findCycle(array)
    }

    int findCycle(int **array) {
    [...]
    }

    OR something else ?

    thanks again
  8. #5
  9. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,625
    Rep Power
    4247
    >>What if I want to pass this array to some function?
    See this FAQ: http://www.eskimo.com/~scs/C-faq/s6.html
    Pay attention to the sections 6.19, 6.20 and 6.18

    HTH

IMN logo majestic logo threadwatch logo seochat tools logo