Modify

Opened 11 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

Attachments (0)

Change History (5)

comment:1 Changed 10 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 10 years ago by Douglas Gregor

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

comment:3 Changed 9 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.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Jeremiah Willcock.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.