[BGL] Fruchtermann-Reingold: grid
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?
On May 30, 2006, at 9:49 AM, Jens Müller wrote:
My questions are concerning this part: [snip existing inefficient implementation]
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? [snip more efficient solution]
Shouldn't this be (at least a bit) more efficient?
Yes, it would be. Perhaps you could work up a patch to improve the performance in this area? Doug
Douglas Gregor schrieb:
Yes, it would be. Perhaps you could work up a patch to improve the performance in this area?
Yes, no that I have CVS boost installed and working (see -user ...), I can start ... Should be ready by the weekend ... Expect more questions on both boost and boost-user in the future ...
Douglas Gregor wrote:
Yes, it would be. Perhaps you could work up a patch to improve the performance in this area?
Umm, what exactly is the stuff that was already in rev 1.9? http://boost.cvs.sourceforge.net/boost/boost/boost/graph/fruchterman_reingold.hpp?r1=1.9.2.1&r2=1.9 The log just says "Fix bug in enumerating grid-force pairs" ... Anyway, I have written something that still uses the for loops and for my test program is about 1% faster. Eliminating the for loops and writing all 4 cases by hand is, strangely enough, about 4% slower in my setup ... I have the code at home, so I'll send it this afternoon.
Jens Müller schrieb:
I have the code at home, so I'll send it this afternoon.
It's attached ... Please test if it's faster for you, too ... Index: fruchterman_reingold.hpp =================================================================== RCS file: /cvsroot/boost/boost/boost/graph/fruchterman_reingold.hpp,v retrieving revision 1.11 diff -r1.11 fruchterman_reingold.hpp 134c134 < std::size_t adj_start_row = row == 0? 0 : row - 1; ---
/* std::size_t adj_start_row = row == 0? 0 : row - 1;
147a148,201
} */
// Alternative 1: 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 && (other_row != row || other_column != column)) || (other_column == column+1 && other_row == row - 1)) {
// 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); apply_force(*v, *u); } } // Alternative 2: /* if (row != 0) { std::size_t other_row = row - 1; if (column != 0) { std::size_t other_column = column - 1; // field 1 bucket_t& other_bucket = buckets[other_row * columns + other_column]; for (v = other_bucket.begin(); v != other_bucket.end(); ++v) { apply_force(*u, *v); apply_force(*v, *u); } } // field 2 bucket_t& other_bucket = buckets[other_row * columns + column]; for (v = other_bucket.begin(); v != other_bucket.end(); ++v) { apply_force(*u, *v); apply_force(*v, *u); }
if (column != columns - 1) { // field 3 std::size_t other_column = column + 1; bucket_t& other_bucket = buckets[other_row * columns + column]; for (v = other_bucket.begin(); v != other_bucket.end(); ++v) { apply_force(*u, *v); apply_force(*v, *u); }
148a203,215
} if (column != 0) { std::size_t other_column = column - 1; // field 4 bucket_t& other_bucket = buckets[row * columns + other_column]; for (v = other_bucket.begin(); v != other_bucket.end(); ++v) { apply_force(*u, *v); apply_force(*v, *u); } } */
participants (2)
-
Douglas Gregor -
Jens Müller