1 /** \file 2 * \brief Declaration of class Set. 3 * 4 * \author Stefan Hachul 5 * 6 * \par License: 7 * This file is part of the Open Graph Drawing Framework (OGDF). 8 * 9 * \par 10 * Copyright (C)<br> 11 * See README.md in the OGDF root directory for details. 12 * 13 * \par 14 * This program is free software; you can redistribute it and/or 15 * modify it under the terms of the GNU General Public License 16 * Version 2 or 3 as published by the Free Software Foundation; 17 * see the file LICENSE.txt included in the packaging of this file 18 * for details. 19 * 20 * \par 21 * This program is distributed in the hope that it will be useful, 22 * but WITHOUT ANY WARRANTY; without even the implied warranty of 23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 24 * GNU General Public License for more details. 25 * 26 * \par 27 * You should have received a copy of the GNU General Public 28 * License along with this program; if not, see 29 * http://www.gnu.org/copyleft/gpl.html 30 */ 31 32 #pragma once 33 34 #include <ogdf/basic/List.h> 35 #include <ogdf/basic/Graph.h> 36 #include <ogdf/basic/NodeArray.h> 37 #include <ogdf/energybased/fmmm/NodeAttributes.h> 38 39 namespace ogdf { 40 namespace energybased { 41 namespace fmmm { 42 43 //! Helping data structure that holds set S_node of nodes in the range [0, 44 //! G.number_of_nodes()-1] (needed for class Multilevel) for randomly choosing nodes 45 //! (with uniform or weighted probability!) 46 class Set 47 { 48 public: 49 Set(); //!< constructor 50 ~Set(); //!< destructor 51 52 void set_seed(int rand_seed); //!< the the random seed to rand_seed 53 54 55 //! \name for set of nodes @{ 56 57 //! Inits S_node[0,...,G.number_of_nodes()-1] and stores the i-th node of P 58 //! at position S_node[i] and in position_in_node_set for each node its index in 59 //! S_node. 60 void init_node_set(Graph& G); 61 62 //! Returns whether S_node is empty or not. empty_node_set()63 bool empty_node_set() { 64 return last_selectable_index_of_S_node < 0; 65 } 66 67 //! Returns true if and only if v is deleted from S_node. is_deleted(node v)68 bool is_deleted(node v) { 69 return position_in_node_set[v] > last_selectable_index_of_S_node; 70 } 71 72 //! Deletes the node v from S_node. 73 void delete_node(node v); 74 75 //! @} 76 //! \name for set of nodes with uniform probability @{ 77 78 //! Selects a random element from S_node with uniform probability and updates S_node 79 //! and position_in_node_set. 80 node get_random_node(); 81 82 //! @} 83 //! \name for set of nodes with weighted probability @{ 84 85 //! Same as init_node_set(G), but additionally the array mass_of_star is caculated. 86 void init_node_set(Graph& G,NodeArray<NodeAttributes>& A); 87 88 //! @} 89 //! \name for set of nodes with ``lower mass'' probability @{ 90 91 //! Gets rand_tries random elements from S_node and selects the one with the lowest 92 //! mass_of_star and updates S_node and position_in_node_set. 93 node get_random_node_with_lowest_star_mass(int rand_tries); 94 95 //! @} 96 //! \name for set of nodes with ``higher mass'' probability @{ 97 98 //! Gets rand_tries random elements from S_node and selects the one with the highest 99 //! mass_of_star and updates S_node and position_in_node_set. 100 node get_random_node_with_highest_star_mass(int rand_tries); 101 102 //! @} 103 104 protected: 105 //! Common updates for each get_random_node method 106 node get_random_node_common(int, int &); 107 108 //! Helper function for get_random_node methods with lowest or highest star mass 109 template<typename Comp> 110 node get_random_node_with_some_star_mass(int rand_tries, Comp comp = Comp()); 111 112 private: 113 node* S_node; //!< representation of the node set S_node[0,G.number_of_nodes()-1] 114 int last_selectable_index_of_S_node;//!< index of the last randomly choosable element 115 //! in S_node (this value is decreased after each 116 //! select operation) 117 NodeArray<int> position_in_node_set;//!< holds for each node of G the index of its 118 //! position in S_node 119 NodeArray<int> mass_of_star; //!< the sum of the masses of a node and its neighbours 120 }; 121 122 } 123 } 124 } 125