6 * $Date: 2012-07-07 23:10:08 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
10 * \brief Implements planar orthogonal drawing algorithm for
11 * mixed-upward embedded graphs
13 * \author Carsten Gutwenger, Sebastian Leipert
16 * This file is part of the Open Graph Drawing Framework (OGDF).
20 * See README.txt in the root directory of the OGDF installation for details.
23 * This program is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU General Public License
25 * Version 2 or 3 as published by the Free Software Foundation;
26 * see the file LICENSE.txt included in the packaging of this file
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
36 * You should have received a copy of the GNU General Public
37 * License along with this program; if not, write to the Free
38 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
39 * Boston, MA 02110-1301, USA.
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
45 #include <ogdf/orthogonal/OrthoLayout.h>
46 #include <ogdf/orthogonal/LongestPathCompaction.h>
47 #include <ogdf/orthogonal/FlowCompaction.h>
48 #include <ogdf/orthogonal/EdgeRouter.h>
49 #include <ogdf/internal/orthogonal/RoutingChannel.h>
50 #include <ogdf/orthogonal/MinimumEdgeDistances.h>
51 #include <ogdf/orthogonal/OrthoShaper.h>
57 OrthoLayout::OrthoLayout()
59 //drawing object distances
63 //preferred hierarchy direction
64 // SHOULD ACTUALLY BE odNorth, but we use odSouth since gml's are flipped!
65 m_preferedDir
= odSouth
;
68 m_costAssoc
= 1;//should be set by profile
70 //align hierarchy nodes on same level
72 //scale layout while improving it
73 m_useScalingCompaction
= false;
75 m_bendBound
= 2; //bounds number of bends per edge in ortho shaper
77 m_orthoStyle
= 0;//0; //traditional 0, progressive 1
82 void OrthoLayout::call(PlanRepUML
&PG
,
86 // if we have only one vertex in PG ...
87 if(PG
.numberOfNodes() == 1) {
88 node v1
= PG
.firstNode();
89 node vOrig
= PG
.original(v1
);
90 double w
= PG
.widthOrig(vOrig
);
91 double h
= PG
.heightOrig(vOrig
);
93 drawing
.x(v1
) = m_margin
+ w
/2;
94 drawing
.y(v1
) = m_margin
+ h
/2;
95 m_boundingBox
= DPoint(w
+ 2*m_margin
, h
+ 2*m_margin
);
100 //classify brother-to-brother hierarchy edges to allow alignment
103 classifyEdges(PG
, adjExternal
);
105 //compaction with scaling: help node cages to pass by each other
106 double l_orsep
= m_separation
;
107 if (m_useScalingCompaction
)
110 double scaleFactor
= double(int(1 << m_scalingSteps
));
111 m_separation
= scaleFactor
*m_separation
; //reduce this step by step in compaction
115 //***********************************
116 // PHASE 1: determine orthogonal shape
118 // expand high-degree vertices and generalization mergers
121 //check preconditions, currently not necessary
122 //assureDrawability(PG);
124 // get combinatorial embedding
125 CombinatorialEmbedding
E(PG
);
126 E
.setExternalFace(E
.rightFace(adjExternal
));
128 // determine orthogonal shape
135 OFG
.align(m_align
); //align brother objects on hierarchy levels
136 OFG
.traditional(m_orthoStyle
> 0 ? false : true); //prefer 90/270 degree angles over 180/180
139 OFG
.setBendBound(m_bendBound
);
142 // remove face splitter
144 for(e
= PG
.firstEdge(); e
; e
= eSucc
)
147 if(PG
.faceSplitter(e
)) {
148 OR
.angle(e
->adjSource()->cyclicPred()) = 2;
149 OR
.angle(e
->adjTarget()->cyclicPred()) = 2;
154 //******************************************************************
155 // PHASE 2: construction of a feasible drawing of the expanded graph
157 // expand low degree vertices
158 PG
.expandLowDegreeVertices(OR
);
160 OGDF_ASSERT(PG
.representsCombEmbedding());
164 E
.setExternalFace(E
.rightFace(adjExternal
));
166 // apply constructive compaction heuristics
169 OR
.dissect2(&PG
); //OR.dissect();
171 OR
.orientate(PG
,m_preferedDir
);
173 // compute cage information and routing channels
174 OR
.computeCageInfoUML(PG
);
176 // adjust value of cOverhang
177 if(m_cOverhang
< 0.05)
179 if(m_cOverhang
> 0.5)
182 //temporary grid layout
183 GridLayoutMapped
gridDrawing(PG
,OR
,m_separation
,m_cOverhang
,2);
185 RoutingChannel
<int> rcGrid(PG
,gridDrawing
.toGrid(m_separation
),m_cOverhang
);
186 rcGrid
.computeRoutingChannels(OR
, m_align
);
190 const OrthoRep::VertexInfoUML
*pInfoExp
;
192 pInfoExp
= OR
.cageInfo(v
);
197 FlowCompaction
fca(0,m_costGen
,m_costAssoc
);
199 fca
.constructiveHeuristics(PG
,OR
,rcGrid
,gridDrawing
);
201 OR
.undissect(m_align
);
203 // call flow compaction on grid
204 FlowCompaction
fc(0,m_costGen
,m_costAssoc
);
206 fc
.scalingSteps(m_scalingSteps
);
208 fc
.improvementHeuristics(PG
,OR
,rcGrid
,gridDrawing
);
210 //remove alignment edges before edgerouter call because compaction
211 //may do an unsplit at the nodes corners, which is impossible if
212 //there are alignment edges attached
213 if (m_align
) OR
.undissect(false);
215 // PHASE 3: routing of edges
219 MinimumEdgeDistances
<int> minDistGrid(PG
, gridDrawing
.toGrid(m_separation
));
220 //router.setOrSep(int(gridDrawing.toGrid(l_orsep))); //scaling test
221 router
.call(PG
,OR
,gridDrawing
,E
,rcGrid
,minDistGrid
, gridDrawing
.width(),
222 gridDrawing
.height(), m_align
);
226 OGDF_ASSERT(OR
.check(msg
) == true);
228 OR
.orientate(pInfoExp
->m_corner
[odNorth
],odNorth
);
230 //*************************************************
231 // PHASE 4: apply improvement compaction heuristics
233 // call flow compaction on grid
234 fc
.improvementHeuristics(PG
, OR
, minDistGrid
, gridDrawing
, int(gridDrawing
.toGrid(l_orsep
)));
238 gridDrawing
.remap(drawing
);
240 // collapse all expanded vertices by introducing a new node in the center
241 // of each cage representing the original vertex
242 PG
.collapseVertices(OR
,drawing
);
244 // finally set the bounding box
245 computeBoundingBox(PG
,drawing
);
247 m_separation
= l_orsep
;
252 //-----------------------------------------------------------------------------
254 //-----------------------------------------------------------------------------
255 void OrthoLayout::classifyEdges(PlanRepUML
&PG
, adjEntry
&adjExternal
)
257 //classify brother-to-brother hierarchy edges to allow alignment
258 //when shifting this to planrep, guarantee edge type correction in planarization
259 //save external face entry
262 //potential direct connection are all non-gen. edges that are alignUpward
264 for(e
= PG
.firstEdge(); e
; e
= eSucc
)
267 if (PG
.typeOf(e
) != Graph::generalization
)
269 adjEntry as
= e
->adjSource();
270 node v
= e
->source();
271 if ( (PG
.alignUpward(as
))
272 && (PG
.typeOf(e
->target()) != Graph::dummy
)//TODO: crossings ?
273 && (PG
.typeOf(v
) != Graph::dummy
)
278 adjEntry runAE
= as
->cyclicSucc();
279 edge run
= runAE
->theEdge();
280 while ( (stop
< v
->degree()) && //only once
281 ((PG
.typeOf(run
) != Graph::generalization
) || //search generalization
282 (run
->source() != v
) //outgoing gen
287 runAE
= runAE
->cyclicSucc();
288 run
= runAE
->theEdge();
290 OGDF_ASSERT(stop
<= v
->degree());
292 //now we have the outgoing generalization (to the merger) at v
295 node w
= e
->target(); //crossings ?
296 adjEntry asTwin
= as
->twin();
299 runAE
= asTwin
->cyclicSucc();
300 run
= runAE
->theEdge();
301 while ( (stop
< w
->degree()) &&
302 ((PG
.typeOf(run
) != Graph::generalization
) ||
308 runAE
= runAE
->cyclicSucc();
309 run
= runAE
->theEdge();
311 OGDF_ASSERT(stop
<= w
->degree());
313 //now we have the outgoing generalization (to the merger) at w
316 //two possible orientations
318 bool ltr
= ( gen1
->adjSource()->faceCycleSucc() == gen2
->adjTarget() );
320 bool rtl
= ( gen2
->adjSource()->faceCycleSucc() == gen1
->adjTarget() );
321 if (ltr
|| rtl
) //should be disjoint cases because of merger node
325 //now check if the embedding does include unnecessary nodes in the slope
328 //there are edges between e and gen2 at target
329 if (!(e
->adjTarget()->faceCyclePred() == gen2
->adjTarget()))
331 OGDF_ASSERT(v
!= e
->target());
332 PG
.moveAdj(e
->adjTarget(), before
, gen2
->adjTarget()->twin());
334 //there are edges between e and gen1 at source
335 if (!(e
->adjTarget()->faceCycleSucc() == gen1
->adjSource()))
337 //test if we discard the outer face entry
338 if (adjExternal
== e
->adjSource())
340 adjExternal
= e
->adjSource()->faceCyclePred();
342 PG
.moveAdj(e
->adjSource(), after
, gen1
->adjSource());
344 }//if gen 1 left of gen 2
347 //there are edges between e and gen2 at target
348 if (!(e
->adjSource()->faceCycleSucc() == gen2
->adjSource()))
350 //test if we discard the outer face entry
351 if (adjExternal
== e
->adjTarget())
353 adjExternal
= e
->adjTarget()->faceCycleSucc();
355 PG
.moveAdj(e
->adjTarget(), after
, gen2
->adjSource());
357 //there are edges between e and gen1 at source
358 if (!(e
->adjSource()->faceCyclePred() == gen1
->adjTarget()))
360 PG
.moveAdj(e
->adjSource(), before
, gen1
->adjSource());
363 }//if gen 2 left of gen 1
365 else PG
.setHalfBrother(e
);
368 }//if not generalization
374 // compute bounding box and move final drawing such that it is 0 aligned
375 // respecting margins
376 void OrthoLayout::computeBoundingBox(
377 const PlanRepUML
&PG
,
380 double minX
, maxX
, minY
, maxY
;
382 minX
= maxX
= drawing
.x(PG
.firstNode());
383 minY
= maxY
= drawing
.y(PG
.firstNode());
388 double x
= drawing
.x(v
);
389 if (x
< minX
) minX
= x
;
390 if (x
> maxX
) maxX
= x
;
392 double y
= drawing
.y(v
);
393 if (y
< minY
) minY
= y
;
394 if (y
> maxY
) maxY
= y
;
397 double deltaX
= m_margin
- minX
;
398 double deltaY
= m_margin
- minY
;
402 drawing
.x(v
) += deltaX
;
403 drawing
.y(v
) += deltaY
;
406 m_boundingBox
= DPoint(maxX
+deltaX
+m_margin
, maxY
+deltaY
+m_margin
);
410 } // end namespace ogdf