ext/OGDF/src/planarity/GraphReduction.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 GraphReduction.
  11  *
  12  * \author Markus Chimani
  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/graphalg/GraphReduction.h>
  45
  46 namespace ogdf {
  47
  48 GraphReduction::GraphReduction(const Graph &G) : m_pGraph(&G),
  49 m_vOrig(), m_eOrig(), m_vReduction(), m_eReduction() {
  50         Graph::construct(*m_pGraph,m_vReduction,m_eReduction);
  51
  52         int d;
  53         node v,ov;
  54         edge e1,e2;
  55
  56         m_vOrig.init(*this);
  57         m_eOrig.init(*this);
  58         forall_nodes(v, *m_pGraph)
  59                 m_vOrig[m_vReduction[v]] = v;
  60
  61         forall_edges(e1, *m_pGraph)
  62                 m_eOrig[m_eReduction[e1]].pushBack(e1);
  63
  64         // remove selfloops
  65         forall_edges(e1, *this) {
  66                 if(e1->isSelfLoop()) {
  67                         m_eReduction[e1] = NULL;
  68                         this->delEdge(e1);
  69                 }
  70         }
  71
  72         List<node> next;
  73         forall_nodes(v, *m_pGraph)
  74                 next.pushBack(v);
  75         while(next.size()) {
  76                 ov = next.front();
  77                 next.popFront();
  78                 v = m_vReduction[ov];
  79                 if( v && (d=v->degree()) < 3) {
  80                         if(d == 2) {
  81                                 e1 = v->firstAdj()->theEdge();
  82                                 e2 = v->lastAdj()->theEdge();
  83
  84                                 if( e1->source() == v) {
  85                                         if(e2->source() == v) m_eOrig[e2].reverse();
  86                                         this->moveSource(e1, e2->opposite(v));
  87                                         for(ListConstIterator<edge> it = m_eOrig[e2].rbegin(); it.valid(); --it) {
  88                                                 m_eReduction[*it] = e1;
  89                                                 m_eOrig[e1].pushFront( *it );
  90                                         }
  91                                 } else {
  92                                         if(e2->target() == v) m_eOrig[e2].reverse();
  93                                         this->moveTarget(e1, e2->opposite(v));
  94                                         for(ListConstIterator<edge> it = m_eOrig[e2].begin(); it.valid(); ++it) {
  95                                                 m_eReduction[*it] = e1;
  96                                                 m_eOrig[e1].pushBack( *it );
  97                                         }
  98                                 }
  99                                 m_eOrig[e2].clear();
 100                                 this->delEdge(e2);
 101                         } else if(d == 1) {
 102                                 e1 = v->firstAdj()->theEdge();
 103                                 const List<edge>& el = m_eOrig[e1];
 104                                 node nv;
 105                                 if(el.size() == 1)
 106                                         nv = el.front()->opposite(ov);
 107                                 else {
 108                                         bool front_e1 = el.front()->source() == ov || el.front()->target() == ov;
 109                                         edge e3;
 110                                         if(front_e1) {
 111                                                 e2 = el.back();
 112                                                 e3 = *(el.rbegin().pred());
 113                                         } else {
 114                                                 e2 = el.front();
 115                                                 e3 = *(el.begin().succ());
 116                                         }
 117                                         nv = (e2->source() == e3->source() || e2->source() == e3->target()) ? e2->target() : e2->source();
 118                                 }
 119                                 next.pushBack(nv);
 120
 121                                 for(ListIterator<edge> it = m_eOrig[e1].begin(); it.valid(); it++)
 122                                         m_eReduction[*it] = 0;
 123                                 this->delEdge(e1);
 124                         }
 125                         m_vReduction[ ov ] = 0;
 126                         this->delNode(v);
 127                 }
 128         }
 129
 130 #ifdef OGDF_DEBUG
 131         edge em;
 132         forall_edges(em, *this) {
 133                 node t = 0;
 134                 OGDF_ASSERT( original(em).front()->source() == original(em->source()) );
 135                 for(ListConstIterator<edge> it = original(em).begin(); it.valid(); ++it) {
 136                         if(t) {
 137                                 OGDF_ASSERT( (*it)->source() == t);
 138                         }
 139                 }
 140                 OGDF_ASSERT( original(em).back()->target() == original(em->target()) );
 141         }
 142 #endif
 143
 144 }
 145
 146 }