BalloonLayout.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/
 
/*
 * The layout is computed by first computing a spanning tree
 * of the graph that is then used to derive the vertices' coordinates.
 * First, the radii at each vertex are computed.
 * Then, depending on the embedding option, the order of the 
 * edges around each vertex is optimized to maximize angular
 * resolution and to minimize the aspect ratio.
 * 
 * Finally, the layout is shifted into the positive quadrant
 * of the cartesian plane
 * */
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_BALLOON_LAYOUT_H_
#define OGDF_BALLOON_LAYOUT_H_

#include <ogdf/module/LayoutModule.h>
#include <ogdf/basic/List.h>


namespace ogdf {

class OGDF_EXPORT BalloonLayout : public LayoutModule
{
 public:
    //Root may be defined by center of the graph
    //Directed cases: source/sink
    enum RootSelection {rootCenter, rootHighestDegree};
    //either keep the given embedding or optimize
    //the order wrto angular resolution and minimum aspect ratio
    enum ChildOrder {orderFixed, orderOptimized};
    //compute tree by different methods
    enum TreeComputation {treeBfs, treeDfs, treeBfsRandom};
    BalloonLayout();
    virtual ~BalloonLayout();
    BalloonLayout &operator=(const BalloonLayout &bl);
    
    virtual void call(GraphAttributes & AG);
    
    virtual void callFractal(GraphAttributes & AG, double ratio = 0.3)
    {
        bool even = getEvenAngles();
        setEvenAngles(true);
        call(AG);
        setEvenAngles(even);
    }
    
    void setEvenAngles(bool b) {m_evenAngles = b;}
    bool getEvenAngles() {return m_evenAngles;}
    
    
    
 protected:
    void computeTree(const Graph &G);
    void computeBFSTree(const Graph &G, node v);
    void selectRoot(const Graph &G);
    //------------------------------------------------
    #ifdef OGDF_DEBUG
    void computeRadii(GraphAttributes &AG);
    #else
    void computeRadii(const GraphAttributes &AG);
    #endif

    void computeAngles(const Graph &G);
    void computeCoordinates(GraphAttributes &AG);
    
 private:
    NodeArray<double> m_radius; 
    NodeArray<double> m_oRadius; 
    NodeArray<double> m_maxChildRadius; 
    NodeArray<node>   m_parent; 
    NodeArray<int>    m_childCount; 
    NodeArray<double> m_angle; 
    NodeArray<double> m_estimate; 
    NodeArray<double> m_size;   
   
    NodeArray< List<node> > m_childList;
    #ifdef OGDF_DEBUG

    void checkTree(const Graph &G, bool treeRoot = true); 
    EdgeArray<bool> *m_treeEdge; 
    #endif
    
    //-----------------------
    //optimization parameters    
    RootSelection     m_rootSelection; 
    node              m_treeRoot; 
    node              m_root;     
    
    double            m_estimateFactor; 
                                        //estimate to compute radius.
    double            m_fractalRatio;   
    
    ChildOrder        m_childOrder; 
    TreeComputation   m_treeComputation; 
    bool              m_evenAngles; 
    
    void check(Graph &G); 
    
    OGDF_NEW_DELETE
}; //class BalloonLayout

}//end namespace ogdf
#endif /*BALLOONLAYOUT_H_*/