Adding of a vertex in graph using adjacency-list in c++

Question

This is how I've defined my graph. This is not a typical graph, it is specific to the type of problem I'm dealing with.

class Vertex;

class Edge
{
public:
    Vertex *org;
    Vertex *dest;
    bool dir;
};

struct Vertex{
    int id;
    vector<Edge> edges;
    int weight;
};
struct Graph{
    vector<Vertex> vertices;
};

I'm having problem in adding a vertex in the graph. This is how I'm doing it

Graph* graph1;
Vertex* first = addVertex(0);
graph1->vertices.push_back(*first);

The addVertex function is working properly, but if you still want to refer, here it is

Vertex* addVertex(int id){
    Vertex*newVertex = new Vertex;
    newVertex->id=id;
    newVertex->weight=0;
    return newVertex;
}

The function stops working just before graph1->vertices.push_back(*first);

Mahesh · Accepted Answer · 2014-03-07 18:35:39Z

2

graph1 itself is an unitialized pointer. So, calling it's members is causing the program to crash. Initialize it with new operator.

graph1 = new Graph();
// .......
delete graph1;

Or use a smart pointer like std::unique_ptr to automatically manage memory.

answered Mar 7, 2014 at 18:35

Mahesh

34.7k23 gold badges93 silver badges116 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

japreiss Over a year ago

No! Just declare Graph graph1;. Only use pointers when necessary.

Mahesh Over a year ago

@japreiss In general, yes. But here it actually depends on how graph1 grows.

japreiss · Accepted Answer · 2014-03-07 18:50:32Z

0

In addition to the uninitialized Graph* graph1, there is another memory management problem in your code:

addVertex allocates a single Vertex in its own block of heap memory. But then

graph1->vertices.push_back(*first);

copies first into the block of memory managed by graph1's std::vector.

I guess that you are new to C++ coming from another language like Java or Python. You should read an introductory C++ book. Memory management in C++ has a lot of pitfalls and concepts to keep track of compared to other languages.

answered Mar 7, 2014 at 18:50

japreiss

11.3k2 gold badges42 silver badges79 bronze badges

Collectives™ on Stack Overflow

Adding of a vertex in graph using adjacency-list in c++

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related