?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / src / planarity / PlanarizationLayout_inc.cpp
blobf83fdc8c5b838d2dec3f2d1b3f28ea2f4d2c3559
1 /*
2 * $Revision: 2559 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief implementation of class UMLPlanarizationLayout.
11 *
12 * applies planarization approach for drawing UML diagrams
13 * by calling a planar layouter for every planarized connected
14 * component
15 * Static and incremental calls available
16 * Replaces cliques (if m_processCliques is set) to speed up
17 * the computation, this does only work in non-UML mode
18 *
19 * \author Carsten Gutwenger
20 *
21 * \par License:
22 * This file is part of the Open Graph Drawing Framework (OGDF).
23 *
24 * \par
25 * Copyright (C)<br>
26 * See README.txt in the root directory of the OGDF installation for details.
27 *
28 * \par
29 * This program is free software; you can redistribute it and/or
30 * modify it under the terms of the GNU General Public License
31 * Version 2 or 3 as published by the Free Software Foundation;
32 * see the file LICENSE.txt included in the packaging of this file
33 * for details.
34 *
35 * \par
36 * This program is distributed in the hope that it will be useful,
37 * but WITHOUT ANY WARRANTY; without even the implied warranty of
38 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
39 * GNU General Public License for more details.
40 *
41 * \par
42 * You should have received a copy of the GNU General Public
43 * License along with this program; if not, write to the Free
44 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
45 * Boston, MA 02110-1301, USA.
46 *
47 * \see http://www.gnu.org/copyleft/gpl.html
48 ***************************************************************/
49
50
51 #include <ogdf/planarity/PlanarizationLayout.h>
52 #include <ogdf/basic/TopologyModule.h>
53 #include <ogdf/planarity/PlanRepInc.h>
54 #include <ogdf/basic/Queue.h>
55 #include <ogdf/planarity/SimpleIncNodeInserter.h>
56
57
58 namespace ogdf {
59
60 //-----------------------------------------------------------------------------
61 //incremental call: takes a fixed part of the input
62 //graph (indicated by fixedNodes/Edges==true), embeds it using
63 //the input layout, then inserts the remaining part into this embedding
64 //currently, only the subgraph induced by the fixed nodes is fixed
65 void PlanarizationLayout::callIncremental(
66 UMLGraph &umlGraph,
67 NodeArray<bool> &fixedNodes,
68 const EdgeArray<bool> & /* fixedEdges */)
69 {
70 try {
71
72 if(((const Graph &)umlGraph).empty())
73 return;
74 //-------------------
75 //check preconditions
76 //(change edge types in umlGraph at non-tree hierarchies
77 //or replace cliques by nodes)
78 preProcess(umlGraph);
79
80 m_nCrossings = 0; //number of inserted crossings
81
82 //use the options set at the planar layouter
83 int l_layoutOptions = m_planarLayouter.get().getOptions();
84 bool l_align = ((l_layoutOptions & umlOpAlign)>0);
85
86 //check: only use alignment mode if there are generalizations
87 bool l_gensExist = false; //set this for all CC's, start with first gen
88
89 //-------------------------------------------------------
90 //first, we sort all edges around each node corresponding
91 //to the given layout in umlGraph, then we insert the mergers
92 //May be inserted in original or in copy
93 bool umlMerge = false; //Standard: insertion in copy
94 //if (umlMerge)
95 //{
96 // umlGraph.sortEdgesFromLayout();
97 // prepareIncrementalMergers(umlGraph);
98 //}
99 //-----------------------------------------------------------
100 //second, we embed the fixed part corresponding to the layout
101 //given in umlgraph
102 //TODO: check if we still need the global lists, do this
103 //for all CCs
104 //we create lists of the additional elements, maybe this can
105 //later be done implicitly within some other loop
106
107 //----------------------------------------------------------
108 // first phase: Compute planarized representation from input
109 //----------------------------------------------------------
110
111 //------------------------------------------------
112 //now we derive a partial planar representation of
113 //the input graph using its layout information
114 PlanRepInc PG(umlGraph, fixedNodes);
115
116 const int numCC = PG.numberOfCCs();
117
118 //TODO: adjust for CC number before/after insertion
119 // (width,height) of the layout of each connected component
120 Array<DPoint> boundingBox(numCC);
121
122 //------------------------------------------
123 //now planarize CCs and apply drawing module
124 int i;
125 for(i = 0; i < numCC; ++i)
126 {
127 // we treat connected component i where PG is set
128 // to a copy of this CC consisting only of fixed nodes
129 node minActive = PG.initMinActiveCC(i);
130 //if a single node was made active, we update its status
131 if (minActive != 0)
132 {
133 fixedNodes[minActive] = true;
134 }
135
136 #ifdef OGDF_DEBUG
137 edge e;
138 forall_edges(e, PG)
139 {
140 edge eOrig = PG.original(e);
141 if (eOrig)
142 {
143 OGDF_ASSERT(PG.chain(eOrig).size() <= 1)
144 }
145 }//foralledges
146 #endif
147
148 int nOrigVerticesPG = PG.numberOfNodes();
149 //TODO: check if copying is really necessary
150 //we want to sort the additional nodes and therefore
151 //copy the list
152 List<node> addNodes;
153 ListConstIterator<node> it = PG.nodesInCC().begin();
154 while (it.valid())
155 {
156 if (!fixedNodes[(*it)])
157 addNodes.pushBack((*it));
158 it++;
159 }//while
160
161
162 //--------------------------------------------
163 //now we insert the additional nodes and edges
164 //sort the additional nodes
165 //simple strategy: sort by their #connections to the fixed part
166 //we can therefore only count if we have fixed nodes
167 if ((addNodes.size() > 1) && (PG.nodesInCC().size() != addNodes.size()))
168 sortIncrementalNodes(addNodes, fixedNodes);
169
170 //TODO: guarantee that the CC is non-empty and connected
171 //insert a first part otherwise
172 //DONE: unconnected parts are connected in a chain
173
174 //attention: the following list pop relies on the property of
175 //the sorting algorithm, that the first node has a connection
176 //to a fixed node or otherwise none of the addnodes has a
177 //connection to fixednodes (its a CC on its own)
178 //in the worst case, we have to introduce a tree, which equals
179 //the steinertree problem, which is NP-hard. As we do not want
180 //to preinsert nodes that do not have layout information (they
181 //do have, but we do not consider it (e.g. for randomly
182 //inserted nodes)), we avoid the problem by inserting artificial
183 //edges connecting all CCs, building a tree of CCs
184
185 //now we derive the embedding given in umlgraph for the fixed part
186 //we work on a copy of umlgraph, because we have to add/delete nodes
187 //and edges and create a PlanRep on an intermediate representation
188 adjEntry adjExternal = 0;
189
190 //--------------------------------------------
191 //here lies the main difference to the static call
192 //we first set the embedding corresponding to the
193 //input and then planarize the given layout
194 TopologyModule TM;
195
196 bool embedded = true;
197 try { //TODO:should be catched within setEmbeddingFromGraph
198 //do not yet compute external face, embed and planarize
199 //with layout given in umlGraph
200 embedded = TM.setEmbeddingFromGraph(PG, umlGraph,
201 adjExternal, false, umlMerge);
202 }//try
203 catch(...)
204 {
205 embedded = false;
206 }//catch
207
208 //returns true if connnectivity edges introduced
209 //TODO: hierhin oder eins nach unten?
210 PG.makeTreeConnected(adjExternal);
211
212 //if embedding could not be set correctly, use standard embedding
213 if (!embedded)
214 {
215 reembed(PG, i, l_align, l_gensExist);
216 }
217
218 //--------------------------------------------
219 //now we compute a combinatorial embedding on
220 //the partial PlanRep that is used for node insertion
221 //and the external face
222 bool singleNode = (PG.numberOfNodes() == 1);
223 if ((PG.numberOfEdges() > 0) || singleNode)
224 {
225 CombinatorialEmbedding E(PG);
226
227 //if we have edges, but no external face, find one
228 //we have also to select one later if there are no edges yet
229 if((adjExternal == 0) && PG.numberOfEdges() > 0)
230 {
231 //face fExternal = E.maximalFace();
232 face fExternal = findBestExternalFace(PG,E);
233 adjExternal = fExternal->firstAdj();
234 //while (PG.sinkConnect(adjExternal->theEdge()))
235 // adjExternal = adjExternal->faceCycleSucc();
236 }
237 if ( (adjExternal != 0) && (PG.numberOfEdges() > 0) )
238 E.setExternalFace(E.rightFace(adjExternal));
239
240 //-------------------------------------------------
241 //we insert additional nodes into the given PlanRep
242 SimpleIncNodeInserter inserter(PG);
243 ListIterator<node> itAdd = addNodes.begin();
244 while (itAdd.valid())
245 {
246 #ifdef OGDF_DEBUG
247 edge eDebug = (*itAdd)->firstAdj()->theEdge();
248 #endif
249 OGDF_ASSERT(PG.chain(eDebug).size() <= 1)
250 //we can check here if PG CC connected and speed
251 //up insertion by not updating CC part information
252 inserter.insertCopyNode((*itAdd), E, umlGraph.type((*itAdd)));
253
254 //select an arbitrary external face if there was only one fixed node
255 if (singleNode && (PG.numberOfEdges() > 0))
256 {
257 adjExternal = PG.firstEdge()->adjSource();
258 E.setExternalFace(E.rightFace(adjExternal));
259 }
260 else
261 {
262 adjExternal = E.externalFace()->firstAdj();
263 int eNum = max(10, PG.numberOfEdges()+1);
264 int count = 0;
265 while ((adjExternal->theNode() == adjExternal->twinNode()) &&
266 (count < eNum))
267 {
268 adjExternal = adjExternal->faceCycleSucc();
269 count++;
270 }
271 OGDF_ASSERT(count < eNum)
272 }
273
274 itAdd++;
275 }//while
276
277 if (!umlMerge)
278 PG.setupIncremental(i, E);
279 OGDF_ASSERT(E.consistencyCheck())
280
281 //we now have a complete representation of the
282 //original CC
283
284 m_nCrossings += PG.numberOfNodes() - nOrigVerticesPG;
285
286 //********************
287 //copied from fixembed
288
289 //*********************************************************
290 // third phase: Compute layout of planarized representation
291 //*********************************************************
292 Layout drawing(PG);
293
294 //distinguish between CC's with/without generalizations
295 //this changes the input layout modules options!
296 if (l_gensExist)
297 m_planarLayouter.get().setOptions(l_layoutOptions);
298 else m_planarLayouter.get().setOptions((l_layoutOptions & ~umlOpAlign));
299
300
301 //***************************************
302 //call the Layouter for the CC's UMLGraph
303 m_planarLayouter.get().call(PG,adjExternal,drawing);
304
305 // copy layout into umlGraph
306 // Later, we move nodes and edges in each connected component, such
307 // that no two overlap.
308 const List<node> &origInCC = PG.nodesInCC(i);
309 ListConstIterator<node> itV;
310
311 //set position for original nodes and set bends for
312 //all edges
313 for(itV = origInCC.begin(); itV.valid(); ++itV)
314 {
315 node vG = *itV;
316
317 umlGraph.x(vG) = drawing.x(PG.copy(vG));
318 umlGraph.y(vG) = drawing.y(PG.copy(vG));
319
320 adjEntry adj;
321 forall_adj(adj,vG)
322 {
323 if ((adj->index() & 1) == 0) continue;
324 edge eG = adj->theEdge();
325
326 drawing.computePolylineClear(PG,eG,umlGraph.bends(eG));
327 }//foralladj
328 }//for orig nodes
329
330
331 if (!umlMerge)
332 {
333 //insert bend point for incremental mergers
334 const SList<node>& mergers = PG.incrementalMergers(i);
335 SListConstIterator<node> itMerger = mergers.begin();
336 while (itMerger.valid())
337 {
338 node vMerger = (*itMerger);
339 //due to the fact that the merger may be expanded, we are
340 //forced to run through the face
341 adjEntry adjMerger = PG.expandAdj(vMerger);
342 //first save a pointer to the bends of the generalization
343 //leading to the target
344 DPolyline dpUp;
345
346 //check if there is an expansion face
347 if (adjMerger != 0)
348 {
349 //if there are bends on the edge, copy them
350 //TODO: check where to derive the bends from
351 //if eUp is nil
352 adjEntry adjUp = adjMerger->cyclicPred();
353 OGDF_ASSERT(PG.isGeneralization(adjUp->theEdge()))
354 edge eUp = PG.original(adjUp->theEdge());
355 //There is never an original here in current incremental algo
356 //OGDF_ASSERT(eUp)
357 if (eUp) dpUp = umlGraph.bends(eUp);
358 //we run through the expansion face to the connected edges
359 //this edge is to dummy corner
360 adjEntry runAdj = adjMerger->faceCycleSucc();
361 while (runAdj != adjMerger)
362 {
363 node vConnect = runAdj->theNode();
364 //because of the node collapse using the original
365 //edges instead of the merger copy edges (should be
366 //fixed for incremental mode) the degree is 4
367 //FIXED!?
368 //if (vConnect->degree() != 4)
369 //while?
370 if (vConnect->degree() != 3)
371 {
372 runAdj = runAdj->faceCycleSucc();
373 continue;
374 }
375 edge eCopy = runAdj->cyclicPred()->theEdge();
376 OGDF_ASSERT(eCopy->target() == runAdj->theNode())
377 OGDF_ASSERT(PG.isGeneralization(eCopy))
378 OGDF_ASSERT(PG.original(eCopy))
379
380 DPolyline &eBends = umlGraph.bends(PG.original(eCopy));
381
382 eBends.pushBack(
383 DPoint(drawing.x(vMerger), drawing.y(vMerger)));
384
385 if (eUp)
386 {
387 ListConstIterator<DPoint> itDp;
388 for(itDp = dpUp.begin(); itDp.valid(); ++itDp)
389 eBends.pushBack(*itDp);
390 }
391 else
392 eBends.pushBack(DPoint(drawing.x(adjUp->twinNode()),
393 drawing.y(adjUp->twinNode())));
394
395 runAdj = runAdj->faceCycleSucc();
396
397 }
398
399 }
400 else //currently all nodes are expanded, but this is not guaranteed
401 {
402 //first save the bends
403 adjEntry adjUp = 0;
404 forall_adj(adjMerger, vMerger)
405 {
406 //upgoing edge
407 if (adjMerger->theEdge()->source() == vMerger)
408 {
409 adjUp = adjMerger;
410 OGDF_ASSERT(PG.isGeneralization(adjMerger->theEdge()))
411 edge eUp = PG.original(adjMerger->theEdge());
412 //check if this is
413 //a) the merger up edge and not a connectivity edge
414 //b) what to do if there is no original of outgoing edge
415 if (eUp)
416 dpUp = umlGraph.bends(eUp);
417 break;
418 }//if
419
420 }//foralladj
421 forall_adj(adjMerger, vMerger)
422 {
423 if (adjMerger->theEdge()->target() == vMerger)
424 {
425 edge eOrig = PG.original(adjMerger->theEdge());
426 if (eOrig)
427 {
428 //incoming merger edges always have an original here!
429 umlGraph.bends(eOrig).pushBack(DPoint(drawing.x(vMerger),
430 drawing.y(vMerger)));
431
432 //was there an original edge?
433 if (dpUp.size()>0)
434 {
435 ListConstIterator<DPoint> itDp;
436 for(itDp = dpUp.begin(); itDp.valid(); ++itDp)
437 umlGraph.bends(eOrig).pushBack(*itDp);
438 }//if
439 else
440 {
441 if (adjUp)
442 umlGraph.bends(eOrig).pushBack(DPoint(drawing.x(adjUp->twinNode()),
443 drawing.y(adjUp->twinNode())));
444 }//else
445 }//if
446
447 }
448 }//forall adj
449 }//else
450 itMerger++;
451 }//while merger nodes
452 }//if !umlMerge
453
454 //umlGraph.writeGML("C:\\FullLayout2Inc.gml");
455
456 // the width/height of the layout has been computed by the planar
457 // layout algorithm; required as input to packing algorithm
458 boundingBox[i] = m_planarLayouter.get().getBoundingBox();
459
460 //*******************
461
462 }//if #edges > 0
463
464 else
465 {
466 //TODO: what if there are no edges but the insertion edges
467 //DONE: we make the CC treeConnected
468 //Nonetheless we have to compute a layout here
469 OGDF_ASSERT(PG.numberOfNodes() < 2)
470 }
471
472
473
474 //TODO: set m_crossings here
475 //m_nCrossings += PG.numberOfNodes() - numOrigNodes;
476
477 }//for connected components
478
479 //*******************
480 //TODO: check shifting to new place
481
482 //----------------------------------------
483 // Arrange layouts of connected components
484 //----------------------------------------
485
486 arrangeCCs(PG, umlGraph, boundingBox);
487
488 if (umlMerge) umlGraph.undoGenMergers();
489
490 umlGraph.removeUnnecessaryBendsHV();
491
492 //********************
493 //new position after adding clique process, check if correct
494 postProcess(umlGraph);
495 }//try
496 catch (...)
497 {
498 call(umlGraph);
499 return;
500 }
501 }//callIncremental
502
503
504 //Insertion order of added nodes:
505 //sorting strategy: we count all adjacent nodes that are in
506 //fixedNodes and sort the nodes correspondingly
507 //In addition, we guarantee that no node is inserted before at least one
508 //of its neighbours is inserted
509
510 //compute how far away from the fixed part the added nodes lay
511 //uses BFS
512 void PlanarizationLayout::getFixationDistance(node startNode,
513 HashArray<int, int> &distance,
514 const NodeArray<bool> &fixedNodes)
515 {
516 //we only change the distance for nodes with distance <=0 because they are not
517 //connected to the fixed part
518 //we only care about nodes which are members of array distance
519 HashArray<int, bool> indexMark(false);
520 //the BFS queue
521 QueuePure<node> nodeQ;
522
523 nodeQ.append(startNode);
524 indexMark[startNode->index()] = true;
525 while (!nodeQ.empty())
526 {
527 adjEntry adjE;
528 node topNode = nodeQ.pop();
529 //hier aufpassen: geht nur, wenn kein fixedNode eine Distance hat
530 //alternativ: alle auf null
531 //zur sicherheit: fixed uebergeben und vergleichen
532 bool fixedBase = fixedNodes[topNode];
533
534 forall_adj(adjE, topNode)
535 {
536 node testNode = adjE->twinNode();
537 int ind = testNode->index();
538
539 if (!indexMark[ind])
540 {
541 indexMark[ind] = true;
542 nodeQ.append(testNode);
543 }
544
545 //we have a distance value, i.e. ind is an additional node
546 if (!fixedNodes[testNode])
547 {
548 if (distance[ind] <= 0)
549 {
550 //should never occur (check: nodes not in CC?)
551 if (fixedBase)
552 {
553 distance[ind] = max(-1, distance[ind]);
554 OGDF_ASSERT(false)
555 }
556 else
557 {
558 if (distance[ind] == 0) distance[ind] = min(-1, distance[topNode->index()] - 1);
559 else distance[ind] = min(-1, max(distance[ind], distance[topNode->index()] - 1));
560 }//else
561 }//if node without contact to fixed nodes
562 }//if distance (is an addnode)
563 }//foralladj
564 }//while
565
566 }//getFixationDistance
567
568 //Attention: changing this behavior makes it necessary to check
569 //the call procedure for the case where one of the addnodes is
570 //made fix to allow insertion of an edge
571 void PlanarizationLayout::sortIncrementalNodes(List<node> &addNodes,
572 const NodeArray<bool> &fixedNodes)
573 {
574 //if there are no fixed nodes, we can not sort
575 //todo: do some other sorting
576
577 //we count all adjacent fixed nodes
578 //store degree by node index
579 HashArray<int, int> indexToDegree(0);
580 ListIterator<node> it = addNodes.begin();
581 adjEntry adjE;
582 node someFixedNode = 0;
583
584 while (it.valid())
585 {
586 if ((*it)->degree() < 1)
587 {
588 indexToDegree[(*it)->index()] = 0;
589 it++;
590 continue;
591 }
592 int vDegree = 0;
593 adjE = (*it)->firstAdj();
594 do {
595 if (fixedNodes[adjE->twinNode()])
596 {
597 vDegree++;
598 someFixedNode = adjE->twinNode();
599 }
600 adjE = adjE->cyclicSucc();
601 } while (adjE != (*it)->firstAdj());
602
603 indexToDegree[(*it)->index()] = vDegree;
604
605 it++;
606 }//while
607 //for all nodes that are not connected to the fixed part we have to guarantee
608 //that they are not inserted before one of their neighbours is inserted
609 //therefore we set negative values for all nodes corresponding to their distance
610 //to the fixed part
611 OGDF_ASSERT(someFixedNode != 0)
612 if (someFixedNode == 0) throw AlgorithmFailureException();
613 //we start the BFS at some fixed node
614 getFixationDistance(someFixedNode,indexToDegree, fixedNodes);
615
616
617 //we sort the nodes in decreasing vDegree value order
618 AddNodeComparer comp(indexToDegree);
619 addNodes.quicksort(comp);
620
621 }//sortincrementalnodes
622
623 } // end namespace ogdf
Windows Explorer Extension to Operate Git