Thread: Memory Allocation

Hello all,

I had a homework assignment in my cs3050 last week, that I was having trouble with what should be the easiest part.

The homework looked like this:


In this program you will read a file specifying an undirected graph as a list of edges and output the number of connected components as well as the size (number of vertices) of the smallest component. The number of vertices is given on the first line of the input. The vertices are numbered in order from 1 to the total number of vertices. The rest of the input file simply lists the edges in arbitrary order as pairs of vertices, with each edge on a separate line. For example for the following input:
7
1 2
4 5
3 6
2 7
The output is:
The number of connected components is 3
The smallest component has

I had trouble setting up the adjacency list. I knew that I could just use breadths first search or depths first search once I had it, but I have always had trouble with allocating memory. I didn't end up figuring it out before it was due, but I know we are going to be having more like this.

All I need to know is how to get it all into the adjacency list and then I know what to do from there.

Let's see what you tried, so we can see where the problems were and help you understand what you did wrong.

Code:

      
 //global variable for colorint color[1001] = {0};


//prototype for Depths First Search
int DFS(int array[1001][1001], int vertex, int numVertices, int reset);


int main (int argc, char** argv)
{
        //declare variables
        FILE *in = NULL;
        int i = 0;
        int j = 0;
        int numVertices = 0;
        int vertex1 = 0, vertex2 = 0;
        int num2 = 0;
        int array[1001][1001] = {0};


        //check to make sure enough arguments
        if(argc != 2){
                printf("wrong entry\n");
                return 1;
        }
        //open file in read only
        in = fopen(argv[1], "r");


        //check to make sure file exists
        if(in == NULL){
                printf("File can not be opened.\n");
                return 2;
        }


        //read in the first line of the input, which will give you the number of Vertices
        fscanf(in, "%d", &numVertices);


        //create the matrix of the graph
        for(i=1; i<numVertices; i++)
        {
                fscanf(in, "%d %d", &vertex1, &vertex2);


                array[vertex1][vertex2] = 1;
                array[vertex2][vertex1] = 1;
        }


        int num = 0, smallest = 0;


        //This for loop will go through every vertex. First it checks to see if the vertex has been visited.
        //if so skip it, if not then call DFS. Then check to see if the returning component is the smallest.         
        //If not skip it, if so then put it in 'smallest'. Lastly bump the counter which keeps track of the number of components
        for(i = 1; i<numVertices + 1; i++)
        {
                if(color[i] == 0)
                {
                        num = DFS(array, i, numVertices, 1);
                        if(smallest > num || smallest == 0)
                        {
                                smallest = num;
                        }
                        num2++;
                }
        }
        //print outputs
        printf("The number of connected components is %d\n", num2);
        printf("The smallest component has %d vertices\n", smallest);
}


//this function first sets the vertex to being visited, next it checks to see if the count has been changed yet
//if so then skip over it, if not change to zero. Next the function bumps the counter. The for loop takes the 
//vertice that you brought down and goes through all of the other vertices. If there is a connecting vertex 
//and it has not already been visited then recursively call DFS. Lastly return the number of times DFS was called 
//recursively which will provide the number of vertices on each component.
int DFS(int array[1001][1001], int vertex, int numVertices, int reset)
{
        int i = 0;
        static int count = 0;
        color[vertex] = 1;
        if(reset == 1)
        {
                count = 0;
        }
        count++;


        for(i = 1; i<numVertices+1; i++)
        {
                if((array[vertex][i] == 1) && (color[i] == 0))
                {
                        DFS(array, i, numVertices, 0);
                }
        }


        return count;
}

I couldn't figure it out, so I ended up making a two dimensional array, which is wayy wrong.

Oh sorry
I don't have any code for the list. As you can see I took the easy/wrong way out. I am interested in building a list.

How do I allocate the memory for the list once i read in the first line? Right now in my code, I just have the 2 dimensional array that is made 1000 x 1000 then change resize it after I read in the number of vertices.

Originally Posted by Goku

How do I allocate the memory for the list once i read in the first line? Right now in my code, I just have the 2 dimensional array that is made 1000 x 1000 then change resize it after I read in the number of vertices.

How have you made it this far in your programming classes if you can't create a basic linked list or even dynamically allocate an array of objects? If you don't understand those concepts, you need to study them. Also, if you don't understand what an adjacency list is conceptually, then you need to study that as well. You can't program a solution if you don't even understand the problem.

Once you're clear on the concepts, plan out a rough solution with paper and pencil, then turn that into code, little bits at a time. Start with some basics, like declaring a struct to hold all the pertinent adjacency list information (node visited, etc). Then, dynamically allocate an array of those nodes (using malloc). You need an array with numVertices elements in it.

Originally Posted by anduril462

How have you made it this far in your programming classes if you can't create a basic linked list or even dynamically allocate an array of objects?

This seems to be something of a trend. Students who are given homework so obviously above their current skill level. Could a professor really expect one to do graph algorithms without knowledge of a linked list or dynamic array? Hmm....

I go to class everyday, but the problem is in previous classes we have been spoon fed all prototypes and given brief descriptions of what each function does, and basically told what to do. We talked very limitedly about allocating memory and only used it in the very simplest of cases

Then this class starts and we are never shown any code and only talk algorithms without their applications. Then we are given home works like this one and given free reign on what to do. To say the least it is a bit overwhelming.

Well, you're on the right path by visiting this site. I joined many years ago, and I learned everything I know about C from here. In particular, the member Prelude has some great tutorials on data structures in the tutorial section, including linked lists.

I'll have to check it out, Thank you. And also thank you to everyone else who replied.