8

I'm currently working on a directed graph data structure in C++ (no Boost GL for this project). The primary application will be identifying connected components and sinks. The graphs are expected to be sparse (E ~ 4V upper limit on num edges) and will all be uniform weight. I'm trying to decide between adjacency list, incidence list or possibly some other representation that I haven't heard of yet (adj. matrix not an option bc of sparsity). The bottleneck is likely going to be space overall and speed of graph initialization: Graphs will be initialized from potentially huge arrays such that each element in the array will end up being a vertex with a directed edge to one of its neighboring elements. To get the edges for each vertex, all its neighboring elements must be compared first.

My questions are: (1) Which representation is typically faster to initialize and also fast for BFS traversal, (2) What algorithms (other than vanilla BFS) are there for finding connected components? I know it's O(V+E) using BFS (which is optimal, I think) but I'm worried about the size of the intermediate queue as the graph width grows exponentially with height.

Don't have too much experience with graph implementations, so I'd be grateful for any suggestions.

4
  • There's vanilla DFS for finding components as well ;) But generally speaking, you can't do faster than those; you'll have to examine every edge to decide whether it is required to connect some vertices or not. Take for example a star, a comet (meaning a star with a path as its tail) or a tree; every edge is required to connect all vertices. There's nothing faster than BFS/DFS as far as I'm aware(!), and that includes algorithms in O(|E|+|V|) with different coefficients.
    – G. Bach
    Mar 8, 2013 at 1:27
  • I guess DFS might actually be better since the intermediate stack is implicit and won't be as high as the queue will be long in BFS.
    – 42point2
    Mar 8, 2013 at 1:46
  • That depends entirely on the graph; for a path, the queue will always be 1 element, while the stack will reach the length of the path. Since your graphs are sparse, you actually may have subgraphs very similar to paths or at least something that has fewer elements in each boundary of a BFS than the longest path is.
    – G. Bach
    Mar 8, 2013 at 1:50
  • Good point, might be worth testing both for a couple of the datasets.
    – 42point2
    Mar 8, 2013 at 1:59

3 Answers 3

5

Consider a layout as follows:

enter image description here

An adjacency list can be implemented as an array of [Nx4] (n being 3 in this case, and 4 because you are saying that 4 is the maximum number of edges in your case) in the following form:

2  3  0  0
3  0  0  0
0  0  0  0

the above representation assumes that the number of vertices are in sorted order where first index into the array is given by (v-1).

Incidence list on the other hand, requires you to define a vertex list, an edge list and connection elements in between (incidence list - graph).

Both are good in terms of space usage compared to an adjacency matrix since your graph is very sparse, as you stated.

My suggestion would be to go with the adjacency list, which you can initialize as an [Nx4] contiguous array in the memory (since you are saying that you will have at most 4 edges for one vertex). This representation will be faster to initialize. (Also, this representation will perform better in terms of cache efficiency.)

However, if you expect the size of your graph changing dynamically and frequently, incidence lists might be better since they are generally implemented as lists which are non contiguous spaces (see the link above). De-allocation and allocation of the adjacency array might be undesirable in that case.

2
  • Interesting, haven't thought about representing an adj list like this - good to know, since another thing I was worried about (but didn't mention) was cache performance. The resulting matrix (aka adjacency list repr) will still be quite sparse but is definitely going to use less space than a vector-of-linked-list kind of representation that requires a lot of pointers.
    – 42point2
    Mar 8, 2013 at 1:44
  • Definitely this contiguous representation will behave much better in terms of cache performance. let me add that to the answer.
    – meyumer
    Mar 8, 2013 at 1:46
2

The most efficient way to implement a graph for your purposes probably is a combination of an adjacency list for each vertex and additionally a hashing structure that maps pairs of vertices to edges, if those exist. This'll require O(|V|+ |E|) space for the adjacency list, O(|E|) for the hashing structure and give you on expected O(1) containsEdge(vertex v, vertex w), insertEdge(vertex v, vertex w) and removeEdge(vertex v, vertex w) by using the mapping to get the pointers required to quickly modify the adjacency lists of the vertices.

1

The Adjacency matrix is good for dense graphs, they prove bad choice for large sparse graphs. Here are time and space complexities of simple operations for sparse graphs.

Sparse Graph Big O Time and Space Complexities

Consider the average number of edges less than 4 for a graph of 1 million nodes. Most modern computers are inadequate to hold the adjacency matrix, given their space complexity of O(n*n) - i.e. RAM requirement of several TB. Whereas, it can fit easily in an inexpensive laptop with basic configuration with RAM requirement of several MB.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.