1 /** \file
2 * \brief Implementation of class BCTree
3 *
4 * \author Jan Papenfuß
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
33 #include <ogdf/decomposition/BCTree.h>
34
35
36 namespace ogdf {
37
initBasic(node vG)38 void BCTree::initBasic(node vG)
39 {
40 m_numB = 0;
41 m_numC = 0;
42
43 m_gNode_isMarked.init(m_G, false);
44 m_gNode_hNode.init(m_G, nullptr);
45 m_gEdge_hEdge.init(m_G);
46
47 m_bNode_type.init(m_B);
48 m_bNode_isMarked.init(m_B, false);
49 m_bNode_hRefNode.init(m_B);
50 m_bNode_hParNode.init(m_B);
51 m_bNode_hEdges.init(m_B);
52 m_bNode_numNodes.init(m_B);
53
54 m_hNode_bNode.init(m_H);
55 m_hEdge_bNode.init(m_H);
56 m_hNode_gNode.init(m_H);
57 m_hEdge_gEdge.init(m_H);
58
59 m_count = 0;
60 m_number.init(m_G, 0);
61 m_lowpt.init(m_G);
62 m_gtoh.init(m_G);
63
64 biComp(nullptr, vG);
65 }
66
initEdges()67 void BCTree::initEdges()
68 {
69 // first clear temporaries
70 m_number.init();
71 m_lowpt.init();
72 m_eStack.clear();
73 m_gtoh.init();
74
75 // now add edges
76 for (node uB : m_B.nodes) {
77 node vB = parent(uB);
78 if (vB) {
79 m_B.newEdge(uB, vB);
80 }
81 }
82 }
83
init(node vG)84 void BCTree::init (node vG)
85 {
86 initBasic(vG);
87 initEdges();
88 }
89
90
initNotConnected(node vG)91 void BCTree::initNotConnected (node vG)
92 {
93 initBasic(vG);
94
95 // call biComp for all nodes that are not in the
96 // first connected component
97 for (node v : m_G.nodes) {
98 if (m_number[v] == 0) {
99 m_eStack.clear();
100 biComp(nullptr, v);
101 }
102 }
103
104 initEdges();
105 }
106
107
biComp(adjEntry adjuG,node vG)108 void BCTree::biComp (adjEntry adjuG, node vG)
109 {
110 m_lowpt[vG] = m_number[vG] = ++m_count;
111
112 for(adjEntry adj : vG->adjEntries) {
113 #if 0
114 edge eG = adj->theEdge();
115 #endif
116 node wG = adj->twinNode();
117 if ((adjuG != nullptr) && (adj == adjuG->twin())) continue;
118 if (m_number[wG]==0) {
119 m_eStack.push(adj);
120 biComp(adj,wG);
121 if (m_lowpt[wG]<m_lowpt[vG]) m_lowpt[vG] = m_lowpt[wG];
122 if (m_lowpt[wG]>=m_number[vG]) {
123 node bB = m_B.newNode();
124 m_bNode_type[bB] = BNodeType::BComp;
125 m_bNode_isMarked[bB] = false;
126 m_bNode_hRefNode[bB] = nullptr;
127 m_bNode_hParNode[bB] = nullptr;
128 m_bNode_numNodes[bB] = 0;
129 m_numB++;
130 adjEntry adjfG;
131 do {
132 adjfG = m_eStack.popRet();
133 edge fG = adjfG->theEdge();
134 for (int i=0; i<=1; ++i) {
135 node xG = i ? fG->target() : fG->source();
136 if (m_gNode_isMarked[xG]) continue;
137 m_gNode_isMarked[xG] = true;
138 m_nodes.pushBack(xG);
139 m_bNode_numNodes[bB]++;
140 node zH = m_H.newNode();
141 m_hNode_bNode[zH] = bB;
142 m_hNode_gNode[zH] = xG;
143 m_gtoh[xG] = zH;
144 node xH = m_gNode_hNode[xG];
145 if (!xH) m_gNode_hNode[xG] = zH;
146 else {
147 node xB = m_hNode_bNode[xH];
148 if (!m_bNode_hRefNode[xB]) {
149 node cB = m_B.newNode();
150 node yH = m_H.newNode();
151 m_hNode_bNode[yH] = cB;
152 m_hNode_gNode[yH] = xG;
153 m_gNode_hNode[xG] = yH;
154 m_bNode_type[cB] = BNodeType::CComp;
155 m_bNode_isMarked[cB] = false;
156 m_bNode_hRefNode[xB] = xH;
157 m_bNode_hParNode[xB] = yH;
158 m_bNode_hRefNode[cB] = yH;
159 m_bNode_hParNode[cB] = zH;
160 m_bNode_numNodes[cB] = 1;
161 m_numC++;
162 }
163 else {
164 node yH = m_bNode_hParNode[xB];
165 node yB = m_hNode_bNode[yH];
166 m_bNode_hParNode[yB] = xH;
167 m_bNode_hRefNode[yB] = yH;
168 m_bNode_hParNode[xB] = zH;
169 }
170 }
171 }
172 edge fH = m_H.newEdge(m_gtoh[fG->source()],m_gtoh[fG->target()]);
173 m_bNode_hEdges[bB].pushBack(fH);
174 m_hEdge_bNode[fH] = bB;
175 m_hEdge_gEdge[fH] = fG;
176 m_gEdge_hEdge[fG] = fH;
177 } while (adj!=adjfG);
178 while (!m_nodes.empty()) m_gNode_isMarked[m_nodes.popFrontRet()] = false;
179 }
180 }
181 else if (m_number[wG]<m_number[vG]) {
182 m_eStack.push(adj);
183 if (m_number[wG]<m_lowpt[vG]) m_lowpt[vG] = m_number[wG];
184 }
185 }
186 }
187
188
parent(node vB) const189 node BCTree::parent (node vB) const
190 {
191 if (!vB) return nullptr;
192 node vH = m_bNode_hParNode[vB];
193 if (!vH) return nullptr;
194 return m_hNode_bNode[vH];
195 }
196
197
bComponent(node uG,node vG) const198 node BCTree::bComponent (node uG, node vG) const
199 {
200 node uB = bcproper(uG);
201 node vB = bcproper(vG);
202 if (uB==vB) return uB;
203 if (typeOfBNode(uB)==BNodeType::BComp) {
204 if (typeOfBNode(vB)==BNodeType::BComp) return nullptr;
205 if (parent(uB)==vB) return uB;
206 if (parent(vB)==uB) return uB;
207 return nullptr;
208 }
209 if (typeOfBNode(vB)==BNodeType::BComp) {
210 if (parent(uB)==vB) return vB;
211 if (parent(vB)==uB) return vB;
212 return nullptr;
213 }
214 node pB = parent(uB);
215 node qB = parent(vB);
216 if (pB==qB) return pB;
217 if (parent(pB)==vB) return pB;
218 if (parent(qB)==uB) return qB;
219 return nullptr;
220 }
221
222
findNCA(node uB,node vB) const223 node BCTree::findNCA (node uB, node vB) const
224 {
225 if (m_bNode_isMarked[uB]) return uB;
226 m_bNode_isMarked[uB] = true;
227 node wB = parent(uB);
228 if (wB) wB = findNCA(vB,wB);
229 else for (wB=vB; !m_bNode_isMarked[wB]; wB=parent(wB));
230 m_bNode_isMarked[uB] = false;
231 return wB;
232 }
233
234
findPath(node sG,node tG) const235 SList<node>& BCTree::findPath (node sG, node tG) const
236 {
237 SList<node>& pB = *new SList<node>;
238 node sB = bcproper(sG);
239 node tB = bcproper(tG);
240 node nB = findNCA(sB,tB);
241 for (pB.pushBack(sB); sB!=nB; pB.pushBack(sB)) sB = parent(sB);
242 for (SListIterator<node> iB=pB.backIterator(); tB!=nB; tB=parent(tB)) pB.insertAfter(tB,iB);
243 return pB;
244 }
245
246
findPathBCTree(node sB,node tB) const247 SList<node>* BCTree::findPathBCTree (node sB, node tB) const
248 {
249 SList<node> *pB = new SList<node>;
250 node nB = findNCA(sB,tB);
251 for (pB->pushBack(sB); sB!=nB; pB->pushBack(sB)) sB = parent(sB);
252 for (SListIterator<node> iB=pB->backIterator(); tB!=nB; tB=parent(tB)) pB->insertAfter(tB,iB);
253 return pB;
254 }
255
256
repVertex(node uG,node vB) const257 node BCTree::repVertex (node uG, node vB) const
258 {
259 node uB = bcproper(uG);
260 if (uB==vB) return m_gNode_hNode[uG];
261 if (typeOfBNode(uB)==BNodeType::BComp) return nullptr;
262 if (parent(uB)==vB) return m_bNode_hParNode[uB];
263 if (uB==parent(vB)) return m_bNode_hRefNode[vB];
264 return nullptr;
265 }
266
cutVertex(node uB,node vB) const267 node BCTree::cutVertex (node uB, node vB) const
268 {
269 if (uB==vB) return typeOfBNode(uB)==BNodeType::CComp ? m_bNode_hRefNode[vB] : nullptr;
270 if (parent(uB)==vB) return m_bNode_hParNode[uB];
271 if (uB==parent(vB)) return m_bNode_hRefNode[vB];
272 return nullptr;
273 }
274
275
276 }
277