6 * $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of dominance layout algorithm.
12 * \author Hoi-Ming Wong and Carsten Gutwenger
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
43 #include <ogdf/upward/DominanceLayout.h>
48 void DominanceLayout::call(GraphAttributes
&GA
)
50 if (GA
.constGraph().numberOfNodes() <= 1)
53 //call upward planarizer
55 UPR
.createEmpty(GA
.constGraph());
56 m_upPlanarizer
.get().call(UPR
);
61 void DominanceLayout::layout(GraphAttributes
&GA
, const UpwardPlanRep
&UPROrig
)
64 UpwardPlanRep UPR
= UPROrig
;
68 forall_edges(e
, GA
.constGraph()) {
72 //compute and splite transitiv edges
74 findTransitiveEdges(UPR
, splitMe
);
76 forall_listiterators(edge
, it
, splitMe
) {
77 UPR
.getEmbedding().split(*it
);
80 // set up first-/lastout, first-/lastin
81 firstout
.init(UPR
, 0);
86 node s
= UPR
.getSuperSource();
87 node t
= UPR
.getSuperSink();
89 firstout
[t
] = lastout
[t
] = 0;
90 firstin
[s
] = lastin
[s
] = 0;
91 firstin
[t
] = lastin
[t
] =t
->firstAdj()->theEdge();
92 adjEntry adjRun
= s
->firstAdj();
93 while (UPR
.getEmbedding().rightFace(adjRun
) != UPR
.getEmbedding().externalFace()) {
94 adjRun
= adjRun
->cyclicSucc();
96 lastout
[s
] = adjRun
->theEdge();
97 firstout
[s
] = adjRun
->cyclicSucc()->theEdge();
100 forall_nodes(v
, UPR
) {
101 if (v
== t
|| v
== s
) continue;
103 adjEntry adj
= UPR
.leftInEdge(v
);
104 firstin
[v
] = adj
->theEdge();
105 firstout
[v
] = adj
->cyclicSucc()->theEdge();
107 adjEntry adjRightIn
= adj
;
108 while (adjRightIn
->cyclicPred()->theEdge()->source() != v
)
109 adjRightIn
= adjRightIn
->cyclicPred();
111 lastin
[v
] = adjRightIn
->theEdge();
112 lastout
[v
] = adjRightIn
->cyclicPred()->theEdge();
116 //compute m_L and m_R for min. area drawing
119 forall_edges(e
, UPR
) {
120 node src
= e
->source();
121 node tgt
= e
->target();
122 if (lastin
[tgt
] == e
&& firstout
[src
] == e
)
124 if (firstin
[tgt
] == e
&& lastout
[src
] == e
)
128 // compute preleminary coordinate
132 labelX(UPR
, s
, count
);
134 labelY(UPR
, s
, count
);
139 // map coordinate to GA
140 forall_nodes(v
, GA
.constGraph()) {
141 node vUPR
= UPR
.copy(v
);
142 GA
.x(v
) = xCoord
[vUPR
];
143 GA
.y(v
) = yCoord
[vUPR
];
145 // add bends to original edges
146 forall_edges(e
, GA
.constGraph()) {
147 List
<edge
> chain
= UPR
.chain(e
);
148 forall_nonconst_listiterators(edge
, it
, chain
) {
149 node tgtUPR
= (*it
)->target();
150 if (tgtUPR
!= chain
.back()->target()) {
151 DPoint
p(xCoord
[tgtUPR
], yCoord
[tgtUPR
]);
152 GA
.bends(e
).pushBack(p
);
159 forall_nodes(v
, GA
.constGraph()) {
160 double r
= sqrt(GA
.x(v
)*GA
.x(v
) + GA
.y(v
)*GA
.y(v
));
163 double alpha
= asin(GA
.y(v
)/r
);
164 double yNew
= sin(alpha
+ m_angle
)*r
;
165 double xNew
= cos(alpha
+ m_angle
)*r
;
170 forall_edges(e
, GA
.constGraph()) {
171 DPolyline
&poly
= GA
.bends(e
);
172 DPoint
pSrc(GA
.x(e
->source()), GA
.y(e
->source()));
173 DPoint
pTgt(GA
.x(e
->target()), GA
.y(e
->target()));
174 poly
.normalize(pSrc
, pTgt
);
176 forall_nonconst_listiterators(DPoint
, it
, poly
) {
177 double r
= (*it
).distance(DPoint(0,0));
182 double alpha
= asin( (*it
).m_y
/r
);
183 double yNew
= sin(alpha
+ m_angle
)*r
;
184 double xNew
= cos(alpha
+ m_angle
)*r
;
193 void DominanceLayout::labelX(const UpwardPlanRep
&UPR
, node v
, int &count
)
196 xPreCoord
[v
] = count
;
198 if (v
!= UPR
.getSuperSink()) {
199 adjEntry adj
= firstout
[v
]->adjSource();
201 node w
= adj
->theEdge()->target();
202 if (adj
->theEdge() == lastin
[w
])
203 labelX(UPR
, w
, count
);
204 adj
= adj
->cyclicSucc();
205 } while (adj
->cyclicPred()->theEdge() != lastout
[v
]);
211 void DominanceLayout::labelY(const UpwardPlanRep
&UPR
, node v
, int &count
)
214 yPreCoord
[v
] = count
;
216 if (v
!= UPR
.getSuperSink()) {
217 adjEntry adj
= lastout
[v
]->adjSource();
219 node w
= adj
->theEdge()->target();
220 if (adj
->theEdge() == firstin
[w
])
221 labelY(UPR
, w
, count
);
222 adj
= adj
->cyclicPred();
223 } while (adj
->cyclicSucc()->theEdge() != firstout
[v
]);
228 void DominanceLayout::compact(const UpwardPlanRep
&UPR
, GraphAttributes
&GA
)
230 double maxNodeSize
= 0;
232 forall_nodes(v
, GA
.constGraph()) {
233 if (GA
.width(v
) > maxNodeSize
|| GA
.height(v
) > maxNodeSize
)
234 maxNodeSize
= max(GA
.width(v
), GA
.height(v
));
237 int gridDist
= m_grid_dist
;
238 if (gridDist
< maxNodeSize
+1)
239 gridDist
= (int) maxNodeSize
+1;
244 //ASSIGN X COORDINATE
246 OGDF_ASSERT(!xNodes
.empty());
248 v
= xNodes
.popFrontRet();
250 while (!xNodes
.empty()) {
251 node u
= xNodes
.popFrontRet();
252 if ( (yPreCoord
[v
] > yPreCoord
[u
]) || (firstout
[v
] == lastout
[v
] && firstin
[u
] == lastin
[u
] && m_L
<= m_R
)) {
253 xCoord
[u
] = xCoord
[v
] + gridDist
;
256 xCoord
[u
] = xCoord
[v
];
260 //ASSIGN Y COORDINATE
261 OGDF_ASSERT(!yNodes
.empty());
263 v
= yNodes
.popFrontRet();
265 while (!yNodes
.empty()) {
266 node u
= yNodes
.popFrontRet();
267 if ( (xPreCoord
[v
] > xPreCoord
[u
]) || (firstout
[v
] == lastout
[v
] && firstin
[u
] == lastin
[u
] && m_L
> m_R
)) {
268 yCoord
[u
] = yCoord
[v
] + gridDist
;
271 yCoord
[u
] = yCoord
[v
];
278 void DominanceLayout::findTransitiveEdges(const UpwardPlanRep
&UPR
, List
<edge
> &edges
)
281 // e = (u,v) transitive <=> ex. face f: e in f and u source-switch and v = sink-switch
283 forall_faces(f
, UPR
.getEmbedding()) {
284 if (f
== UPR
.getEmbedding().externalFace())
288 forall_face_adj(adj
, f
) {
289 node src
= adj
->theEdge()->source();
290 node tgt
= adj
->theEdge()->target();
291 if ( (adj
->faceCycleSucc()->theEdge()->source() == src
&& adj
->faceCyclePred()->theEdge()->target() == tgt
)
292 || (adj
->faceCycleSucc()->theEdge()->target() == tgt
&& adj
->faceCyclePred()->theEdge()->source() == src
)) {
293 edges
.pushBack(adj
->theEdge());