Graphs using Adjacency List in c++

Question

I am trying to implement a graph in C++. I am representing a node in graph using a structure which contains two variables -
a) an integer to contain some information about the node.
b) a list to contain index of other vertex which are connected to it.
Following is the code.

// Graphs using adjacency list

#include <iostream>
#include <list>
#include <cstdlib>
using namespace std;

// structure to represent a vertex(node) in a graph
typedef struct vertex{
    int info;
    list<int> adj;   // adjacency list of edges contains the indexes to vertex
} *vPtr;             

int main(){
    vPtr node = (vPtr)malloc(sizeof(struct vertex));
    node->info = 34;            // some arbitrary value
    (node->adj).push_back(2);   // trying to insert a value in the list
    return 0;
}

The code is compiling fine but I am getting a run time error while I am pushing back an element in the list. Is there any problem in my structure.
I am using code blocks and GNU GCC, C++ 98 compiler to compile my code.

Answer 1

malloc is a C function - it shouldn't be used with C++ objects, which is very well explained here (short answer: in C++, when you are not dealing with POD types, std::list in your case, you must call the object's constructor to have the actual object ready for use, and malloc() does not do that).

You should used new instead. While malloc only allocates a block of memory of size vertex, new does that and also initializes std::list aswell by calling it's constructor (interesting to point out that when you call delete(), you are calling your object's desctructor aswell).

Here is a piece of code that works for your case, although I suggest you to start using more C++ features within C++ projects:

#include <iostream>
#include <list>
#include <cstdlib>
#include <new>

using namespace std;

// structure to represent a vertex(node) in a graph
typedef struct vertex{
    int info;
    list<int> adj;   // adjacency list of edges contains the indexes to vertex
} *vPtr;             

int main(){
    cout << "allocating memory for our vertex struct... \n";
    vPtr node = new vertex();
    node->info = 34;            // some arbitrary value
    (node->adj).push_back(2);   // trying to insert a value in the list
    cout << "cleaning allocated memory... \n";
    delete(node);

    return 0;
}

Answer 2

Couple of things.

1. Because you are using malloc no constructor is ever called, and as such the non primitive member adj is never constructed and is NULL.

2. You are leaking memory since you never free/delete any of your dynamically allocated memory.

3. If you are using C++ why are you using malloc instead of new and delete?

4. You don't have to say struct vertex in the sizeof for C++.

To fix it you could do:

vPtr node = new struct vertex(); // also change to delete instead of free

or

// use current malloc line, change adj to be a pointer to a list and new it
// but this will cause additional problems for you since you really need to use a constructor for STL::list
node->adj = new list<int>;

Bottom line you really shouldn't be using malloc here.

Answer 3

This is UpAndAdam's answer, written completely.

// Graphs using adjacency list
//
#include <iostream>
#include <list>
#include <cstdlib>
using namespace std;

// structure to represent a vertex(node) in a graph
typedef struct vertex{
    int info;
    list<int> *adj;   // adjacency list of edges contains the indexes to vertex
} *vPtr;             

int main(){
    vPtr node = (vPtr)malloc(sizeof(struct vertex));
    node->adj = new list<int>;
    node->info = 34;            // some arbitrary value
    (node->adj)->push_back(2);  // trying to insert a value in the list
    return 0;
}