1 /*
2 * Copyright 2007 Sandia Corporation. Under the terms of Contract
3 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government retains
4 * certain rights in this software.
5 *
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are
10 * met:
11 *
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * * Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * * Neither the name of Sandia National Laboratories nor the names of
18 * its contributors may be used to endorse or promote products derived from
19 * this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33 // Layout
34 //
35 // This program implements a parallel force directed graph drawing
36 // algorithm. The algorithm used is based upon a random decomposition
37 // of the graph and simulated shared memory of node position and density.
38 // In this version, the simulated shared memory is spread among all processors
39 //
40 // The structure of the inputs and outputs of this code will be displayed
41 // if the program is called without parameters, or if an erroneous
42 // parameter is passed to the program.
43 //
44 // S. Martin
45 // 5/6/2005
46
47 // C++ library routines
48 #include <map>
49 #include <vector>
50
51 using namespace std;
52
53 // layout routines and constants
54 #include "drl_layout.h"
55 #include "drl_parse.h"
56 #include "drl_graph.h"
57
58 // MPI
59 #ifdef MUSE_MPI
60 #include <mpi.h>
61 #endif
62
63 using namespace drl;
64 #include "igraph_layout.h"
65 #include "igraph_random.h"
66 #include "igraph_interface.h"
67
68 #include "igraph_handle_exceptions.h"
69
70 namespace drl {
71
72 // int main(int argc, char **argv) {
73
74
75 // // initialize MPI
76 // int myid, num_procs;
77
78 // #ifdef MUSE_MPI
79 // MPI_Init ( &argc, &argv );
80 // MPI_Comm_size ( MPI_COMM_WORLD, &num_procs );
81 // MPI_Comm_rank ( MPI_COMM_WORLD, &myid );
82 // #else
83 // myid = 0;
84 // num_procs = 1;
85 // #endif
86
87 // // parameters that must be broadcast to all processors
88 // int rand_seed;
89 // float edge_cut;
90
91 // char int_file[MAX_FILE_NAME];
92 // char coord_file[MAX_FILE_NAME];
93 // char real_file[MAX_FILE_NAME];
94 // char parms_file[MAX_FILE_NAME];
95
96 // int int_out = 0;
97 // int edges_out = 0;
98 // int parms_in = 0;
99 // float real_in = -1.0;
100
101 // // user interaction is handled by processor 0
102 // if ( myid == 0 )
103 // {
104 // if ( num_procs > MAX_PROCS )
105 // {
106 // cout << "Error: Maximum number of processors is " << MAX_PROCS << "." << endl;
107 // cout << "Adjust compile time parameter." << endl;
108 // #ifdef MUSE_MPI
109 // MPI_Abort ( MPI_COMM_WORLD, 1 );
110 // #else
111 // exit (1);
112 // #endif
113 // }
114
115 // // get user input
116 // parse command_line ( argc, argv );
117 // rand_seed = command_line.rand_seed;
118 // edge_cut = command_line.edge_cut;
119 // int_out = command_line.int_out;
120 // edges_out = command_line.edges_out;
121 // parms_in = command_line.parms_in;
122 // real_in = command_line.real_in;
123 // strcpy ( coord_file, command_line.coord_file.c_str() );
124 // strcpy ( int_file, command_line.sim_file.c_str() );
125 // strcpy ( real_file, command_line.real_file.c_str() );
126 // strcpy ( parms_file, command_line.parms_file.c_str() );
127
128 // }
129
130 // // now we initialize all processors by reading .int file
131 // #ifdef MUSE_MPI
132 // MPI_Bcast ( &int_file, MAX_FILE_NAME, MPI_CHAR, 0, MPI_COMM_WORLD );
133 // #endif
134 // graph neighbors ( myid, num_procs, int_file );
135
136 // // check for user supplied parameters
137 // #ifdef MUSE_MPI
138 // MPI_Bcast ( &parms_in, 1, MPI_INT, 0, MPI_COMM_WORLD );
139 // #endif
140 // if ( parms_in )
141 // {
142 // #ifdef MUSE_MPI
143 // MPI_Bcast ( &parms_file, MAX_FILE_NAME, MPI_CHAR, 0, MPI_COMM_WORLD );
144 // #endif
145 // neighbors.read_parms ( parms_file );
146 // }
147
148 // // set random seed, edge cutting, and real iterations parameters
149 // #ifdef MUSE_MPI
150 // MPI_Bcast ( &rand_seed, 1, MPI_INT, 0, MPI_COMM_WORLD );
151 // MPI_Bcast ( &edge_cut, 1, MPI_FLOAT, 0, MPI_COMM_WORLD );
152 // MPI_Bcast ( &real_in, 1, MPI_INT, 0, MPI_COMM_WORLD );
153 // #endif
154 // neighbors.init_parms ( rand_seed, edge_cut, real_in );
155
156 // // check for .real file with existing coordinates
157 // if ( real_in >= 0 )
158 // {
159 // #ifdef MUSE_MPI
160 // MPI_Bcast ( &real_file, MAX_FILE_NAME, MPI_CHAR, 0, MPI_COMM_WORLD );
161 // #endif
162 // neighbors.read_real ( real_file );
163 // }
164
165 // neighbors.draw_graph ( int_out, coord_file );
166
167 // // do we have to write out the edges?
168 // #ifdef MUSE_MPI
169 // MPI_Bcast ( &edges_out, 1, MPI_INT, 0, MPI_COMM_WORLD );
170 // #endif
171 // if ( edges_out )
172 // {
173 // #ifdef MUSE_MPI
174 // MPI_Bcast ( &coord_file, MAX_FILE_NAME, MPI_CHAR, 0, MPI_COMM_WORLD );
175 // #endif
176 // for ( int i = 0; i < num_procs; i++ )
177 // {
178 // if ( myid == i )
179 // neighbors.write_sim ( coord_file );
180 // #ifdef MUSE_MPI
181 // MPI_Barrier ( MPI_COMM_WORLD );
182 // #endif
183 // }
184 // }
185
186 // // finally we output file and quit
187 // float tot_energy;
188 // tot_energy = neighbors.get_tot_energy ();
189 // if ( myid == 0 )
190 // {
191 // neighbors.write_coord ( coord_file );
192 // cout << "Total Energy: " << tot_energy << "." << endl
193 // << "Program terminated successfully." << endl;
194 // }
195
196 // // MPI finalize
197 // #ifdef MUSE_MPI
198 // MPI_Finalize ();
199 // #endif
200
201 // return 0;
202 // }
203
204 } // namespace drl
205
206 /**
207 * \section about_drl
208 *
209 * <para>
210 * DrL is a sophisticated layout generator developed and implemented by
211 * Shawn Martin et al. As of October 2012 the original DrL homepage is
212 * unfortunately not available. You can read more about this algorithm
213 * in the following technical report: Martin, S., Brown, W.M.,
214 * Klavans, R., Boyack, K.W., DrL: Distributed Recursive (Graph)
215 * Layout. SAND Reports, 2008. 2936: p. 1-10.
216 * </para>
217 *
218 * <para>
219 * Only a subset of the complete DrL functionality is
220 * included in igraph, parallel runs and recursive, multi-level
221 * layouting is not supported.
222 * </para>
223 *
224 * <para>
225 * The parameters of the layout are stored in an \ref
226 * igraph_layout_drl_options_t structure, this can be initialized by
227 * calling the function \ref igraph_layout_drl_options_init().
228 * The fields of this structure can then be adjusted by hand if needed.
229 * The layout is calculated by an \ref igraph_layout_drl() call.
230 * </para>
231 */
232
233 /**
234 * \function igraph_layout_drl_options_init
235 * Initialize parameters for the DrL layout generator
236 *
237 * This function can be used to initialize the struct holding the
238 * parameters for the DrL layout generator. There are a number of
239 * predefined templates available, it is a good idea to start from one
240 * of these by modifying some parameters.
241 * \param options The struct to initialize.
242 * \param templ The template to use. Currently the following templates
243 * are supplied: \c IGRAPH_LAYOUT_DRL_DEFAULT, \c
244 * IGRAPH_LAYOUT_DRL_COARSEN, \c IGRAPH_LAYOUT_DRL_COARSEST,
245 * \c IGRAPH_LAYOUT_DRL_REFINE and \c IGRAPH_LAYOUT_DRL_FINAL.
246 * \return Error code.
247 *
248 * Time complexity: O(1).
249 */
250
igraph_layout_drl_options_init(igraph_layout_drl_options_t * options,igraph_layout_drl_default_t templ)251 int igraph_layout_drl_options_init(igraph_layout_drl_options_t *options,
252 igraph_layout_drl_default_t templ) {
253
254 options->edge_cut = 32.0 / 40.0;
255
256 switch (templ) {
257 case IGRAPH_LAYOUT_DRL_DEFAULT:
258 options->init_iterations = 0;
259 options->init_temperature = 2000;
260 options->init_attraction = 10;
261 options->init_damping_mult = 1.0;
262
263 options->liquid_iterations = 200;
264 options->liquid_temperature = 2000;
265 options->liquid_attraction = 10;
266 options->liquid_damping_mult = 1.0;
267
268 options->expansion_iterations = 200;
269 options->expansion_temperature = 2000;
270 options->expansion_attraction = 2;
271 options->expansion_damping_mult = 1.0;
272
273 options->cooldown_iterations = 200;
274 options->cooldown_temperature = 2000;
275 options->cooldown_attraction = 1;
276 options->cooldown_damping_mult = .1;
277
278 options->crunch_iterations = 50;
279 options->crunch_temperature = 250;
280 options->crunch_attraction = 1;
281 options->crunch_damping_mult = 0.25;
282
283 options->simmer_iterations = 100;
284 options->simmer_temperature = 250;
285 options->simmer_attraction = .5;
286 options->simmer_damping_mult = 0;
287
288 break;
289 case IGRAPH_LAYOUT_DRL_COARSEN:
290 options->init_iterations = 0;
291 options->init_temperature = 2000;
292 options->init_attraction = 10;
293 options->init_damping_mult = 1.0;
294
295 options->liquid_iterations = 200;
296 options->liquid_temperature = 2000;
297 options->liquid_attraction = 2;
298 options->liquid_damping_mult = 1.0;
299
300 options->expansion_iterations = 200;
301 options->expansion_temperature = 2000;
302 options->expansion_attraction = 10;
303 options->expansion_damping_mult = 1.0;
304
305 options->cooldown_iterations = 200;
306 options->cooldown_temperature = 2000;
307 options->cooldown_attraction = 1;
308 options->cooldown_damping_mult = .1;
309
310 options->crunch_iterations = 50;
311 options->crunch_temperature = 250;
312 options->crunch_attraction = 1;
313 options->crunch_damping_mult = 0.25;
314
315 options->simmer_iterations = 100;
316 options->simmer_temperature = 250;
317 options->simmer_attraction = .5;
318 options->simmer_damping_mult = 0;
319
320 break;
321 case IGRAPH_LAYOUT_DRL_COARSEST:
322 options->init_iterations = 0;
323 options->init_temperature = 2000;
324 options->init_attraction = 10;
325 options->init_damping_mult = 1.0;
326
327 options->liquid_iterations = 200;
328 options->liquid_temperature = 2000;
329 options->liquid_attraction = 2;
330 options->liquid_damping_mult = 1.0;
331
332 options->expansion_iterations = 200;
333 options->expansion_temperature = 2000;
334 options->expansion_attraction = 10;
335 options->expansion_damping_mult = 1.0;
336
337 options->cooldown_iterations = 200;
338 options->cooldown_temperature = 2000;
339 options->cooldown_attraction = 1;
340 options->cooldown_damping_mult = .1;
341
342 options->crunch_iterations = 200;
343 options->crunch_temperature = 250;
344 options->crunch_attraction = 1;
345 options->crunch_damping_mult = 0.25;
346
347 options->simmer_iterations = 100;
348 options->simmer_temperature = 250;
349 options->simmer_attraction = .5;
350 options->simmer_damping_mult = 0;
351
352 break;
353 case IGRAPH_LAYOUT_DRL_REFINE:
354 options->init_iterations = 0;
355 options->init_temperature = 50;
356 options->init_attraction = .5;
357 options->init_damping_mult = 0;
358
359 options->liquid_iterations = 0;
360 options->liquid_temperature = 2000;
361 options->liquid_attraction = 2;
362 options->liquid_damping_mult = 1.0;
363
364 options->expansion_iterations = 50;
365 options->expansion_temperature = 500;
366 options->expansion_attraction = .1;
367 options->expansion_damping_mult = .25;
368
369 options->cooldown_iterations = 50;
370 options->cooldown_temperature = 200;
371 options->cooldown_attraction = 1;
372 options->cooldown_damping_mult = .1;
373
374 options->crunch_iterations = 50;
375 options->crunch_temperature = 250;
376 options->crunch_attraction = 1;
377 options->crunch_damping_mult = 0.25;
378
379 options->simmer_iterations = 0;
380 options->simmer_temperature = 250;
381 options->simmer_attraction = .5;
382 options->simmer_damping_mult = 0;
383
384 break;
385 case IGRAPH_LAYOUT_DRL_FINAL:
386 options->init_iterations = 0;
387 options->init_temperature = 50;
388 options->init_attraction = .5;
389 options->init_damping_mult = 0;
390
391 options->liquid_iterations = 0;
392 options->liquid_temperature = 2000;
393 options->liquid_attraction = 2;
394 options->liquid_damping_mult = 1.0;
395
396 options->expansion_iterations = 50;
397 options->expansion_temperature = 50;
398 options->expansion_attraction = .1;
399 options->expansion_damping_mult = .25;
400
401 options->cooldown_iterations = 50;
402 options->cooldown_temperature = 200;
403 options->cooldown_attraction = 1;
404 options->cooldown_damping_mult = .1;
405
406 options->crunch_iterations = 50;
407 options->crunch_temperature = 250;
408 options->crunch_attraction = 1;
409 options->crunch_damping_mult = 0.25;
410
411 options->simmer_iterations = 25;
412 options->simmer_temperature = 250;
413 options->simmer_attraction = .5;
414 options->simmer_damping_mult = 0;
415
416 break;
417 default:
418 IGRAPH_ERROR("Unknown DrL template", IGRAPH_EINVAL);
419 break;
420 }
421
422 return 0;
423 }
424
425 /**
426 * \function igraph_layout_drl
427 * The DrL layout generator
428 *
429 * This function implements the force-directed DrL layout generator.
430 * Please see more in the following technical report: Martin, S.,
431 * Brown, W.M., Klavans, R., Boyack, K.W., DrL: Distributed Recursive
432 * (Graph) Layout. SAND Reports, 2008. 2936: p. 1-10.
433 * \param graph The input graph.
434 * \param use_seed Logical scalar, if true, then the coordinates
435 * supplied in the \p res argument are used as starting points.
436 * \param res Pointer to a matrix, the result layout is stored
437 * here. It will be resized as needed.
438 * \param options The parameters to pass to the layout generator.
439 * \param weights Edge weights, pointer to a vector. If this is a null
440 * pointer then every edge will have the same weight.
441 * \param fixed Pointer to a logical vector, or a null pointer. Originally,
442 * this argument was used in the DrL algorithm to keep the nodes marked
443 * with this argument as fixed; fixed nodes would then keep their
444 * positions in the initial stages of the algorithm. However, due to how
445 * the DrL code imported into igraph is organized, it seems that the
446 * argument does not do anything and we are not sure whether this is a
447 * bug or a feature in DrL. We are leaving the argument here in order not
448 * to break the API, but note that at the present stage it has no effect.
449 * \return Error code.
450 *
451 * Time complexity: ???.
452 */
453
igraph_layout_drl(const igraph_t * graph,igraph_matrix_t * res,igraph_bool_t use_seed,igraph_layout_drl_options_t * options,const igraph_vector_t * weights,const igraph_vector_bool_t * fixed)454 int igraph_layout_drl(const igraph_t *graph, igraph_matrix_t *res,
455 igraph_bool_t use_seed,
456 igraph_layout_drl_options_t *options,
457 const igraph_vector_t *weights,
458 const igraph_vector_bool_t *fixed) {
459
460 IGRAPH_HANDLE_EXCEPTIONS(
461 RNG_BEGIN();
462
463 drl::graph neighbors(graph, options, weights);
464 neighbors.init_parms(options);
465 if (use_seed) {
466 IGRAPH_CHECK(igraph_matrix_resize(res, igraph_vcount(graph), 2));
467 neighbors.read_real(res, fixed);
468 }
469 neighbors.draw_graph(res);
470
471 RNG_END();
472 );
473
474 return 0;
475 }
476