1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
/**
*
* This file is part of Tulip (www.tulip-software.org)
*
* Authors: David Auber and the Tulip development Team
* from LaBRI, University of Bordeaux
*
* Tulip is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* Tulip is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
*/
#ifndef IMPROVEDWALKER_H
#define IMPROVEDWALKER_H
#include <map>
#include <vector>
#include <tulip/TulipPluginHeaders.h>
#include "TreeTools.h"
class OrientableLayout;
class OrientableCoord;
class OrientableSizeProxy;
class ImprovedWalkerIterator;
/** \addtogroup layout */
/** This plugin is an implementation of a linear Walker's algorithm:
*
* Christoph Buchheim and Michael Junger and Sebastian Leipert,
* Improving Walker's Algorithm to Run in Linear Time
* citeseer.ist.psu.edu/buchheim02improving.html
*
* \note This algorith works on tree.
* Let n be the number of nodes, the algorithm complexity is in O(n).
*
* \author Julien Testut, Antony Durand, Pascal Ollier, Yashvin Nababsing, \n
* Sebastien Leclerc, Thibault Ruchon, Eric Dauchier \n
* University Bordeaux I France
**/
class ImprovedWalker : public tlp::LayoutAlgorithm {
friend class ImprovedWalkerUnitTests;
public:
PLUGININFORMATION( "Improved Walker",
"Julien Testut, Antony Durand, Pascal Ollier, "
"Yashvin Nababsing, Sebastien Leclerc, "
"Thibault Ruchon, Eric Dauchier",
"11/11/04",
"It is a linear implementation of the Walker's tree layout improved algorithm described in<br/>"
"<b>Improving Walker's Algorithm to Run in Linear Time</b>, Christoph Buchheim and Michael Junger and Sebastian Leipert (2002).",
"1.0", "Tree")
ImprovedWalker(const tlp::PluginContext* context);
~ImprovedWalker();
bool run();
private:
typedef std::vector<float> levelToFloatType;
typedef std::map<tlp::node, float> nodeToFloatType;
typedef std::map<tlp::node, int> nodeToIntegerPropertyType;
typedef std::map<tlp::node, tlp::node> nodeToNodeType;
tlp::Graph *tree;
float spacing;
float nodeSpacing;
static const tlp::node BADNODE;
OrientableLayout* oriLayout;
OrientableSizeProxy* oriSize;
int depthMax;
nodeToIntegerPropertyType order;
levelToFloatType maxYbyLevel;
levelToFloatType posYbyLevel;
nodeToFloatType prelimX;
nodeToFloatType modChildX;
nodeToNodeType thread;
nodeToFloatType shiftNode;
nodeToFloatType shiftDelta;
nodeToNodeType ancestor;
int initializeAllNodes(tlp::node root);
int initializeNode(tlp::node root, unsigned int depth);
int countSibling(tlp::node from, tlp::node to);
ImprovedWalkerIterator* iterateSibling(tlp::node from, tlp::node to);
tlp::Iterator<tlp::node>* getChildren(tlp::node n);
ImprovedWalkerIterator* getReversedChildren(tlp::node n);
void firstWalk(tlp::node v);
void secondWalk(tlp::node v, float modifierX, int depth);
void combineSubtree(tlp::node v, tlp::node* defaultAncestor);
void moveSubtree(tlp::node fromNode, tlp::node toNode,
float rightShift);
void executeShifts(tlp::node v);
inline tlp::node getSuperGraph(tlp::node n);
inline tlp::node leftmostChild(tlp::node n);
inline tlp::node rightmostChild(tlp::node n);
inline tlp::node leftSibling(tlp::node n);
inline tlp::node rightSibling(tlp::node n);
inline tlp::node leftMostSibling(tlp::node n);
inline tlp::node nextRightContour(tlp::node v);
inline tlp::node nextLeftContour(tlp::node v);
inline tlp::node findCommonAncestor(tlp::node left, tlp::node right, tlp::node defaultAncestor);
};
//====================================================================
inline tlp::node ImprovedWalker::getSuperGraph(tlp::node n) {
if (tree->indeg(n)<1)
return BADNODE;
return tree->getInNode(n,1);
}
//====================================================================
inline tlp::node ImprovedWalker::leftmostChild(tlp::node n) {
if (tree->outdeg(n)<1)
return BADNODE;
return tree->getOutNode(n,1);
}
//====================================================================
inline tlp::node ImprovedWalker::rightmostChild(tlp::node n) {
int pos;
if ((pos=tree->outdeg(n))<1)
return BADNODE;
return tree->getOutNode(n,pos);
}
//====================================================================
inline tlp::node ImprovedWalker::leftSibling(tlp::node n) {
if (order[n]<=1)
return BADNODE;
else
return tree->getOutNode( getSuperGraph(n) ,order[n]-1);
}
//====================================================================
inline tlp::node ImprovedWalker::rightSibling(tlp::node n) {
tlp::node father=getSuperGraph(n);
if (order[n]>=int(tree->outdeg(father)))
return BADNODE;
return tree->getOutNode(father ,order[n]+1);
}
//====================================================================
inline tlp::node ImprovedWalker::leftMostSibling(tlp::node n) {
tlp::node father=getSuperGraph(n);
return leftmostChild(father);
}
//====================================================================
inline tlp::node ImprovedWalker::nextRightContour(tlp::node n) {
if (isLeaf(tree, n))
return thread[n];
else
return rightmostChild(n);
}
//====================================================================
inline tlp::node ImprovedWalker::nextLeftContour(tlp::node n) {
if (isLeaf(tree, n))
return thread[n];
else
return leftmostChild(n);
}
//====================================================================
inline tlp::node ImprovedWalker::findCommonAncestor(tlp::node left, tlp::node right,
tlp::node defaultAncestor) {
if (getSuperGraph(ancestor[left]) == getSuperGraph(right) /*&& left!=right*/)
return ancestor[left];
else
return defaultAncestor;
}
#endif
|
