Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
BalloonLayout.h
Go to the documentation of this file.
1
37/*
38 * The layout is computed by first computing a spanning tree
39 * of the graph that is then used to derive the vertices' coordinates.
40 * First, the radii at each vertex are computed.
41 * Then, depending on the embedding option, the order of the
42 * edges around each vertex is optimized to maximize angular
43 * resolution and to minimize the aspect ratio.
44 *
45 * Finally, the layout is shifted into the positive quadrant
46 * of the cartesian plane
47 * */
48
49#pragma once
50
52#include <ogdf/basic/List.h>
53
54namespace ogdf {
55
57public:
58 //Root may be defined by center of the graph
59 //Directed cases: source/sink
60 enum class RootSelection { Center, HighestDegree };
61 //either keep the given embedding or optimize
62 //the order wrto angular resolution and minimum aspect ratio
63 enum class ChildOrder { Fixed, Optimized };
64 //compute tree by different methods
65 enum class TreeComputation { Bfs, Dfs, BfsRandom };
70
72 virtual void call(GraphAttributes& AG) override;
73
77 virtual void callFractal(GraphAttributes& AG, double ratio = 0.3) {
78 bool even = getEvenAngles();
79 setEvenAngles(true);
80 call(AG);
81 setEvenAngles(even);
82 }
83
85 void setEvenAngles(bool b) { m_evenAngles = b; }
86
88 bool getEvenAngles() { return m_evenAngles; }
89
90protected:
94 void computeTree(const Graph& G);
95
97 void computeBFSTree(const Graph& G, node v);
98
101 void selectRoot(const Graph& G);
102
108#ifdef OGDF_DEBUG
109 void computeRadii(GraphAttributes& AG);
110#else
112#endif
113
115 void computeAngles(const Graph& G);
116
119
120private:
129
131#ifdef OGDF_DEBUG
133 void checkTree(const Graph& G, bool treeRoot = true);
134 EdgeArray<bool> m_treeEdge;
135#endif
136
140
142
146
147 void check(Graph& G);
148
150};
151
152OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const BalloonLayout::RootSelection& rs);
153
154}
Declaration of interface for layout algorithms (class LayoutModule)
Declaration of doubly linked lists and iterators.
void computeAngles(const Graph &G)
Computes the angle distribution: assigns m_angle each node.
NodeArray< double > m_maxChildRadius
Outer radius of largest child.
NodeArray< double > m_estimate
Rough estimate of circumference of subtrees.
NodeArray< double > m_angle
Angle assigned to nodes.
NodeArray< double > m_size
Radius of circle around node box.
NodeArray< node > m_parent
Parent in spanning tree.
bool getEvenAngles()
returns how the angles are assigned to subtrees.
void setEvenAngles(bool b)
Subtrees may be assigned even angles or angles depending on their size.
node m_treeRoot
Root of tree after computation.
NodeArray< int > m_childCount
Number of children in spanning tree.
TreeComputation m_treeComputation
How to derive the spanning tree.
void check(Graph &G)
Use even angles independent of subtree size.
ChildOrder m_childOrder
How to arrange the children.
NodeArray< double > m_oRadius
Radius at node center.
BalloonLayout()
Constructor, sets options to default values.
virtual void call(GraphAttributes &AG) override
Standard call using the stored parameter settings.
NodeArray< List< node > > m_childList
BalloonLayout & operator=(const BalloonLayout &bl)
Assignmentoperator.
virtual void callFractal(GraphAttributes &AG, double ratio=0.3)
Call using special parameter settings for fractal model takes radius ratio < 0.5 as parameter.
node m_root
Root of tree by selection method.
NodeArray< double > m_radius
void computeRadii(const GraphAttributes &AG)
Computes a radius for each of the vertices in G. fractal model: same radius on same level,...
void computeBFSTree(const Graph &G, node v)
Computes tree by BFS, fills m_parent and m_childCount.
void computeTree(const Graph &G)
Computes the spanning tree that is used for the layout computation, the non-tree edges are simply add...
void computeCoordinates(GraphAttributes &AG)
Computes coordinates from angles and radii.
RootSelection m_rootSelection
Defines how the tree root is selected.
double m_estimateFactor
Weight of value (largestchild / number of children) added to estimate to compute radius.
void selectRoot(const Graph &G)
Selects the root of the spanning tree that is placed in the layout center.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Stores additional attributes of a graph (like layout information).
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Interface of general layout algorithms.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:84
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition Array.h:978