src/qanLayout.cpp

   1 /*
   2 Qanava - Graph drawing library for QT
   3 Copyright (C) 2006 Benoit AUTHEMAN
   4
   5 This library is free software; you can redistribute it and/or
   6 modify it under the terms of the GNU Lesser General Public
   7 License as published by the Free Software Foundation; either
   8 version 2.1 of the License, or (at your option) any later version.
   9
  10 This library is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public
  16 License along with this library; if not, write to the Free Software
  17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18 */
  19
  20 //-----------------------------------------------------------------------------
  21 // This file is a part of the Qanava software.
  22 //
  23 // \file        qanLayout.cpp
  24 // \author      Benoit Autheman (benoit@libqanava.org)
  25 // \date        2004 May 22
  26 //-----------------------------------------------------------------------------
  27
  28
  29 // Qanava headers
  30 #include "./qanLayout.h"
  31 #include "./qanSimpleLayout.h"
  32
  33
  34 // Std headers
  35 #include <vector>
  36
  37
  38 namespace qan { // ::qan
  39
  40
  41 /* Layout Generation Management *///-------------------------------------------
  42 void    Layout::resetNodesPositions( Graph& graph )
  43 {
  44         Node::List& nodes = graph.getNodes( );
  45         for ( Node::List::iterator nodeIter = nodes.begin( ); nodeIter != nodes.end( ); nodeIter++ )
  46                 ( *nodeIter )->setPosition( -1.0f, -1.0f );
  47 }
  48 //-----------------------------------------------------------------------------
  49
  50
  51
  52 /* Random Layout Generation Management *///------------------------------------
  53 void    Random::layout( Graph& graph, QGraphicsScene* scene, QRectF r, QProgressDialog* progress, int step )
  54 {
  55         if ( progress != 0 )
  56         {
  57                 progress->setMaximum( graph.getNodeCount( ) );
  58                 progress->setValue( 0 );
  59         }
  60
  61         srand( QDateTime::currentDateTime( ).toTime_t( ) );
  62
  63         Node::List& nodes = graph.getNodes( );
  64         for ( Node::List::iterator nodeIter = nodes.begin( ); nodeIter != nodes.end( ); nodeIter++ )
  65         {
  66                 Node* node = *nodeIter;
  67
  68                 float w = ( float )( ( rand( ) % 100 ) / 100.0 * r.width( ) );
  69                 float h = ( float )( ( rand( ) % 100 ) / 100.0 * r.height( ) );
  70                 node->setPosition( w, h );
  71
  72                 if ( progress != 0 )
  73                         progress->setValue( progress->value( ) + 1 );
  74         }
  75
  76         if ( progress != 0 )
  77                 progress->close( );
  78 }
  79 //-----------------------------------------------------------------------------
  80
  81
  82 /* Force Layout Generation Management *///-------------------------------------
  83 /*! Initial positions will be generated using a fixed layout (random or colimacon) if step is
  84         superior of 1.
  85  */
  86 void    UndirectedGraph::layout( Graph& graph, QGraphicsScene* scene, QRectF r, QProgressDialog* progress, int step )
  87 {
  88         int runCount = 50;
  89         if ( step != -1 )
  90                 runCount = step;
  91         if ( progress != 0 )
  92         {
  93                 progress->setMaximum( runCount );
  94                 progress->setValue( 0 );
  95         }
  96
  97         // Generate a random layout for algorithm initialisation
  98         if ( runCount > 1 )
  99         {
 100                 //Random initalLayout;
 101                 Colimacon initalLayout;
 102                 initalLayout.layout( graph, scene, r );
 103         }
 104
 105         // Apply the spring force algorithm
 106         std::vector< VectorF > positions;
 107         positions.reserve( graph.getNodeCount( ) + 1 );  // Last position reserved for a virtual center node
 108         unsigned int n = 0;
 109         for ( ; n < graph.getNodeCount( ) + 1; n++ )
 110                 positions.push_back( VectorF( 2 ) );
 111         Node::Set nodesSet; graph.collectNodes( nodesSet );
 112
 113         _center.setPosition( r.width( ) / 2, r.height( ) / 2 );
 114         //_center.setPosition( 100., 100. );
 115         Node::List& nodes = graph.getNodes( );
 116         for ( int iter = 0; iter < runCount; iter++ )
 117         {
 118                 double modification = 0.;
 119
 120                 // Compute new nodes positions using the spring embedder model
 121                 Node::List::iterator nodeIter = nodes.begin( );
 122                 for ( n = 0; nodeIter != nodes.end( ); n++, nodeIter++ )
 123                 {
 124                         Node& node = **nodeIter;
 125
 126                         Node::Set adjacentNodes;
 127                         node.getAdjacentNodesSet( adjacentNodes );
 128                         if ( graph.isRootNode( node ) )
 129                                 adjacentNodes.insert( &_center );
 130                         VectorF fspring = computeSpringForce( node, adjacentNodes, graph );
 131                         VectorF frep = computeRepulseForce( node, adjacentNodes, nodesSet, graph );
 132
 133                         VectorF delta( 2 );
 134                         delta = ( frep + fspring ) / ( float )( nodes.size( ) + 1.f );
 135                         positions[ n ] = node.getPosition( ) + delta;
 136                         modification += length2( delta );
 137                 }
 138
 139                 // Apply modifications for a virtual center node connected to all root nodes
 140                 {
 141                         n = nodes.size( );
 142                         VectorF fspring = computeSpringForce( _center, graph.getRootNodesSet( ), graph );
 143                         VectorF frep = computeRepulseForce( _center, graph.getRootNodesSet( ), nodesSet, graph );
 144
 145                         VectorF delta( 2 );
 146                         delta = ( frep + fspring ) / ( float )( nodes.size( ) + 1.f );
 147                         positions[ n ] = _center.getPosition( ) + delta;
 148                 }
 149
 150                 // Move the nodes to their new positions
 151                 int p = 0;
 152                 for ( nodeIter = nodes.begin( ); nodeIter != nodes.end( ); nodeIter++, p++ )
 153                         ( *nodeIter )->setPosition( positions[ p ] );
 154                 _center.setPosition( positions[ nodes.size( ) ] );
 155
 156                 // Stop iterating if node have converged to a fixed position
 157                 if ( modification < ( 5. * nodes.size( ) ) )
 158                         break;
 159
 160                 // Update progress bar
 161                 if ( progress != 0 )
 162                         progress->setValue( iter );
 163
 164                 // Detect process interruption
 165                 if ( progress != 0 && progress->wasCanceled( ) )
 166                         break;
 167         }
 168
 169         if ( progress != 0 )
 170                 progress->close( );
 171 }
 172
 173 VectorF UndirectedGraph::computeRepulseForce( Node& u, Node::Set& adjacentNodes, Node::Set& nodes, Graph& graph )
 174 {
 175         VectorF force( 2 );
 176         force( 0 ) = force( 1 ) = 0.f;
 177
 178         // Compute repulsion forces for all non adjacent nodes
 179         Node::Set nonAdjacentNodes( nodes );
 180         nonAdjacentNodes.subtract( adjacentNodes );
 181         if ( !graph.isRootNode( u ) )
 182                 nonAdjacentNodes.insert( &_center );
 183
 184         Node::Set::iterator nonAdjacentNodeIter = nonAdjacentNodes.begin( );
 185         for ( ; nonAdjacentNodeIter != nonAdjacentNodes.end( ); nonAdjacentNodeIter++ )
 186         {
 187                 Node& v = **nonAdjacentNodeIter;
 188                 if ( &v == &u )
 189                         continue;
 190
 191                 // Compute repulsion forces between item and
 192                 VectorF& pu = u.getPosition( );
 193                 VectorF& pv = v.getPosition( );
 194                 VectorF uv = pv - pu;
 195                 uv *= - ( 80 * 80 ) / ( 1.0 + length2( uv ) );
 196                 force += uv;
 197         }
 198         return force;
 199 }
 200
 201 VectorF UndirectedGraph::computeSpringForce( Node& u, Node::Set& adjacentNodes, Graph& graph )
 202 {
 203         VectorF force( 2 );
 204         force( 0 ) = 0.f; force( 1 ) = 0.f;
 205
 206         // Compute attraction forces for all adjacent nodes (roots nodes are considered adjacents)
 207         Node::Set::iterator adjacentNodeIter = adjacentNodes.begin( );
 208         for ( ; adjacentNodeIter != adjacentNodes.end( ); adjacentNodeIter++ )
 209         {
 210                 Node& v = **adjacentNodeIter;
 211
 212                 // Compute attraction forces between item and
 213                 VectorF& pu = u.getPosition( );
 214                 VectorF& pv = v.getPosition( );
 215                 VectorF uv = pv - pu;
 216
 217                 double l = length( uv ) / 100.f;
 218                 double size = 1.;
 219                 if ( l > 1.0 )
 220                         size = 2.f * log( l );
 221
 222                 uv *= size;
 223                 force += uv;
 224         }
 225
 226         return force;
 227 }
 228
 229 float           UndirectedGraph::length( const VectorF& v )
 230 {
 231         return sqrt( ( v( 0 ) * v( 0 ) ) + ( v( 1 ) * v( 1 ) ) );
 232 }
 233
 234 float           UndirectedGraph::length2( const VectorF& v )
 235 {
 236         return ( v( 0 ) * v( 0 ) ) + ( v( 1 ) * v( 1 ) );
 237 }
 238 //-----------------------------------------------------------------------------
 239
 240
 241 } // ::qan