ext/OGDF/src/decomposition/TricComp.h

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declares class TricComp which realizes the Hopcroft/Tarjan
  11  * algorithm for finding the triconnected components of a biconnected
  12  * multi-graph.
  13  *
  14  * \author Carsten Gutwenger
  15  *
  16  * \par License:
  17  * This file is part of the Open Graph Drawing Framework (OGDF).
  18  *
  19  * \par
  20  * Copyright (C)<br>
  21  * See README.txt in the root directory of the OGDF installation for details.
  22  *
  23  * \par
  24  * This program is free software; you can redistribute it and/or
  25  * modify it under the terms of the GNU General Public License
  26  * Version 2 or 3 as published by the Free Software Foundation;
  27  * see the file LICENSE.txt included in the packaging of this file
  28  * for details.
  29  *
  30  * \par
  31  * This program is distributed in the hope that it will be useful,
  32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  34  * GNU General Public License for more details.
  35  *
  36  * \par
  37  * You should have received a copy of the GNU General Public
  38  * License along with this program; if not, write to the Free
  39  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  40  * Boston, MA 02110-1301, USA.
  41  *
  42  * \see  http://www.gnu.org/copyleft/gpl.html
  43  ***************************************************************/
  44
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49
  50 #ifndef OGDF_TRIC_COMP_H
  51 #define OGDF_TRIC_COMP_H
  52
  53
  54 #include <ogdf/basic/NodeArray.h>
  55 #include <ogdf/basic/EdgeArray.h>
  56 #include <ogdf/basic/Array.h>
  57 #include <ogdf/basic/BoundedStack.h>
  58
  59
  60 namespace ogdf {
  61
  62         class GraphCopySimple;
  63
  64
  65 //---------------------------------------------------------
  66 // TricComp
  67 // realizes Hopcroft/Tarjan algorithm for finding the triconnected
  68 // components of a biconnected multi-graph
  69 //---------------------------------------------------------
  70 class TricComp
  71 {
  72 public:
  73         // construction
  74         TricComp(const Graph &G);
  75
  76         TricComp(const Graph &G, bool &isTric, node &s1, node &s2);
  77
  78         // destruction
  79         ~TricComp();
  80
  81         // type of split-components / triconnected components
  82         enum CompType { bond, polygon, triconnected };
  83
  84         // representation of a component
  85         struct CompStruct {
  86                 List<edge> m_edges;
  87                 CompType m_type;
  88
  89                 CompStruct &operator<<(edge e) {
  90                         m_edges.pushBack(e);
  91                         return *this;
  92                 }
  93
  94                 void finishTricOrPoly(edge e) {
  95                         m_edges.pushBack(e);
  96                         m_type = (m_edges.size() >= 4) ? triconnected : polygon;
  97                 }
  98         };
  99
 100         // copy of G containing also virtual edges
 101         GraphCopySimple  *m_pGC;
 102         // array of components
 103         Array<CompStruct> m_component;
 104         // number of components
 105         int m_numComp;
 106
 107         // check if computed triconnected componets are correct
 108         bool checkComp();
 109
 110
 111 private:
 112         bool checkSepPair(edge eVirt);
 113
 114         // splits bundles of multi-edges into bonds and creates
 115         // a new virtual edge in GC.
 116         void splitMultiEdges();
 117
 118         // stack of triples
 119         int *m_TSTACK_h, *m_TSTACK_a, *m_TSTACK_b;
 120         int m_top;
 121
 122         // push a triple on TSTACK
 123         void TSTACK_push (int h, int a, int b) {
 124                 m_TSTACK_h[++m_top] = h;
 125                 m_TSTACK_a[m_top] = a;
 126                 m_TSTACK_b[m_top] = b;
 127         }
 128
 129         // push end-of-stack marker on TSTACK
 130         void TSTACK_pushEOS() {
 131                 m_TSTACK_a[++m_top] = -1;
 132         }
 133
 134         // returns true iff end-of-stack marker is not on top of TSTACK
 135         bool TSTACK_notEOS() {
 136                 return (m_TSTACK_a[m_top] != -1);
 137         }
 138
 139         // create a new empty component
 140         CompStruct &newComp() {
 141                 return m_component[m_numComp++];
 142         }
 143
 144         // create a new empty component of type t
 145         CompStruct &newComp(CompType t) {
 146                 CompStruct &C = m_component[m_numComp++];
 147                 C.m_type = t;
 148                 return C;
 149         }
 150
 151         // type of edges with respect to palm tree
 152         enum edgeType { unseen, tree, frond, removed };
 153
 154         // first dfs traversal
 155         void DFS1 (const Graph& G, node v, node u);
 156         // special version for triconnectivity tes
 157         void DFS1 (const Graph& G, node v, node u, node &s1);
 158
 159         // constructs ordered adjaceny lists
 160         void buildAcceptableAdjStruct (const Graph& G);
 161         // the second dfs traversal
 162         void DFS2 (const Graph& G);
 163         void pathFinder(const Graph& G, node v);
 164
 165         // finding of split components
 166         void pathSearch (const Graph& G, node v);
 167
 168         bool pathSearch (const Graph &G, node v, node &s1, node &s2);
 169
 170         // merges split-components into triconnected components
 171         void assembleTriconnectedComponents();
 172
 173         // debugging stuff
 174         void printOs(edge e);
 175         void printStacks();
 176
 177         // returns high(v) value
 178         int high(node v) {
 179                 return (m_HIGHPT[v].empty()) ? 0 : m_HIGHPT[v].front();
 180         }
 181
 182         void delHigh(edge e) {
 183                 ListIterator<int> it = m_IN_HIGH[e];
 184                 if (it.valid()) {
 185                         node v = e->target();
 186                         m_HIGHPT[v].del(it);
 187                 }
 188         }
 189
 190         NodeArray<int>   m_NUMBER; // (first) dfs-number of v
 191         NodeArray<int>   m_LOWPT1;
 192         NodeArray<int>   m_LOWPT2;
 193         NodeArray<int>   m_ND;     // number of descendants in palm tree
 194         NodeArray<int>   m_DEGREE; // degree of v
 195         Array<node>      m_NODEAT; // node with number i
 196         NodeArray<node> m_FATHER;  // father of v in palm tree
 197         EdgeArray<edgeType> m_TYPE; // type of edge e
 198         NodeArray<List<edge> > m_A; // adjacency list of v
 199         NodeArray<int>  m_NEWNUM;  // (second) dfs-number of v
 200         EdgeArray<bool> m_START;   // edge starts a path
 201         NodeArray<edge> m_TREE_ARC; // tree arc entering v
 202         NodeArray<List<int> > m_HIGHPT; // list of fronds entering v in the order they are visited
 203         EdgeArray<ListIterator<edge> > m_IN_ADJ;        // pointer to element in adjacency list containing e
 204         EdgeArray<ListIterator<int> >  m_IN_HIGH;       // pointer to element in HIGHPT list containing e
 205         BoundedStack<edge> m_ESTACK; // stack of currently active edges
 206
 207         node m_start;     // start node of dfs traversal
 208         int  m_numCount;  // counter for dfs-traversal
 209         bool m_newPath;   // true iff we start a new path
 210 };
 211
 212
 213 } // end namespace ogdf
 214
 215
 216 #endif