/*
* $Revision: 2552 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
***************************************************************/
/** \file
* \brief Implementation of class Set.
*
* \author Stefan Hachul
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#include "Set.h"
namespace ogdf {
Set::Set()
{
last_selectable_index_of_S_node = -1;
S_node = NULL;
using_S_node = false;
}
Set::~Set()
{
if (using_S_node) delete [] S_node;
}
void Set::set_seed(int rand_seed)
{
srand(rand_seed);
}
void Set::init_node_set(Graph& G)
{
using_S_node = true;
node v;
S_node = new node[G.numberOfNodes()];
position_in_node_set.init(G);
forall_nodes(v,G)
{
S_node[v->index()] = v;
position_in_node_set[v] = v->index();
}
last_selectable_index_of_S_node = G.numberOfNodes()-1;
}
bool Set::empty_node_set()
{
if(last_selectable_index_of_S_node < 0)
return true;
else
return false;
}
bool Set::is_deleted(node v)
{
if (position_in_node_set[v] > last_selectable_index_of_S_node )
return true;
else
return false;
}
void Set::delete_node(node del_node)
{
int del_node_index = position_in_node_set[del_node];
node last_selectable_node = S_node[last_selectable_index_of_S_node];
S_node[last_selectable_index_of_S_node] = del_node;
S_node[del_node_index] = last_selectable_node;
position_in_node_set[del_node] = last_selectable_index_of_S_node;
position_in_node_set[last_selectable_node] = del_node_index;
last_selectable_index_of_S_node -=1;
}
//---------------- for set of nodes with uniform probability -------------------
node Set::get_random_node()
{
int rand_index = randomNumber(0,last_selectable_index_of_S_node);
node random_node = S_node[rand_index];
node last_selectable_node = S_node[last_selectable_index_of_S_node];
S_node[last_selectable_index_of_S_node] = random_node;
S_node[rand_index] = last_selectable_node;
position_in_node_set[random_node] = last_selectable_index_of_S_node;
position_in_node_set[last_selectable_node] = rand_index;
last_selectable_index_of_S_node -=1;
return random_node;
}
//---------------- for set of nodes with weighted probability ------------------
void Set::init_node_set(Graph& G,NodeArray& A)
{
node v,v_adj;
edge e_adj;
init_node_set(G);
mass_of_star.init(G);
forall_nodes(v,G)
{
mass_of_star[v] = A[v].get_mass();
forall_adj_edges(e_adj, v)
{
if(e_adj->source() != v)
v_adj = e_adj->source();
else
v_adj = e_adj->target();
mass_of_star[v] += A[v_adj].get_mass();
}
}
}
//---------------- for set of nodes with ``lower mass'' probability --------------
node Set::get_random_node_with_lowest_star_mass(int rand_tries)
{
int rand_index = 0, new_rand_index, min_mass = 0;
int i = 1;
node random_node = node(), new_rand_node,last_trie_node,last_selectable_node;
//randomly select rand_tries distinct!!! nodes from S_node and select the one
//with the lowest mass
int last_trie_index = last_selectable_index_of_S_node;
while( (i<= rand_tries) && (last_trie_index >= 0) )
{//while
last_trie_node = S_node[last_trie_index];
new_rand_index = randomNumber(0,last_trie_index);
new_rand_node = S_node[new_rand_index];
S_node[last_trie_index] = new_rand_node;
S_node[new_rand_index] = last_trie_node;
position_in_node_set[new_rand_node] = last_trie_index;
position_in_node_set[last_trie_node] = new_rand_index;
if( (i == 1) || (min_mass > mass_of_star[S_node[last_trie_index]]) )
{
rand_index = last_trie_index;
random_node = S_node[last_trie_index];
min_mass = mass_of_star[random_node];
}
i++;
last_trie_index -=1;
}//while
//now rand_index and random_node have been fixed
last_selectable_node = S_node[last_selectable_index_of_S_node];
S_node[last_selectable_index_of_S_node] = random_node;
S_node[rand_index] = last_selectable_node;
position_in_node_set[random_node] = last_selectable_index_of_S_node;
position_in_node_set[last_selectable_node] = rand_index;
last_selectable_index_of_S_node -=1;
return random_node;
}
//---------------- for set of nodes with ``higher mass'' probability --------------
node Set::get_random_node_with_highest_star_mass(int rand_tries)
{
int rand_index = 0, new_rand_index, min_mass = 0;
int i = 1;
node random_node = node(), new_rand_node,last_trie_node,last_selectable_node;
//randomly select rand_tries distinct!!! nodes from S_node and select the one
//with the lowest mass
int last_trie_index = last_selectable_index_of_S_node;
while( (i<= rand_tries) && (last_trie_index >= 0) )
{//while
last_trie_node = S_node[last_trie_index];
new_rand_index = randomNumber(0,last_trie_index);
new_rand_node = S_node[new_rand_index];
S_node[last_trie_index] = new_rand_node;
S_node[new_rand_index] = last_trie_node;
position_in_node_set[new_rand_node] = last_trie_index;
position_in_node_set[last_trie_node] = new_rand_index;
if( (i == 1) || (min_mass < mass_of_star[S_node[last_trie_index]]) )
{
rand_index = last_trie_index;
random_node = S_node[last_trie_index];
min_mass = mass_of_star[random_node];
}
i++;
last_trie_index -=1;
}//while
//now rand_index and random_node have been fixed
last_selectable_node = S_node[last_selectable_index_of_S_node];
S_node[last_selectable_index_of_S_node] = random_node;
S_node[rand_index] = last_selectable_node;
position_in_node_set[random_node] = last_selectable_index_of_S_node;
position_in_node_set[last_selectable_node] = rand_index;
last_selectable_index_of_S_node -=1;
return random_node;
}
}//namespace ogdf