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.

Hollah

Something fishy about the vPtr declaration. – Kettledrummer

@Jim : I don't think so because the code only gives problem when I am pushing back in the list. If I remove that line then the code works fine. – Hollah

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;
}

Anitaanitra

Well, indeed it strongly changes the code. But I believe it's needed, due to the nature of the problem - which is using the wrong tools for the job. – Anitaanitra

I agree completely. But it's an interesting academic exercise in seeing how malloc and STL interact (or don't). The insight on malloc not running construct is interesting. – Kettledrummer

Yes, I think you had the better answer in that it addresses the issue. Streppel bypassed it, which is probably the right thing to do, but doesn't explain things. I will +1 your answer, least I can do.... – Kettledrummer

@Jim, Is it that malloc do not do the stuff needed for stl objects? – Sunken

I think STL can do everything, but some folks familiar with different methods sometimes want to mix them. In general, probably not the best thing to do, but it happens. – Kettledrummer

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 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.

Arabist

Maybe he shouldn't but it's good to know (anyways) how these interact. – Kettledrummer

I don't think node->adj = new list<int>; compiles. – Kettledrummer

Oops, yes it does, when you make adj a ptr. – Kettledrummer

Yup which is exactly what I said you had to do in my comment :-) – Arabist

@Jim No worries mate! Cheers and thanks for up vote! It's fitting my first post answers that are right never get the love :-p Found some good posts of yours I trudged through too. It's funny but you'll occasionally encounter scenarios where you do have to mix the two together, particularly if you can't use placement-new yet and have to mix them together for other performance reasons (calling new and malloc are bad for latency).. and yes i realize so is STL often.. – Arabist

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;
}

Kettledrummer