/* Qanava - Graph drawing library for QT Copyright (C) 2006 Benoit AUTHEMAN This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ //----------------------------------------------------------------------------- // This file is a part of the Qanava software. // // \file laLayout.h // \author Benoit Autheman (benoit@libqanava.org) // \date 2004 May 22 //----------------------------------------------------------------------------- #ifndef laLayout_h #define laLayout_h // Qanava headers #include "../utl/utlProgress.h" #include "./laGraph.h" #include "./laGrid.h" // STD headers #include // QT headers #include //----------------------------------------------------------------------------- namespace qan { // ::qan namespace la { // ::qan::la //! Abstract interface defining a graph layout algorithm (placement of node in space). /*! \nosubgrouping */ class Layout { public: /*! \name Layout Constructor/Destructor *///--------------------------- //@{ //! Layout constructor. Layout( ) { } //! Layout virtual destructor. virtual ~Layout( ) { } private: Layout( const Layout& l ); //@} //--------------------------------------------------------------------- /*! \name Layout Generation Management *///---------------------------- //@{ public: //! Layout nodes from a given graph using r as a clipping rect, and update grid. virtual void layout( la::Graph& graph, la::Grid& grid, QRectF r, utl::Progress& progress, int step = -1 ) = 0; protected: //! Reset all nodes positions. static void resetNodesPositions( la::Graph& graph ); //@} //--------------------------------------------------------------------- }; //! Randomly layout an undirected graph. /*! \nosubgrouping */ class Random : public Layout { /*! \name Random Constructor/Destructor *///--------------------------- //@{ public: //! Random constructor. Random( ) : Layout( ) { } //@} //--------------------------------------------------------------------- /*! \name Random Layout Generation Management *///--------------------- //@{ public: //! . virtual void layout( la::Graph& graph, la::Grid& grid, QRectF r, utl::Progress& progress, int step = -1 ); //@} //--------------------------------------------------------------------- }; //! Layout a graph as concentric circles of nodes. /*! \nosubgrouping */ class Concentric : public Layout { /*! \name Concentric Constructor/Destructor *///----------------------- //@{ public: //! Concentric constructor. Concentric( double azimutDelta = 45., double circleInterval = 50. ) : Layout( ), _azimutDelta( azimutDelta ), _circleInterval( circleInterval ) { } private: double _azimutDelta; double _circleInterval; //@} //--------------------------------------------------------------------- /*! \name Concentric Layout Management *///---------------------------- //@{ public: //! . virtual void layout( la::Graph& graph, la::Grid& grid, QRectF r, utl::Progress& progress, int step = -1 ); //@} //--------------------------------------------------------------------- }; //! Layout nodes in a (logarithm) colimacon. /*! \nosubgrouping */ class Colimacon : public Layout { /*! \name Colimacon Constructor/Destructor *///------------------------ //@{ public: //! Colimacon constructor. Colimacon( double azimutDelta = 15., double circleInterval = 10. ) : Layout( ), _azimutDelta( azimutDelta ), _circleInterval( circleInterval ) { } private: double _azimutDelta; double _circleInterval; //@} //--------------------------------------------------------------------- /*! \name Colimacon Layout Management *///----------------------------- //@{ public: //! . virtual void layout( la::Graph& graph, la::Grid& grid, QRectF r, utl::Progress& progress, int step = -1 ); //@} //--------------------------------------------------------------------- }; //! Layout an undirected graph as a directed top-down tree. /*! \nosubgrouping */ class DirectedTree : public Layout { /*! \name DirectedTree Constructor/Destructor *///--------------------- //@{ public: //! Define layout orientation. enum Orientation { //! . NONE = 0, //! . HORIZONTAL = 1, //! . VERTICAL = 2 }; //! DirectedTree constructor with orientation initialization. /*! \param spacing spacing between node on x and y (ex: 120, 70 with VERTICAL). */ DirectedTree( const VectorF& spacing, Orientation orientation ) : Layout( ), _origin( 2 ), _spacing( spacing ), _orientation( orientation ), _stopRecursion( false ) { _origin( 0 ) = 0.f; _origin( 1 ) = 0.f; } //! DirectedTree constructor with origin and orientation initialization. /*! \param spacing spacing between node on x and y (ex: 120, 70 with VERTICAL). */ DirectedTree( const VectorF& origin, const VectorF& spacing, Orientation orientation ) : Layout( ), _origin( origin ), _spacing( spacing ), _orientation( orientation ), _stopRecursion( false ) { } private: VectorF _origin; //@} //--------------------------------------------------------------------- /*! \name Hierarchy Layout Generation Management *///------------------ //@{ public: //! Layout a graph as a hierarchy tree. virtual void layout( la::Graph& graph, la::Grid& grid, QRectF r, utl::Progress& progress, int step = -1 ); protected: //! Layout a node hierarchy as a hierarchy tree. void layout( la::Node& node, VectorF& bbox, int depth, utl::Progress& progress ); //! Invert the x/y coordinates to set the desired orientation. static void transpose( la::Graph& graph ); //! Spacing on x and y between tree nodes. VectorF _spacing; //! Generated tree orientation. Orientation _orientation; //! Container for already laid out nodes. la::Node::Set _marked; private: //! Get the 'x' horizontal spacing according to the current orientation. float getXSpacing( ) const { return ( _orientation == HORIZONTAL ? _spacing( 1 ) : _spacing( 0 ) ); } //! Get the 'y' vertical spacing according to the current orientation. float getYSpacing( ) const{ return ( _orientation == HORIZONTAL ? _spacing( 0 ) : _spacing( 1 ) ); } //! Get the 'x' horizontal origin according to the current orientation. float getXOrigin( ) const { return ( _orientation == HORIZONTAL ? _origin( 1 ) : _origin( 0 ) ); } //! Get the 'y' vertical origin according to the current orientation. float getYOrigin( ) const { return ( _orientation == HORIZONTAL ? _origin( 0 ) : _origin( 1 ) ); } //! Force the tree layout algorithm to stop recursion. void stopRecursion( ) { _stopRecursion = true; } //! Return the value of the stop recursion flag. bool getStopRecusrion( ) const { return _stopRecursion; } //! Indicate that the algorithm execution is canceled and that the layout algorithm recusrion must stop. bool _stopRecursion; //@} //--------------------------------------------------------------------- }; //! Layout an undirected graph using a spring force algorithm. /*! \nosubgrouping */ class UndirectedGraph : public Layout { /*! \name UndirectedGraph Constructor/Destructor *///------------------ //@{ public: //! UndirectedGraph constructor. UndirectedGraph( ) : Layout( ), _center( "" ) { } //@} //--------------------------------------------------------------------- /*! \name Force Layout Generation Management *///---------------------- //@{ public: //! Layout 'graph' using a spring force algorithm. virtual void layout( la::Graph& graph, la::Grid& grid, QRectF r, utl::Progress& progress, int step = -1 ); static void add( VectorF& a, const VectorF& b ); static void scale( VectorF& p, float scale ); static VectorF vector( VectorF a, VectorF b ); static float length( const VectorF& v ); static float length2( const VectorF& v ); private: VectorF computeRepulseForce( la::Node& node, la::Node::Set& adjacentNodes, la::Node::Set& nodes, la::Graph& graph ); VectorF computeSpringForce( la::Node& node, la::Node::Set& adjacentNodes, la::Graph& graph ); la::Node _center; protected: static void computeBoundingBox( std::vector< VectorF >& positions, VectorF& min, VectorF& max ); //@} //--------------------------------------------------------------------- }; } // ::qan::la } // ::qan //----------------------------------------------------------------------------- #endif // laLayout_h