CODEWITHSUNDEEP
c++graphadjacency-list
24n8
24n8

Reputation: 2236

Efficient representation for adjacency list and weights in directed graph

I would like to get some feedback on storing adjacency lists for graphs.

I typically represent an adjacent list using a vector of vectors, e.g., std::vector<std::vector<int>> adj_list

For an edge E=(u,v), it is simply stored using adj_list[u].push_back(v). If I want to remove this edge, I simply do 

it = std::find(adj_list[u_idx].begin(), adj_list[u_idx].end(), v);
adj_list[u_idx].erase(it);

I also need a data structure for storing the weights corresponding to the edges. So originally, I was thinking of making another vector of vectors std::vector<std::vector<double>> weights, but it seems this is not the most efficient solution. Adding a new element in weights is simple, just like the above. All I have to do is weights[u].push_back(weight_to_add). But removing a weight from the weights seems a bit more difficult than doing what I did above, i.e., finding the iterator, and then using that iterator to perform the deletion. I could find the index corresponding to the iterator in adj_list, and then delete the index from weights, but I don't know if that is the best way to go about this.

So instead of having two variables to represent the adjacency list and weights, I was thinking of making a single 3-D vector that stores both the adjacency list and weights. A vector of vector of vectors. The last dimension is size 2, that stores the node ID, v, and the corresponding weight of the edge. So really, it could just be a vector of vector of arrays. So something like vector<vector<array<...>>>. But the problem here is v is an int and the weights are doubles, so obviously I can't use arrays here. I could encapsulate the two inside a struct and then do something like vector<vector<my_struct>>. Or perhaps something like vector<vector<pair<int,double>>> would be better?

Any advice on how to approach this problem?

Upvotes: 0

Views: 3167

Answers (2)

Uchiha_Sasuke
Uchiha_Sasuke

Reputation: 31

Yes you can use an adjacency list of pair of vector to do the same vector< pair<int, int> > adj[V];

void printGraph(vector<pair<int,int> > adj[], int V) 
{ 
    int v, w; 
    for (int u = 0; u < V; u++) 
    { 
        cout << "Node " << u << " makes an edge with \n"; 
        for (auto it = adj[u].begin(); it!=adj[u].end(); it++) 
        { 
            v = it->first; 
            w = it->second; 
            cout << "\tNode " << v << " with edge weight ="
                 << w << "\n"; 
        } 
        cout << "\n"; 
    } 
}

Upvotes: 1

Skriptkiddie
Skriptkiddie

Reputation: 413

Use a 

std::vector<std::vector<Entry>> adj_list

With Entry being

typedef struct {
    int node;
    double weight;

    bool operator == (const int e) const
    {
    return (node == e);
    }
} Entry;

Upvotes: 2

Related Questions