1 /** \file 2 * 3 * \par License: 4 * This file is part of the Open Graph Drawing Framework (OGDF). 5 * 6 * \par 7 * Copyright (C)<br> 8 * See README.md in the OGDF root directory for details. 9 * 10 * \par 11 * This program is free software; you can redistribute it and/or 12 * modify it under the terms of the GNU General Public License 13 * Version 2 or 3 as published by the Free Software Foundation; 14 * see the file LICENSE.txt included in the packaging of this file 15 * for details. 16 * 17 * \par 18 * This program is distributed in the hope that it will be useful, 19 * but WITHOUT ANY WARRANTY; without even the implied warranty of 20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 21 * GNU General Public License for more details. 22 * 23 * \par 24 * You should have received a copy of the GNU General Public 25 * License along with this program; if not, see 26 * http://www.gnu.org/copyleft/gpl.html 27 */ 28 29 #pragma once 30 31 #include <ogdf/basic/Graph.h> 32 33 namespace ogdf { 34 namespace energybased { 35 namespace dtree { 36 37 //! Simple implementation of the slightly modified version of Hachul by Gronemann 38 class OGDF_EXPORT GalaxyLevel 39 { 40 public: 41 //! constructor for the finest level i.e. the original graph 42 //! \pre the graph has to be connected 43 explicit GalaxyLevel(const Graph& graph); 44 45 //! destructor, deletes this level and all subsequent i.e coarser ones 46 ~GalaxyLevel(); 47 48 //! returns the graph 49 const Graph& graph() const; 50 51 //! returns the parent node of a node on the coarser level 52 node parent(node v) const; 53 54 //! returns the weight of a node 55 double weight(node v) const; 56 57 //! returns the edge weight of e 58 double edgeWeight(edge e) const; 59 60 //! returns the weight of a node 61 void setWeight(node v, double weight); 62 63 //! returns the edge weight of e 64 void setEdgeWeight(edge e, double weight); 65 66 //! returns true if this is the level of the original graph 67 bool isFinestLevel() const; 68 69 //! returns true if this is the coarsest level 70 bool isCoarsestLevel() const; 71 72 //! return the next coarser one 73 GalaxyLevel* nextCoarser(); 74 75 //! return the next finer one 76 GalaxyLevel* nextFiner(); 77 78 /** 79 * Builds all levels until the graph has less than \c maxNumNodes 80 * 81 * In case there are already coarser levels attached to this, it will 82 * extend the coarsest if necessary. If not i.e. the coarsest has 83 * less than maxNumNodes, it will return the coarsest. 84 */ 85 GalaxyLevel* buildLevelsUntil(int maxNumNodes); 86 87 private: 88 //! creates a new coarser version of this graph 89 GalaxyLevel* buildNextCoarserLevel(int numLabels = 3); 90 91 //! private constructor for creating a coarser level 92 GalaxyLevel(GalaxyLevel* pNextFiner); 93 94 //! remove par edges with weight 95 void removeParEdgesWithWeight(); 96 97 //! pointer to the next finer level 98 GalaxyLevel* m_pNextFiner; 99 100 //! pointer to the next coarser 101 GalaxyLevel* m_pNextCoarser; 102 103 //! the graph 104 Graph* m_pGraph; 105 106 //! the weight of the node is the sum of weights of the children 107 NodeArray<double> m_nodeWeight; 108 109 //! pointer to the parent node on the coarser level 110 NodeArray<node> m_parent; 111 112 //! edge weight 113 EdgeArray<double> m_edgeWeight; 114 }; 115 116 }}} 117