Re: [Boost-bugs] [Boost C++ Libraries] #735: Fruchterman-Reingold grid performance can be improved

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #735: Fruchterman-Reingold grid performance can be improved
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-04-29 18:28:07

#735: Fruchterman-Reingold grid performance can be improved
----------------------+-----------------------------------------------------
  Reporter:  dgregor  |       Owner:  dgregor     
      Type:  Bugs     |      Status:  new         
 Milestone:           |   Component:  graph       
   Version:  None     |    Severity:  Optimization
Resolution:  None     |    Keywords:              
----------------------+-----------------------------------------------------
Changes (by dgregor):

  * owner:  doug_gregor => dgregor

Old description:

> {{{
> 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
> }}}

New description:

 {{{
 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
 }}}

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/735#comment:2>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.