From: Jean-Baptiste Hervé <jean-baptiste.herve@esial.net>
Date: Wed, 1 Aug 2012 09:02:20 +0000 (+0200)
Subject: Platform generation : add the Barabasi-Albert algorithm to build the graph
X-Git-Tag: v3_8~234
X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/9f31e0d16a04b8da74182a1228ec872b191aa6d5

Platform generation : add the Barabasi-Albert algorithm to build the graph
---

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));