src/qanTreeLayout.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        qanTreeLayout.h
  24 // \author      Benoit Autheman (benoit@libqanava.org)
  25 // \date        2007 January 06
  26 //-----------------------------------------------------------------------------
  27
  28
  29 #ifndef qanTreeLayout_h
  30 #define qanTreeLayout_h
  31
  32
  33 // Qanava headers
  34 #include "./qanLayout.h"
  35
  36
  37 //-----------------------------------------------------------------------------
  38 namespace qan { // ::qan
  39
  40
  41         //! Layout an undirected graph as a directed top-down tree.
  42         /*!
  43                 \nosubgrouping
  44         */
  45         class HierarchyTree : public Layout
  46         {
  47                 /*! \name HierarchyTree Constructor/Destructor *///---------------------
  48                 //@{
  49         public:
  50
  51
  52                 //! HierarchyTree constructor with orientation initialization.
  53                 /*! \param spacing spacing between node on x and y (ex: 120, 70 with Qt::Vertical).     */
  54                 HierarchyTree( QPointF spacing, QPointF origin = QPointF( 0., 0. ), Qt::Orientation orientation = Qt::Vertical ) :
  55                         Layout( ), _spacing( spacing ), _origin( origin ), _orientation( orientation )
  56                 {
  57                         if ( orientation == Qt::Horizontal )    // Layout is computed for vertical, swap parameters when laying out horizontaly
  58                         {
  59                                 _spacing.rx( ) = spacing.y( );
  60                                 _spacing.ry( ) = spacing.x( );
  61                                 _origin.rx( ) = origin.y( );
  62                                 _origin.ry( ) = origin.x( );
  63                         }
  64                 }
  65                 //@}
  66                 //---------------------------------------------------------------------
  67
  68
  69
  70                 /*! \name Hierarchy Layout Generation Management *///------------------
  71                 //@{
  72         public:
  73
  74                 //! Layout a graph as a hierarchy tree.
  75                 virtual void    layout( Graph& graph, QGraphicsScene* scene,
  76                                                                 QRectF r, QProgressDialog* progress = 0, int step = -1 );
  77
  78         protected:
  79
  80                 //! Layout a node hierarchy as a hierarchy tree.
  81                 void                    layout( Node& node, QRectF& bbox, int depth, QProgressDialog* progress = 0, int step = 0 );
  82
  83                 QPointF                 _origin;
  84
  85                 //! Spacing on x and y between tree nodes.
  86                 QPointF                 _spacing;
  87
  88                 //! Generated tree orientation.
  89                 Qt::Orientation _orientation;
  90
  91                 //! Container for already laid out nodes.
  92                 Node::Set               _marked;
  93                 //@}
  94                 //---------------------------------------------------------------------
  95         };
  96
  97
  98
  99         //!     Layout a tree using a greedy spatial optimisation based on the binary tree layout algorithm from Chan (1999).
 100         /*!
 101                 While this layout algorithm is stricly upward and preserve node order, two node at the
 102                 same depth might not be drawn at the same level (y). This algorithm might not be suitable for
 103                 drawing hierarchy (use the HierarchyTree algorithm instead).
 104
 105                 \nosubgrouping
 106         */
 107         class ChanTree : public Layout
 108         {
 109                 /*! \name HierarchyTree Constructor/Destructor *///---------------------
 110                 //@{
 111         public:
 112
 113                 //! .
 114                 /*! */
 115                 ChanTree( );
 116                 //@}
 117                 //---------------------------------------------------------------------
 118
 119
 120
 121                 /*! \name Hierarchy Layout Generation Management *///------------------
 122                 //@{
 123         public:
 124
 125                 //! Layout a graph as a hierarchy tree.
 126                 virtual void    layout( Graph& graph, QGraphicsScene* scene,
 127                                                                 QRectF r, QProgressDialog* progress = 0, int step = -1 );
 128
 129         protected:
 130
 131                 void                    layoutSubTree( Node& node, Node::Set& leafTrees, QMap< Node*, QRectF >& bboxes );
 132
 133                 void                    applyLeftRule( Node& root, Node::List& left, Node::List& right, QMap< Node*, QRectF >& bboxes );
 134
 135                 void                    applyRightRule( Node& root, Node::List& left, Node::List& right, QMap< Node*, QRectF >& bboxes );
 136
 137                 //! Perform a simple layout for a leaf subtree (node being the root of a tree of depth 2).
 138                 /*!
 139                         See "Drawing Graphs - Methods end Models" p50 for details.
 140
 141                         \param  node    root of a tree of depth 2.
 142                  */
 143                 void                    trivialLayout( Node& node, QMap< Node*, QRectF >& bboxes );
 144
 145                 //! Add all leaf tree root node to a given set.
 146                 /*!
 147                         \param  leafTrees       All result leaft tree root nodes will be added in this (not necessarilly empty) set.
 148                         \return return          Return value is used internally for recursion control and should be ignored.
 149                 */
 150                 bool                    findLeafTrees( Node& node, Node::Set& leafTrees );
 151
 152                 //! Transform all node coordinate from their local coordinate system the a global tree CS.
 153                 /*!
 154                         A VectorF( 2 ) with tree origin coordinates must be specified for the root node.
 155
 156                         \param  node    root node for the tree that must be translated.
 157                 */
 158                 void                    transformPositions( QGraphicsScene* scene, Node& node, VectorF current, QMap< Node*, QRectF >& bboxes, Node::Set& leafTrees );
 159
 160                 //! Compute a bounding box enclosing all bounding boxes for a given set of nodes.
 161                 QRectF                  computeHorizontalBbox( Node::List& nodes, QMap< Node*, QRectF >& bboxes );
 162
 163                 //! Recursively compute a bounding boxe for a given node.
 164                 /*!
 165                         Bounding box will be specified in the node local coordinate system, to obtain a bounding
 166                         box valid in the super node, it must be translated by its node position.
 167                 */
 168                 QRectF                  computeBBox( Node& node, QMap< Node*, QRectF >& bboxes );
 169
 170         private:
 171
 172                 QRectF                  computeBBox( Node& node, VectorF current, QMap< Node*, QRectF >& bboxes );
 173                 //@}
 174                 //---------------------------------------------------------------------
 175         };
 176 } // ::qan
 177 //-----------------------------------------------------------------------------
 178
 179
 180 #endif // qanTreeLayout_h
 181