1 /** \file
2 * \brief A simple embedder algorithm.
3 *
4 * \author Thorsten Kerkhof
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 #include <ogdf/planarity/SimpleEmbedder.h>
33 #include <ogdf/basic/FaceArray.h>
34
35 namespace ogdf {
36
doCall(Graph & G,adjEntry & adjExternal)37 void SimpleEmbedder::doCall(Graph& G, adjEntry& adjExternal)
38 {
39 // determine embedding of G
40
41 // We currently compute any embedding and choose the maximal face
42 // as external face
43
44 // if we use FixedEmbeddingInserterOld, we have to re-use the computed
45 // embedding, otherwise crossing nodes can turn into "touching points"
46 // of edges (alternatively, we could compute a new embedding and
47 // finally "remove" such unnecessary crossings).
48 adjExternal = nullptr;
49 if(!G.representsCombEmbedding())
50 planarEmbed(G);
51
52 CombinatorialEmbedding CE(G);
53 PlanRep PR(G);
54 //face fExternal = E.maximalFace();
55 face fExternal = findBestExternalFace(PR, CE);
56 adjExternal = fExternal->firstAdj();
57 }
58
59
findBestExternalFace(const PlanRep & PG,const CombinatorialEmbedding & E)60 face SimpleEmbedder::findBestExternalFace(
61 const PlanRep& PG,
62 const CombinatorialEmbedding& E)
63 {
64 FaceArray<int> weight(E);
65
66 for(face f : E.faces)
67 weight[f] = f->size();
68
69 for(node v : PG.nodes)
70 {
71 if(PG.typeOf(v) != Graph::NodeType::generalizationMerger)
72 continue;
73
74 adjEntry adjFound = nullptr;
75 for(adjEntry adj : v->adjEntries) {
76 if (adj->theEdge()->source() == v) {
77 adjFound = adj;
78 break;
79 }
80 }
81
82 OGDF_ASSERT(adjFound->theEdge()->source() == v);
83
84 node w = adjFound->theEdge()->target();
85 bool isBase = true;
86
87 for(adjEntry adj : w->adjEntries) {
88 edge e = adj->theEdge();
89 if(e->target() != w && PG.typeOf(e) == Graph::EdgeType::generalization) {
90 isBase = false;
91 break;
92 }
93 }
94
95 if(!isBase)
96 continue;
97
98 face f1 = E.leftFace(adjFound);
99 face f2 = E.rightFace(adjFound);
100
101 weight[f1] += v->indeg();
102 if(f2 != f1)
103 weight[f2] += v->indeg();
104 }
105
106 face fBest = E.firstFace();
107 for(face f : E.faces)
108 if(weight[f] > weight[fBest])
109 fBest = f;
110
111 return fBest;
112 }
113
114 }
115