I have a graph (say, about a million vertices) where the degree of every vertex is somewhat large (about 100 000). We want to find the shortest path between two vertices -- but we know the graph is such that there is a very small upper limit (say, 10) for the shortest path length. There are no edge weights (or consider them 1).
Edit: also, I probably need to run this several times on different pairs. What data structure could be used to speed this up?
Assuming that you’re using BFS — or, more likely, a bidirectional BFS — and that you have no guiding heuristic (for an A* search or the like), what you’d probably like to optimize is the time it takes to consider the neighbors of each newly discovered node. After all, if each node has 100 000 neighbors, but there are only about 1 000 000 nodes in total, most nodes will be irrelevant (i.e., already visited) really fast.
The “normal” approach would be to have, say, adjacency lists for every node, and some global set data structure (e.g., a hash) for determining whether you’ve already seen a given node. This would keep the “already visited” checks fast, but you’d have to wade through lots of irrelevant neighbors.
One alternative would be to do it the other way around. Keep a global structure (like a linked list) that lets you iterate over the remaining relevant nodes (and remove the ones you visit), and then have a lookup-table for every node instead. If the node you’re looking at in the global list is found in the local lookup-table, you add it to your queue and remove it from the global list. That way, the number of potential nodes you’d look at would (probably) decrease quite a bit.
This approach would only help after a while, though; at least in the first iteration, it would be better to iterate over the neighbors of a given node, and to look them up in a global look-up table. You can do both, however…
For the local tables, you could use some compact (possibly perfect) hash tables that would let you efficiently check for membership, as well as iterate over the neighbors in linear time. Or, if you’d like to keep things simple (probably a good idea in this case), just keep the neighbor IDs in a sorted array, and use bisection for lookup checks.
For the global list/table you need something more, however. You’d like the structure to do several things:
I’m sure there are several ways of dealing with this, but one I’ve come up with for my current research code lets you do 1., 3. and 4. in constant time with a really small memory overhead. The structure assumes that every member is represented by an integer $0\ldots n-1$, and that you have two tables of size $n$ that can accomodate such integers; let's call these $\pi$ and $\pi^{-1}$. You can then use these to represent a permutation of the members — as well as the inverse permutation. Basically, the inverse permutation $\pi^{-1}$ is simply an array of members (answering the question “Which member is in position $k$?”), while the permutation ($\pi$) gives you the location of any given member. In addition, you store the number of remanining members, $m$.
Initially, you need to fill these two arrays so that $\pi = \pi^{-1} = \langle 0, 1, 2, \ldots, n-1\rangle$, as well as set $m=n$. To reset it, though, you only need to set $m=n$ (constant time).
Adding and removing elements only requires you to swap the given member into the position just inside/outside the “cutoff point” given by $m$ (updating both $\pi$ and $\pi^{-1}$), and then to increment or decrement $m$, as needed.
To make best use of this setup, you would only have to compare $m$ to size of the neighbor array of the current node in your BFS. Iterate over whichever is smaller, and do the lookups in the other one.
Well, for example did you try sorting the list of outneighrs of each vertex according to their degree ? Sort them once and for all, then each time you do a BFS it will use this ordering, which may be a "good enough" heuristic.
I don't think the key lies in a data structure. I tried to optimise this kind of algorithm for a while, and it turns out that efficiency-speaking, storing the list of neighbors is a "good data structure" to compute BFS often.
In which language are you coding, and how is your graph structure implemented ? How much BFS do you want to run ? What is your current computing time ? How large is the graph in memory ? Is memory the key problem ? Do you compute BFS between random vertices, or do specific ones appear more often than others ?
Nathann
