[boost] [BGL] Fruchtermann-Reingold: grid

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2006-05-30 09:49:43

My questions are concerning this part:

>           std::size_t adj_start_row = row == 0? 0 : row - 1;
>           std::size_t adj_end_row = row == rows - 1? row : row + 1;
>           std::size_t adj_start_column = column == 0? 0 : column - 1;
>           std::size_t adj_end_column = column == columns - 1? column : column + 1;
>           for (std::size_t other_row = adj_start_row; other_row <= adj_end_row;
>                ++other_row)
>             for (std::size_t other_column = adj_start_column; 
>                  other_column <= adj_end_column; ++other_column)
>               if (other_row != row || other_column != column) {
>                 // Repulse vertices in this bucket
>                 bucket_t& other_bucket 
>                   = buckets[other_row * columns + other_column];
>                 for (v = other_bucket.begin(); v != other_bucket.end(); ++v)
>                   apply_force(*u, *v);
>               }

In the code above, where repelling forces inside a bucket are computed,
each pair of nodes is considered only once, and then

apply_force(*u, *v);
apply_force(*v, *u);

are called.

Wouldn't something like this be more efficient here, too?

We have

+------+------+------+
|      |      |      |
|   1  |  2   |  3   |
|      |      |      |
|------|------|------|
|      |      |      |
|   4  |  X   |  6   |
|      |      |      |
|------|------|------|
|      |      |      |
|   7  |  8   |  9   |
|      |      |      |
+------+------+------+,

where X is the bucket u resides in, and the others are the adjacent
buckets considered.

For every u, all nodes from all other buckets are considered.

My proposal: Consider only 1, 2, 3 and 4 and
do
 apply_force(*u, *v);
 apply_force(*v, *u);
again

6, 7, 8 and 9 will be considered when those buckets are processed.

Shouldn't this be (at least a bit) more efficient?