Merge lp:~mvngu/igraph/game-junk into lp:~igraph/igraph/0.6-main-old

[Minh Van Nguyen]

A bunch of documentation fixes. In particular:

* Where possible, clearly document possible values that an argument would accept.

* Clarify the concept of selector and iterator for vertices (and edges).

* Proper citation of the paper (Vitter 1987) for the algorithm on random sampling.

* In the function for random sampling using the algorithm in (Vitter 1987), handle some corner cases that would cause that function to hang indefinitely.

[lp:~mvngu/igraph/game-junk]

2485. By Tamás Nepusz on 2011-05-26

Python: sorted out Graph.assortativity() properly

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

Thanks! This seems mostly fine, except, that I think the Vitter algorithm is supposed to work when l=h. If I remember well.

[lp:~mvngu/igraph/game-junk]

2486. By Gábor Csárdi on 2011-05-26

Clarify the concepts of vertex (edge) selector and iterator.

2487. By Gábor Csárdi on 2011-05-26

Clarify the documentation of igraph_vs_adj().

2488. By Gábor Csárdi on 2011-05-26

Clarify documentation of igraph_vs_nonadj().

2489. By Gábor Csárdi on 2011-05-26

Clarify documentation of igraph_small().

2490. By Gábor Csárdi on 2011-05-26

Clarify documentation of igraph_empty().

2491. By Gábor Csárdi on 2011-05-26

Clarify documentation of igraph_empty_attrs().

2492. By Gábor Csárdi on 2011-05-26

Proper citation of (Vitter 1987) for algorithm for random sampling.

2493. By Gábor Csárdi on 2011-05-26

Handle boundary cases for random sampling with algorithm in (Vitter 1987).

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

OK, I merged everything, after some minor changes.

review: Approve

=== modified file '.bzrignore'
--- .bzrignore	2011-05-17 16:30:25 +0000
+++ .bzrignore	2011-05-22 08:26:01 +0000
@@ -255,6 +255,7 @@
 examples/simple/igraph_preference_game.c.xml
 examples/simple/igraph_psumtree.c.xml
 examples/simple/igraph_radius.c.xml
+examples/simple/igraph_random_sample.c.xml
 examples/simple/igraph_read_graph_dl.c.xml
 examples/simple/igraph_read_graph_graphdb.c.xml
 examples/simple/igraph_read_graph_lgl.c.xml

=== added file 'examples/simple/igraph_random_sample.c'
--- examples/simple/igraph_random_sample.c	1970-01-01 00:00:00 +0000
+++ examples/simple/igraph_random_sample.c	2011-05-22 08:26:01 +0000
@@ -0,0 +1,183 @@
+/* -*- mode: C -*-  */
+/*
+  Test suite for random sampling.
+  Copyright (C) 2011 Minh Van Nguyen <[e-mail]>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 of the License, or
+  (at your option) any later version.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
+  02110-1301 USA
+*/
+
+#include <assert.h>
+#include <igraph.h>
+#include <math.h>
+#include <stdio.h>
+#include <time.h>
+
+#define R_INTEGER(a,b) (igraph_rng_get_integer(&igraph_rng_default, (a), (b)))
+
+/* test parameters */
+typedef struct {
+  igraph_integer_t low;
+  igraph_integer_t high;
+  igraph_integer_t length;
+  int retval;
+} sampling_test_t;
+
+/* Error tests. Don't be afraid to crash the library function.
+ */
+int error_test() {
+  const igraph_integer_t min = -1000;
+  const igraph_integer_t max = 1000;
+  igraph_integer_t low;       /* lower limit */
+  igraph_integer_t high;      /* upper limit */
+  igraph_integer_t length;    /* sample size */
+  igraph_integer_t poolsize;  /* size of candidate pool */
+  igraph_vector_t V;
+  int i, n, ret;
+  sampling_test_t *test;
+
+  igraph_rng_seed(&igraph_rng_default, time(0));
+  igraph_vector_init(&V, /*size*/ 0);
+
+  /* test parameters */
+  /*----------low----high----length----retval----------*/
+  /* lower limit is greater than upper limit */
+  do {
+    high = (igraph_integer_t)R_INTEGER(min, max);
+  } while (high == max);
+  do {
+    low = (igraph_integer_t)R_INTEGER(min, max);
+  } while (low <= high);
+  assert(low > high);
+  length = (igraph_integer_t)R_INTEGER(min, max);
+  sampling_test_t lower_bigger = {low, high, length, IGRAPH_EINVAL};
+  /* lower limit equals upper limit */
+  high = (igraph_integer_t)R_INTEGER(min, max);
+  low = high;
+  length = (igraph_integer_t)R_INTEGER(min, max);
+  sampling_test_t low_is_high = {low, high, length, IGRAPH_EINVAL};
+  /* sample size is greater than size of candidate pool */
+  do {
+    high = (igraph_integer_t)R_INTEGER(min, max);
+  } while (high == min);
+  do {
+    low = (igraph_integer_t)R_INTEGER(min, max);
+  } while (low >= high);
+  assert(low < high);
+  poolsize = (igraph_integer_t)fabs((double)high - (double)low);
+  length = poolsize * poolsize;
+  sampling_test_t sample_size_bigger = {low, high, length, IGRAPH_EINVAL};
+
+  sampling_test_t *all_checks[] = {/* 1 */ &lower_bigger,
+                                   /* 2 */ &low_is_high,
+                                   /* 3 */ &sample_size_bigger};
+
+  /* failure is the mother of success */
+  igraph_set_error_handler(igraph_error_handler_ignore);
+  n = 3;
+  for (i = 0; i < n; i++) {
+    test = all_checks[i];
+    ret = igraph_random_sample(&V, test->low, test->high, test->length);
+    if (ret != test->retval) {
+      printf("Error test no. %d failed.\n", (int)(i + 1));
+      return IGRAPH_FAILURE;
+    }
+  }
+
+  igraph_vector_destroy(&V);
+
+  return IGRAPH_SUCCESS;
+}
+
+/* Get a few random samples and test their properties.
+ */
+int random_sample_test() {
+  const igraph_integer_t min = -1000;
+  const igraph_integer_t max = 1000;
+  igraph_integer_t low;       /* lower limit */
+  igraph_integer_t high;      /* upper limit */
+  igraph_integer_t length;    /* sample size */
+  igraph_integer_t poolsize;  /* size of candidate pool */
+  igraph_real_t sP;           /* population total sum */
+  igraph_real_t ss;           /* sample total sum */
+  igraph_vector_t V;
+  int i;
+
+  igraph_rng_seed(&igraph_rng_default, time(0));
+
+  /* The generated sequence of numbers must be in increasing order. */
+  igraph_vector_init(&V, /*size*/ 0);
+  do {
+    high = (igraph_integer_t)R_INTEGER(min, max);
+  } while (high == min);
+  do {
+    low = (igraph_integer_t)R_INTEGER(min, max);
+  } while (low >= high);
+  poolsize = (igraph_integer_t)fabs((double)high - (double)low);
+  do {
+    length = (igraph_integer_t)R_INTEGER(1, max);
+  } while (length > poolsize);
+  igraph_random_sample(&V, low, high, length);
+  if (length != igraph_vector_size(&V)) {
+    printf("Requested vector length and resulting length mismatch.\n");
+    return IGRAPH_FAILURE;
+  }
+  for (i = 0; i < length - 1; i++) {
+    if (VECTOR(V)[i] >= VECTOR(V)[i+1]) {
+      printf("Sample not in increasing order.\n");
+      return IGRAPH_FAILURE;
+    }
+  }
+  igraph_vector_destroy(&V);
+
+  /* Let P be a candidate pool of positive integers with total sum s_P. */
+  /* Let S be a random sample from P and having total sum s_S. Then we */
+  /* have the bound s_s <= s_P. */
+  igraph_vector_init(&V, /*size*/ 0);
+  low = 1;
+  do {
+    high = (igraph_integer_t)R_INTEGER(low, max);
+  } while (high == low);
+  poolsize = (igraph_integer_t)fabs((double)high - (double)low);
+  do {
+    length = (igraph_integer_t)R_INTEGER(low, max);
+  } while (length > poolsize);
+  igraph_random_sample(&V, low, high, length);
+  /* Use Gauss' formula to sum all consecutive positive integers from 1 */
+  /* up to and including an upper limit. In LaTeX, Gauss' formula is */
+  /* \sum_{i=1}^n i = \frac{n(n+1)}{2} where n is the upper limit. */
+  sP = (high * (high + 1)) / 2;
+  ss = igraph_vector_sum(&V);
+  if (ss > sP) {
+    printf("Sum of sampled sequence exceeds sum of whole population.\n");
+    return IGRAPH_FAILURE;
+  }
+  igraph_vector_destroy(&V);
+
+  return IGRAPH_SUCCESS;
+}
+
+int main() {
+  int ret;
+
+  ret = error_test();
+  if (ret)
+    return IGRAPH_FAILURE;
+  ret = random_sample_test();
+  if (ret)
+    return IGRAPH_FAILURE;
+
+  return IGRAPH_SUCCESS;
+}

=== modified file 'src/iterators.c'
--- src/iterators.c	2011-03-01 20:27:49 +0000
+++ src/iterators.c	2011-05-22 08:26:01 +0000
@@ -41,23 +41,33 @@
  * independently of the graph.</para>
  *
  * <para>While this might sound quite mysterious, it is actually very
- * simple. For example all vertices of a graph can be selected by
- * \ref igraph_vs_all(), and the graph independence means that
- * \ref igraph_vs_all() is not parametrized by a graph object. Ie. 
- * \ref igraph_vs_all() is the \em concept of selecting all vertices
- * of a graph.</para>
- * 
- * <para>This means that for determining the actual vertex id's implied
- * by a vertex selector it needs to be instantiated with a graph
- * object, the instantiation results a vertex iterator.</para>
- * 
- * <para>Some vertex selectors have \em immediate versions, these have
- * prefix <code>igraph_vss</code> instead of <code>igraph_vs</code>, eg. 
- * \ref igraph_vss_all() instead of \ref igraph_vs_all(). 
- * These immediate versions are to be used in the parameter list of the igraph
- * functions, like \ref igraph_degree(). These functions are not
- * associated with any \type igraph_vs_t object, so they have no
- * separate constructors and destructors (destroy functions).</para> 
+ * simple. For example, all vertices of a graph can be selected by
+ * \ref igraph_vs_all() and the graph independence means that
+ * \ref igraph_vs_all() is not parametrized by a graph object. That is,
+ * \ref igraph_vs_all() is the general \em concept of selecting all vertices
+ * of a graph. A vertex selector is then a way to specify the class of vertices
+ * to be visited. The selector might specify that all vertices of a graph or
+ * all the neighbours of a vertex are to be visited. A vertex selector is a
+ * way of saying that you want to visit a bunch of vertices, as opposed to a
+ * vertex iterator which is a concrete plan for visiting each of the
+ * chosen vertices of a specific graph.</para>
+ *
+ * <para>To determine the actual vertex IDs implied by a vertex selector, you
+ * need to apply the concept of selecting vertices to a specific graph object.
+ * This can be accomplished by instantiating a vertex iterator using a
+ * specific vertex selection concept and a specific graph object. The notion
+ * of vertex iterators can be thought of in the following way. Given a
+ * specific graph object and the class of vertices to be visited, a vertex
+ * iterator is a road map, plan or route for how to visit the chosen
+ * vertices.</para>
+ * 
+ * <para>Some vertex selectors have \em immediate versions. These have the
+ * prefix \c igraph_vss instead of \c igraph_vs, e.g. \ref igraph_vss_all()
+ * instead of \ref igraph_vs_all(). The immediate versions are to be used in
+ * the parameter list of the igraph functions, such as \ref igraph_degree().
+ * These functions are not associated with any \type igraph_vs_t object, so
+ * they have no separate constructors and destructors
+ * (destroy functions).</para>
  */ 
 
 /**
@@ -115,19 +125,25 @@
  * All neighboring vertices of a given vertex are selected by this
  * selector. The \c mode argument controls the type of the neighboring 
  * vertices to be selected. The vertices are visited in increasing vertex
- * id order, as of igraph version 0.4.
+ * ID order, as of igraph version 0.4.
  * 
  * \param vs Pointer to an uninitialized vertex selector object.
- * \param vid Vertex id, the center of the neighborhood.
+ * \param vid Vertex ID, the center of the neighborhood.
  * \param mode Decides the type of the neighborhood for directed
- *        graphs. Possible values:
- *        \c IGRAPH_OUT,  all vertices to which there is a directed edge
- *           from \c vid.
- *        \c IGRAPH_IN, all vertices from which there is a directed
- *           edge from \c vid.
- *        \c IGRAPH_ALL, all vertices to which or from which there is
- *           a directed edge from/to \c vid.
- *        This parameter is ignored for undirected graphs.
+ *        graphs. This parameter is ignored for undirected graphs.
+ *        Possible values:
+ *        \clist
+ *        \cli IGRAPH_OUT
+ *          All vertices to which there is a directed edge from \c vid. That
+ *          is, all the out-neighbors of \c vid.
+ *        \cli IGRAPH_IN
+ *          All vertices from which there is a directed edge to \c vid. In
+ *          other words, all the in-neighbors of \c vid.
+ *        \cli IGRAPH_ALL
+ *          All vertices to which or from which there is a directed edge
+ *          from/to \c vid. That is, all the neighbors of \c vid considered
+ *          as if the graph is undirected.
+ *        \endclist
  * \return Error code.
  * 
  * Time complexity: O(1).
@@ -147,19 +163,29 @@
  * 
  * All non-neighboring vertices of a given vertex. The \p mode
  * argument controls the type of neighboring vertices \em not to
- * select.
+ * select. Instead of selecting immediate neighbors of \c vid as is done by
+ * \ref igraph_vs_adj(), the current function selects vertices that are \em not
+ * immediate neighbors of \c vid.
+ *
  * \param vs Pointer to an uninitialized vertex selector object.
- * \param vid Vertex id, the \quote center \endquote of the
+ * \param vid Vertex ID, the \quote center \endquote of the
  *        non-neighborhood.
  * \param mode The type of neighborhood not to select in directed
  *        graphs. Possible values:
- *        \c IGRAPH_OUT, all vertices will be selected except those to
- *           which there is a directed edge from \p vid.
- *        \c IGRAPH_IN, all vertices will be selected except those
- *           from which there is a directed edge to \p vid.
- *        \c IGRAPH_ALL, all vertices will be selected except those 
- *           from or to which there is a directed edge to or from \p
- *           vid. 
+ *        \clist
+ *        \cli IGRAPH_OUT
+ *          All vertices will be selected except those to which there is a
+ *          directed edge from \c vid. That is, we select all vertices
+ *          excluding the out-neighbors of \c vid.
+ *        \cli IGRAPH_IN
+ *          All vertices will be selected except those from which there is a
+ *          directed edge to \c vid. In other words, we select all vertices
+ *          but the in-neighbors of \c vid.
+ *        \cli IGRAPH_ALL
+ *          All vertices will be selected except those from or to which there
+ *          is a directed edge to or from \c vid. That is, we select all
+ *          vertices of \c vid except for its immediate neighbors.
+ *        \endclist
  * \return Error code.
  *
  * Time complexity: O(1).

=== modified file 'src/random.c'
--- src/random.c	2011-05-09 17:54:01 +0000
+++ src/random.c	2011-05-22 08:26:01 +0000
@@ -948,27 +948,44 @@
  * </para><para>
  * This function generates an increasing sequence of random integer
  * numbers from a given interval. The algorithm is taken literally
- * from Jeffrey Scott Vitter: 'An Efficient Algorithm for Sequential
- * Random Sampling', ACM Transactions on Mathematical Software, 13/1,
- * 58--67. This method can be used for generating numbers from a
- * \em very large interval, it is primarily created for randomly
+ * from (Vitter 1987). This method can be used for generating numbers from a
+ * \em very large interval. It is primarily created for randomly
  * selecting some edges from the sometimes huge set of possible edges
  * in a large graph.
- * \param res Pointer to an initialized vector, this will hold the
+ * \param res Pointer to an initialized vector. This will hold the
  *        result. It will be resized to the proper size.
- * \param l The lower limit of the generation interval (inclusive).
- * \param h The upper limit of the generation interval (inclusive).
+ * \param l The lower limit of the generation interval (inclusive). This must
+ *        be less than the upper limit.
+ * \param h The upper limit of the generation interval (inclusive). This must
+ *        be greater than the lower limit.
  * \param length The number of random integers to generate.
- * \return Error code.
+ * \return The error code \c IGRAPH_EINVAL is returned in each of the
+ *         following cases: (1) The given lower limit is greater than the
+ *         given upper limit, i.e. \c l &gt; \c h. (2) The lower limit is
+ *         equal to the upper limit, i.e. \c l = \c h. (3) Assumming that
+ *         \c l &lt; \c h and N is the sample size, the above error code is
+ *         returned if N &gt; |\c h - \c l|, i.e. the sample size exceeds the
+ *         size of the candidate pool.
  *
- * Time complexity: according to the referenced paper, the expected
+ * Time complexity: according to (Vitter 1987), the expected
  * running time is O(length).
+ *
+ * </para><para>
+ * Reference:
+ * \clist
+ * \cli (Vitter 1987)
+ *   J. S. Vitter. An efficient algorithm for sequential random sampling.
+ *   \emb ACM Transactions on Mathematical Software, \eme 13(1):58--67, 1987.
+ * \endclist
+ *
+ * \example examples/simple/igraph_random_sample.c
  */
 
 int igraph_random_sample(igraph_vector_t *res, igraph_integer_t l, igraph_integer_t h, 
 			 igraph_integer_t length) {
   igraph_real_t N=h-l+1;
   igraph_real_t n=length;
+  igraph_integer_t poolsize;  /* size of candidate pool */
   int retval;
 
   igraph_real_t nreal=length;
@@ -980,7 +997,17 @@
   igraph_real_t negalphainv=-13;
   igraph_real_t threshold=-negalphainv*n;
   igraph_real_t S;
-  
+
+  /* getting back some sense of sanity */
+  if (l > h)
+    IGRAPH_ERROR("Lower limit is greater than upper limit", IGRAPH_EINVAL);
+  if (l == h)
+    IGRAPH_ERROR("Lower limit equals upper limit", IGRAPH_EINVAL);
+  /* now we know that l < h */
+  poolsize = (igraph_integer_t)fabs((double)h - (double)l);
+  if (length > poolsize)
+    IGRAPH_ERROR("Sample size exceeds size of candidate pool", IGRAPH_EINVAL);
+
   igraph_vector_clear(res);
   IGRAPH_CHECK(igraph_vector_reserve(res, length));  
 

=== modified file 'src/structure_generators.c'
--- src/structure_generators.c	2011-05-16 11:23:07 +0000
+++ src/structure_generators.c	2011-05-22 08:26:01 +0000
@@ -1028,7 +1028,7 @@
 
 /**
  * \function igraph_small
- * \brief Shorthand to create a short graph, giving the edges as arguments
+ * \brief Shorthand to create a short graph, giving the edges as arguments.
  * 
  * </para><para>
  * This function is handy when a relatively small graph needs to be created. 
@@ -1040,11 +1040,17 @@
  * the highest value of the 'int' type can be created this way. If you
  * give larger values then the result is undefined.
  * 
- * \param graph Pointer to an uninitialized graph object, the result
+ * \param graph Pointer to an uninitialized graph object. The result
  *        will be stored here.
- * \param n The number of vertices in the graph, an integer.
- * \param directed Logical constant, gives whether the graph should be
- *        directed. 
+ * \param n The number of vertices in the graph; a nonnegative integer.
+ * \param directed Logical constant; gives whether the graph should be
+ *        directed. Supported values are:
+ *        \clist
+ *        \cli IGRAPH_DIRECTED
+ *          The graph to be created will be \em directed.
+ *        \cli IGRAPH_UNDIRECTED
+ *          The graph to be created will be \em undirected.
+ *        \endclist
  * \param ... The additional arguments giving the edges of the
  *        graph. Don't forget to supply an additional '-1' after the last
  *        (meaningful) argument.

=== modified file 'src/type_indexededgelist.c'
--- src/type_indexededgelist.c	2011-05-05 10:25:07 +0000
+++ src/type_indexededgelist.c	2011-05-22 08:26:01 +0000
@@ -61,7 +61,14 @@
  * \param graph Pointer to a not-yet initialized graph object.
  * \param n The number of vertices in the graph, a non-negative
  *          integer number is expected.
- * \param directed Whether the graph is directed or not.
+ * \param directed Boolean; whether the graph is directed or not. Supported
+ *        values are:
+ *        \clist
+ *        \cli IGRAPH_DIRECTED
+ *          The graph will be \em directed.
+ *        \cli IGRAPH_UNDIRECTED
+ *          The graph will be \em undirected.
+ *        \endclist
  * \return Error code:
  *         \c IGRAPH_EINVAL: invalid number of vertices.
  * 
@@ -83,12 +90,19 @@
  * </para><para>
  * Use this instead of \ref igraph_empty() if you wish to add some graph
  * attributes right after initialization. This function is currently
- * not very interesting for the ordinary user, just supply 0 here or 
+ * not very interesting for the ordinary user. Just supply 0 here or 
  * use \ref igraph_empty().
  * \param graph Pointer to a not-yet initialized graph object.
- * \param n The number of vertices in the graph, a non-negative
+ * \param n The number of vertices in the graph; a non-negative
  *          integer number is expected.
- * \param directed Whether the graph is directed or not.
+ * \param directed Boolean; whether the graph is directed or not. Supported
+ *        values are:
+ *        \clist
+ *        \cli IGRAPH_DIRECTED
+ *          Create a \em directed graph.
+ *        \cli IGRAPH_UNDIRECTED
+ *          Create an \em undirected graph.
+ *        \endclist
  * \param attr The attributes. 
  * \return Error code:
  *         \c IGRAPH_EINVAL: invalid number of vertices.

=== modified file 'tests/other.at'
--- tests/other.at	2011-05-09 17:54:01 +0000
+++ tests/other.at	2011-05-22 08:26:01 +0000
@@ -36,6 +36,11 @@
 AT_COMPILE_CHECK([simple/mt.c])
 AT_CLEANUP
 
+AT_SETUP([Random sampling from consecutive sequence:])
+AT_KEYWORDS([random sampling])
+AT_COMPILE_CHECK([simple/igraph_random_sample.c])
+AT_CLEANUP
+
 AT_SETUP([Fisher-Yates shuffle:])
 AT_KEYWORDS([Fisher-Yates shuffle random permutation])
 AT_COMPILE_CHECK([simple/igraph_fisher_yates_shuffle.c])