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