Re: [boost] [BGL] Fruchtermann-Reingold: grid

31 May 2006

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