I have to implement a directed graph (digraph) which is permitted to have multiple arcs (multigraph), like in the image linked. The graph has to be optimized to handle a lot of nodes but a few edges between two of them. The graph has to be frequently updated and it has to support efficient path search. Which is an efficient data structure to have a compromise between space used and time for a query? The language is standard C (only libc).
2 Answers
Supposing you have NODE_COUNT nodes. You create a vector GRAPH of length NODE_COUNT. On the entry X you have an array of variable size (dynamically allocated). Each entry looks like GRAPH[X]=[A1, A2, A3] to represent the edges { (X,A1), (X,A2), (X,A3) }.
If you need to search for some edges it is also convenient to use a binary search tree on the entry GRAPH[X]. If you have more than 6 edges for each node you can consider this possibility as well instead of using a non-ordered array on position GRAPH[X].
Because the graph has many nodes and few edges you should not use a matrix.
If you have millions or billions of nodes the problem is different and you should think at using BDDs. This is another topic, I do not enter in details in this thread. The idea is that a graph can be represented as the characteristic function of a set representing the graph.
You could use an Adjacency Matrix. It's essentially a 2D array that shows the adjacency list.
Here's an example. I believe they are fairly quick, it takes Θ(1) time to determine if an edge exists in the graph.
This would be good if "frequent updating" referred to updating the edges because it takes constant time to update one of the values. (ie. adding edge(3, 2) would take constant time because you would just increment the value at 3,2 in the matrix)
For determining shortest path Dijkstra’s algorithm would be your best bet.
Related