Opened 12 years ago

Closed 9 years ago

#735 closed Feature Requests (fixed)

Fruchterman-Reingold grid performance can be improved

Reported by: Douglas Gregor Owned by: Jeremiah Willcock
Milestone: Boost 1.40.0 Component: graph
Version: None Severity: Optimization
Keywords: Cc:

Description (last modified by 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

Change History (5)

comment:1 Changed 11 years ago by Marshall Clow

Owner: changed from Douglas Gregor to doug_gregor
Severity: Optimization
Status: assignednew

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

comment:2 Changed 11 years ago by Douglas Gregor

Description: modified (diff)
Owner: changed from doug_gregor to Douglas Gregor

comment:3 Changed 10 years ago by Jeremiah Willcock

Owner: changed from Douglas Gregor to Jeremiah Willcock
Status: newassigned

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

comment:4 Changed 9 years ago by Jeremiah Willcock

Milestone: Boost 1.40.0
Type: BugsFeature Requests

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

comment:5 Changed 9 years ago by Jeremiah Willcock

Resolution: Nonefixed
Status: assignedclosed

This has already been applied.

Note: See TracTickets for help on using tickets.