src/la/laTimeTree.h

   1 /*
   2 Qanava - Graph drawing library for QT
   3 Copyright (C) 2005 Benoit AUTHEMAN
   4
   5 This program is free software; you can redistribute it and/or
   6 modify it under the terms of the GNU General Public License
   7 as published by the Free Software Foundation; either version 2
   8 of the License, or (at your option) any later version.
   9
  10 This program 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
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; 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        laTimeTree.h
  24 // \author      Benoit Autheman (benoit@faktiss.net)
  25 // \date        2004 December 05
  26 //-----------------------------------------------------------------------------
  27
  28
  29 #ifndef laTimeTree_h
  30 #define laTimeTree_h
  31
  32
  33 // UTL headers
  34 #include "../utl/utlManager.h"
  35 #include "../utl/utlProgress.h"
  36
  37
  38 // Qanava headers
  39 #include "laLayout.h"
  40 #include "laGrid.h"
  41
  42
  43 // Boost headers
  44 #ifndef DOXYSKIP
  45 #include "boost/date_time/posix_time/posix_time.hpp"
  46 #endif
  47
  48 //-----------------------------------------------------------------------------
  49 namespace qan { // ::qan
  50         namespace la { // ::qan::la
  51
  52         //! Layout a graph in space taking into account group membership (clusters) and respecting a chronological order.
  53         /*!
  54
  55                 <img src="./images/qan-timetree_shot.png" alt="Qanava timetree sample">
  56
  57                 \nosubgrouping
  58         */
  59         class TimeTree : public Layout
  60         {
  61         public:
  62
  63                 //! Sort nodes on the basis of their date (older first).
  64                 struct NodeDateComp
  65                 {
  66                         bool operator()( const Node* n1, const Node* n2 ) const;
  67                 };
  68
  69                 //! STL set sorting node by date.
  70                 typedef std::multiset< la::Node*, NodeDateComp >        NodeSet;
  71
  72                 //! Manager of NodeSet objects.
  73                 typedef utl::Manager< NodeSet >                                         NodeSetManager;
  74
  75         protected:
  76
  77                 //! Construct the grid for a cluster based time tree graph layout.
  78                 /*!
  79                         \nosubgrouping
  80                 */
  81                 class GridBuilder
  82                 {
  83                         /*! \name TimeTree Grid Management *///----------------------------
  84                         //@{
  85                 public:
  86
  87                         //! .
  88                         GridBuilder( la::Grid& grid ) : _grid( grid ) { }
  89
  90                 public:
  91
  92                         //! Add _one_ grid element for a given cluster coordinates.
  93                         void    buildClusterGrid( int cy, int w, int h, int r, int g, int b );
  94
  95                         //! Add all horizontal time grid elements for the given (sorted) nodes.
  96                         void    buildTimeGrid( NodeSet& nodes, int width, int height );
  97
  98                         //! .
  99                         void    buildTimeLabel( Node& node, int x, int y );
 100
 101                         //! .
 102                         Grid&   getGrid( ) { return _grid; }
 103
 104                 private:
 105
 106                         //! .
 107                         Grid&   _grid;
 108                         //@}
 109                         //-----------------------------------------------------------------
 110                 };
 111
 112         public:
 113
 114                 //! Models a group of nodes in the same track (usually a group equals a cluster of nodes).
 115                 /*!
 116                         \nosubgrouping
 117                 */
 118                 class Group
 119                 {
 120                 private:
 121
 122                         class GroupMedDateComp
 123                         {
 124                         public:
 125                                 bool operator()( const Group* g1, const Group* g2 ) const;
 126                         };
 127
 128                 public:
 129
 130                         //! .
 131                         Group( ) { }
 132
 133                         //! .
 134                         ~Group( ) { }
 135
 136                         //! Add a group of nodes corresponding to a line of nodes for a given cluster.
 137                         /*! The node must be sorted by date ascending order.                                                    */
 138                         void                            addLine( la::Node::Nodes* lineNodes ) { _lines.push_back( lineNodes ); }
 139
 140                         //! Get the number of lines in this group.
 141                         int                                     getLineCount( ) const { return _lines.size( ); }
 142
 143                         //! Get the ith line in this group.
 144                         la::Node::Nodes*        getLine( unsigned int line );
 145
 146                         //! Collect this group nodes to a given node list (list can be non emtpy).
 147                         void                            collectNodes( la::Node::Nodes& nodes ) const;
 148
 149                         //! Affect a given style type to all of this group nodes.
 150                         void                            setNodesType( int type );
 151
 152                         //! Test if a group intersect with this group time interval.
 153                         bool                            intersect( const Group& group ) const;
 154
 155                         //! Get this group median date.
 156                         boost::posix_time::ptime        getMedianDate( ) const;
 157
 158                         typedef std::list< Group* >                                                     Groups;
 159
 160                         typedef std::vector< la::Node::Nodes* >                         Lines;
 161
 162                         //! STL multi set with median date group sorting.
 163                         typedef std::multiset< Group*, GroupMedDateComp >       GroupSet;
 164
 165                 protected:
 166
 167                         //! Nodes in each lines must be stored in .
 168                         Lines           _lines;
 169                 };
 170
 171
 172         protected:
 173
 174                 //! Models a line of related groups of nodes (the track form a line, but the group in the track can take ultiple single lines).
 175                 /*!
 176                         \nosubgrouping
 177                 */
 178                 class Track
 179                 {
 180                 public:
 181
 182                         Track( ) { }
 183
 184                         void    addGroup( Group* group ) { _groups.push_back( group ); }
 185
 186                         //! Test if a given track time duration interval is disjoint from this track own duration.
 187                         bool    isDisjointOf( Track& track );
 188
 189                         //! Merge a given track groups to this track.
 190                         void    mergeTrack( Track& track );
 191
 192                         typedef std::list< Track* >     Tracks;
 193
 194                         int             getLineCount( ) const;
 195
 196                         float   layout( float trackY, float width, GridBuilder& gridBuilder );
 197
 198                         //! Collect groups in this track sorted by group's average date.
 199                         void    collectGroups( Group::Groups& groups );
 200
 201                         Group::Groups&  getGroups( ) { return _groups; }
 202
 203                         int             getNodeCount( ) const;
 204
 205                 protected:
 206
 207                 private:
 208
 209                         Group::Groups   _groups;
 210                 };
 211
 212
 213                 //! Sort tracks on the basis of their node (spatial) density.
 214                 struct TrackDensityComp
 215                 {
 216                         bool operator()( const Track* t1, const Track* t2 ) const;
 217                 };
 218
 219
 220                 //! Model a series of tracks.
 221                 /*!
 222                         \nosubgrouping
 223                 */
 224                 class Tracks
 225                 {
 226                 public:
 227
 228                         Tracks( ) { }
 229
 230                         void    addTrack( Track* track );
 231
 232                         void    mergeTracks( );
 233
 234                         float   layout( float width, GridBuilder& gridBuilder );
 235
 236                         //! Collect all tracks group to a group list in the left-right top to bottom order.
 237                         void    collectGroups( Group::Groups& groups );
 238
 239                         void    sortByNodeDensity( );
 240
 241                 protected:
 242
 243                         Track::Tracks   _tracks;
 244                 };
 245
 246
 247                 /*! \name TimeTree Constructor/Destructor *///-------------------------
 248                 //@{
 249         public:
 250
 251                 //! TimeTree constructor.
 252                 TimeTree( NodeSetManager& nodeSetManager ) :
 253                         Layout( ),
 254                         _nodeSetManager( nodeSetManager ) { }
 255
 256                 ~TimeTree( )
 257                 {
 258
 259                 }
 260
 261         private:
 262
 263                 //! .
 264                 NodeSetManager&         _nodeSetManager;
 265                 //@}
 266                 //---------------------------------------------------------------------
 267
 268
 269
 270                 /*! \name TimeTree Layout Generation Management *///-------------------
 271                 //@{
 272         public:
 273
 274                 static float incX;
 275
 276                 static float lineIntervalY;
 277
 278                 static float trackIntervalY;
 279
 280                 //! .
 281                 virtual void    layout( la::Graph& graph, la::Grid& grid, int width, int height, utl::Progress& progress );
 282
 283         protected:
 284
 285                 //! Set nodes horizontal position, and return the resulting layout width.
 286                 float                   layoutNodesX( NodeSet& nodes );
 287
 288                 //! .
 289                 Group*                  buildGroup( NodeSet& clusterNodes );
 290                 //@}
 291                 //---------------------------------------------------------------------
 292         };
 293         } // ::qan::la
 294 } // ::qan
 295 //-----------------------------------------------------------------------------
 296
 297
 298 #endif // laTimeTree_h
 299