RadialTreeLayout.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) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_RADIAL_TREE_LAYOUT_H
#define OGDF_RADIAL_TREE_LAYOUT_H

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


namespace ogdf {



class OGDF_EXPORT RadialTreeLayout : public LayoutModule
{
public:
    enum RootSelectionType {
        rootIsSource, 
        rootIsSink,   
        rootIsCenter  
    };

private:
    double m_levelDistance;          
    double m_connectedComponentDistance; 

    RootSelectionType m_selectRoot;  

    node            m_root;          

    int             m_numLevels;     
    NodeArray<int>  m_level;         
    NodeArray<node> m_parent;        
    NodeArray<double> m_leaves;      
    Array<SListPure<node> > m_nodes; 

    NodeArray<double> m_angle;       
    NodeArray<double> m_wedge;       

    NodeArray<double> m_diameter;    
    Array<double>     m_width;       

    Array<double>   m_radius;        
    double          m_outerRadius;   
    
    struct Group
    {
        RadialTreeLayout *m_data;

        bool            m_leafGroup;
        SListPure<node> m_nodes;
        double          m_sumD;
        double          m_sumW;
        double          m_leftAdd;
        double          m_rightAdd;

        Group(RadialTreeLayout *data, node v) {
            m_data = data;
            m_leafGroup = (v->degree() == 1);
            m_nodes.pushBack(v);
            m_sumD = m_data->diameter()[v] + m_data->levelDistance();
            m_sumW = m_data->leaves()[v];
            m_leftAdd = m_rightAdd = 0.0;
        }

        bool isSameType(node v) const {
            return (m_leafGroup == (v->degree() == 1));
        }

        void append(node v) {
            m_nodes.pushBack(v);
            m_sumD += m_data->diameter()[v] + m_data->levelDistance();
            m_sumW += m_data->leaves()[v];
        }

        double add() const { return m_leftAdd + m_rightAdd; }
        node leftVertex () const { return m_nodes.front(); }
        node rightVertex() const { return m_nodes.back (); }
    };

    class Grouping : public List<Group>
    {
    public:
        void computeAdd(double &D, double &W);
    };

    NodeArray<Grouping> m_grouping;

public:
    RadialTreeLayout();

    RadialTreeLayout(const RadialTreeLayout &tl);

    // destructor
    ~RadialTreeLayout();

    RadialTreeLayout &operator=(const RadialTreeLayout &tl);


    void call(GraphAttributes &GA);


    // option that determines the minimal vertical distance 
    // required between levels

    double levelDistance() const { return m_levelDistance; }

    void levelDistance(double x) { m_levelDistance = x; }

    // option that determines the minimal horizontal distance 
    // required between trees in the forest

    double connectedComponentDistance() const { return m_connectedComponentDistance; }

    void connectedComponentDistance(double x) { m_connectedComponentDistance = x; }

    // option that determines if the root is on the top or on the bottom

    RootSelectionType rootSelection() const { return m_selectRoot; }

    void rootSelection(RootSelectionType sel) { m_selectRoot = sel; }

    const NodeArray<double> &diameter() const { return m_diameter; }
    const NodeArray<double> &leaves()   const { return m_leaves;   }

private:
    void FindRoot(const Graph &G);
    void ComputeLevels(const Graph &G);
    void ComputeDiameters(GraphAttributes &AG);
    void ComputeAngles(const Graph &G);
    void ComputeCoordinates(GraphAttributes &AG);
    void ComputeGrouping(int i);

    OGDF_NEW_DELETE
};

} // end namespace ogdf

#endif