ext/OGDF/ogdf/orthogonal/LongestPathCompaction.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 Contains constructive and improvement compaction by
  11  *        applying computation of longest paths in constraint graphs
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49
  50 #ifndef OGDF_LONGEST_PATH_COMPACTION_H
  51 #define OGDF_LONGEST_PATH_COMPACTION_H
  52
  53
  54 #include <ogdf/orthogonal/OrthoRep.h>
  55 #include <ogdf/planarity/PlanRepUML.h>
  56 #include <ogdf/internal/orthogonal/RoutingChannel.h>
  57 #include <ogdf/basic/tuples.h>
  58 #include <ogdf/basic/GridLayoutMapped.h>
  59
  60
  61 namespace ogdf {
  62
  63         template<class ATYPE> class CompactionConstraintGraph;
  64         class Layout;
  65
  66
  67 /**
  68  * \brief Compaction algorithm using longest paths in the constraint graph.
  69  *
  70  * <h3>Optional Parameters</h3>
  71  *
  72  * <table>
  73  *   <tr>
  74  *     <th>Option</th><th>Type</th><th>Default</th><th>Description</th>
  75  *   </tr><tr>
  76  *     <td><i>tighten</i></td><td>bool</td><td>true</td>
  77  *     <td>if true, an additional improvement step tries to reduce the total edge length</td>
  78  *   </tr><tr>
  79  *     <td><i>max improvement steps</i></td><td>int</td><td>0</td>
  80  *     <td>the maximal number of steps performed by the improvement heuristic; 0 means no upper limit.</td>
  81  *   </tr>
  82  * </table>
  83 */
  84 class OGDF_EXPORT LongestPathCompaction
  85 {
  86 public:
  87         //! Creates an instance of the longest path compaction algorithm.
  88         LongestPathCompaction(bool tighten = true,
  89                 int maxImprovementSteps = 0);
  90
  91         //! Constructive heurisitic for orthogonal representations.
  92         void constructiveHeuristics(
  93                 PlanRepUML &PG,
  94                 OrthoRep &OR,
  95                 const RoutingChannel<int> &rc,
  96                 GridLayoutMapped &drawing);
  97
  98
  99         //! Improvement heurisitic for orthogonal drawings.
 100         void improvementHeuristics(
 101                 PlanRepUML &PG,
 102                 OrthoRep &OR,
 103                 const RoutingChannel<int> &rc,
 104                 GridLayoutMapped &drawing);
 105
 106         //
 107         // options
 108
 109         //! Sets option <i>tighten</i> to \a select.
 110         void tighten(bool select) {
 111                 m_tighten = select;
 112         }
 113
 114         //! Returns the option <i>tighten</i>.
 115         bool tighten() const {
 116                 return m_tighten;
 117         }
 118
 119
 120         //! Sets the option <i>max improvement steps</i>.
 121         void maxImprovementSteps(int maxSteps) {
 122                 m_maxImprovementSteps = maxSteps;
 123         }
 124
 125         //! Returns the option <i>max improvement steps</i>.
 126         int maxImprovementSteps() const {
 127                 return m_maxImprovementSteps;
 128         }
 129
 130
 131 private:
 132         void computeCoords(
 133                 const CompactionConstraintGraph<int> &D,
 134                 NodeArray<int> &pos);
 135
 136         void applyLongestPaths(const CompactionConstraintGraph<int> &D,
 137                 NodeArray<int> &pos);
 138
 139         void moveComponents(const CompactionConstraintGraph<int> &D,
 140                 NodeArray<int> &pos);
 141
 142
 143         // options
 144         bool m_tighten;  //!< Tighten pseudo-components.
 145         int m_maxImprovementSteps; //!< The maximal number of improvement steps.
 146
 147         SList<node>    m_pseudoSources; //!< The list of pseudo-sources.
 148         NodeArray<int> m_component;     //!< The pseudo component of a node.
 149 };
 150
 151
 152 } // end namespace ogdf
 153
 154
 155 #endif