ext/OGDF/src/energybased/Set.cpp

   1 /*
   2  * $Revision: 2552 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of class Set.
  11  *
  12  * \author Stefan Hachul
  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 #include "Set.h"
  45
  46 namespace ogdf {
  47
  48 Set::Set()
  49 {
  50         last_selectable_index_of_S_node = -1;
  51         S_node = NULL;
  52         using_S_node = false;
  53 }
  54
  55
  56 Set::~Set()
  57 {
  58         if (using_S_node) delete [] S_node;
  59 }
  60
  61
  62 void Set::set_seed(int rand_seed)
  63 {
  64         srand(rand_seed);
  65 }
  66
  67
  68 void Set::init_node_set(Graph& G)
  69 {
  70         using_S_node = true;
  71         node v;
  72
  73         S_node = new node[G.numberOfNodes()];
  74         position_in_node_set.init(G);
  75
  76         forall_nodes(v,G)
  77         {
  78                 S_node[v->index()] = v;
  79                 position_in_node_set[v] = v->index();
  80         }
  81         last_selectable_index_of_S_node = G.numberOfNodes()-1;
  82 }
  83
  84
  85 bool Set::empty_node_set()
  86 {
  87         if(last_selectable_index_of_S_node < 0)
  88                 return true;
  89         else
  90                 return false;
  91 }
  92
  93
  94 bool Set::is_deleted(node v)
  95 {
  96         if (position_in_node_set[v] > last_selectable_index_of_S_node )
  97                 return true;
  98         else
  99                 return false;
 100 }
 101
 102
 103 void Set::delete_node(node del_node)
 104 {
 105         int del_node_index = position_in_node_set[del_node];
 106         node last_selectable_node = S_node[last_selectable_index_of_S_node];
 107
 108         S_node[last_selectable_index_of_S_node] = del_node;
 109         S_node[del_node_index] = last_selectable_node;
 110         position_in_node_set[del_node] = last_selectable_index_of_S_node;
 111         position_in_node_set[last_selectable_node] = del_node_index;
 112         last_selectable_index_of_S_node -=1;
 113 }
 114
 115
 116 //---------------- for set of nodes with uniform probability -------------------
 117
 118 node Set::get_random_node()
 119 {
 120         int rand_index = randomNumber(0,last_selectable_index_of_S_node);
 121         node random_node =  S_node[rand_index];
 122         node last_selectable_node = S_node[last_selectable_index_of_S_node];
 123
 124         S_node[last_selectable_index_of_S_node] = random_node;
 125         S_node[rand_index] = last_selectable_node;
 126         position_in_node_set[random_node] = last_selectable_index_of_S_node;
 127         position_in_node_set[last_selectable_node] = rand_index;
 128         last_selectable_index_of_S_node -=1;
 129         return random_node;
 130 }
 131
 132
 133 //---------------- for set of nodes with weighted  probability ------------------
 134
 135 void Set::init_node_set(Graph& G,NodeArray<NodeAttributes>& A)
 136 {
 137         node v,v_adj;
 138         edge e_adj;
 139
 140         init_node_set(G);
 141         mass_of_star.init(G);
 142         forall_nodes(v,G)
 143         {
 144                 mass_of_star[v] = A[v].get_mass();
 145                 forall_adj_edges(e_adj, v)
 146                 {
 147                         if(e_adj->source() != v)
 148                                 v_adj = e_adj->source();
 149                         else
 150                                 v_adj = e_adj->target();
 151                         mass_of_star[v] += A[v_adj].get_mass();
 152                 }
 153         }
 154 }
 155
 156 //---------------- for set of nodes with ``lower mass'' probability --------------
 157
 158 node Set::get_random_node_with_lowest_star_mass(int rand_tries)
 159 {
 160         int rand_index,new_rand_index,min_mass;
 161         int i = 1;
 162         node random_node,new_rand_node,last_trie_node,last_selectable_node;
 163
 164         //randomly select rand_tries distinct!!! nodes from S_node and select the one
 165         //with the lowest mass
 166
 167         int last_trie_index = last_selectable_index_of_S_node;
 168         while( (i<= rand_tries) && (last_trie_index >= 0) )
 169         {//while
 170                 last_trie_node = S_node[last_trie_index];
 171                 new_rand_index = randomNumber(0,last_trie_index);
 172                 new_rand_node = S_node[new_rand_index];
 173                 S_node[last_trie_index] = new_rand_node;
 174                 S_node[new_rand_index] = last_trie_node;
 175                 position_in_node_set[new_rand_node] = last_trie_index;
 176                 position_in_node_set[last_trie_node] = new_rand_index;
 177
 178                 if( (i == 1) || (min_mass > mass_of_star[S_node[last_trie_index]]) )
 179                 {
 180                         rand_index = last_trie_index;
 181                         random_node = S_node[last_trie_index];
 182                         min_mass = mass_of_star[random_node];
 183                 }
 184                 i++;
 185                 last_trie_index -=1;
 186         }//while
 187
 188         //now rand_index and random_node have been fixed
 189         last_selectable_node = S_node[last_selectable_index_of_S_node];
 190         S_node[last_selectable_index_of_S_node] = random_node;
 191         S_node[rand_index] = last_selectable_node;
 192         position_in_node_set[random_node] = last_selectable_index_of_S_node;
 193         position_in_node_set[last_selectable_node] = rand_index;
 194         last_selectable_index_of_S_node -=1;
 195         return random_node;
 196 }
 197
 198
 199 //---------------- for set of nodes with ``higher mass'' probability --------------
 200
 201 node Set::get_random_node_with_highest_star_mass(int rand_tries)
 202 {
 203         int rand_index,new_rand_index,min_mass;
 204         int i = 1;
 205         node random_node,new_rand_node,last_trie_node,last_selectable_node;
 206
 207         //randomly select rand_tries distinct!!! nodes from S_node and select the one
 208         //with the lowest mass
 209
 210         int last_trie_index = last_selectable_index_of_S_node;
 211         while( (i<= rand_tries) && (last_trie_index >= 0) )
 212         {//while
 213                 last_trie_node = S_node[last_trie_index];
 214                 new_rand_index = randomNumber(0,last_trie_index);
 215                 new_rand_node = S_node[new_rand_index];
 216                 S_node[last_trie_index] = new_rand_node;
 217                 S_node[new_rand_index] = last_trie_node;
 218                 position_in_node_set[new_rand_node] = last_trie_index;
 219                 position_in_node_set[last_trie_node] = new_rand_index;
 220
 221                 if( (i == 1) || (min_mass < mass_of_star[S_node[last_trie_index]]) )
 222                 {
 223                         rand_index = last_trie_index;
 224                         random_node = S_node[last_trie_index];
 225                         min_mass = mass_of_star[random_node];
 226                 }
 227                 i++;
 228                 last_trie_index -=1;
 229         }//while
 230
 231         //now rand_index and random_node have been fixed
 232         last_selectable_node = S_node[last_selectable_index_of_S_node];
 233         S_node[last_selectable_index_of_S_node] = random_node;
 234         S_node[rand_index] = last_selectable_node;
 235         position_in_node_set[random_node] = last_selectable_index_of_S_node;
 236         position_in_node_set[last_selectable_node] = rand_index;
 237         last_selectable_index_of_S_node -=1;
 238         return random_node;
 239 }
 240
 241 }//namespace ogdf