TreeLayout.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_TREE_LAYOUT_H
#define OGDF_TREE_LAYOUT_H

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

namespace ogdf {

class OGDF_EXPORT TreeLayout : public LayoutModule {
public:
    enum RootSelectionType {
        rootIsSource, 
        rootIsSink,   
        rootByCoord   
    };

private:
    double m_siblingDistance;        
    double m_subtreeDistance;        
    double m_levelDistance;          
    double m_treeDistance;           

    bool m_orthogonalLayout;         
    Orientation m_orientation;       
    RootSelectionType m_selectRoot;  

    NodeArray<int> m_number;         

    NodeArray<node> m_parent;        
    NodeArray<node> m_leftSibling;   
    NodeArray<node> m_firstChild;    
    NodeArray<node> m_lastChild;     
    NodeArray<node> m_thread;        
    NodeArray<node> m_ancestor;      

    NodeArray<double> m_preliminary; 
    NodeArray<double> m_modifier;    
    NodeArray<double> m_change;      
    NodeArray<double> m_shift;       

    SListPure<edge> m_reversedEdges; 
    Graph           *m_pGraph; 

public:
    TreeLayout();

    TreeLayout(const TreeLayout &tl);

    // destructor
    ~TreeLayout();


    void call(GraphAttributes &GA);

    void callSortByPositions(GraphAttributes &AG, Graph &G);



    double siblingDistance() const { return m_siblingDistance; }

    void siblingDistance(double x) { m_siblingDistance = x; }

    double subtreeDistance() const { return m_subtreeDistance; }

    void subtreeDistance(double x) { m_subtreeDistance = x; }

    double levelDistance() const { return m_levelDistance; }

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

    double treeDistance() const { return m_treeDistance; }

    void treeDistance(double x) { m_treeDistance = x; }

    bool orthogonalLayout() const { return m_orthogonalLayout; }

    void orthogonalLayout(bool b) { m_orthogonalLayout = b; }

    Orientation orientation() const { return m_orientation; }

    void orientation(Orientation orientation) { m_orientation = orientation; }

    RootSelectionType rootSelection() const { return m_selectRoot; }

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



    TreeLayout &operator=(const TreeLayout &tl);


private:
    class AdjComparer;

    void adjustEdgeDirections(Graph &G, node v, node parent);
    void setRoot(GraphAttributes &AG, Graph &tree);
    void undoReverseEdges(GraphAttributes &AG);

    // initialize all node arrays and
    // compute the tree structure from the adjacency lists
    //
    // returns the root node
    void initializeTreeStructure(const Graph &tree, List<node> &roots);

    // delete all node arrays
    void deleteTreeStructure();

    // returns whether node v is a leaf
    int isLeaf(node v) const;

    // returns the successor of node v on the left/right contour
    // returns 0 if there is none
    node nextOnLeftContour(node v) const;
    node nextOnRightContour(node v) const;

    // recursive bottom up traversal of the tree for computing
    // preliminary x-coordinates
    void firstWalk(node subtree,const GraphAttributes &AG,bool upDown);

    // space out the small subtrees on the left hand side of subtree
    // defaultAncestor is used for all nodes with obsolete m_ancestor
    void apportion(node subtree,
                   node &defaultAncestor,
                   const GraphAttributes &AG,
                   bool upDown);

    // recursive top down traversal of the tree for computing final
    // x-coordinates
    void secondWalkX(node subtree,
                    double modifierSum,
                    GraphAttributes &AG);
    void secondWalkY(node subtree,
                    double modifierSum,
                    GraphAttributes &AG);

    // compute y-coordinates and edge shapes 
    void computeYCoordinatesAndEdgeShapes(node root,GraphAttributes &AG);
    void computeXCoordinatesAndEdgeShapes(node root,GraphAttributes &AG);

    void findMinX(GraphAttributes &AG, node root, double &minX);
    void findMinY(GraphAttributes &AG, node root, double &minY);
    void findMaxX(GraphAttributes &AG, node root, double &maxX);
    void findMaxY(GraphAttributes &AG, node root, double &maxY);
    void shiftTreeX(GraphAttributes &AG, node root, double shift);
    void shiftTreeY(GraphAttributes &AG, node root, double shift);
};

} // end namespace ogdf

#endif