ext/OGDF/ogdf/layered/Level.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 Declaration and implementation of Level class
  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 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_LEVEL_H
  49 #define OGDF_LEVEL_H
  50
  51
  52
  53 #include <ogdf/basic/Graph.h>
  54 #include <ogdf/basic/SList.h>
  55 #include <ogdf/basic/tuples.h>
  56
  57
  58 namespace ogdf {
  59
  60 class OGDF_EXPORT Hierarchy;
  61
  62 class LayerBasedUPRLayout;
  63
  64
  65 template <class T = double>
  66 class WeightComparer {
  67         const NodeArray<T> *m_pWeight;
  68
  69 public:
  70         WeightComparer(const NodeArray<T> *pWeight) : m_pWeight(pWeight) { }
  71
  72         bool less(node v, node w) const { return (*m_pWeight)[v] < (*m_pWeight)[w]; }
  73         bool operator()(node v, node w) const { return (*m_pWeight)[v] < (*m_pWeight)[w]; }
  74 };
  75
  76
  77 //! Representation of levels in hierarchies.
  78 /**
  79  * \see Hierarchy, SugiyamaLayout
  80  */
  81 class OGDF_EXPORT Level {
  82
  83         friend class Hierarchy;
  84         friend class LayerBasedUPRLayout;
  85         friend class HierarchyLayoutModule;
  86
  87         Array<node> m_nodes;     //!< The nodes on this level.
  88         Hierarchy *m_pHierarchy; //!< The hierarchy to which this level belongs.
  89         int m_index;             //!< The index of this level.
  90
  91 public:
  92         //! Creates a level with index \a index in hierarchy \a pHierarchy.
  93         /**
  94          * @param pHierarchy is a pointer to the hierarchy to which the created
  95          *        level will belong.
  96          * @param index is the index of the level.
  97          * @param num is the number of nodes on this level.
  98          */
  99         Level(Hierarchy *pHierarchy, int index, int num) :
 100                 m_nodes(num), m_pHierarchy(pHierarchy), m_index(index) { }
 101
 102         // destruction
 103         ~Level() { }
 104
 105         //! Returns the node at position \a i.
 106         const node &operator[](int i) const { return m_nodes[i]; }
 107         //! Returns the node at position \a i.
 108         node &operator[](int i) { return m_nodes[i]; }
 109
 110         //! Returns the number of nodes on this level.
 111         int size() const { return m_nodes.size(); }
 112         //! Returns the maximal array index (= size()-1).
 113         int high() const { return m_nodes.high(); }
 114
 115         //! Returns the array index of this level in the hierarchy.
 116         int index() const { return m_index; }
 117
 118         //! Returns the (sorted) array of adjacent nodes of \a v (according to direction()).
 119         const Array<node> &adjNodes(node v);
 120
 121         //! Returns the hierarchy to which this level belongs.
 122         const Hierarchy &hierarchy() const { return *m_pHierarchy; }
 123
 124         //! Exchanges nodes at position \a i and \a j.
 125         void swap(int i, int j);
 126
 127         //! Sorts the nodes according to \a weight using quicksort.
 128         void sort(NodeArray<double> &weight);
 129
 130         //! Sorts the nodes according to \a weight using bucket sort.
 131         void sort(NodeArray<int> &weight, int minBucket, int maxBucket);
 132
 133         //! Sorts the nodes according to \a weight (without special placement for "isolated" nodes).
 134         void sortByWeightOnly(NodeArray<double> &weight);
 135
 136         //!Sorts the nodes according to \a orderComparer
 137         template<class C>
 138         void sortOrder(C &orderComparer) {
 139                 m_nodes.quicksort(orderComparer);
 140                 recalcPos();
 141         }
 142
 143         void recalcPos();
 144
 145         friend ostream &operator<<(ostream &os, const Level &L) {
 146                 os << L.m_nodes;
 147                 return os;
 148         }
 149
 150 private:
 151         void getIsolatedNodes(SListPure<Tuple2<node,int> > &isolated);
 152         void setIsolatedNodes(SListPure<Tuple2<node,int> > &isolated);
 153
 154         OGDF_MALLOC_NEW_DELETE
 155 };
 156
 157 } // end namespace ogdf
 158
 159
 160 #endif