12

at first i am a beginner at c++ and i am self learning it, so please be quite simple in answers ...

i need to program a graph that contains nodes each node has id and list of edges each edge has the other node id and the distance

what i am looking for is what should i use to build this graph considering that i wants to use dijkstra algorithm to get the shortest path form one point to the other ... so searching performance should be the most important i think !!

i have searched a lot and i am so confused now

thank you in advance for the help

unkulunkulu
  • 11,576
  • 2
  • 31
  • 49
Dawnlight
  • 179
  • 1
  • 2
  • 11

4 Answers4

12

You can define an Edge structure like

struct Edge
{
    int destination;
    int weight;
};

And create a graph as

vector<vector<Edge> > graph;

Then to access all the edges coming from the vertex u, you write something like

for( int i = 0; i < graph[u].size(); ++i ) {
    Edge edge = graph[u][i];
    // here edge.destination and edge.weight give you some details.
}

You can dynamically add new edges, for example an edge from 3rd vertex to 7th with a weight of 8:

Edge newEdge;
newEdge.destination = 7;
newEdge.weight = 8;
graph[3].push_back( newEdge );

etc.

For undirected graphs you should not forget to add the symmetric edge, of course.

This should do ok.

Edit The choice of base containers (std::vector, std::list, std::map) depends on the use case, e.g. what are you doing with the graph more often: add/remove vertices/edges, just traversing. Once your graph is created, either std::list or std::vector is equally good for Dijkstra, std::vector being a bit faster thanks to sequential access pattern of the relaxation stage.

unkulunkulu
  • 11,576
  • 2
  • 31
  • 49
  • 1
    this answer i already know .. i am asking if the vector is the best thing to use .. for the performance ?? and which is better map or vecotrs ?? – Dawnlight Jul 29 '11 at 20:02
  • thanks for the edit it clears things up but if i want to sort the graph nodes and the edges according to id a heap sort .. will this make it faster ?? and if yes .. what should i use to do such thing ?? – Dawnlight Jul 29 '11 at 20:22
  • These are general programming questions independent of graphs, right? You should ask a separate question (first search for one though) – unkulunkulu Jul 29 '11 at 20:26
  • i should program my graph according to what i wants to build it for ... so i need it to implement dijkstra effiecintly putting in mine that graph will have huge number of nods and edges – Dawnlight Jul 29 '11 at 20:37
  • if you need to read graph from some place, run dijkstra and output the results, vector of vectors is perfect. – unkulunkulu Jul 29 '11 at 20:48
  • 1
    @Dawnlight If you want to do performance programming, you typically need exactly these containers, in order of frequency: `std::vector<>`, `std::unordered_map<>`, and `std::unordered_set<>`. All other containers are outperformed by one of these three in any use case, they just have to be used correctly. – cmaster - reinstate monica Mar 24 '18 at 10:21
0

Use unordered_map<int,vector<int>> to represent adjacency list if you have huge number of vertexes. If you're planning on implementing a small scale graph, then go with array of vectors. Eg: vector<int> v[20];

Guru Nadhan
  • 1
  • 2
-1

I personally would use a std::map<Node*, std::set<Node*> >. This is extremely useful because each time you are at a node, you can quickly find out which nodes that node is connected to. It is also really easy to iterate over all the nodes if you need to. If you need to put weights on the edges, you could use std::map<Node*, std::set< std::pair<int, Node*> > >. This will give much better performance than using vectors, especially for large graphs.

setholopolus
  • 253
  • 3
  • 17
  • `std::vector<>` outperforms `std::map<>` anytime, and `std::vector<>` outperforms `std::set<>` when you don't need ordering. Both `std::map<>` and `std::set<>` rely on trees internally, and thus have much higher allocation overhead while broadly scattering the data about. `std::vector<>` uses a contiguous array internally, and is thus 1. memory efficient, 2. cache efficient, 3 allocation efficient, 4. prefetching friendly. Really, `std::map<>` and `std::set` are *not* a part of the optimizer's toolbox. – cmaster - reinstate monica Mar 24 '18 at 10:15
  • I really think that for doing complex algorithms across large graphs with lots of access, `std::map<>` and `std::set<>` would win because of lower exponential access time. I would be open to seeing benchmarks that prove me wrong though. – setholopolus Mar 24 '18 at 16:07
  • 1
    No, they definitely won't: Access time of `std::vector<>` is a single pointer dereference operation on the machine level, while both `std::map<>` and `std::set<>` have to traverse a tree, which means `log(n)` pointer dereference operations. **Especially** for large data sets, where the trees are deep. You cannot beat the performance of a contiguous array in memory. – cmaster - reinstate monica Mar 24 '18 at 19:27
  • 2
    Ok, yes, of course vector is better if you know the index of what you are looking for. I was thinking more of the case when you don't, then look up is worse for vectors. – setholopolus Mar 25 '18 at 01:08
-1

a graph that contains nodes each node has id and list of edges each edge has the other node id and the distance

If we consider each node id as an index. We can draw an nxn matrix of the edges as follows.

This can help you draw the graph with edges.

     [0][1][2][3]

[0] | 1  0  0  0|
[1] | 0  0  1  0|
[2] | 1  0  0  1|
[3] | 0  0  1  0|

So, a 2D array is a good representation of matrix.

int maxtrix[4][4] = new int[4][4];
Sorter
  • 9,704
  • 6
  • 64
  • 74
  • 2
    This is not a performant solution if the matrix is sparse, which you have to assume when Dijkstra's algorithm comes into play. The performance will be lost searching for non-zero edges leading away from a given node. – cmaster - reinstate monica Mar 24 '18 at 10:07
  • Thanks for the comment. In case the data turns in into a sparse matrix, We must apply a better-suited algorithm or use the Yale format. – Sorter Mar 24 '18 at 10:26