Efficient Adjacency list.
Hello,
In most of my graph-problem projects, I've been working with a n² distance matrix. As an experiment, I'm going to try a radically different encoding of my solutions, which is based on linked lists rather than the usual position vectors.
One of my goals is to get improved locality of reference. Instead of having large, external matrices with all data where look-ups appear sporadically, I'm going to try to get all data related to a Node in/near that Node. This includes their part of the distance matrix.
Now, I could simply cut rows out of the matrix and have Node[i] store Row[i]. For a complete graph, I'm guessing this is by far the easiest and probably even best solution. However, to speed up certain phases of the algorithm, I want to remove costly edges and just keep a subset N' best edges. However, this means that edge[j] no longer contains the distance from the current node to 'j'.
So, what I'm looking for is a good way to store a subset of edges, so that
a) Checking if J is "reachable" from current, and
b) Checking the distance to any reachable J,
is efficient.
In the original, a) was O(1), with the only slowdown being the cost of accessing a random spot of memory in a very large array. Regardless of how "random" the access is, I except the newer version will take a performance hit here, even if the data is very close to other data currently being read.
For b), the cost was a random memory access in a large array, plus comparing the result to a specified number (often another random access in a different very large array). I'm hoping to speed this up.
The size of N' is going to be quite small compared to the full set N. Think around N~[1000->20.000] and N'~[1%->5% of N]. I haven't decided whether the size of N' will be constant, constant-per-run or entirely variable; I'm waiting until I've decided on an implementation before I make this decision.
Anyone have an idea? I'm sort of expecting this version to be slower, but I'm still hoping for comparable speed with less memory requirements [it's not really an issue; it's mostly out of curiosity].
Any insights and tips are welcome!
In most of my graph-problem projects, I've been working with a n² distance matrix. As an experiment, I'm going to try a radically different encoding of my solutions, which is based on linked lists rather than the usual position vectors.
One of my goals is to get improved locality of reference. Instead of having large, external matrices with all data where look-ups appear sporadically, I'm going to try to get all data related to a Node in/near that Node. This includes their part of the distance matrix.
Now, I could simply cut rows out of the matrix and have Node[i] store Row[i]. For a complete graph, I'm guessing this is by far the easiest and probably even best solution. However, to speed up certain phases of the algorithm, I want to remove costly edges and just keep a subset N' best edges. However, this means that edge[j] no longer contains the distance from the current node to 'j'.
So, what I'm looking for is a good way to store a subset of edges, so that
a) Checking if J is "reachable" from current, and
b) Checking the distance to any reachable J,
is efficient.
In the original, a) was O(1), with the only slowdown being the cost of accessing a random spot of memory in a very large array. Regardless of how "random" the access is, I except the newer version will take a performance hit here, even if the data is very close to other data currently being read.
For b), the cost was a random memory access in a large array, plus comparing the result to a specified number (often another random access in a different very large array). I'm hoping to speed this up.
The size of N' is going to be quite small compared to the full set N. Think around N~[1000->20.000] and N'~[1%->5% of N]. I haven't decided whether the size of N' will be constant, constant-per-run or entirely variable; I'm waiting until I've decided on an implementation before I make this decision.
Anyone have an idea? I'm sort of expecting this version to be slower, but I'm still hoping for comparable speed with less memory requirements [it's not really an issue; it's mostly out of curiosity].
Any insights and tips are welcome!
Topic archived. No new replies allowed.