Memory Allocation

This is a discussion on Memory Allocation within the C Programming forums, part of the General Programming Boards category; Hello all, I had a homework assignment in my cs3050 last week, that I was having trouble with what should ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    7

    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.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,443
    Let's see what you tried, so we can see where the problems were and help you understand what you did wrong.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    7
    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.

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    What anduril meant was that you are supposed to try to build the list. So he asked for the code to see in which point of the list you have troubles. However, it seems that you do not have code for a list. Are you interested in building your own list?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    Registered User
    Join Date
    Feb 2013
    Posts
    7
    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.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,443
    Quote Originally Posted by Goku View Post
    I couldn't figure it out, so I ended up making a two dimensional array, which is wayy wrong.
    Actually, you can solve this with a 2-d array or linked lists. Either way, you have a data structure that shows a relationship of each node, and all the neighbors of that node.

    An adjacency list is very similar to your 2-d array (array of arrays), except each row is a linked list of neighbors, so you don't have to store data about unconnected nodes. Basically, an adjacency list is an array of linked lists.

    Your DFS will behave much the same either way, it's simply whether you look for neighbors by doing
    Code:
    DFS()
        for (i = 0; i < numVertices; i++)
            if adjArray[vertex][i] is connected  // vertex has node i as a neighbor
                do DFS from node j
    or something like:
    Code:
    DFS()
        for (p = vertex->adjList; p != NULL; p = p->next)  // p just walks the linked list of neighbors
            do DFS from node p  // note, no need to check if vertex is connected to p, we know they are, since the adj list only contains actual neighbors
    Last edited by anduril462; 02-20-2013 at 11:20 AM.

  7. #7
    Registered User
    Join Date
    Feb 2013
    Posts
    7
    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.

  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Ok, it seems that you are way to far from having you own list.

    I will show you the list I first used and till today, I am still based on it. It is fully commented and its ideal (in my opinion) for educational purposes.
    Make sure you read it more than once. Actually I suggest you to study what you will find in the link I am going to share with you.

    Here you are : Single linked list
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,443
    Quote Originally Posted by Goku View Post
    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.

  10. #10
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    307
    Quote Originally Posted by anduril462 View Post
    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....
    GCC on Fedora Core 10

  11. #11
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,323
    Quote Originally Posted by MacNilly View Post
    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 don't think that it's fair to say that - You don't know what professor has taught or what resources have been provided. The OP might have not attended class, or read their prescribed text.
    Fact - Beethoven wrote his first symphony in C

  12. #12
    Registered User
    Join Date
    Feb 2013
    Posts
    7
    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.

  13. #13
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    307
    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.
    GCC on Fedora Core 10

  14. #14
    Registered User
    Join Date
    Feb 2013
    Posts
    7
    I'll have to check it out, Thank you. And also thank you to everyone else who replied.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help on memory allocation(?)
    By adameye in forum C Programming
    Replies: 3
    Last Post: 09-02-2009, 02:31 PM
  2. Memory allocation
    By sarathius in forum C Programming
    Replies: 5
    Last Post: 03-13-2008, 06:21 AM
  3. memory allocation
    By mbooka in forum C Programming
    Replies: 3
    Last Post: 02-28-2006, 02:13 PM
  4. Memory Allocation
    By DutchStud in forum C++ Programming
    Replies: 3
    Last Post: 12-28-2001, 03:43 PM
  5. Memory Allocation
    By Marcelo in forum C Programming
    Replies: 1
    Last Post: 10-26-2001, 08:43 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21