[boost] [Boost-bugs] [ boost-Bugs-1567818 ] Fruchterman-Reingold grid performance can be improved

From: SourceForge.net (noreply_at_[hidden])
Date: 2006-09-29 11:23:03

Bugs item #1567818, was opened at 2006-09-29 11:23
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1567818&group_id=7586

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: graph
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Douglas Gregor (dgregor)
Assigned to: Douglas Gregor (dgregor)
Summary: Fruchterman-Reingold grid performance can be improved

Initial Comment:
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
----------------------------------------------------------------------
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1567818&group_id=7586
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys -- and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Boost-bugs mailing list
Boost-bugs_at_[hidden]
https://lists.sourceforge.net/lists/listinfo/boost-bugs