ext/OGDF/src/upward/ExpansionGraph.cpp

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implements class ExpansionGraph
  11  *
  12  * \author Carsten Gutwenger
  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
  44 #include <ogdf/upward/ExpansionGraph.h>
  45 #include <ogdf/basic/simple_graph_alg.h>
  46 #include <ogdf/basic/NodeSet.h>
  47
  48
  49 namespace ogdf {
  50
  51
  52 // constructor
  53 // computes biconnected componets of original graph
  54 // does not create a copy graph
  55 ExpansionGraph::ExpansionGraph(const Graph &G) :
  56         m_compNum(G), m_adjComponents(G), m_vCopy(G,0)
  57 {
  58         m_vOrig.init(*this,0);
  59         m_vRep .init(*this,0);
  60         m_eOrig.init(*this,0);
  61
  62         // compute biconnected components
  63         int numComp = biconnectedComponents(G,m_compNum);
  64
  65         // for each component, build list of contained edges
  66         m_component.init(numComp);
  67
  68         edge e;
  69         forall_edges(e,G)
  70                 m_component[m_compNum[e]].pushBack(e);
  71
  72         // for each vertex v, build list of components containing v
  73         NodeSetSimple contained(G);
  74         for(int i = 0; i < numComp; ++i)
  75         {
  76                 SListConstIterator<edge> it;
  77                 for(it = m_component[i].begin(); it.valid(); ++it)
  78                 {
  79                         e = *it;
  80                         node v = e->source();
  81                         if (contained.isMember(v) == false) {
  82                                 contained.insert(v);
  83                                 m_adjComponents[v].pushBack(i);
  84                         }
  85
  86                         v = e->target();
  87                         if (contained.isMember(v) == false) {
  88                                 contained.insert(v);
  89                                 m_adjComponents[v].pushBack(i);
  90                         }
  91                 }
  92
  93                 contained.clear();
  94         }
  95 }
  96
  97
  98 // builds expansion graph of i-th biconnected component of the original graph
  99 void ExpansionGraph::init(int i)
 100 {
 101         OGDF_ASSERT(0 <= i && i <= m_component.high());
 102
 103         // remove previous component
 104         node v;
 105         forall_nodes(v,*this) {
 106                 node vOrig = m_vOrig[v];
 107                 if (vOrig)
 108                         m_vCopy[vOrig] = 0;
 109         }
 110         clear();
 111
 112
 113         // create new component
 114         SListConstIterator<edge> it;
 115         for(it = m_component[i].begin(); it.valid(); ++it)
 116         {
 117                 edge e = *it;
 118
 119                 edge eCopy = newEdge(getCopy(e->source()),getCopy(e->target()));
 120                 m_eOrig[eCopy] = e;
 121         }
 122
 123         // expand vertices
 124         forall_nodes(v,*this)
 125         {
 126                 if (original(v) && v->indeg() >= 1 && v->outdeg() >= 1) {
 127                         node vPrime = newNode();
 128                         m_vRep[vPrime] = m_vOrig[v];
 129
 130                         SListPure<edge> edges;
 131                         outEdges(v,edges);
 132
 133                         SListConstIterator<edge> it;
 134                         for(it = edges.begin(); it.valid(); ++it)
 135                                 moveSource(*it,vPrime);
 136
 137                         newEdge(v,vPrime);
 138                 }
 139         }
 140 }
 141
 142
 143 // builds expansion graph of graph G
 144 // for debugging purposes only
 145 void ExpansionGraph::init(const Graph &G)
 146 {
 147         // remove previous component
 148         node v;
 149         forall_nodes(v,*this) {
 150                 node vOrig = m_vOrig[v];
 151                 if (vOrig)
 152                         m_vCopy[vOrig] = 0;
 153         }
 154         clear();
 155
 156
 157         // create new component
 158         forall_nodes(v,G)
 159                 getCopy(v);
 160
 161         edge e;
 162         forall_edges(e,G)
 163         {
 164                 edge eCopy = newEdge(getCopy(e->source()),getCopy(e->target()));
 165                 m_eOrig[eCopy] = e;
 166         }
 167
 168         // expand vertices
 169         forall_nodes(v,*this)
 170         {
 171                 if (original(v) && v->indeg() >= 1 && v->outdeg() >= 1) {
 172                         node vPrime = newNode();
 173
 174                         SListPure<edge> edges;
 175                         outEdges(v,edges);
 176
 177                         SListConstIterator<edge> it;
 178                         for(it = edges.begin(); it.valid(); ++it)
 179                                 moveSource(*it,vPrime);
 180
 181                         newEdge(v,vPrime);
 182                 }
 183         }
 184 }
 185
 186
 187 } // end namespace ogdf
 188