CODEWITHSUNDEEP
c++vectorgraphadjacency-list
Mano Ranjith
Mano Ranjith

Reputation: 33

Adding of a edge in a graph using adjaceny-list in c++

This how i've defined my graph,it is specific to the problem i'm dealing with.

    class Vertex;

    Class Edge
    {
        Vertex *org;
        Vertex *dest;
        int traverse_time;
    };
    struct Vertex{
        int id;
        vector<Edge> edges;
        int weight;
    };
    struct Graph{
        vector<Vertex> vertices;
    };

This is how i've been adding vertices

Graph* g1=new Graph; Vertex* newvertex = addVertex(0); graph1->vertices.push_back(*newvertex);

The add Vertex function works fine but still if you need

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

I'm having a problem when i try to add edges to these vertices.This how i've been doing

org=&(g1->vertices[0]);
dest=&(g1->vertices[1]);
Edge* newedge=addRoad(org,dest,1);
org->edges.push_back(*newedge);
dest->edges.push_back(*newedge);

The addEdge function is defined as follows:

Edge* addedge(Vertex* j_id1,Vertex* j_id2,int t)
{
    Edge *newedge =new Edge;
    newedge->org=j_id1;
    newedge->dest=j_id2;
    newedge->traverse_time=t;
    return newedge;
}

The function stops working just before org->edges.push_back(*newedge);

Upvotes: 3

Views: 4216

Answers (3)

meowgoesthedog
meowgoesthedog

Reputation: 15035

One must be careful when working with pointers to elements of vectors, because when a vector is resized (calling push_back when it has no reserve space left), there is no guarantee that each element will still occupy the same memory address.

Instead, use indices.

struct Edge
{
    unsigned A, B;  // indices
    int weight;

    Edge(unsigned a, unsigned b, int w) : A(a), B(b), weight(w) {}
};
struct Vertex
{
    int id, weight;
    vector<unsigned> edges;  // edge indices

    Vertex(int i, int w) : id(i), weight(w) {}
};

struct Graph
{
    vector<Vertex> vertices;
    vector<Edge>   edges;   // use a vector for edges too for EZ deallocation

    // make the relevant functions members

    void addVertex(int id)
    {
        // in-place constructor
        vertices.emplace_back(id, 0);
    }
    bool addEdge(unsigned v1, unsigned v2, int t)
    { 
        // check if indices are valid
        if (v1 >= vertices.size() && v2 >= vertices.size())
            return false;

        unsigned newindex = edges.size();  // index of new edge
        edges.emplace_back(v1, v2, t);

        // add this edge's index to endpoints
        vertices[v1].edges.push_back(newindex);
        vertices[v2].edges.push_back(newindex);

        return true;
    }
};

Lots of other possible improvements, but this should at least fix the memory access problem.

Upvotes: 2

Temple
Temple

Reputation: 1631

Your design has couple of flaws, why you are defining Edge as:

Class Edge
{
    Vertex *org;
    Vertex *dest;
    int traverse_time;
};

Relationship between Vertexes should be clear if one has its neighbors defined as adjacency-list i.e:

Class Cost
{
    int traverse_time;
};

struct Vertex{
    int id;
    map<shared_ptr<Vertex>, Cost> neighbours;
    int weight;
};

Next, when you add vertexes in your solution you write:

Edge* newedge=addRoad(org,dest,1);
org->edges.push_back(*newedge);
dest->edges.push_back(*newedge);

This don't make much sense for dest vertex as your edge is from orig -> dest.

Upvotes: -1

pointerless
pointerless

Reputation: 753

Change Edge from a class to a struct, or make it's properties public, classes have private members as standard whereas structs have public.

Upvotes: 0

Related Questions