ext/OGDF/ogdf/upward/ExpansionGraph.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declares class ExpansionGraph...
  11  *
  12  * ...which represents the expansion graph of each biconnected
  13  * component of a given digraph.
  14  *
  15  * \author Carsten Gutwenger
  16  *
  17  * \par License:
  18  * This file is part of the Open Graph Drawing Framework (OGDF).
  19  *
  20  * \par
  21  * Copyright (C)<br>
  22  * See README.txt in the root directory of the OGDF installation for details.
  23  *
  24  * \par
  25  * This program is free software; you can redistribute it and/or
  26  * modify it under the terms of the GNU General Public License
  27  * Version 2 or 3 as published by the Free Software Foundation;
  28  * see the file LICENSE.txt included in the packaging of this file
  29  * for details.
  30  *
  31  * \par
  32  * This program is distributed in the hope that it will be useful,
  33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35  * GNU General Public License for more details.
  36  *
  37  * \par
  38  * You should have received a copy of the GNU General Public
  39  * License along with this program; if not, write to the Free
  40  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  41  * Boston, MA 02110-1301, USA.
  42  *
  43  * \see  http://www.gnu.org/copyleft/gpl.html
  44  ***************************************************************/
  45
  46 #ifdef _MSC_VER
  47 #pragma once
  48 #endif
  49
  50
  51 #ifndef OGDF_EXPANSION_GRAPH_H
  52 #define OGDF_EXPANSION_GRAPH_H
  53
  54
  55 #include <ogdf/basic/EdgeArray.h>
  56 #include <ogdf/basic/NodeArray.h>
  57 #include <ogdf/basic/SList.h>
  58
  59
  60 namespace ogdf {
  61
  62
  63 //---------------------------------------------------------
  64 // ExpansionGraph
  65 // represents expansion graph of each biconnected component
  66 // of a given digraph, i.e., each vertex v with in- and outdegree
  67 // greater than 1 is expanded into two vertices x and y connected
  68 // by an edge x->y such that all incoming edges are moved from
  69 // v to x and all outgoing edges from v to y
  70 //---------------------------------------------------------
  71 class OGDF_EXPORT ExpansionGraph : public Graph
  72 {
  73 public:
  74         // constructor
  75         ExpansionGraph(const Graph &G);
  76
  77         // number of biconnected components of G
  78         int numberOfBCs() const {
  79                 return m_component.high()+1;
  80         }
  81
  82         // returns number of bic. component containing edge e
  83         int componentNumber(edge e) const {
  84                 return m_compNum[e];
  85         }
  86
  87         void setComponentNumber(edge e, int i) {
  88                 m_compNum[e] = i;
  89         }
  90
  91         // returns list of edges contained in component i
  92         const SListPure<edge> &component(int i) const {
  93                 return m_component[i];
  94         }
  95
  96         // returns list of components containing vertex v
  97         const SList<int> &adjacentComponents(node v) const {
  98                 return m_adjComponents[v];
  99         }
 100
 101
 102         // original node of node v
 103         // Precond.: v is a node in the expansion graph
 104         node original(node v) const {
 105                 return m_vOrig[v];
 106         }
 107
 108         node representative(node v) const {
 109                 node vOrig = m_vOrig[v];
 110                 return (vOrig != 0) ? vOrig : m_vRep[v];
 111         }
 112
 113         node copy(node vG) const {
 114                 return m_vCopy[vG];
 115         }
 116
 117         // original edge of edge e
 118         // Precond.: e is a edge in the expansion graph
 119         edge original(edge e) const {
 120                 return m_eOrig[e];
 121         }
 122
 123         // sets the original node of vCopy to vOriginal
 124         void setOriginal(node vCopy, node vOriginal) {
 125                 m_vOrig[vCopy] = vOriginal;
 126         }
 127
 128
 129         // initializes to the expansion graph of the i-th biconnected component
 130         // of G
 131         void init(int i);
 132
 133         // initializes to the expansion graph of G
 134         // advantage is that the vertices in the created copy are created in the
 135         // order in which the corresponding originals appear in the list of nodes
 136         // in G and therefore mostly have the same indices
 137         // mainly for debbugging purposes
 138         void init(const Graph &G);
 139
 140 private:
 141         node getCopy(node vOrig) {
 142                 node vCopy = m_vCopy[vOrig];
 143                 if (vCopy == 0) {
 144                         vCopy = newNode();
 145                         m_vOrig[m_vCopy[vOrig] = vCopy] = vOrig;
 146                 }
 147                 return vCopy;
 148         }
 149
 150         EdgeArray<int>          m_compNum;   // component of edge e
 151         Array<SListPure<edge> > m_component; // edges in i-th biconnected comp.
 152         NodeArray<SList<int> >  m_adjComponents; // components containing v
 153         NodeArray<node>         m_vCopy;     // copy of original vertex
 154         NodeArray<node>         m_vOrig;     // original vertex of copy
 155         NodeArray<node>         m_vRep;
 156         EdgeArray<edge>         m_eOrig;     // original edge of copy
 157 }; // class ExpansionGraph
 158
 159
 160 } // end namespace ogdf
 161
 162
 163 #endif