Fruchterman-Reingold grid performance can be improved

[Douglas Gregor]

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);
            }
          } */


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/
listinfo.cgi/boost

[Marshall Clow]

Assigned to "doug_gregor" instead of nonexistent user "dgregor"

[Jeremiah Willcock]

Does this issue still apply to the current version of Boost? If so, could I please get a unified diff for your patch?

[Jeremiah Willcock]

I need a new version of the patch to apply before I can do anything with this bug.

[Jeremiah Willcock]

This has already been applied.