ext/OGDF/ogdf/internal/planarity/ConnectedSubgraph.h

   1 /*
   2  * $Revision: 2589 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-12 23:31:45 +0200 (Do, 12. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Computes a connected subgraph G' of G containing node n.
  11  *
  12  * \author Thorsten Kerkhof
  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 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47 #ifndef OGDF_CONNECTED_SUBGRAPH_h
  48 #define OGDF_CONNECTED_SUBGRAPH_h
  49
  50 #include <ogdf/basic/NodeArray.h>
  51 #include <ogdf/basic/EdgeArray.h>
  52
  53 namespace ogdf {
  54
  55 template<class T>
  56 class ConnectedSubgraph
  57 {
  58 public:
  59         //constructor
  60         ConnectedSubgraph() { }
  61
  62         /**
  63          * \brief Computes a connected subgraph SG of G containing node nG.
  64          * \param G is the original graph.
  65          * \param SG is assigned the connected subgraph containing nG.
  66          * \param nG is a node in G.
  67          * \param nSG is assigned the corresponding node of nG in SG.
  68          * \param nodeLengthG stores for each node of G its length.
  69          * \param nodeLengthSG is assigned for each node of SG its length.
  70          */
  71         static void call(const Graph& G,
  72                 Graph& SG,
  73                 const node& nG,
  74                 node& nSG,
  75                 const NodeArray<T>& nodeLengthG,
  76                 NodeArray<T>& nodeLengthSG)
  77         {
  78                 EdgeArray<T> edgeLengthG(G, 1);
  79                 EdgeArray<T> edgeLengthSG;
  80                 call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
  81         }
  82
  83         /**
  84          * \brief Computes a connected subgraph SG of G containing node nG.
  85          * \param G is the original graph.
  86          * \param SG is assigned the connected subgraph containing nG.
  87          * \param nG is a node in G.
  88          * \param nodeLengthG stores for each node of G its length.
  89          * \param nodeLengthSG is assigned for each node of SG its length.
  90          * \param nG_to_nSG is assigned a mapping of nodes in G to nodes in SG.
  91          */
  92         static void call(const Graph& G,
  93                 Graph& SG,
  94                 const node& nG,
  95                 const NodeArray<T>& nodeLengthG,
  96                 NodeArray<T>& nodeLengthSG,
  97                 NodeArray<node>& nG_to_nSG)
  98         {
  99                 node nSG;
 100                 NodeArray<node> nSG_to_nG;
 101                 EdgeArray<edge> eSG_to_eG;
 102                 EdgeArray<edge> eG_to_eSG;
 103                 EdgeArray<T> edgeLengthG(G, 1);
 104                 EdgeArray<T> edgeLengthSG;
 105                 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG,
 106                         nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
 107         }
 108
 109         /**
 110          * \brief Computes a connected subgraph SG of G containing node nG.
 111          * \param G is the original graph.
 112          * \param SG is assigned the connected subgraph containing nG.
 113          * \param nG is a node in G.
 114          * \param nSG is assigned the corresponding node of nG in SG.
 115          * \param nodeLengthG is saving for each node of G its length.
 116          * \param nodeLengthSG is assigned for each node of SG its length.
 117          * \param edgeLengthG is saving for each edge of G its length.
 118          * \param edgeLengthSG is assigned for each edge of SG its length.
 119          */
 120         static void call(const Graph& G,
 121                 Graph& SG,
 122                 const node& nG,
 123                 node& nSG,
 124                 const NodeArray<T>& nodeLengthG,
 125                 NodeArray<T>& nodeLengthSG,
 126                 const EdgeArray<T>& edgeLengthG,
 127                 EdgeArray<T>& edgeLengthSG)
 128         {
 129                 NodeArray<node> nSG_to_nG(SG);
 130                 EdgeArray<edge> eSG_to_eG(SG);
 131                 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nodeLengthG,
 132                         nodeLengthSG, edgeLengthG, edgeLengthSG);
 133         }
 134
 135         /**
 136          * \brief Computes a connected subgraph SG of G containing node nG.
 137          * \param G is the original graph.
 138          * \param SG is assigned the connected subgraph containing nG.
 139          * \param nG is a node in G.
 140          * \param nodeLengthG stores for each node of G its length.
 141          * \param nodeLengthSG is assigned for each node of SG its length.
 142          */
 143         static void call(const Graph& G,
 144                 Graph& SG,
 145                 const node& nG,
 146                 const NodeArray<T>& nodeLengthG,
 147                 NodeArray<T>& nodeLengthSG)
 148         {
 149                 node nSG;
 150                 call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG);
 151         }
 152
 153         /**
 154          * \brief Computes a connected subgraph SG of G containing node nG.
 155          * \param G is the original graph.
 156          * \param SG is assigned the connected subgraph containing nG.
 157          * \param nG is a node in G.
 158          * \param nodeLengthG stores for each node of G its length.
 159          * \param nodeLengthSG is assigned for each node of SG its length.
 160          * \param edgeLengthG stores for each edge of G its length.
 161          * \param edgeLengthSG is assigned for each edge of SG its length.
 162          */
 163         static void call(const Graph& G,
 164                 Graph& SG,
 165                 const node& nG,
 166                 const NodeArray<T>& nodeLengthG,
 167                 NodeArray<T>& nodeLengthSG,
 168                 const EdgeArray<T>& edgeLengthG,
 169                 EdgeArray<T>& edgeLengthSG)
 170         {
 171                 node nSG = 0;
 172                 call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
 173         }
 174
 175         /**
 176          * \brief Computes a connected subgraph SG of G containing node nG.
 177          * \param G is the original graph.
 178          * \param SG is assigned the connected subgraph containing nG.
 179          * \param nG is a node in G.
 180          * \param nSG
 181          * \param nSG_to_nG is mapping nodes in SG to nodes in G
 182          * \param eSG_to_eG is mapping edges in SG to edges in G
 183          * \param nodeLengthG is saving for each node of G its length.
 184          * \param nodeLengthSG is assigned for each node of SG its length.
 185          * \param edgeLengthG stores for each edge of G its length.
 186          * \param edgeLengthSG is assigned for each edge of SG its length.
 187          */
 188         static void call(const Graph& G,
 189                 Graph& SG,
 190                 const node& nG,
 191                 node& nSG,
 192                 NodeArray<node>& nSG_to_nG,
 193                 EdgeArray<edge>& eSG_to_eG,
 194                 const NodeArray<T>& nodeLengthG,
 195                 NodeArray<T>& nodeLengthSG,
 196                 const EdgeArray<T>& edgeLengthG,
 197                 EdgeArray<T>& edgeLengthSG)
 198         {
 199                 NodeArray<node> nG_to_nSG;
 200                 EdgeArray<edge> eG_to_eSG;
 201                 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG, nodeLengthG,
 202                         nodeLengthSG, edgeLengthG, edgeLengthSG);
 203         }
 204
 205         /**
 206          * \brief Computes a connected subgraph SG of G containing node nG.
 207          * \param G is the original graph.
 208          * \param SG is assigned the connected subgraph containing nG.
 209          * \param nG is a node in G.
 210          * \param nSG
 211          * \param nSG_to_nG is mapping nodes in SG to nodes in G
 212          * \param eSG_to_eG is mapping edges in SG to edges in G
 213          * \param nG_to_nSG is mapping nodes in G to nodes in SG
 214          * \param eG_to_eSG is mapping edges in G to edges in SG
 215          * \param nodeLengthG stores for each node of G its length.
 216          * \param nodeLengthSG is assigned for each node of SG its length.
 217          * \param edgeLengthG stores for each edge of G its length.
 218          * \param edgeLengthSG is assigned for each edge of SG its length.
 219          */
 220         static void call(const Graph& G,
 221                 Graph& SG,
 222                 const node& nG,
 223                 node& nSG,
 224                 NodeArray<node>& nSG_to_nG,
 225                 EdgeArray<edge>& eSG_to_eG,
 226                 NodeArray<node>& nG_to_nSG,
 227                 EdgeArray<edge>& eG_to_eSG,
 228                 const NodeArray<T>& nodeLengthG,
 229                 NodeArray<T>& nodeLengthSG,
 230                 const EdgeArray<T>& edgeLengthG,
 231                 EdgeArray<T>& edgeLengthSG);
 232
 233         /**
 234          * \brief Computes a connected subgraph SG of G containing node nG.
 235          * \param G is the original graph.
 236          * \param SG is assigned the connected subgraph containing nG.
 237          * \param nG is a node in G.
 238          * \param nSG_to_nG is mapping nodes in SG to nodes in G
 239          * \param eSG_to_eG is mapping edges in SG to edges in G
 240          * \param nG_to_nSG is mapping nodes in G to nodes in SG
 241          * \param eG_to_eSG is mapping edges in G to edges in SG
 242          */
 243         static void call(const Graph& G,
 244                 Graph& SG,
 245                 const node& nG,
 246                 NodeArray<node>& nSG_to_nG,
 247                 EdgeArray<edge>& eSG_to_eG,
 248                 NodeArray<node>& nG_to_nSG,
 249                 EdgeArray<edge>& eG_to_eSG);
 250
 251         /**
 252          * \brief Computes a connected subgraph SG of G containing node nG.
 253          * \param G is the original graph.
 254          * \param SG is assigned the connected subgraph containing nG.
 255          * \param nG is a node in G.
 256          * \param nSG_to_nG is mapping nodes in SG to nodes in G
 257          */
 258         static void call(const Graph& G,
 259                 Graph& SG,
 260                 const node& nG,
 261                 NodeArray<node>& nSG_to_nG)
 262         {
 263                 NodeArray<T> nodeLengthG(G, 0);
 264                 NodeArray<T> nodeLengthSG(SG);
 265                 EdgeArray<T> edgeLengthG(G, 0);
 266                 EdgeArray<T> edgeLengthSG(SG);
 267                 node nSG;
 268                 EdgeArray<edge> eSG_to_eG;
 269                 call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);
 270         }
 271
 272 private:
 273         /**
 274          * \brief Copies to SG node nG and recursively all adjacent edges
 275          *  and nodes.
 276          *
 277          * \param SG is the connected subgraph.
 278          * \param nodeVisited saves for all nodes in G, if they were already
 279          *    treated.
 280          * \param edgeVisited saves for all edges in G, if they were already
 281          *    treated.
 282          * \param nG is a node in G.
 283          * \param nodeLengthG is saving for each node of G its length.
 284          * \param nodeLengthSG is saving for each node of SG its length.
 285          * \param edgeLengthG is saving for each edge of G its length.
 286          * \param edgeLengthSG is saving for each edge of SG its length.
 287          * \param nSG_to_nG is mapping nodes in SG to nodes in G
 288          * \param eSG_to_eG is mapping edges in SG to edges in G
 289          * \param nG_to_nSG is mapping nodes in G to nodes in SG
 290          * \param eG_to_eSG is mapping edges in G to edges in SG
 291          */
 292         static void recursion(Graph& SG,
 293                 bool* nodeVisited,
 294                 bool* edgeVisited,
 295                 const node& nG,
 296                 const NodeArray<T>& nodeLengthG,
 297                 NodeArray<T>& nodeLengthSG,
 298                 const EdgeArray<T>& edgeLengthG,
 299                 EdgeArray<T>& edgeLengthSG,
 300                 NodeArray<node>& nSG_to_nG,
 301                 EdgeArray<edge>& eSG_to_eG,
 302                 NodeArray<node>& nG_to_nSG,
 303                 EdgeArray<edge>& eG_to_eSG);
 304 };
 305
 306
 307 template<class T>
 308 void ConnectedSubgraph<T>::recursion(Graph& SG,
 309          bool* nodeVisited,
 310          bool* edgeVisited,
 311          const node& nG,
 312          const NodeArray<T>& nodeLengthG,
 313          NodeArray<T>& nodeLengthSG,
 314          const EdgeArray<T>& edgeLengthG,
 315          EdgeArray<T>& edgeLengthSG,
 316          NodeArray<node>& nSG_to_nG,
 317          EdgeArray<edge>& eSG_to_eG,
 318          NodeArray<node>& nG_to_nSG,
 319          EdgeArray<edge>& eG_to_eSG)
 320 {
 321         node nSG = SG.newNode();
 322         nodeLengthSG[nSG] = nodeLengthG[nG];
 323         nG_to_nSG[nG] = nSG;
 324         nSG_to_nG[nSG] = nG;
 325         nodeVisited[nG->index()] = true;
 326
 327         edge eG;
 328         forall_adj_edges(eG, nG)
 329         {
 330                 if (!nodeVisited[eG->source()->index()])
 331                         recursion(SG, nodeVisited, edgeVisited, eG->source(),
 332                                 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
 333                                 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
 334                 else if (!nodeVisited[eG->target()->index()])
 335                         recursion(SG, nodeVisited, edgeVisited, eG->target(),
 336                                 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
 337                                 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
 338                 if (!edgeVisited[eG->index()])
 339                 {
 340                         edge eSG = SG.newEdge(nG_to_nSG[eG->source()], nG_to_nSG[eG->target()]);
 341                         edgeLengthSG[eSG] = edgeLengthG[eG];
 342                         eG_to_eSG[eG] = eSG;
 343                         eSG_to_eG[eSG] = eG;
 344                         edgeVisited[eG->index()] = true;
 345                 }
 346         }
 347 }
 348
 349
 350 template<class T>
 351 void ConnectedSubgraph<T>::call(const Graph& G,
 352         Graph& SG,
 353         const node& nG,
 354         node& nSG,
 355         NodeArray<node>& nSG_to_nG,
 356         EdgeArray<edge>& eSG_to_eG,
 357         NodeArray<node>& nG_to_nSG,
 358         EdgeArray<edge>& eG_to_eSG,
 359         const NodeArray<T>& nodeLengthG,
 360         NodeArray<T>& nodeLengthSG,
 361         const EdgeArray<T>& edgeLengthG,
 362         EdgeArray<T>& edgeLengthSG)
 363 {
 364         SG.clear();
 365         bool* nodeVisited = new bool[G.numberOfNodes()];
 366         bool* edgeVisited = new bool[G.numberOfEdges()];
 367         for (int i = 0; i < G.numberOfNodes(); i++)
 368                 nodeVisited[i] = false;
 369         for (int i = 0; i < G.numberOfEdges(); i++)
 370                 edgeVisited[i] = false;
 371         nSG_to_nG.init(SG);
 372         eSG_to_eG.init(SG);
 373         nodeLengthSG.init(SG);
 374         edgeLengthSG.init(SG);
 375         nG_to_nSG.init(G);
 376         eG_to_eSG.init(G);
 377
 378         recursion(SG, nodeVisited, edgeVisited, nG,
 379                 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
 380                 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
 381         nSG = nG_to_nSG[nG];
 382
 383         delete nodeVisited;
 384         delete edgeVisited;
 385 }
 386
 387
 388 template<class T>
 389 void ConnectedSubgraph<T>::call(const Graph& G,
 390         Graph& SG,
 391         const node& nG,
 392         NodeArray<node>& nSG_to_nG,
 393         EdgeArray<edge>& eSG_to_eG,
 394         NodeArray<node>& nG_to_nSG,
 395         EdgeArray<edge>& eG_to_eSG)
 396 {
 397         SG.clear();
 398         bool* nodeVisited = new bool[G.numberOfNodes()];
 399         bool* edgeVisited = new bool[G.numberOfEdges()];
 400         for (int i = 0; i < G.numberOfNodes(); i++)
 401                 nodeVisited[i] = false;
 402         for (int i = 0; i < G.numberOfEdges(); i++)
 403                 edgeVisited[i] = false;
 404         nSG_to_nG.init(SG);
 405         eSG_to_eG.init(SG);
 406         NodeArray<T> nodeLengthG(G, 0);
 407         NodeArray<T> nodeLengthSG(SG);
 408         EdgeArray<T> edgeLengthG(G, 1);
 409         EdgeArray<T> edgeLengthSG(SG);
 410         nG_to_nSG.init(G);
 411         eG_to_eSG.init(G);
 412
 413         recursion(SG, nodeVisited, edgeVisited, nG,
 414                 nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG,
 415                 nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);
 416
 417         delete nodeVisited;
 418         delete edgeVisited;
 419 }
 420
 421
 422 } // end namespace ogdf
 423
 424 #endif