Re: [igraph] Simple random tree generation

[Tamás Nepusz]

> I'm new to igraph and I'm looking to create random tree with 0 to 4 sons for 
> each node for example.
> I was wondering if this is possible with igraph
Yes, it is, but most of the hard work must be done by you and not by igraph (as 
igraph can only generate regular trees as a built-in function). Basically, you 
have to generate the edge list yourself and then pass it to igraph_create.

Something like this (totally untested, but you get the idea):


int create_tree(igraph_t* graph, int desired_number_of_non_leaf_nodes, int 
min_children, int max_children) {
  igraph_vector_t edgelist;
  int next_parent = 0, next_child = 1, i;

  igraph_vector_init(&edgelist, 0);

  while (next_parent < desired_number_of_non_leaf_nodes) {
    int num_children = rand() % (max_children - min_children + 1) + 
min_children;

    if (next_parent >= next_child) {
      /* You may simply break out of the loop here instead of printing an error 
*/
      IGRAPH_ERROR("ran out of potential parent nodes", IGRAPH_EINVAL);
    }

    for (i = 0; i < num_children; i++) {
      IGRAPH_CHECK(igraph_vector_push_back(&edgelist, next_parent));
      IGRAPH_CHECK(igraph_vector_push_back(&edgelist, next_child));
      next_child++;
    }

    next_parent++;
  }

  igraph_create(graph, edgelist, 0, 0);

  return IGRAPH_SUCCESS;
}

Usage:

igraph_t graph;

srand(time(0));
create_tree(&graph, 123, 0, 4);

-- 
Tamas