src/qanTimeTree.h

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