Merge lp:~samuel-thiriot-accounts/igraph/add_game_islands into lp:~igraph/igraph/0.6-main-old

[SamThiriot]

As discussed in the igraph-help list, I propose here to add another game which creates networks made of interconnected islands (small ER graphs).

This network generator is especially usefull for benchmarking, as it enables to tune easily the average path length and clustering rate in the graph.

I'm a newbie in bzr, so I hope I made things in the right way.

Added the generator into the C files (games.c, igraph_games.h ), and the relevant interfaces into the R interface folder.

Please let me now if something is wrong !

Regards,

Sam.

[Tamás Nepusz (ntamas)]

Hi Sam,

This one seemed to work, thanks. One of us will review this soon. You'll probably get notified by Launchpad.

Tamas

[SamThiriot (samuel-thiriot-accounts)]

Hi Tamas,

thanks for your help !

Sam.

[Gábor Csárdi (gabor.csardi)]

Thanks for the code! Next time please consider also

1) writing some test cases, and
2) writing the R documentation if you add an R interface.

These are not strictly required for the inclusion of your patch, but they make our lives a lot easier.

review: Approve

=== modified file 'include/igraph_games.h'
--- include/igraph_games.h	2011-05-11 21:44:47 +0000
+++ include/igraph_games.h	2011-05-26 21:28:30 +0000
@@ -162,6 +162,14 @@
 			    igraph_real_t fw_prob, igraph_real_t bw_factor,
 			    igraph_integer_t ambs, igraph_bool_t directed);
 
+
+int igraph_simple_interconnected_islands_game(
+				igraph_t *graph, 
+				igraph_integer_t islands_n, 
+				igraph_integer_t islands_size,
+				igraph_real_t islands_pin, 
+				igraph_integer_t n_inter);
+
 __END_DECLS
 
 #endif

=== modified file 'interfaces/R/igraph/R/games.R'
--- interfaces/R/igraph/R/games.R	2011-05-11 21:44:47 +0000
+++ interfaces/R/igraph/R/games.R	2011-05-26 21:28:30 +0000
@@ -335,3 +335,17 @@
   res
 }
 
+
+simple.interconnected.islands.game <- function(islands.n, islands.size, islands.pin, n.inter) {
+  
+
+  on.exit( .Call("R_igraph_finalizer", PACKAGE="igraph") )
+  .Call(	"R_igraph_simple_interconnected_islands_game", 
+		as.numeric(islands.n), 
+		as.numeric(islands.size),
+        	as.numeric(islands.pin), 
+		as.numeric(n.inter),
+        	PACKAGE="igraph")
+}
+
+

=== modified file 'interfaces/R/src/rinterface.c.in'
--- interfaces/R/src/rinterface.c.in	2011-05-16 16:20:11 +0000
+++ interfaces/R/src/rinterface.c.in	2011-05-26 21:28:30 +0000
@@ -8461,6 +8461,26 @@
   return result;
 }		   
 			 
+
+
+SEXP R_igraph_simple_interconnected_islands_game(SEXP islands_n, SEXP islands_size, SEXP islands_pin, SEXP n_inter) {
+  
+  igraph_t g;
+  igraph_integer_t a=REAL(islands_n)[0];
+  igraph_integer_t b=REAL(islands_size)[0];
+  igraph_real_t c=REAL(islands_pin)[0];
+  igraph_integer_t d=REAL(n_inter)[0];
+  SEXP result;
+  
+  igraph_simple_interconnected_islands_game(&g, a, b, c, d);
+  PROTECT(result=R_igraph_to_SEXP(&g));
+  igraph_destroy(&g);
+  
+  UNPROTECT(1);
+  return result;
+}
+
+
 /***********************************************/
 /* THE REST IS GENERATED BY inger.py           */
 /***********************************************/

=== modified file 'src/games.c'
--- src/games.c	2011-05-15 17:07:38 +0000
+++ src/games.c	2011-05-26 21:28:30 +0000
@@ -2975,3 +2975,151 @@
   IGRAPH_FINALLY_CLEAN(1);
   return 0;
 }
+
+
+
+/**
+ * \ingroup generators
+ * \function igraph_simple_interconnected_islands_game
+ * \brief Generates a random graph made of several interconnected islands, each island being a random graph.
+ * 
+ * \param graph Pointer to an uninitialized graph object.
+ * \param islands_n The number of islands in the graph.
+ * \param islands_size The size of islands in the graph.
+ * \param islands_pin The probability to create each possible edge into each island .
+ * \param n_inter The number of edges to create between two islands .
+
+ * \return Error code:
+ *         \c IGRAPH_EINVAL: invalid parameter
+ *         \c IGRAPH_ENOMEM: there is not enought
+ *         memory for the operation.
+ * 
+ * Time complexity: O(|V|+|E|), the
+ * number of vertices plus the number of edges in the graph.
+ * 
+ */
+int igraph_simple_interconnected_islands_game(
+				igraph_t 		*graph, 
+				igraph_integer_t 	islands_n, 
+				igraph_integer_t 	islands_size,
+				igraph_real_t 		islands_pin, 
+				igraph_integer_t 	n_inter) {
+
+	
+	igraph_vector_t edges=IGRAPH_VECTOR_NULL;
+	igraph_vector_t s=IGRAPH_VECTOR_NULL;
+	int retval=0;
+
+	if (islands_n<0) {
+	IGRAPH_ERROR("Invalid number of islands", IGRAPH_EINVAL);
+	}
+	if (islands_size<0) {
+	IGRAPH_ERROR("Invalid size for islands", IGRAPH_EINVAL);
+	}
+	if (islands_pin<0 || islands_pin>1) {
+	IGRAPH_ERROR("Invalid probability for islands", IGRAPH_EINVAL);
+	}
+	if ( (n_inter<0) || (n_inter>islands_size) ) {
+	IGRAPH_ERROR("Invalid number of inter-islands links", IGRAPH_EINVAL);
+	}
+
+	// how much memory ?
+	int nbNodes = islands_n*islands_size;
+	double maxpossibleedgesPerIsland = ((double)islands_size*((double)islands_size-(double)1))/(double)2;
+	double maxedgesPerIsland = islands_pin*maxpossibleedgesPerIsland;
+	int nbEdgesInterIslands = n_inter*(islands_n*(islands_n-1))/2;
+	double maxedges = maxedgesPerIsland*islands_n + nbEdgesInterIslands;
+
+	// debug&tests : printf("total nodes %d, maxedgesperisland %f, maxedgesinterislands %d, maxedges %f\n", nbNodes, maxedgesPerIsland, nbEdgesInterIslands, maxedges);
+
+	// reserve enough place for all the edges, thanks !
+	IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
+      	IGRAPH_CHECK(igraph_vector_reserve(&edges, maxedges));
+
+	RNG_BEGIN();
+
+	// first create all the islands
+	  
+	int startIsland = 0;
+	int endIsland = 0;
+	int i,j, is;
+	for (is=1; is<=islands_n; is++) { // for each island
+	 
+ 		long int slen;
+      
+		// index for start and end of nodes in this island
+		startIsland = islands_size*(is-1); 
+		endIsland = startIsland+islands_size -1;  
+	
+
+		// debug&tests : printf("start %d,end %d\n", startIsland, endIsland);
+
+		// create the random numbers to be used (into s)
+		IGRAPH_VECTOR_INIT_FINALLY(&s, 0);
+		IGRAPH_CHECK(igraph_vector_reserve(&s, maxedgesPerIsland));
+
+
+
+		double rand;
+		double last=RNG_GEOM(islands_pin);
+		// debug&tests : printf("last=%f \n", last);
+		while (last < maxpossibleedgesPerIsland) { // maxedgesPerIsland
+			IGRAPH_CHECK(igraph_vector_push_back(&s, last));
+			rand = RNG_GEOM(islands_pin);
+			last += rand; //RNG_GEOM(islands_pin);
+			//printf("rand=%f , last=%f \n", rand, last);
+			last += 1;
+		}
+
+	
+
+		// change this to edges !
+		for (i=0; i<igraph_vector_size(&s); i++) {
+
+			long int to=floor((sqrt(8*VECTOR(s)[i]+1)+1)/2);
+			long int from=VECTOR(s)[i]-(((igraph_real_t)to)*(to-1))/2;
+			to += startIsland;
+			from += startIsland;
+			// debug&tests : printf("from %d to %d\n", from, to);
+			igraph_vector_push_back(&edges, from);
+			igraph_vector_push_back(&edges, to);
+		}
+
+		// clear the memory used for random number for this island
+		igraph_vector_destroy(&s);
+		IGRAPH_FINALLY_CLEAN(1);
+
+
+		// create the links with other islands
+		for (i=is+1; i<=islands_n; i++) { // for each other island (not the previous ones)
+				
+			// debug&tests : printf("link islands %d and %d\n", is, i);
+			for (j=0; j<n_inter; j++) { // for each link between islands
+
+				long int from = RNG_UNIF(startIsland, endIsland);
+				long int to = RNG_UNIF((i-1)*islands_size, i*islands_size);
+				//printf("from %d to %d\n", from, to);
+				igraph_vector_push_back(&edges, from);
+				igraph_vector_push_back(&edges, to);
+			}
+			
+		}
+	}
+
+
+
+	RNG_END();
+
+
+	// actually fill the graph object
+	IGRAPH_CHECK(retval=igraph_create(graph, &edges, nbNodes, 0));
+
+	// an clear remaining things
+	igraph_vector_destroy(&edges);
+	IGRAPH_FINALLY_CLEAN(1);
+
+
+	return retval;
+
+}
+