6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of class Set.
12 * \author Stefan Hachul
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
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
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.
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.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
50 last_selectable_index_of_S_node
= -1;
58 if (using_S_node
) delete [] S_node
;
62 void Set::set_seed(int rand_seed
)
68 void Set::init_node_set(Graph
& G
)
73 S_node
= new node
[G
.numberOfNodes()];
74 position_in_node_set
.init(G
);
78 S_node
[v
->index()] = v
;
79 position_in_node_set
[v
] = v
->index();
81 last_selectable_index_of_S_node
= G
.numberOfNodes()-1;
85 bool Set::empty_node_set()
87 if(last_selectable_index_of_S_node
< 0)
94 bool Set::is_deleted(node v
)
96 if (position_in_node_set
[v
] > last_selectable_index_of_S_node
)
103 void Set::delete_node(node del_node
)
105 int del_node_index
= position_in_node_set
[del_node
];
106 node last_selectable_node
= S_node
[last_selectable_index_of_S_node
];
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;
116 //---------------- for set of nodes with uniform probability -------------------
118 node
Set::get_random_node()
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
];
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;
133 //---------------- for set of nodes with weighted probability ------------------
135 void Set::init_node_set(Graph
& G
,NodeArray
<NodeAttributes
>& A
)
141 mass_of_star
.init(G
);
144 mass_of_star
[v
] = A
[v
].get_mass();
145 forall_adj_edges(e_adj
, v
)
147 if(e_adj
->source() != v
)
148 v_adj
= e_adj
->source();
150 v_adj
= e_adj
->target();
151 mass_of_star
[v
] += A
[v_adj
].get_mass();
156 //---------------- for set of nodes with ``lower mass'' probability --------------
158 node
Set::get_random_node_with_lowest_star_mass(int rand_tries
)
160 int rand_index
,new_rand_index
,min_mass
;
162 node random_node
,new_rand_node
,last_trie_node
,last_selectable_node
;
164 //randomly select rand_tries distinct!!! nodes from S_node and select the one
165 //with the lowest mass
167 int last_trie_index
= last_selectable_index_of_S_node
;
168 while( (i
<= rand_tries
) && (last_trie_index
>= 0) )
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
;
178 if( (i
== 1) || (min_mass
> mass_of_star
[S_node
[last_trie_index
]]) )
180 rand_index
= last_trie_index
;
181 random_node
= S_node
[last_trie_index
];
182 min_mass
= mass_of_star
[random_node
];
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;
199 //---------------- for set of nodes with ``higher mass'' probability --------------
201 node
Set::get_random_node_with_highest_star_mass(int rand_tries
)
203 int rand_index
,new_rand_index
,min_mass
;
205 node random_node
,new_rand_node
,last_trie_node
,last_selectable_node
;
207 //randomly select rand_tries distinct!!! nodes from S_node and select the one
208 //with the lowest mass
210 int last_trie_index
= last_selectable_index_of_S_node
;
211 while( (i
<= rand_tries
) && (last_trie_index
>= 0) )
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
;
221 if( (i
== 1) || (min_mass
< mass_of_star
[S_node
[last_trie_index
]]) )
223 rand_index
= last_trie_index
;
224 random_node
= S_node
[last_trie_index
];
225 min_mass
= mass_of_star
[random_node
];
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;