1 /** \file
2 * \brief Computes an embedding of a graph with maximum external face.
3 * See paper "Graph Embedding with Minimum Depth and Maximum External
4 * Face" by C. Gutwenger and P. Mutzel (2004) for details.
5 *
6 * \author Thorsten Kerkhof
7 *
8 * \par License:
9 * This file is part of the Open Graph Drawing Framework (OGDF).
10 *
11 * \par
12 * Copyright (C)<br>
13 * See README.md in the OGDF root directory for details.
14 *
15 * \par
16 * This program is free software; you can redistribute it and/or
17 * modify it under the terms of the GNU General Public License
18 * Version 2 or 3 as published by the Free Software Foundation;
19 * see the file LICENSE.txt included in the packaging of this file
20 * for details.
21 *
22 * \par
23 * This program is distributed in the hope that it will be useful,
24 * but WITHOUT ANY WARRANTY; without even the implied warranty of
25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 * GNU General Public License for more details.
27 *
28 * \par
29 * You should have received a copy of the GNU General Public
30 * License along with this program; if not, see
31 * http://www.gnu.org/copyleft/gpl.html
32 */
33
34 #include <ogdf/planarity/EmbedderMaxFace.h>
35 #include <ogdf/planarity/embedder/ConnectedSubgraph.h>
36 #include <ogdf/planarity/embedder/EmbedderMaxFaceBiconnectedGraphs.h>
37
38 namespace ogdf {
39
doCall(Graph & G,adjEntry & adjExternal)40 void EmbedderMaxFace::doCall(Graph& G, adjEntry& adjExternal)
41 {
42 adjExternal = nullptr;
43 pAdjExternal = &adjExternal;
44 node rootBlockNode = initBCTree(G);
45
46 if(rootBlockNode == nullptr) {
47 return;
48 }
49
50 //First step: calculate maximum face and node lengths
51
52 //compute block graphs and SPQR trees:
53 blockG.init(pBCTree->bcTree());
54 nBlockEmbedding_to_nH.init(pBCTree->bcTree());
55 eBlockEmbedding_to_eH.init(pBCTree->bcTree());
56 nH_to_nBlockEmbedding.init(pBCTree->bcTree());
57 eH_to_eBlockEmbedding.init(pBCTree->bcTree());
58 nodeLength.init(pBCTree->bcTree());
59 cstrLength.init(pBCTree->bcTree());
60 spqrTrees.init(pBCTree->bcTree(),nullptr);
61 computeBlockGraphs(rootBlockNode, nullptr);
62
63 //Bottom-Up-Traversal:
64 for(adjEntry adj : rootBlockNode->adjEntries) {
65 edge e = adj->theEdge();
66 node cT = e->source();
67 node cH = pBCTree->cutVertex(cT, rootBlockNode);
68 node cB = nH_to_nBlockEmbedding[rootBlockNode][cH];
69
70 //set length of v in block graph of root block node:
71 int length_v_in_rootBlock = 0;
72 for(adjEntry adjCT : cT->adjEntries) {
73 edge e2 = adjCT->theEdge();
74 //check if edge is an incoming edge:
75 if (e2->target() != cT)
76 continue;
77
78 node blockNode = e2->source();
79 node cutVertex = pBCTree->cutVertex(cT, blockNode);
80 length_v_in_rootBlock += constraintMaxFace(blockNode, cutVertex);
81 }
82 nodeLength[rootBlockNode][cB] = length_v_in_rootBlock;
83 }
84
85 node bT_opt = G.chooseNode(); //= G.chooseNode() only to get rid of warning
86 int ell_opt = 0;
87 maximumFaceRec(rootBlockNode, bT_opt, ell_opt);
88
89
90 //Second step: Embed G by expanding a maximum face in bT_opt
91 newOrder.init(G);
92 treeNodeTreated.init(pBCTree->bcTree(), false);
93 embedBlock(bT_opt);
94
95 for(node v : G.nodes)
96 G.sort(v, newOrder[v]);
97
98 for(node v : pBCTree->bcTree().nodes)
99 delete spqrTrees[v];
100
101 delete pBCTree;
102 }
103
104
computeBlockGraphs(const node & bT,const node & cH)105 void EmbedderMaxFace::computeBlockGraphs(const node& bT, const node& cH)
106 {
107 //recursion:
108 for(adjEntry adj : bT->adjEntries) {
109 edge e = adj->theEdge();
110 if (e->source() == bT)
111 continue;
112
113 node cT = e->source();
114 for(adjEntry adjCT : cT->adjEntries) {
115 edge e2 = adjCT->theEdge();
116 if (e2->source() == cT)
117 continue;
118 node cH2 = pBCTree->cutVertex(cT, e2->source());
119 computeBlockGraphs(e2->source(), cH2);
120 }
121 }
122
123 //embed block bT:
124 node m_cH = cH;
125 if (m_cH == nullptr)
126 m_cH = pBCTree->cutVertex(bT->firstAdj()->twinNode(), bT);
127 embedder::ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockG[bT], m_cH,
128 nBlockEmbedding_to_nH[bT], eBlockEmbedding_to_eH[bT],
129 nH_to_nBlockEmbedding[bT], eH_to_eBlockEmbedding[bT]);
130 nodeLength[bT].init(blockG[bT], 0);
131 cstrLength[bT].init(blockG[bT], 0);
132 if ( !blockG[bT].empty()
133 && blockG[bT].numberOfNodes() != 1
134 && blockG[bT].numberOfEdges() > 2)
135 {
136 spqrTrees[bT] = new StaticSPQRTree(blockG[bT]);
137 }
138 }
139
140
constraintMaxFace(const node & bT,const node & cH)141 int EmbedderMaxFace::constraintMaxFace(const node& bT, const node& cH)
142 {
143 computeNodeLength(bT, [&](node vH) -> int& { return nodeLength[bT][nH_to_nBlockEmbedding[bT][vH]]; });
144
145 EdgeArray<int> edgeLength(blockG[bT], 1);
146 int cstrLengthBc = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(
147 blockG[bT],
148 nH_to_nBlockEmbedding[bT][cH],
149 nodeLength[bT],
150 edgeLength,
151 spqrTrees[bT]);
152 cstrLength[bT][nH_to_nBlockEmbedding[bT][cH]] = cstrLengthBc;
153 return cstrLengthBc;
154 }
155
156
maximumFaceRec(const node & bT,node & bT_opt,int & ell_opt)157 void EmbedderMaxFace::maximumFaceRec(const node& bT, node& bT_opt, int& ell_opt)
158 {
159 internalMaximumFaceRec(
160 bT, bT_opt, ell_opt,
161 blockG[bT],
162 nodeLength[bT],
163 spqrTrees[bT],
164 [&](node cH) -> node& { return nH_to_nBlockEmbedding[bT][cH]; },
165 [&](node v, node u) -> int& { return cstrLength[v][nH_to_nBlockEmbedding[v][u]]; },
166 [&](node v, node u) -> int& { return nodeLength[v][nH_to_nBlockEmbedding[v][u]]; });
167 }
168
169
embedBlock(const node & bT)170 void EmbedderMaxFace::embedBlock(const node& bT)
171 {
172 ListIterator<adjEntry> after;
173 node cT = nullptr;
174 embedBlock(bT, cT, after);
175 }
176
177
embedBlock(const node & bT,const node & cT,ListIterator<adjEntry> & after)178 void EmbedderMaxFace::embedBlock(
179 const node& bT,
180 const node& cT,
181 ListIterator<adjEntry>& after)
182 {
183 treeNodeTreated[bT] = true;
184 node cH = nullptr;
185 if (cT != nullptr)
186 cH = pBCTree->cutVertex(cT, bT);
187
188 EdgeArray<int> edgeLength(blockG[bT], 1);
189 internalEmbedBlock(bT, cT, after, blockG[bT], nodeLength[bT], edgeLength, nBlockEmbedding_to_nH[bT], eBlockEmbedding_to_eH[bT], cH == nullptr ? nullptr : nH_to_nBlockEmbedding[bT][cH]);
190 }
191
192 }
193