Archived

This topic is now archived and is closed to further replies.

Sir Valeq

Graph

Recommended Posts

Sir Valeq    122
Hi! I am to write a program, which is supposed to calculate the shortest paths in a graph using the Bellman-Ford algoritm. I found the algoritm, even find it not very complicated, but... My question is: how should I implement this graph in my code? Should I keep a list of vertices and a "neighbourhood matrix" (I don''t know how to call it)? It can be even a graph with a static number of vertices and edges. Only the weights of the edges would be dynamic values. I''ll be grateful for any, any, any help. I also have to draw this graph, but I think I can manage doing it in OpenGL. I prefer DX, for I do know far more about it, but there are so many tuts about OGL, that I thinks it''s not going to be a problem. -------------- "We cannot all be masters." - William Shakespeare

Share this post


Link to post
Share on other sites
snk_kid    1312
Hi i haven''t done much graph theory but do you need to make your own graph type? boost libaries have a graph type thats STL like

Share this post


Link to post
Share on other sites
Matei    190
There are two ways to represent a graph. Which one you choose depends on the properties of the graph and on what you want to do with it.

In both ways, name each graph vertex by a number from 0 to V-1 (V being the number of vertices).

In the "adjacency matrix" representation, have a two-dimensional V x V array of values, such that adj[v1][v2] = the cost of the edge from v1 to v2. If there is no edge between two vertices, use a sentinel value like infinity. If you need some extra information for each edge, you can instead have a 2D array of Edge objects; each object might also store whether there is an edge there (so you can do something like if(adj[v1][v2].exists) {cost += adj[v1][v2].cost}). This representation clearly takes O(V^2) space, since you have a V by V array.

In the "adjacency list" representation, have a one-dimensional array of V linked lists (or even STL vector objects) of Edge objects. Each edge stores a cost and a destination. To get all the neighbours of node v1, look through the Edge objects in its linked list. This representation takes O(V+E) size: there is one Edge entry for each edge, and there are V lists. However, there may be more overhead (a larger constant hidden by the O) because either you have to store a pointer within each linked list node to the next node, or you have extra space allocated by each vector, etc.

How to decide which one to use? It depends on your actual graph and what you'll be doing with it.
- Is the graph dense or sparse? That is, are there lots of edges or very few edges? For a dense graph, use the matrix, and for a sparse graph, use the list reperesentation. For example, if there was an edge between every two vertices, you'd have O(V^2) edges, so using the adjacency list would not help much. On the other hand, if you had only about two edges per node, you'd have O(V) edges and you'd be wasting a lot of space using the adjacency matrix.
- Will you need to frequently find all the neighbours of a vertex? In that case, using an adjancency list is better because in the adjacency matrix you have to go through a whole row of V elements (many of which might say "there's no edge here") to find the neighbours of a given vertex, whereas in the list you see only these neighbours.
- Will you need to frequently find the cost between two arbitrary vertices? In that case, the matrix is better since you just have to look at one entry instead of looking through the entire adjacency list of a node.
- Might there be multiple edges between the same two vertices? This is harder to represent with an adjacency matrix; you'd need a 2D array of linked lists.
- Is the graph really small? If there are only, say, 100 vertices, it probably doesn't matter what representation you choose, since you will never notice the inefficiency.

I think that for the Bellman-Ford algorithm, you're iterating through all of the edges of the graph, so the adjacency list might be better as long as your graph isn't very dense, since it stores only the edges and no extra information.

[edited by - Matei on May 25, 2004 8:52:28 AM]

[edited by - Matei on May 25, 2004 8:54:36 AM]

Share this post


Link to post
Share on other sites
Sir Valeq    122
Thanks, it''s always nice to read some theoretical stuff written in an easy-to-understand way.
I think that the way with the adjacency matrix will fit my problem, because it''s easy to implement, and I don''t have much time for this program.
If I encounter any further problems, I hope you can help me again.
Thanks.


--------------
"We cannot all be masters." - William Shakespeare

Share this post


Link to post
Share on other sites