ext/OGDF/ogdf/orthogonal/FlowCompaction.h

   1 /*
   2  * $Revision: 2564 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief constructive compaction applying computation of min-cost
  11  * flow in the dual of the 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 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48
  49 #ifndef OGDF_FLOW_COMPACTION_H
  50 #define OGDF_FLOW_COMPACTION_H
  51
  52
  53 #include <ogdf/orthogonal/OrthoRep.h>
  54 #include <ogdf/planarity/PlanRep.h>
  55 #include <ogdf/internal/orthogonal/RoutingChannel.h>
  56 #include <ogdf/orthogonal/MinimumEdgeDistances.h>
  57 #include <ogdf/basic/GridLayoutMapped.h>
  58
  59
  60 namespace ogdf {
  61
  62         template<class ATYPE> class CompactionConstraintGraph;
  63         class Layout;
  64
  65
  66 //! represents compaction algorithm using min-cost flow in the dual of the constraint graph
  67 class OGDF_EXPORT FlowCompaction
  68 {
  69 public:
  70         //! construction
  71         FlowCompaction(int maxImprovementSteps = 0,
  72                 int costGen = 1,
  73                 int costAssoc = 1);
  74
  75         //! call of constructive heuristics for orthogonal representation
  76         void constructiveHeuristics(
  77                 PlanRep &PG,
  78                 OrthoRep &OR,
  79                 const RoutingChannel<int> &rc,
  80                 GridLayoutMapped &drawing);
  81
  82
  83         //! call of improvement heuristics for orthogonal drawing (variable cages)
  84         void improvementHeuristics(
  85                 PlanRep &PG,
  86                 OrthoRep &OR,
  87                 const RoutingChannel<int> &rc,
  88                 GridLayoutMapped &drawing);
  89
  90         //! call of improvement heuristics for orthogonal drawing (tight cages)
  91         void improvementHeuristics(
  92                 PlanRep &PG,
  93                 OrthoRep &OR,
  94                 //const
  95                 MinimumEdgeDistances<int> &minDist,
  96                 GridLayoutMapped &drawing,
  97                 int originalSeparation //the input value before multiplication test for compaction improvement
  98                 );
  99
 100         //
 101         // options
 102
 103         //! sets option maxImprovementSteps, which is the maximal number of steps performed by improvementHeuristics().
 104         void maxImprovementSteps(int maxSteps) {
 105                 m_maxImprovementSteps = maxSteps;
 106         }
 107
 108         //! returns option maxImprovementSteps
 109         int maxImprovementSteps() const {
 110                 return m_maxImprovementSteps;
 111         }
 112
 113         //! sets cost of arcs in constraint graph corresponding to generalizations
 114         void costGen(int c) {
 115                 m_costGen = c;
 116         }
 117
 118         //! returns option costGen
 119         int costGen() const {
 120                 return m_costGen;
 121         }
 122
 123         //! sets cost of arcs in constraint graph corresponding to associations
 124         void costAssoc(int c) {
 125                 m_costAssoc = c;
 126         }
 127
 128         //! returns option costGen
 129         int costAssoc() const {
 130                 return m_costAssoc;
 131         }
 132
 133         //! sets number of separation scaling improvement steps
 134         void scalingSteps(int sc) {m_scalingSteps = sc;}
 135
 136         //! set alignment option
 137         void align(bool b) {m_align = b;}
 138
 139
 140 private:
 141         void computeCoords(
 142                 CompactionConstraintGraph<int> &D,
 143                 NodeArray<int> &pos,
 144                 bool fixZeroLength = false,
 145                 bool fixVertexSize = false,
 146                 bool improvementHeuristics = false,
 147                 bool onlyGen = false);
 148         void dfsAssignPos(
 149                 NodeArray<bool> &visited,
 150                 NodeArray<int> &pos,
 151                 node v,
 152                 int x);
 153
 154         // options
 155         int m_maxImprovementSteps; //!< maximal number of improvement steps
 156         int m_costGen;   //!< cost of arcs in constraint graph corresponding to generalization
 157         int m_costAssoc; //!< cost of arcs in constraint graph corresponding to associations
 158         bool m_cageExpense; //!< should cageedges be more expensive than others? will be propagated to compactionConstraintGraph
 159         //int m_costCage; //!< preliminary: Carsten uses 10
 160         int m_numGenSteps; //!< number of steps reserved for generalization compaction
 161         int m_scalingSteps; //!< number of improvement steps with decreasing separation
 162         bool m_align; //!< toggle if brother nodes in hierarchies should be aligned
 163
 164
 165         EdgeArray<edge> m_dualEdge;
 166         EdgeArray<int>  m_flow;
 167 };
 168
 169
 170 } // end namespace ogdf
 171
 172
 173 #endif