00001
00002
00003
00004
00005
00006
00007
00008
00042 #ifdef _MSC_VER
00043 #pragma once
00044 #endif
00045
00046 #ifndef OGDF_CONNECTED_SUBGRAPH_h
00047 #define OGDF_CONNECTED_SUBGRAPH_h
00048
00049 #include <ogdf/basic/NodeArray.h>
00050 #include <ogdf/basic/EdgeArray.h>
00051
00052 namespace ogdf {
00053
00054 template<class T>
00055 class ConnectedSubgraph
00056 {
00057 public:
00058
00059 ConnectedSubgraph() { }
00060
00070 static void call(const Graph& G,
00071 Graph& SG,
00072 const node& nG,
00073 node& nSG,
00074 const NodeArray<T>& nodeLengthG,
00075 NodeArray<T>& nodeLengthSG)
00076 {
00077 EdgeArray<T> edgeLengthG(G, 1);
00078 EdgeArray<T> edgeLengthSG;
00079 call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
00080 }
00081
00091 static void call(const Graph& G,
00092 Graph& SG,
00093 const node& nG,
00094 const NodeArray<T>& nodeLengthG,
00095 NodeArray<T>& nodeLengthSG,
00096 NodeArray<node>& nG_to_nSG)
00097 {
00098 node nSG;
00099 NodeArray<node> nSG_to_nG;
00100 EdgeArray<edge> eSG_to_eG;
00101 EdgeArray<edge> eG_to_eSG;
00102 EdgeArray<T> edgeLengthG(G, 1);
00103 EdgeArray<T> edgeLengthSG;
00104 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG,
00105 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
00106 }
00107
00119 static void call(const Graph& G,
00120 Graph& SG,
00121 const node& nG,
00122 node& nSG,
00123 const NodeArray<T>& nodeLengthG,
00124 NodeArray<T>& nodeLengthSG,
00125 const EdgeArray<T>& edgeLengthG,
00126 EdgeArray<T>& edgeLengthSG)
00127 {
00128 NodeArray<node> nSG_to_nG(SG);
00129 EdgeArray<edge> eSG_to_eG(SG);
00130 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nodeLengthG,
00131 nodeLengthSG, edgeLengthG, edgeLengthSG);
00132 }
00133
00142 static void call(const Graph& G,
00143 Graph& SG,
00144 const node& nG,
00145 const NodeArray<T>& nodeLengthG,
00146 NodeArray<T>& nodeLengthSG)
00147 {
00148 node nSG;
00149 call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG);
00150 }
00151
00162 static void call(const Graph& G,
00163 Graph& SG,
00164 const node& nG,
00165 const NodeArray<T>& nodeLengthG,
00166 NodeArray<T>& nodeLengthSG,
00167 const EdgeArray<T>& edgeLengthG,
00168 EdgeArray<T>& edgeLengthSG)
00169 {
00170 node nSG = 0;
00171 call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
00172 }
00173
00187 static void call(const Graph& G,
00188 Graph& SG,
00189 const node& nG,
00190 node& nSG,
00191 NodeArray<node>& nSG_to_nG,
00192 EdgeArray<edge>& eSG_to_eG,
00193 const NodeArray<T>& nodeLengthG,
00194 NodeArray<T>& nodeLengthSG,
00195 const EdgeArray<T>& edgeLengthG,
00196 EdgeArray<T>& edgeLengthSG)
00197 {
00198 NodeArray<node> nG_to_nSG;
00199 EdgeArray<edge> eG_to_eSG;
00200 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG, nodeLengthG,
00201 nodeLengthSG, edgeLengthG, edgeLengthSG);
00202 }
00203
00219 static void call(const Graph& G,
00220 Graph& SG,
00221 const node& nG,
00222 node& nSG,
00223 NodeArray<node>& nSG_to_nG,
00224 EdgeArray<edge>& eSG_to_eG,
00225 NodeArray<node>& nG_to_nSG,
00226 EdgeArray<edge>& eG_to_eSG,
00227 const NodeArray<T>& nodeLengthG,
00228 NodeArray<T>& nodeLengthSG,
00229 const EdgeArray<T>& edgeLengthG,
00230 EdgeArray<T>& edgeLengthSG);
00231
00242 static void call(const Graph& G,
00243 Graph& SG,
00244 const node& nG,
00245 NodeArray<node>& nSG_to_nG,
00246 EdgeArray<edge>& eSG_to_eG,
00247 NodeArray<node>& nG_to_nSG,
00248 EdgeArray<edge>& eG_to_eSG);
00249
00257 static void call(const Graph& G,
00258 Graph& SG,
00259 const node& nG,
00260 NodeArray<node>& nSG_to_nG)
00261 {
00262 NodeArray<T> nodeLengthG(G, 0);
00263 NodeArray<T> nodeLengthSG(SG);
00264 EdgeArray<T> edgeLengthG(G, 0);
00265 EdgeArray<T> edgeLengthSG(SG);
00266 node nSG;
00267 EdgeArray<edge> eSG_to_eG;
00268 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
00269 }
00270
00271 private:
00291 static void recursion(Graph& SG,
00292 bool* nodeVisited,
00293 bool* edgeVisited,
00294 const node& nG,
00295 const NodeArray<T>& nodeLengthG,
00296 NodeArray<T>& nodeLengthSG,
00297 const EdgeArray<T>& edgeLengthG,
00298 EdgeArray<T>& edgeLengthSG,
00299 NodeArray<node>& nSG_to_nG,
00300 EdgeArray<edge>& eSG_to_eG,
00301 NodeArray<node>& nG_to_nSG,
00302 EdgeArray<edge>& eG_to_eSG);
00303 };
00304
00305
00306 template<class T>
00307 void ConnectedSubgraph<T>::recursion(Graph& SG,
00308 bool* nodeVisited,
00309 bool* edgeVisited,
00310 const node& nG,
00311 const NodeArray<T>& nodeLengthG,
00312 NodeArray<T>& nodeLengthSG,
00313 const EdgeArray<T>& edgeLengthG,
00314 EdgeArray<T>& edgeLengthSG,
00315 NodeArray<node>& nSG_to_nG,
00316 EdgeArray<edge>& eSG_to_eG,
00317 NodeArray<node>& nG_to_nSG,
00318 EdgeArray<edge>& eG_to_eSG)
00319 {
00320 node nSG = SG.newNode();
00321 nodeLengthSG[nSG] = nodeLengthG[nG];
00322 nG_to_nSG[nG] = nSG;
00323 nSG_to_nG[nSG] = nG;
00324 nodeVisited[nG->index()] = true;
00325
00326 edge eG;
00327 forall_adj_edges(eG, nG)
00328 {
00329 if (!nodeVisited[eG->source()->index()])
00330 recursion(SG, nodeVisited, edgeVisited, eG->source(),
00331 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
00332 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
00333 else if (!nodeVisited[eG->target()->index()])
00334 recursion(SG, nodeVisited, edgeVisited, eG->target(),
00335 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
00336 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
00337 if (!edgeVisited[eG->index()])
00338 {
00339 edge eSG = SG.newEdge(nG_to_nSG[eG->source()], nG_to_nSG[eG->target()]);
00340 edgeLengthSG[eSG] = edgeLengthG[eG];
00341 eG_to_eSG[eG] = eSG;
00342 eSG_to_eG[eSG] = eG;
00343 edgeVisited[eG->index()] = true;
00344 }
00345 }
00346 }
00347
00348
00349 template<class T>
00350 void ConnectedSubgraph<T>::call(const Graph& G,
00351 Graph& SG,
00352 const node& nG,
00353 node& nSG,
00354 NodeArray<node>& nSG_to_nG,
00355 EdgeArray<edge>& eSG_to_eG,
00356 NodeArray<node>& nG_to_nSG,
00357 EdgeArray<edge>& eG_to_eSG,
00358 const NodeArray<T>& nodeLengthG,
00359 NodeArray<T>& nodeLengthSG,
00360 const EdgeArray<T>& edgeLengthG,
00361 EdgeArray<T>& edgeLengthSG)
00362 {
00363 SG.clear();
00364 bool* nodeVisited = new bool[G.numberOfNodes()];
00365 bool* edgeVisited = new bool[G.numberOfEdges()];
00366 for (int i = 0; i < G.numberOfNodes(); i++)
00367 nodeVisited[i] = false;
00368 for (int i = 0; i < G.numberOfEdges(); i++)
00369 edgeVisited[i] = false;
00370 nSG_to_nG.init(SG);
00371 eSG_to_eG.init(SG);
00372 nodeLengthSG.init(SG);
00373 edgeLengthSG.init(SG);
00374 nG_to_nSG.init(G);
00375 eG_to_eSG.init(G);
00376
00377 recursion(SG, nodeVisited, edgeVisited, nG,
00378 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
00379 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
00380 nSG = nG_to_nSG[nG];
00381
00382 delete nodeVisited;
00383 delete edgeVisited;
00384 }
00385
00386
00387 template<class T>
00388 void ConnectedSubgraph<T>::call(const Graph& G,
00389 Graph& SG,
00390 const node& nG,
00391 NodeArray<node>& nSG_to_nG,
00392 EdgeArray<edge>& eSG_to_eG,
00393 NodeArray<node>& nG_to_nSG,
00394 EdgeArray<edge>& eG_to_eSG)
00395 {
00396 SG.clear();
00397 bool* nodeVisited = new bool[G.numberOfNodes()];
00398 bool* edgeVisited = new bool[G.numberOfEdges()];
00399 for (int i = 0; i < G.numberOfNodes(); i++)
00400 nodeVisited[i] = false;
00401 for (int i = 0; i < G.numberOfEdges(); i++)
00402 edgeVisited[i] = false;
00403 nSG_to_nG.init(SG);
00404 eSG_to_eG.init(SG);
00405 NodeArray<T> nodeLengthG(G, 0);
00406 NodeArray<T> nodeLengthSG(SG);
00407 EdgeArray<T> edgeLengthG(G, 1);
00408 EdgeArray<T> edgeLengthSG(SG);
00409 nG_to_nSG.init(G);
00410 eG_to_eSG.init(G);
00411
00412 recursion(SG, nodeVisited, edgeVisited, nG,
00413 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
00414 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
00415
00416 delete nodeVisited;
00417 delete edgeVisited;
00418 }
00419
00420
00421 }
00422
00423 #endif
