BalloonLayout.h

Go to the documentation of this file.

 
/*
 * 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
 * */
 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/LayoutModule.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/memory.h>
 
#include <iosfwd>
 
namespace ogdf {
class GraphAttributes;
template<class E>
class List;
 
class OGDF_EXPORT BalloonLayout : public LayoutModule {
public:
    //Root may be defined by center of the graph
    //Directed cases: source/sink
    enum class RootSelection { Center, HighestDegree };
    //either keep the given embedding or optimize
    //the order wrto angular resolution and minimum aspect ratio
    enum class ChildOrder { Fixed, Optimized };
    //compute tree by different methods
    enum class TreeComputation { Bfs, Dfs, BfsRandom };
    BalloonLayout();
    BalloonLayout& operator=(const BalloonLayout& bl);
 
    virtual void call(GraphAttributes& AG) override;
 
    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
 
    RootSelection m_rootSelection; 
    node m_treeRoot; 
    node m_root; 
 
    double m_estimateFactor; 
 
    ChildOrder m_childOrder; 
    TreeComputation m_treeComputation; 
    bool m_evenAngles; 
 
    void check(Graph& G);
 
    OGDF_NEW_DELETE
};
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const BalloonLayout::RootSelection& rs);
 
}