From 9f31e0d16a04b8da74182a1228ec872b191aa6d5 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Baptiste=20Herv=C3=A9?= Date: Wed, 1 Aug 2012 11:02:20 +0200 Subject: [PATCH] Platform generation : add the Barabasi-Albert algorithm to build the graph --- include/simgrid/platf_generator.h | 1 + src/surf/platf_generator.c | 23 +++++++++++++++++++++++ 2 files changed, 24 insertions(+) diff --git a/include/simgrid/platf_generator.h b/include/simgrid/platf_generator.h index 13c32debe8..72ff74ed72 100644 --- a/include/simgrid/platf_generator.h +++ b/include/simgrid/platf_generator.h @@ -36,6 +36,7 @@ XBT_PUBLIC(void) platf_graph_interconnect_ring(void); XBT_PUBLIC(void) platf_graph_interconnect_clique(void); XBT_PUBLIC(void) platf_graph_interconnect_uniform(double alpha); XBT_PUBLIC(void) platf_graph_interconnect_exponential(double alpha); +XBT_PUBLIC(void) platf_graph_interconnect_barabasi(void); XBT_PUBLIC(void) platf_graph_promote_to_host(context_node_t node, sg_platf_host_cbarg_t parameters); XBT_PUBLIC(void) platf_graph_promote_to_cluster(context_node_t node, sg_platf_cluster_cbarg_t parameters); diff --git a/src/surf/platf_generator.c b/src/surf/platf_generator.c index bdbfe41bfb..889c14765e 100644 --- a/src/surf/platf_generator.c +++ b/src/surf/platf_generator.c @@ -224,6 +224,29 @@ void platf_graph_interconnect_exponential(double alpha) { } } +void platf_graph_interconnect_barabasi(void) { + /* Create a topology constructed according to the Barabasi-Albert algorithm (follows power laws) + (see Barabasi and Albert, Emergence of scaling in random networks, Science 1999, num 59, p509­-512.) */ + xbt_dynar_t dynar_nodes = NULL; + xbt_node_t first_node = NULL; + xbt_node_t second_node = NULL; + context_node_t node_data = NULL; + unsigned int i,j; + unsigned long sum = 0; + dynar_nodes = xbt_graph_get_nodes(platform_graph); + xbt_dynar_foreach(dynar_nodes, i, first_node) { + xbt_dynar_foreach(dynar_nodes, j, second_node) { + if(j>=i) + break; + node_data = xbt_graph_node_get_data(second_node); + if(sum==0 || RngStream_RandU01(rng_stream) < ((double)(node_data->degree)/ (double)sum)) { + platf_node_connect(first_node, second_node); + sum += 2; + } + } + } +} + void platf_graph_promote_to_host(context_node_t node, sg_platf_host_cbarg_t parameters) { node->kind = HOST; memcpy(&(node->host_parameters), parameters, sizeof(s_sg_platf_host_cbarg_t)); -- 2.20.1