1 /** \file
2 * \brief implementation of PlanRepUML class
3 *
4 * \author Carsten Gutwenger
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32 //Debug
33 #include <ogdf/basic/simple_graph_alg.h>
34 #include <ogdf/fileformats/GraphIO.h>
35
36 //zwei Moeglichkeiten: Elemente verstecken mit hide/activate
37 //oder Elemente, die nicht akiv sind, loeschen
38
39 #include <ogdf/planarity/PlanRepInc.h>
40 #include <ogdf/planarity/TopologyModule.h>
41
42 namespace ogdf {
43
PlanRepInc(const UMLGraph & UG)44 PlanRepInc::PlanRepInc(const UMLGraph &UG) : PlanRepUML(UG)
45 {
46 initMembers(UG);
47 }
48
PlanRepInc(const UMLGraph & UG,const NodeArray<bool> & fixed)49 PlanRepInc::PlanRepInc(const UMLGraph &UG, const NodeArray<bool> &fixed)
50 : PlanRepUML(UG)
51 {
52 initMembers(UG);
53
54 const Graph &G = UG.constGraph();
55 //we start the node activation status with the fixed input values
56 for(node v : G.nodes)
57 {
58 m_activeNodes[v] = fixed[v];
59 }
60
61 }
62
initMembers(const UMLGraph & UG)63 void PlanRepInc::initMembers(const UMLGraph &UG)
64 {
65 m_activeNodes.init(UG.constGraph(), true);
66 //braucht man vielleicht gar nicht mehr (Kreuzungen?)
67 //zumindest spaeter durch type in typefields ersetzen
68 m_treeEdge.init(*this, false);
69 m_treeInit = false;
70 }
71
72
73 //activate a cc with at least one node, even if all nodes are
74 //excluded
initMinActiveCC(int i)75 node PlanRepInc::initMinActiveCC(int i)
76 {
77 node v = initActiveCCGen(i, true);
78 return v;
79 }
80
initActiveCC(int i)81 void PlanRepInc::initActiveCC(int i)
82 {
83 initActiveCCGen(i, false);
84 }
85
86 //activates a cc, if minnode==true, at least one node is inserted
initActiveCCGen(int i,bool minNode)87 node PlanRepInc::initActiveCCGen(int i, bool minNode)
88 {
89 //node to be returned
90 node minActive = nullptr;
91 //list to be filled wih activated nodes
92 List<node> activeOrigCCNodes;
93 // a) delete copy / chain fields for originals of nodes in current cc,
94 // since we change the CC number...
95 // (since we remove all these copies in initByNodes(...)
96 // b) create list of currently active original nodes
97
98 for(int j = m_ccInfo.startNode(i); j < m_ccInfo.stopNode(i); ++j)
99 {
100 node vG = m_ccInfo.v(j);
101
102 if (m_activeNodes[vG])
103 activeOrigCCNodes.pushBack(vG);
104
105 if (m_currentCC >= 0)
106 {
107 m_vCopy[vG] = nullptr;
108
109 for(adjEntry adj : vG->adjEntries)
110 {
111 if ((adj->index() & 1) == 0) continue;
112 edge eG = adj->theEdge();
113
114 m_eCopy[eG].clear();
115 }
116 }
117 }
118 //}
119
120 // now we check if we have to activate a single node
121 if (minNode && activeOrigCCNodes.empty()) {
122 //Simple strategy: take the first node
123 minActive = m_ccInfo.v(m_ccInfo.startNode(i));
124 if (minActive != nullptr) {
125 m_activeNodes[minActive] = true;
126 activeOrigCCNodes.pushFront(minActive);
127 }
128 }
129
130 m_currentCC = i;
131
132 //double feature: liste und nodearray, besser
133 GraphCopy::initByActiveNodes(activeOrigCCNodes, m_activeNodes, m_eAuxCopy);
134
135 // set type of edges (gen. or assoc.) in the current CC
136 if (m_pGraphAttributes->has(GraphAttributes::edgeType))
137 for(edge e : edges)
138 {
139 m_eType[e] = m_pGraphAttributes->type(original(e));
140 if (original(e))
141 {
142 switch (m_pGraphAttributes->type(original(e)))
143 {
144 case Graph::EdgeType::generalization: setGeneralization(e); break;
145 case Graph::EdgeType::association: setAssociation(e); break;
146 default: OGDF_ASSERT(false);
147 }
148 }
149 }
150
151 if (m_pGraphAttributes->has(GraphAttributes::nodeType))
152 for(node v : nodes)
153 m_vType[v] = m_pGraphAttributes->type(original(v));
154 //TODO:check only in CCs or global?
155 m_treeInit = false;
156 return minActive;
157 }
158
159 //node activation automatically activates all
160 //adjacent edges
161 //CCs can be joined by this method
activateNode(node v)162 void PlanRepInc::activateNode(node v)
163 {
164 if (m_activeNodes[v]) return;
165
166 m_activeNodes[v] = true;
167 }
168
169 //Connect parts of partial active current CC.
170 //Note that this only makes sense when the CC parts are
171 //already correctly embedded. Crossings are already replaced
172 //by nodes
makeTreeConnected(adjEntry)173 bool PlanRepInc::makeTreeConnected(adjEntry /* adjExternal */)
174 {
175
176 //we compute node numbers for the partial CCs in order to
177 //identify the treeConnect Edges that can be deleted later
178 m_component.init(*this, -1);
179
180 //if there is only one CC, we don't need to connect
181 if (isConnected(*this)) return false;
182 //We have to insert edges connnecting nodes lying on
183 //the "external" face of the active parts
184
185 //First, we activate the CC's parts one by one and compute
186 //the 'external' face from the layout information
187 //If the PlanRepInc is not embedded corresponding to
188 //this layout, we may introduce edges that are non-planar
189 //in the drawing, leading to problems when we compute paths
190 //in the dual graph
191
192 List<node> isolatedNodes;
193 const int numPartialCC = connectedComponents(*this, m_component, &isolatedNodes);
194
195 //CombinatorialEmbedding can cope with unconnected graphs
196 //but does not provide faces for isolated nodes
197 CombinatorialEmbedding E(*this);
198 TopologyModule tm;
199 List<adjEntry> extAdjs;
200 //we run through all faces searching for all outer faces
201 for(face f : E.faces)
202 {
203 //TODO: check if we should select special adjEntry instead of first
204 if (tm.faceSum(*this, *m_pGraphAttributes, f) < 0)
205 extAdjs.pushBack(f->firstAdj());
206
207 #ifdef OGDF_DEBUG
208 std::cout << "FaceSum in Face " << f->index() << " Groesse " << f->size()
209 << " ist: " << tm.faceSum(*this, *m_pGraphAttributes, f) <<"\n" << std::flush;
210 #endif
211 }
212
213 //now we have faces for all partial CCs that are not isolated nodes
214
215 OGDF_ASSERT(extAdjs.size() + isolatedNodes.size() == numPartialCC);
216 #if 0
217 OGDF_ASSERT(extAdjs.size() > 1) //eigentlich: = #partial CCs
218 OGDF_ASSERT(extAdjs.size() == numPartialCC);
219 #endif
220
221 const int n1 = numPartialCC-1;
222 m_eTreeArray.init(0, n1, 0, n1, nullptr);
223 m_treeInit = true;
224
225 //Three cases: only CCs, only isolated nodes, and both (where
226 //only one CC + isolated nodes is possible
227
228 //now we connect all partial CCs by inserting edges at the adjEntries
229 //in extAdjs and adding all isolated nodes
230 adjEntry lastAdj = nullptr;
231 ListIterator<adjEntry> it = extAdjs.begin();
232 while(it.valid())
233 {
234 //for the case: one external face, multiple isolated nodes
235 lastAdj = (*it);
236 adjEntry adj = (*it);
237 ListIterator<adjEntry> it2 = it.succ();
238 if (it2.valid())
239 {
240 adjEntry adj2 = (*it2);
241 edge eTree = newEdge(adj, adj2);
242 m_treeEdge[eTree] = true;
243 lastAdj = eTree->adjTarget();
244 //save the connection edge by CC number index
245 //this is used when deleting obsolete edges later
246 //after edge reinsertion
247 m_eTreeArray(componentNumber(adj->theNode()), componentNumber(adj2->theNode())) =
248 m_eTreeArray(m_component[adj2->theNode()], m_component[adj->theNode()])
249 = eTree;
250 }
251
252 ++it;
253 }
254 while (!isolatedNodes.empty())
255 {
256 node uvw = isolatedNodes.popFrontRet();
257 if (lastAdj)
258 {
259 //same block as above
260 edge eTree = newEdge(uvw, lastAdj);
261 m_treeEdge[eTree] = true;
262 //save the connection edge by CC number index
263 //this is used when deleting obsolete edges later
264 //after edge reinsertion
265 m_eTreeArray(componentNumber(lastAdj->theNode()), componentNumber(uvw)) =
266 m_eTreeArray(m_component[uvw], m_component[lastAdj->theNode()])
267 = eTree;
268 lastAdj = eTree->adjSource();
269 }
270 else //connect the first two isolated nodes / only iso nodes exist
271 {
272 //MUST BE #isonodes>1, else we returned already because CC connected
273 OGDF_ASSERT(!isolatedNodes.empty());
274 node secv = isolatedNodes.popFrontRet();
275 //same block as above
276 edge eTree = newEdge(uvw, secv);
277 m_treeEdge[eTree] = true;
278 //save the connection edge by CC number index
279 //this is used when deleting obsolete edges later
280 //after edge reinsertion
281 m_eTreeArray(componentNumber(secv), componentNumber(uvw)) =
282 m_eTreeArray(m_component[uvw], m_component[secv])
283 = eTree;
284 lastAdj = eTree->adjSource();
285 }
286 }
287
288 OGDF_ASSERT(isConnected(*this));
289
290 #if 0
291 List<adjEntry> extAdjs;
292 getExtAdjs(extAdjs);
293 #endif
294
295 return true;
296 }
297
298 //is only called when CC not connected => m_eTreeArray is initialized
deleteTreeConnection(int i,int j)299 void PlanRepInc::deleteTreeConnection(int i, int j)
300 {
301 edge e = m_eTreeArray(i, j);
302 if (e == nullptr) return;
303 edge nexte = nullptr;
304 OGDF_ASSERT(e);
305 OGDF_ASSERT(m_treeEdge[e]);
306 //we have to take care of treeConnection edges that
307 //are already crossed
308 while ((e->target()->degree() == 4) &&
309 m_treeEdge[e->adjTarget()->cyclicSucc()->cyclicSucc()->theEdge()])
310 {
311 nexte = e->adjTarget()->cyclicSucc()->cyclicSucc()->theEdge();
312 OGDF_ASSERT(original(nexte) == nullptr);
313 delEdge(e);
314 e = nexte;
315 }
316 delEdge(e);
317 m_eTreeArray(i, j) = nullptr;
318 m_eTreeArray(j, i) = nullptr;
319
320 OGDF_ASSERT(isConnected(*this));
321 }
322
323 //is only called when CC not connected => m_eTreeArray is initialized
deleteTreeConnection(int i,int j,CombinatorialEmbedding & E)324 void PlanRepInc::deleteTreeConnection(int i, int j, CombinatorialEmbedding &E)
325 {
326
327 edge e = m_eTreeArray(i, j);
328 if (e == nullptr) return;
329 edge nexte = nullptr;
330 OGDF_ASSERT(e);
331 OGDF_ASSERT(m_treeEdge[e]);
332 //we have to take care of treeConnection edges that
333 //are already crossed
334 while ((e->target()->degree() == 4) &&
335 m_treeEdge[e->adjTarget()->cyclicSucc()->cyclicSucc()->theEdge()])
336 {
337 nexte = e->adjTarget()->cyclicSucc()->cyclicSucc()->theEdge();
338 OGDF_ASSERT(original(nexte) == nullptr);
339 E.joinFaces(e);
340 e = nexte;
341 }
342 E.joinFaces(e);
343 m_eTreeArray(i, j) = nullptr;
344 m_eTreeArray(j, i) = nullptr;
345
346 OGDF_ASSERT(isConnected(*this));
347 }
348
349 //use the layout information in the umlgraph to find nodes in
350 //unconnected active parts of a CC that can be connected without
351 //crossings in the given embedding
getExtAdjs(List<adjEntry> &)352 void PlanRepInc::getExtAdjs(List<adjEntry> & /* extAdjs */)
353 {
354 //in order not to change the current CC initialization,
355 //we construct a copy of the active parts (one by one)
356 //and use the layout information to compute a external
357 //face for that part. An (original) adjEntry on this face
358 //is then inserted into the extAdjs list.
359
360 //derive the unconnected parts by a run through the current
361 //copy
362 //compute connected component of current CC
363
364 NodeArray<int> component(*this);
365 int numPartialCC = connectedComponents(*this, component);
366 EdgeArray<edge> copyEdge;//copy edges in partial CC copy
367 //now we compute a copy for every CC
368 //initialize an array of lists of nodes contained in a CC
369 Array<List<node> > nodesInPartialCC;
370 nodesInPartialCC.init(numPartialCC);
371
372 for(node v : nodes)
373 nodesInPartialCC[component[v]].pushBack(v);
374
375 int i = 0;
376 for (i = 0; i < numPartialCC; i++)
377 {
378 List<node> &theNodes = nodesInPartialCC[i];
379 GraphCopy GC;
380 GC.createEmpty(*this);
381 GC.initByNodes(theNodes, copyEdge);
382 //now we derive an outer face of GC by using the
383 //layout information on it's original
384
385 #if 0
386 //TODO: Insert the bend points into the copy
387
388 CombinatorialEmbedding E(GC);
389
390 //run through the faces and compute angles to
391 //derive outer face
392 //we dont care about the original structure of
393 //the graph, i.e., if crossings are inserted aso
394 //we only take the given partial CC and its layout
395 adjEntry extAdj = getExtAdj(GC, E);
396
397 for(node v : GC.nodes)
398 {
399 }
400 #endif
401 }
402 }
403
404 //return one adjEntry on the outer face of GC where GC
405 //is a partial copy of this PlanRepInc
getExtAdj(GraphCopy &,CombinatorialEmbedding &)406 adjEntry PlanRepInc::getExtAdj(GraphCopy & /* GC */, CombinatorialEmbedding & /* E */)
407 {
408 return adjEntry();
409 }
410
411 //structure updates of underlying graph
412 //signaled by graph structure
nodeDeleted(node)413 void PlanRepInc::nodeDeleted(node /* v */)
414 {
415 }
nodeAdded(node)416 void PlanRepInc::nodeAdded(node /* v */) {}
edgeDeleted(edge)417 void PlanRepInc::edgeDeleted(edge /* e */) {}
edgeAdded(edge)418 void PlanRepInc::edgeAdded(edge /* e */) {}
reInit()419 void PlanRepInc::reInit() {}
cleared()420 void PlanRepInc::cleared() {}
421
422
423 //DEBUGSTUFF
424 #ifdef OGDF_DEBUG
genusLayout(Layout & drawing) const425 int PlanRepInc::genusLayout(Layout &drawing) const
426 {
427 Graph testGraph;
428 GraphAttributes AG(testGraph, GraphAttributes::nodeGraphics |
429 GraphAttributes::edgeGraphics |
430 GraphAttributes::nodeStyle |
431 GraphAttributes::edgeStyle
432 );
433 Layout xy;
434 NodeArray<node> tcopy(*this, nullptr);
435 EdgeArray<bool> finished(*this, false);
436 EdgeArray<edge> eOrig(testGraph, nullptr);
437 Color invalid(0,0,0,0);
438 EdgeArray<Color> eCol(*this, invalid);
439
440 if (numberOfNodes() == 0) return 0;
441
442 int nIsolated = 0;
443 for(node v : nodes)
444 if (v->degree() == 0) ++nIsolated;
445
446 NodeArray<int> component(*this);
447 int nCC = connectedComponents(*this,component);
448
449 AdjEntryArray<bool> visited(*this,false);
450 int nFaceCycles = 0;
451
452 int colBase = 3;
453 int colBase2 = 250;
454 for(node v : nodes)
455 {
456 Color col =Color(colBase,colBase2,colBase);
457 colBase = (colBase*3) % 233;
458 colBase2 = (colBase*2) % 233;
459
460 if (tcopy[v] == nullptr)
461 {
462 node u = testGraph.newNode();
463 tcopy[v] = u;
464 AG.x(u) = drawing.x(v);
465 AG.y(u) = drawing.y(v);
466 AG.fillColor(u) = col;
467 AG.strokeColor(u) = Color::Name::Red;
468 AG.strokeWidth(u) = 8;
469 }
470
471 for(adjEntry adj1 : v->adjEntries) {
472 bool handled = visited[adj1];
473 adjEntry adj = adj1;
474
475 do {
476 node z = adj->theNode();
477 if (tcopy[z] == nullptr)
478 {
479 node u1 = testGraph.newNode();
480 tcopy[z] = u1;
481 AG.x(u1) = drawing.x(z);
482 AG.y(u1) = drawing.y(z);
483 AG.fillColor(u1) = col;
484 }
485 if (!finished[adj->theEdge()])
486 {
487 node w = adj->theEdge()->opposite(z);
488 if (tcopy[w] != nullptr)
489 {
490 edge e;
491 if (w == adj->theEdge()->source())
492 e = testGraph.newEdge(tcopy[w], tcopy[z]);
493 else e = testGraph.newEdge(tcopy[z], tcopy[w]);
494 eOrig[e] = adj->theEdge();
495 if (eCol[adj->theEdge()] == invalid)
496 AG.strokeColor(e) = eCol[adj->theEdge()];
497 else
498 {
499 eCol[adj->theEdge()] = col;
500 AG.strokeColor(e) = col;
501 }
502 finished[adj->theEdge()] = true;
503 }
504 #if 0
505 else {
506 eCol[adj->theEdge()] = col;
507 }
508 #endif
509 }
510 visited[adj] = true;
511 adj = adj->faceCycleSucc();
512 } while (adj != adj1);
513
514 if (handled) continue;
515
516 ++nFaceCycles;
517 }
518 }
519 #if 0
520 //insert the current embedding order by setting bends
521 for(node v : testGraph.nodes)
522 {
523 adjEntry ad1 = v->firstAdj();
524 }
525 #endif
526
527 int genus = (numberOfEdges() - numberOfNodes() - nIsolated - nFaceCycles + 2*nCC) / 2;
528 #if 0
529 if (genus != 0)
530 #endif
531 {
532 GraphIO::write(AG, "GenusErrorLayout.gml", GraphIO::writeGML);
533 }
534 return genus;
535 }
536 //#endif
537
writeGML(std::ostream & os,const GraphAttributes & AG)538 void PlanRepInc::writeGML(std::ostream &os, const GraphAttributes &AG)
539 {
540 OGDF_ASSERT(m_pGraphAttributes == &(AG));
541 const Graph &G = *this;
542
543 NodeArray<int> id(*this);
544 int nextId = 0;
545
546 os.setf(std::ios::showpoint);
547 os.precision(10);
548
549 os << "Creator \"ogdf::PlanRepInc::writeGML\"\n";
550 os << "graph [\n";
551 os << " directed 1\n";
552
553 for(node v : G.nodes) {
554 if (!original(v)) continue;
555 os << " node [\n";
556
557 os << " id " << (id[v] = nextId++) << "\n";
558
559 os << " graphics [\n";
560 os << " x " << AG.x(original(v)) << "\n";
561 os << " y " << AG.y(original(v)) << "\n";
562 os << " w " << 10.0 << "\n";
563 os << " h " << 10.0 << "\n";
564 os << " type \"rectangle\"\n";
565 os << " width 1.0\n";
566 if (typeOf(v) == Graph::NodeType::generalizationMerger) {
567 os << " type \"oval\"\n";
568 os << " fill \"#0000A0\"\n";
569 }
570 else if (typeOf(v) == Graph::NodeType::generalizationExpander) {
571 os << " type \"oval\"\n";
572 os << " fill \"#00FF00\"\n";
573 }
574 else if (typeOf(v) == Graph::NodeType::highDegreeExpander ||
575 typeOf(v) == Graph::NodeType::lowDegreeExpander)
576 os << " fill \"#FFFF00\"\n";
577 else if (typeOf(v) == Graph::NodeType::dummy)
578 {
579 if (isCrossingType(v))
580 {
581 os << " fill \"#FF0000\"\n";
582 }
583 else
584 os << " fill \"#FFFFFF\"\n";
585 os << " type \"oval\"\n";
586 }
587
588 else if (v->degree() > 4)
589 os << " fill \"#FFFF00\"\n";
590
591 else
592 os << " fill \"#000000\"\n";
593
594 os << " ]\n"; // graphics
595
596 os << "]\n"; // node
597 }
598
599 for(edge e : G.edges) {
600 if (!(original(e->source()) && original(e->target()))) continue;
601 os << " edge [\n";
602
603 os << " source " << id[e->source()] << "\n";
604 os << " target " << id[e->target()] << "\n";
605
606 os << " generalization " << typeOf(e) << "\n";
607
608 os << " graphics [\n";
609
610 os << " type \"line\"\n";
611
612 if (typeOf(e) == Graph::EdgeType::generalization)
613 {
614 os << " arrow \"last\"\n";
615 if (m_alignUpward[e->adjSource()])
616 os << " fill \"#0000FF\"\n";
617 else
618 os << " fill \"#FF0000\"\n";
619 os << " width 3.0\n";
620 }
621 else
622 {
623 if (typeOf(e->source()) == Graph::NodeType::generalizationExpander ||
624 typeOf(e->source()) == Graph::NodeType::generalizationMerger ||
625 typeOf(e->target()) == Graph::NodeType::generalizationExpander ||
626 typeOf(e->target()) == Graph::NodeType::generalizationMerger)
627 {
628 os << " arrow \"none\"\n";
629 if (isBrother(e))
630 os << " fill \"#F0F000\"\n"; //gelb
631 else if (isHalfBrother(e))
632 os << " fill \"#FF00AF\"\n";
633 else
634 os << " fill \"#FF0000\"\n";
635 }
636 else
637 os << " arrow \"none\"\n";
638 if (isBrother(e))
639 os << " fill \"#F0F000\"\n"; //gelb
640 else if (isHalfBrother(e))
641 os << " fill \"#FF00AF\"\n";
642 else
643 os << " fill \"#00000F\"\n";
644 os << " width 1.0\n";
645 }
646
647 if (original(e) != nullptr)
648 {
649 const DPolyline &dpl = AG.bends(original(e));
650 if (!dpl.empty()) {
651 os << " Line [\n";
652 os << " point [ x " << AG.x(original(e->source())) << " y " <<
653 AG.y(original(e->source())) << " ]\n";
654
655 ListConstIterator<DPoint> it;
656 for(it = dpl.begin(); it.valid(); ++it)
657 os << " point [ x " << (*it).m_x << " y " << (*it).m_y << " ]\n";
658
659 os << " point [ x " << AG.x(original(e->target())) << " y " <<
660 AG.y(original(e->target())) << " ]\n";
661
662 os << " ]\n"; // Line
663 }
664 }
665
666 os << " ]\n"; // graphics
667
668 os << " ]\n"; // edge
669 }
670
671 os << "]\n"; // graph
672 }
673 //#endif
674
675
writeGML(std::ostream & os,const Layout & drawing,bool colorEmbed)676 void PlanRepInc::writeGML(std::ostream &os, const Layout &drawing, bool colorEmbed)
677 {
678 const Graph &G = *this;
679
680 NodeArray<int> id(*this);
681 int nextId = 0;
682
683 os.setf(std::ios::showpoint);
684 os.precision(10);
685
686 os << "Creator \"ogdf::GraphAttributes::writeGML\"\n";
687
688 os << "graph [\n";
689 os << " directed 1\n";
690
691 for(node v : G.nodes) {
692 os << " node [\n";
693
694 os << " id " << (id[v] = nextId++) << "\n";
695
696 os << " graphics [\n";
697 os << " x " << drawing.x(v) << "\n";
698 os << " y " << drawing.y(v) << "\n";
699 os << " w " << 10.0 << "\n";
700 os << " h " << 10.0 << "\n";
701 os << " type \"rectangle\"\n";
702 os << " width 1.0\n";
703 if (typeOf(v) == Graph::NodeType::generalizationMerger) {
704 os << " type \"oval\"\n";
705 os << " fill \"#0000A0\"\n";
706 }
707 else if (typeOf(v) == Graph::NodeType::generalizationExpander) {
708 os << " type \"oval\"\n";
709 os << " fill \"#00FF00\"\n";
710 }
711 else if (typeOf(v) == Graph::NodeType::highDegreeExpander ||
712 typeOf(v) == Graph::NodeType::lowDegreeExpander)
713 os << " fill \"#FFFF00\"\n";
714 else if (typeOf(v) == Graph::NodeType::dummy)
715 {
716 if (isCrossingType(v))
717 {
718 os << " fill \"#FF0000\"\n";
719 }
720 else os << " fill \"#FFFFFF\"\n";
721 os << " type \"oval\"\n";
722 }
723
724 else if (v->degree() > 4)
725 os << " fill \"#FFFF00\"\n";
726
727 else
728 os << " fill \"#000000\"\n";
729
730
731 os << " ]\n"; // graphics
732
733 os << " ]\n"; // node
734 }
735
736
737 NodeArray<bool> proc(*this, false);
738 for(edge e : G.edges)
739 {
740 os << " edge [\n";
741
742 os << " source " << id[e->source()] << "\n";
743 os << " target " << id[e->target()] << "\n";
744
745 os << " generalization " << typeOf(e) << "\n";
746 os << " graphics [\n";
747
748 os << " type \"line\"\n";
749
750 int embedNum = 0;
751 int sNum = 0;
752 int tNum = 0;
753 if (colorEmbed)
754 {
755 //Find out embedding order number
756 //dirty hack, quadratic time
757 //color after higher degree order
758 node w;
759 if (proc[e->target()] && !proc[e->source()]) w = e->target();
760 else if (proc[e->source()] && !proc[e->target()]) w = e->source();
761 else
762 w = (e->source()->degree() > e->target()->degree() ? e->source() : e->target());
763
764 proc[w] = true;
765 adjEntry adf = w->firstAdj();
766 while (adf->theEdge() != e) //ugly
767 {
768 embedNum++;
769 adf = adf->cyclicSucc();
770 }
771
772 node uvw = e->source();
773 adf = uvw->firstAdj();
774 while (adf->theEdge() != e) //ugly
775 {
776 sNum++;
777 adf = adf->cyclicSucc();
778 }
779 uvw = e->target();
780 adf = uvw->firstAdj();
781 while (adf->theEdge() != e) //ugly
782 {
783 tNum++;
784 adf = adf->cyclicSucc();
785 }
786 }
787
788 if (typeOf(e) == Graph::EdgeType::generalization)
789 {
790 os << " arrow \"last\"\n";
791
792 if (m_alignUpward[e->adjSource()])
793 os << " fill \"#0000FF\"\n";
794 else
795 {
796 switch (embedNum)
797 {
798 case 1: os << " fill \"#F00000\"\n";break;
799 case 2: os << " fill \"#D00000\"\n";break;
800 case 3: os << " fill \"#B00000\"\n";break;
801 case 4: os << " fill \"#900000\"\n";break;
802 case 5: os << "fill \"#800000\"\n";break;
803 case 6: os << " fill \"#600000\"\n";break;
804 case 7: os << " fill \"#400000\"\n";break;
805 default: os << " fill \"#FF0000\"\n";
806 }
807 }
808 os << " width 3.0\n";
809 }
810 else
811 {
812 if (typeOf(e->source()) == Graph::NodeType::generalizationExpander ||
813 typeOf(e->source()) == Graph::NodeType::generalizationMerger ||
814 typeOf(e->target()) == Graph::NodeType::generalizationExpander ||
815 typeOf(e->target()) == Graph::NodeType::generalizationMerger)
816 {
817 os << " arrow \"none\"\n";
818 if (isBrother(e))
819 os << " fill \"#F0F000\"\n"; //gelb
820 else if (isHalfBrother(e))
821 os << " fill \"#FF00AF\"\n";
822 else
823 os << " fill \"#FF0000\"\n";
824 }
825 else
826 os << " arrow \"none\"\n";
827 if (isBrother(e))
828 os << " fill \"#F0F000\"\n"; //gelb
829 else if (isHalfBrother(e))
830 os << " fill \"#FF00AF\"\n";
831 else {
832 switch (embedNum)
833 {
834 case 1: os << " fill \"#000030\"\n";break;
835 case 2: os << " fill \"#000060\"\n";break;
836 case 3: os << " fill \"#200090\"\n";break;
837 case 4: os << " fill \"#3000B0\"\n";break;
838 case 5: os << " fill \"#4000E0\"\n";break;
839 case 6: os << " fill \"#5000F0\"\n";break;
840 case 7: os << " fill \"#8000FF\"\n";break;
841 default: os << " fill \"#000000\"\n";
842 }
843 }
844
845 os << " width 1.0\n";
846 }
847
848 //insert a bend at each end corresponding to the
849 //adjacency order
850 if (colorEmbed)
851 {
852 double rad = 20.0;
853 node vs = e->source();
854 node vt = e->target();
855 double sx, sy, tx, ty;
856
857 const double xs = drawing.x(vs),
858 ys = drawing.y(vs); //aufpunkt
859 const double xt = drawing.x(vt),
860 yt = drawing.y(vt); //aufpunkt
861
862 //double dx = drawing.x(vt) - drawing.x(vs);
863 //double dy = drawing.y(vt) - drawing.y(vs);
864 //double length = sqrt(dx*dx + dy*dy);
865 //reference edge
866 //Aufpunkte
867 node rws = vs->firstAdj()->twinNode();
868 node rwt = vt->firstAdj()->twinNode();
869 //Richtungsvektoren
870 double rdxs = drawing.x(rws) - xs;
871 double rdys = drawing.y(rws) - ys;
872 double rdxt = drawing.x(rwt) - xt;
873 double rdyt = drawing.y(rwt) - yt;
874
875 double rslength = sqrt(rdxs*rdxs + rdys*rdys);
876 double rtlength = sqrt(rdxt*rdxt + rdyt*rdyt);
877
878 double refSx = drawing.x(vs) + (rad/rslength)*rdxs;
879 double refSy = drawing.y(vs) + (rad/rslength)*rdys;
880 double refTx = drawing.x(vt) + (rad/rtlength)*rdxt;
881 double refTy = drawing.y(vt) + (rad/rtlength)*rdyt;
882
883 double refSx2 = drawing.x(vs) + rdxs/rslength;
884 double refSy2 = drawing.y(vs) + rdys/rslength;
885 double refTx2 = drawing.x(vt) + rdxt/rslength;
886 double refTy2 = drawing.y(vt) + rdyt/rslength;
887
888 //do not change reference edge
889 if (sNum <0)//== 0)
890 {
891 sx = refSx;
892 sy = refSy;
893 }
894 else
895 {
896 OGDF_ASSERT(sNum < vs->degree());
897 double angleS = sNum*360.0/vs->degree();
898
899 double refAngleS = DPoint(xs, ys).angleDegrees(
900 DPoint(refSx2, refSy2),
901 DPoint(xs+1.0, ys)
902 );
903 double testAngleS = refAngleS-angleS;
904
905 //---
906 double dTS = Math::degreesToRadians(testAngleS);
907 //--
908 sx = xs + rad*cos(dTS);//testAngleS);
909 sy = ys + rad*sin(dTS);//testAngleS);
910 }
911 if (tNum <0)//== 0)
912 {
913 tx = refTx;
914 ty = refTy;
915 }
916 else
917 {
918 OGDF_ASSERT(tNum < vt->degree());
919 double angleT = tNum*360/vt->degree();
920
921 double refAngleT = DPoint(xt, yt).angleDegrees(
922 DPoint(refTx2, refTy2),
923 DPoint(xt+1.0, yt)
924 );
925 double testAngleT = refAngleT-angleT;
926
927 //--
928 double dTT = Math::degreesToRadians(testAngleT);
929 //--
930
931 tx = xt + rad*cos(dTT);//testAngleT);
932 ty = yt + rad*sin(dTT);//testAngleT);
933
934 }
935
936 os << " Line [\n";
937 os << " point [ x " << xs << " y " << ys << " ]\n";
938 os << " point [ x " << sx << " y " << sy << " ]\n";
939 os << " point [ x " << tx << " y " << ty << " ]\n";
940 os << " point [ x " << xt << " y " << yt << " ]\n";
941
942 os << " ]\n"; // Line
943 }
944 os << " ]\n"; // graphics
945
946 os << " ]\n"; // edge
947 }
948
949 os << "]\n"; // graph
950 }
951 #endif
952
953 }
954