int igraph_adjlist_simplify(igraph_adjlist_t *al) {
  long int i;
  long int n=al->length;
  igraph_vector_t mark;
  IGRAPH_VECTOR_INIT_FINALLY(&mark, n);
  for (i=0; i<n; i++) {
    igraph_vector_t *v=&al->adjs[i];
    long int j, l=igraph_vector_size(v);
    VECTOR(mark)[i] = i+1;
    for (j=0; j<l; /* nothing */) {
      long int e=VECTOR(*v)[j];
      if (VECTOR(mark)[e] != i+1) {
	VECTOR(mark)[e]=i+1;
	j++;
      } else {
	VECTOR(*v)[j] = igraph_vector_tail(v);
	igraph_vector_pop_back(v);
	l--;
      }
    }
  }
  
  igraph_vector_destroy(&mark);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

int igraph_vector_rank(const igraph_vector_t *v, igraph_vector_t *res,
		       long int nodes) {
  
  igraph_vector_t rad;
  igraph_vector_t ptr;
  long int edges = igraph_vector_size(v);
  long int i, c=0;
  
  IGRAPH_VECTOR_INIT_FINALLY(&rad, nodes);
  IGRAPH_VECTOR_INIT_FINALLY(&ptr, edges);
  IGRAPH_CHECK(igraph_vector_resize(res, edges));
	       
  for (i=0; i<edges; i++) {
    long int elem=VECTOR(*v)[i];
    VECTOR(ptr)[i] = VECTOR(rad)[elem];
    VECTOR(rad)[elem] = i+1;
  }
  
  for (i=0; i<nodes; i++) {
    long int p=VECTOR(rad)[i];
    while (p != 0) {      
      VECTOR(*res)[p-1]=c++;
      p=VECTOR(ptr)[p-1];
    }
  }

  igraph_vector_destroy(&ptr);
  igraph_vector_destroy(&rad);
  IGRAPH_FINALLY_CLEAN(2);
  return 0;
}

int igraph_is_separator(const igraph_t *graph, 
			const igraph_vs_t candidate,
			igraph_bool_t *res) {

  long int no_of_nodes=igraph_vcount(graph);
  igraph_vector_bool_t removed;
  igraph_dqueue_t Q;
  igraph_vector_t neis;
  igraph_vit_t vit;

  IGRAPH_CHECK(igraph_vit_create(graph, candidate, &vit));
  IGRAPH_FINALLY(igraph_vit_destroy, &vit);
  IGRAPH_CHECK(igraph_vector_bool_init(&removed, no_of_nodes));
  IGRAPH_FINALLY(igraph_vector_bool_destroy, &removed);
  IGRAPH_CHECK(igraph_dqueue_init(&Q, 100));
  IGRAPH_FINALLY(igraph_dqueue_destroy, &Q);
  IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);

  IGRAPH_CHECK(igraph_i_is_separator(graph, &vit, -1, res, &removed, 
				     &Q, &neis, no_of_nodes));

  igraph_vector_destroy(&neis);
  igraph_dqueue_destroy(&Q);
  igraph_vector_bool_destroy(&removed);
  igraph_vit_destroy(&vit);
  IGRAPH_FINALLY_CLEAN(4);

  return 0;
}

int igraph_get_edgelist(const igraph_t *graph, igraph_vector_t *res, igraph_bool_t bycol) {

  igraph_eit_t edgeit;
  long int no_of_edges=igraph_ecount(graph);
  long int vptr=0;
  igraph_integer_t from, to;
  
  IGRAPH_CHECK(igraph_vector_resize(res, no_of_edges*2));
  IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_ID),
				 &edgeit));
  IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
  
  if (bycol) {
    while (!IGRAPH_EIT_END(edgeit)) {
      igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &from, &to);
      VECTOR(*res)[vptr]=from;
      VECTOR(*res)[vptr+no_of_edges]=to;
      vptr++;
      IGRAPH_EIT_NEXT(edgeit);
    }
  } else {
    while (!IGRAPH_EIT_END(edgeit)) {
      igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &from, &to);
      VECTOR(*res)[vptr++]=from;
      VECTOR(*res)[vptr++]=to;
      IGRAPH_EIT_NEXT(edgeit);
    }
  }
  
  igraph_eit_destroy(&edgeit);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

int igraph_i_cliquer_callback(const igraph_t *graph,
                    igraph_integer_t min_size, igraph_integer_t max_size,
                    igraph_clique_handler_t *cliquehandler_fn, void *arg)
{
    graph_t *g;
    struct callback_data cd;
    igraph_integer_t vcount = igraph_vcount(graph);

    if (vcount == 0)
        return IGRAPH_SUCCESS;

    if (min_size <= 0) min_size = 1;
    if (max_size <= 0) max_size = 0;

    if (max_size > 0 && max_size < min_size)
        IGRAPH_ERROR("max_size must not be smaller than min_size", IGRAPH_EINVAL);

    igraph_to_cliquer(graph, &g);
    IGRAPH_FINALLY(graph_free, g);

    cd.handler = cliquehandler_fn;
    cd.arg = arg;
    igraph_cliquer_opt.user_data = &cd;
    igraph_cliquer_opt.user_function = &callback_callback;

    CLIQUER_INTERRUPTABLE(clique_unweighted_find_all(g, min_size, max_size, /* maximal= */ FALSE, &igraph_cliquer_opt));

    graph_free(g);
    IGRAPH_FINALLY_CLEAN(1);

    return IGRAPH_SUCCESS;
}

int igraph_i_weighted_clique_number(const igraph_t *graph,
                    const igraph_vector_t *vertex_weights, igraph_real_t *res)
{
    graph_t *g;
    igraph_integer_t vcount = igraph_vcount(graph);

    if (vcount == 0) {
        *res = 0;
        return IGRAPH_SUCCESS;
    }

    igraph_to_cliquer(graph, &g);
    IGRAPH_FINALLY(graph_free, g);

    IGRAPH_CHECK(set_weights(vertex_weights, g));

    igraph_cliquer_opt.user_function = NULL;

    /* we are not using a callback function, thus this is not interruptable */
    *res = clique_max_weight(g, &igraph_cliquer_opt);

    graph_free(g);
    IGRAPH_FINALLY_CLEAN(1);

    return IGRAPH_SUCCESS;
}

int igraph_inclist_init(const igraph_t *graph, 
			      igraph_inclist_t *il, 
			      igraph_neimode_t mode) {
  long int i;

  if (mode != IGRAPH_IN && mode != IGRAPH_OUT && mode != IGRAPH_ALL) {
    IGRAPH_ERROR("Cannot create incidence list view", IGRAPH_EINVMODE);
  }

  if (!igraph_is_directed(graph)) { mode=IGRAPH_ALL; }

  il->length=igraph_vcount(graph);
  il->incs=igraph_Calloc(il->length, igraph_vector_t);
  if (il->incs == 0) {
    IGRAPH_ERROR("Cannot create incidence list view", IGRAPH_ENOMEM);
  }

  IGRAPH_FINALLY(igraph_inclist_destroy, il);  
  for (i=0; i<il->length; i++) {
    IGRAPH_ALLOW_INTERRUPTION();
    IGRAPH_CHECK(igraph_vector_init(&il->incs[i], 0));
    IGRAPH_CHECK(igraph_incident(graph, &il->incs[i], i, mode));
  }
  
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/* Shrinks communities into single vertices, keeping all the edges.
 * This method is internal because it destroys the graph in-place and
 * creates a new one -- this is fine for the multilevel community
 * detection where a copy of the original graph is used anyway.
 * The membership vector will also be rewritten by the underlying
 * igraph_membership_reindex call */
int igraph_i_multilevel_shrink(igraph_t *graph, igraph_vector_t *membership) {
  igraph_vector_t edges;
  long int no_of_nodes = igraph_vcount(graph);
  long int no_of_edges = igraph_ecount(graph);
  igraph_bool_t directed = igraph_is_directed(graph);

  long int i;
  igraph_eit_t eit;

  if (no_of_nodes == 0)
    return 0;

  if (igraph_vector_size(membership) < no_of_nodes) {
    IGRAPH_ERROR("cannot shrink graph, membership vector too short",
        IGRAPH_EINVAL);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&edges, no_of_edges * 2);

  IGRAPH_CHECK(igraph_reindex_membership(membership, 0));

  /* Create the new edgelist */
  igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_ID), &eit);
  IGRAPH_FINALLY(igraph_eit_destroy, &eit);
  i = 0;
  while (!IGRAPH_EIT_END(eit)) {
    igraph_integer_t from, to;
    IGRAPH_CHECK(igraph_edge(graph, IGRAPH_EIT_GET(eit), &from, &to));
    VECTOR(edges)[i++] = VECTOR(*membership)[(long int) from];
    VECTOR(edges)[i++] = VECTOR(*membership)[(long int) to];
    IGRAPH_EIT_NEXT(eit);
  }
  igraph_eit_destroy(&eit);
  IGRAPH_FINALLY_CLEAN(1);

  /* Create the new graph */
  igraph_destroy(graph);
  no_of_nodes = (long int) igraph_vector_max(membership)+1;
  IGRAPH_CHECK(igraph_create(graph, &edges, (igraph_integer_t) no_of_nodes,
			     directed));

  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);

  return 0;
}

int igraph_i_weighted_cliques(const igraph_t *graph,
                    const igraph_vector_t *vertex_weights, igraph_vector_ptr_t *res,
                    igraph_real_t min_weight, igraph_real_t max_weight, igraph_bool_t maximal)
{
    graph_t *g;
    igraph_integer_t vcount = igraph_vcount(graph);

    if (vcount == 0) {
        igraph_vector_ptr_clear(res);
        return IGRAPH_SUCCESS;
    }

    if (min_weight != (int) min_weight) {
        IGRAPH_WARNING("Only integer vertex weights are supported; the minimum weight will be truncated to its integer part");
        min_weight  = (int) min_weight;
    }

    if (max_weight != (int) max_weight) {
        IGRAPH_WARNING("Only integer vertex weights are supported; the maximum weight will be truncated to its integer part");
        max_weight = (int) max_weight;
    }

    if (min_weight <= 0) min_weight = 1;
    if (max_weight <= 0) max_weight = 0;

    if (max_weight > 0 && max_weight < min_weight)
        IGRAPH_ERROR("max_weight must not be smaller than min_weight", IGRAPH_EINVAL);

    igraph_to_cliquer(graph, &g);
    IGRAPH_FINALLY(graph_free, g);   

    IGRAPH_CHECK(set_weights(vertex_weights, g));

    igraph_vector_ptr_clear(res);
    igraph_cliquer_opt.user_data = res;
    igraph_cliquer_opt.user_function = &collect_cliques_callback;

    IGRAPH_FINALLY(free_clique_list, res);
    CLIQUER_INTERRUPTABLE(clique_find_all(g, min_weight, max_weight, maximal, &igraph_cliquer_opt));
    IGRAPH_FINALLY_CLEAN(1);

    graph_free(g);
    IGRAPH_FINALLY_CLEAN(1);

    return IGRAPH_SUCCESS;
}

int igraph_adjlist_init_complementer(const igraph_t *graph,
				       igraph_adjlist_t *al, 
				       igraph_neimode_t mode,
				       igraph_bool_t loops) {
  long int i, j, k, n;
  igraph_bool_t* seen;
  igraph_vector_t vec;

  if (mode != IGRAPH_IN && mode != IGRAPH_OUT && mode != IGRAPH_ALL) {
    IGRAPH_ERROR("Cannot create complementer adjlist view", IGRAPH_EINVMODE);
  }

  if (!igraph_is_directed(graph)) { mode=IGRAPH_ALL; }

  al->length=igraph_vcount(graph);
  al->adjs=igraph_Calloc(al->length, igraph_vector_t);
  if (al->adjs == 0) {
    IGRAPH_ERROR("Cannot create complementer adjlist view", IGRAPH_ENOMEM);
  }

  IGRAPH_FINALLY(igraph_adjlist_destroy, al);

  n=al->length;
  seen=igraph_Calloc(n, igraph_bool_t);
  if (seen==0) {
    IGRAPH_ERROR("Cannot create complementer adjlist view", IGRAPH_ENOMEM);
  }
  IGRAPH_FINALLY(igraph_free, seen);

  IGRAPH_VECTOR_INIT_FINALLY(&vec, 0);

  for (i=0; i<al->length; i++) {
    IGRAPH_ALLOW_INTERRUPTION();
    igraph_neighbors(graph, &vec, i, mode);
    memset(seen, 0, sizeof(igraph_bool_t)*al->length);
    n=al->length;
    if (!loops) { seen[i] = 1; n--; }
    for (j=0; j<igraph_vector_size(&vec); j++) {
      if (! seen [ (long int) VECTOR(vec)[j] ] ) {
	n--;
	seen[ (long int) VECTOR(vec)[j] ] = 1;
      }
    }
    IGRAPH_CHECK(igraph_vector_init(&al->adjs[i], n));
    for (j=0, k=0; k<n; j++) {
      if (!seen[j]) {
	VECTOR(al->adjs[i])[k++] = j;
      }
    }
  }

  igraph_Free(seen);
  igraph_vector_destroy(&vec);
  IGRAPH_FINALLY_CLEAN(3);
  return 0;
}

int igraph_i_separators_store(igraph_vector_ptr_t *separators, 
			      const igraph_adjlist_t *adjlist,
			      igraph_vector_t *components, 
			      igraph_vector_t *leaveout, 
			      unsigned long int *mark, 
			      igraph_vector_t *sorter) {
  
  /* We need to stote N(C), the neighborhood of C, but only if it is 
   * not already stored among the separators.
   */
  
  long int cptr=0, next, complen=igraph_vector_size(components);

  while (cptr < complen) {
    long int saved=cptr;
    igraph_vector_clear(sorter);

    /* Calculate N(C) for the next C */

    while ( (next=(long int) VECTOR(*components)[cptr++]) != -1) {
      VECTOR(*leaveout)[next] = *mark;
    }
    cptr=saved;

    while ( (next=(long int) VECTOR(*components)[cptr++]) != -1) {
      igraph_vector_int_t *neis=igraph_adjlist_get(adjlist, next);
      long int j, nn=igraph_vector_int_size(neis);
      for (j=0; j<nn; j++) {
	long int nei=(long int) VECTOR(*neis)[j];
	if (VECTOR(*leaveout)[nei] != *mark) {
	  igraph_vector_push_back(sorter, nei);
	  VECTOR(*leaveout)[nei] = *mark;
	}
      }    
    }
    igraph_vector_sort(sorter);

    UPDATEMARK();

    /* Add it to the list of separators, if it is new */

    if (igraph_i_separators_newsep(separators, sorter)) {
      igraph_vector_t *newc=igraph_Calloc(1, igraph_vector_t);
      if (!newc) {
	IGRAPH_ERROR("Cannot calculate minimal separators", IGRAPH_ENOMEM);
      }
      IGRAPH_FINALLY(igraph_free, newc);
      igraph_vector_copy(newc, sorter);
      IGRAPH_FINALLY(igraph_vector_destroy, newc);
      IGRAPH_CHECK(igraph_vector_ptr_push_back(separators, newc));
      IGRAPH_FINALLY_CLEAN(2);      
    }
  } /* while cptr < complen */

  return 0;
}

int igraph_i_maximum_bipartite_matching_unweighted_relabel(const igraph_t* graph,
    const igraph_vector_bool_t* types, igraph_vector_t* labels,
    igraph_vector_long_t* match, igraph_bool_t smaller_set) {
  long int i, j, n, no_of_nodes = igraph_vcount(graph), matched_to;
  igraph_dqueue_long_t q;
  igraph_vector_t neis;

  debug("Running global relabeling.\n");

  /* Set all the labels to no_of_nodes first */
  igraph_vector_fill(labels, no_of_nodes);

  /* Allocate vector for neighbors */
  IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);

  /* Create a FIFO for the BFS and initialize it with the unmatched rows
   * (i.e. members of the larger set) */
  IGRAPH_CHECK(igraph_dqueue_long_init(&q, 0));
  IGRAPH_FINALLY(igraph_dqueue_long_destroy, &q);
  for (i = 0; i < no_of_nodes; i++) {
    if (VECTOR(*types)[i] != smaller_set && VECTOR(*match)[i] == -1) {
      IGRAPH_CHECK(igraph_dqueue_long_push(&q, i));
      VECTOR(*labels)[i] = 0;
    }
  }

  /* Run the BFS */
  while (!igraph_dqueue_long_empty(&q)) {
    long int v = igraph_dqueue_long_pop(&q);
    long int w;

    IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) v,
				  IGRAPH_ALL));

    n = igraph_vector_size(&neis);
    //igraph_vector_shuffle(&neis);
    for (j = 0; j < n; j++) {
      w = (long int) VECTOR(neis)[j];
      if (VECTOR(*labels)[w] == no_of_nodes) {
        VECTOR(*labels)[w] = VECTOR(*labels)[v] + 1;
        matched_to = VECTOR(*match)[w];
        if (matched_to != -1 && VECTOR(*labels)[matched_to] == no_of_nodes) {
          IGRAPH_CHECK(igraph_dqueue_long_push(&q, matched_to));
          VECTOR(*labels)[matched_to] = VECTOR(*labels)[w] + 1;
        }
      }
    }
  }
  printf("Inside relabel : ");
  igraph_vector_print(labels);
  igraph_dqueue_long_destroy(&q);
  igraph_vector_destroy(&neis);
  IGRAPH_FINALLY_CLEAN(2);

  return IGRAPH_SUCCESS;
}

int igraph_complementer(igraph_t *res, const igraph_t *graph, 
			igraph_bool_t loops) {

  long int no_of_nodes=igraph_vcount(graph);
  igraph_vector_t edges;
  igraph_vector_t neis;
  long int i, j;
  long int zero=0, *limit;

  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);

  if (igraph_is_directed(graph)) {
    limit=&zero;
  } else {
    limit=&i;
  }
  
  for (i=0; i<no_of_nodes; i++) {
    IGRAPH_ALLOW_INTERRUPTION();
    IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) i, 
				  IGRAPH_OUT));
    if (loops) {
      for (j=no_of_nodes-1; j>=*limit; j--) {
	if (igraph_vector_empty(&neis) || j>igraph_vector_tail(&neis)) {
	  IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
	  IGRAPH_CHECK(igraph_vector_push_back(&edges, j));
	} else {
	  igraph_vector_pop_back(&neis);
	}
      }
    } else {
      for (j=no_of_nodes-1; j>=*limit; j--) {
	if (igraph_vector_empty(&neis) || j>igraph_vector_tail(&neis)) {
	  if (i!=j) {
	    IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
	    IGRAPH_CHECK(igraph_vector_push_back(&edges, j));
	  }
	} else {
	  igraph_vector_pop_back(&neis);
	}
      }
    }      
  }
  
  IGRAPH_CHECK(igraph_create(res, &edges, (igraph_integer_t) no_of_nodes, 
			     igraph_is_directed(graph)));  
  igraph_vector_destroy(&edges);
  igraph_vector_destroy(&neis);
  IGRAPH_I_ATTRIBUTE_DESTROY(res);
  IGRAPH_I_ATTRIBUTE_COPY(res, graph, /*graph=*/1, /*vertex=*/1, /*edge=*/0);
  IGRAPH_FINALLY_CLEAN(2);
  return 0;
}

int igraph_i_maximal_or_largest_cliques_or_indsets(const igraph_t *graph,
                                        igraph_vector_ptr_t *res,
                                        igraph_integer_t *clique_number,
                                        igraph_bool_t keep_only_largest,
                                        igraph_bool_t complementer) {
  igraph_i_max_ind_vsets_data_t clqdata;
  long int no_of_nodes = igraph_vcount(graph), i;

  if (igraph_is_directed(graph))
    IGRAPH_WARNING("directionality of edges is ignored for directed graphs");

  clqdata.matrix_size=no_of_nodes;
  clqdata.keep_only_largest=keep_only_largest;

  if (complementer)
    IGRAPH_CHECK(igraph_adjlist_init_complementer(graph, &clqdata.adj_list, IGRAPH_ALL, 0));
  else
    IGRAPH_CHECK(igraph_adjlist_init(graph, &clqdata.adj_list, IGRAPH_ALL));
  IGRAPH_FINALLY(igraph_adjlist_destroy, &clqdata.adj_list);

  clqdata.IS = igraph_Calloc(no_of_nodes, igraph_integer_t);
  if (clqdata.IS == 0)
    IGRAPH_ERROR("igraph_i_maximal_or_largest_cliques_or_indsets failed", IGRAPH_ENOMEM);
  IGRAPH_FINALLY(igraph_free, clqdata.IS);

  IGRAPH_VECTOR_INIT_FINALLY(&clqdata.deg, no_of_nodes);
  for (i=0; i<no_of_nodes; i++)
    VECTOR(clqdata.deg)[i] = igraph_vector_size(igraph_adjlist_get(&clqdata.adj_list, i));

  clqdata.buckets = igraph_Calloc(no_of_nodes+1, igraph_set_t);
  if (clqdata.buckets == 0)
    IGRAPH_ERROR("igraph_maximal_or_largest_cliques_or_indsets failed", IGRAPH_ENOMEM);
  IGRAPH_FINALLY(igraph_i_free_set_array, clqdata.buckets);

  for (i=0; i<no_of_nodes; i++)
    IGRAPH_CHECK(igraph_set_init(&clqdata.buckets[i], 0));

  if (res) igraph_vector_ptr_clear(res);
  
  /* Do the show */
  clqdata.largest_set_size=0;
  IGRAPH_CHECK(igraph_i_maximal_independent_vertex_sets_backtrack(graph, res, &clqdata, 0));

  /* Cleanup */
  for (i=0; i<no_of_nodes; i++) igraph_set_destroy(&clqdata.buckets[i]);
  igraph_adjlist_destroy(&clqdata.adj_list);
  igraph_vector_destroy(&clqdata.deg);
  igraph_free(clqdata.IS);
  igraph_free(clqdata.buckets);
  IGRAPH_FINALLY_CLEAN(4);

  if (clique_number) *clique_number = clqdata.largest_set_size;
  return 0;
}

int igraph_random_walk(const igraph_t *graph, igraph_vector_t *walk,
		       igraph_integer_t start, igraph_neimode_t mode,
		       igraph_integer_t steps,
		       igraph_random_walk_stuck_t stuck) {

  /* TODO:
     - multiple walks potentially from multiple start vertices
     - weights
  */

  igraph_lazy_adjlist_t adj;
  igraph_integer_t vc = igraph_vcount(graph);
  igraph_integer_t i;

  if (start < 0 || start >= vc) {
    IGRAPH_ERROR("Invalid start vertex", IGRAPH_EINVAL);
  }
  if (steps < 0) {
    IGRAPH_ERROR("Invalid number of steps", IGRAPH_EINVAL);
  }

  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph, &adj, mode,
					IGRAPH_DONT_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &adj);

  IGRAPH_CHECK(igraph_vector_resize(walk, steps));

  RNG_BEGIN();

  VECTOR(*walk)[0] = start;
  for (i = 1; i < steps; i++) {
    igraph_vector_t *neis;
    igraph_integer_t nn;
    neis = igraph_lazy_adjlist_get(&adj, start);
    nn = igraph_vector_size(neis);

    if (IGRAPH_UNLIKELY(nn == 0)) {
      igraph_vector_resize(walk, i);
      if (stuck == IGRAPH_RANDOM_WALK_STUCK_RETURN) {
	break;
      } else {
	IGRAPH_ERROR("Random walk got stuck", IGRAPH_ERWSTUCK);
      }
    }
    start = VECTOR(*walk)[i] = VECTOR(*neis)[ RNG_INTEGER(0, nn - 1) ];
  }

  RNG_END();

  igraph_lazy_adjlist_destroy(&adj);
  IGRAPH_FINALLY_CLEAN(1);

  return 0;
}

/**
 * \ingroup structural
 * \function igraph_similarity_jaccard
 * \brief Jaccard similarity coefficient for the given vertices.
 *
 * </para><para>
 * The Jaccard similarity coefficient of two vertices is the number of common
 * neighbors divided by the number of vertices that are neighbors of at
 * least one of the two vertices being considered. This function calculates
 * the pairwise Jaccard similarities for some (or all) of the vertices.
 *
 * \param graph The graph object to analyze
 * \param res Pointer to a matrix, the result of the calculation will
 *        be stored here. The number of its rows and columns is the same
 *        as the number of vertex ids in \p vids.
 * \param vids The vertex ids of the vertices for which the
 *        calculation will be done.
 * \param mode The type of neighbors to be used for the calculation in
 *        directed graphs. Possible values:
 *        \clist
 *        \cli IGRAPH_OUT
 *          the outgoing edges will be considered for each node.
 *        \cli IGRAPH_IN
 *          the incoming edges will be considered for each node.
 *        \cli IGRAPH_ALL
 *          the directed graph is considered as an undirected one for the
 *          computation.
 *        \endclist
 * \param loops Whether to include the vertices themselves in the neighbor
 *        sets.
 * \return Error code:
 *        \clist
 *        \cli IGRAPH_ENOMEM
 *           not enough memory for temporary data.
 *        \cli IGRAPH_EINVVID
 *           invalid vertex id passed.
 *        \cli IGRAPH_EINVMODE
 *           invalid mode argument.
 *        \endclist
 * 
 * Time complexity: O(|V|^2 d),
 * |V| is the number of vertices in the vertex iterator given, d is the
 * (maximum) degree of the vertices in the graph.
 *
 * \sa \ref igraph_similarity_dice(), a measure very similar to the Jaccard
 *   coefficient
 * 
 * \example examples/simple/igraph_similarity.c
 */
int igraph_similarity_jaccard(const igraph_t *graph, igraph_matrix_t *res,
    const igraph_vs_t vids, igraph_neimode_t mode, igraph_bool_t loops) {
  igraph_lazy_adjlist_t al;
  igraph_vit_t vit, vit2;
  long int i, j, k;
  long int len_union, len_intersection;
  igraph_vector_t *v1, *v2;

  IGRAPH_CHECK(igraph_vit_create(graph, vids, &vit));
  IGRAPH_FINALLY(igraph_vit_destroy, &vit);
  IGRAPH_CHECK(igraph_vit_create(graph, vids, &vit2));
  IGRAPH_FINALLY(igraph_vit_destroy, &vit2);

  IGRAPH_CHECK(igraph_lazy_adjlist_init(graph, &al, mode, IGRAPH_SIMPLIFY));
  IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &al);

  IGRAPH_CHECK(igraph_matrix_resize(res, IGRAPH_VIT_SIZE(vit), IGRAPH_VIT_SIZE(vit)));

  if (loops) {
    for (IGRAPH_VIT_RESET(vit); !IGRAPH_VIT_END(vit); IGRAPH_VIT_NEXT(vit)) {
      i=IGRAPH_VIT_GET(vit);
      v1=igraph_lazy_adjlist_get(&al, (igraph_integer_t) i);
      if (!igraph_vector_binsearch(v1, i, &k))
        igraph_vector_insert(v1, k, i);
    }
  }

  for (IGRAPH_VIT_RESET(vit), i=0;
    !IGRAPH_VIT_END(vit); IGRAPH_VIT_NEXT(vit), i++) {
    MATRIX(*res, i, i) = 1.0;
    for (IGRAPH_VIT_RESET(vit2), j=0;
      !IGRAPH_VIT_END(vit2); IGRAPH_VIT_NEXT(vit2), j++) {
      if (j <= i)
        continue;
      v1=igraph_lazy_adjlist_get(&al, IGRAPH_VIT_GET(vit));
      v2=igraph_lazy_adjlist_get(&al, IGRAPH_VIT_GET(vit2));
      igraph_i_neisets_intersect(v1, v2, &len_union, &len_intersection);
      if (len_union > 0)
        MATRIX(*res, i, j) = ((igraph_real_t)len_intersection)/len_union;
      else
        MATRIX(*res, i, j) = 0.0;
      MATRIX(*res, j, i) = MATRIX(*res, i, j);
    }
  }

  igraph_lazy_adjlist_destroy(&al);
  igraph_vit_destroy(&vit);
  igraph_vit_destroy(&vit2);
  IGRAPH_FINALLY_CLEAN(3);

  return 0;
//.........这里部分代码省略.........

int igraph_is_connected_weak(const igraph_t *graph, igraph_bool_t *res) {

  long int no_of_nodes=igraph_vcount(graph);
  char *already_added;
  igraph_vector_t neis=IGRAPH_VECTOR_NULL;
  igraph_dqueue_t q=IGRAPH_DQUEUE_NULL;
  
  long int i, j;

  if (no_of_nodes == 0) {
    *res = 1;
    return IGRAPH_SUCCESS;
  }

  already_added=igraph_Calloc(no_of_nodes, char);
  if (already_added==0) {
    IGRAPH_ERROR("is connected (weak) failed", IGRAPH_ENOMEM);
  }
  IGRAPH_FINALLY(free, already_added); /* TODO: hack */

  IGRAPH_DQUEUE_INIT_FINALLY(&q, 10);
  IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
  
  /* Try to find at least two clusters */
  already_added[0]=1;
  IGRAPH_CHECK(igraph_dqueue_push(&q, 0));
  
  j=1;
  while ( !igraph_dqueue_empty(&q)) {
    long int actnode=(long int) igraph_dqueue_pop(&q);
    IGRAPH_ALLOW_INTERRUPTION();
    IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) actnode,
				  IGRAPH_ALL));
    for (i=0; i <igraph_vector_size(&neis); i++) {
      long int neighbor=(long int) VECTOR(neis)[i];
      if (already_added[neighbor] != 0) { continue; }
      IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
      j++;
      already_added[neighbor]++;
    }
  }
  
  /* Connected? */
  *res = (j == no_of_nodes);

  igraph_Free(already_added);
  igraph_dqueue_destroy(&q);
  igraph_vector_destroy(&neis);
  IGRAPH_FINALLY_CLEAN(3);

  return 0;
}

int igraph_is_minimal_separator(const igraph_t *graph,
				const igraph_vs_t candidate, 
				igraph_bool_t *res) {

  long int no_of_nodes=igraph_vcount(graph);
  igraph_vector_bool_t removed;
  igraph_dqueue_t Q;
  igraph_vector_t neis;
  long int candsize;
  igraph_vit_t vit;
  
  IGRAPH_CHECK(igraph_vit_create(graph, candidate, &vit));
  IGRAPH_FINALLY(igraph_vit_destroy, &vit);
  candsize=IGRAPH_VIT_SIZE(vit);

  IGRAPH_CHECK(igraph_vector_bool_init(&removed, no_of_nodes));
  IGRAPH_FINALLY(igraph_vector_bool_destroy, &removed);
  IGRAPH_CHECK(igraph_dqueue_init(&Q, 100));
  IGRAPH_FINALLY(igraph_dqueue_destroy, &Q);
  IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);

  /* Is it a separator at all? */
  IGRAPH_CHECK(igraph_i_is_separator(graph, &vit, -1, res, &removed, 
				     &Q, &neis, no_of_nodes));
  if (!(*res)) {
    /* Not a separator at all, nothing to do, *res is already set */
  } else if (candsize == 0) {
    /* Nothing to do, minimal, *res is already set */
  } else {
    /* General case, we need to remove each vertex from 'candidate'
     * and check whether the remainder is a separator. If this is
     * false for all vertices, then 'candidate' is a minimal
     * separator.
     */
    long int i;
    for (i=0, *res=0; i<candsize && (!*res); i++) {
      igraph_vector_bool_null(&removed);
      IGRAPH_CHECK(igraph_i_is_separator(graph, &vit, i, res, &removed, 
					 &Q, &neis, no_of_nodes));    
    }
    (*res) = (*res) ? 0 : 1;	/* opposite */
  }
  
  igraph_vector_destroy(&neis);
  igraph_dqueue_destroy(&Q);
  igraph_vector_bool_destroy(&removed);
  igraph_vit_destroy(&vit);
  IGRAPH_FINALLY_CLEAN(4);

  return 0;
}

/* call-seq:
 *   graph.constraint(vs,weights) -> Array
 *
 * Returns an Array of constraint measures for the vertices 
 * in the graph. Weights is an Array of weight measures for each edge.
 */
VALUE cIGraph_constraint(int argc, VALUE *argv, VALUE self){

  igraph_t *graph;
  igraph_vs_t vids;
  igraph_vector_t vidv;
  igraph_vector_t res;
  igraph_vector_t wght;
  int i;
  VALUE constraints = rb_ary_new();
  VALUE vs, weights;

  rb_scan_args(argc,argv,"11",&vs, &weights);

  //vector to hold the results of the degree calculations
  IGRAPH_FINALLY(igraph_vector_destroy, &res);
  IGRAPH_FINALLY(igraph_vector_destroy, &wght);
  IGRAPH_FINALLY(igraph_vector_destroy, &vidv);
  IGRAPH_CHECK(igraph_vector_init(&res,0));
  IGRAPH_CHECK(igraph_vector_init(&wght,0));

  Data_Get_Struct(self, igraph_t, graph);

  //Convert an array of vertices to a vector of vertex ids
  IGRAPH_CHECK(igraph_vector_init_int(&vidv,0));
  cIGraph_vertex_arr_to_id_vec(self,vs,&vidv);
  //create vertex selector from the vecotr of ids
  igraph_vs_vector(&vids,&vidv);

  if(weights == Qnil){
    IGRAPH_CHECK(igraph_constraint(graph,&res,vids,NULL));
  } else {
    for(i=0;i<RARRAY_LEN(weights);i++){
      IGRAPH_CHECK(igraph_vector_push_back(&wght,NUM2DBL(RARRAY_PTR(weights)[i])));
    }
    IGRAPH_CHECK(igraph_constraint(graph,&res,vids,&wght));
  }

  for(i=0;i<igraph_vector_size(&res);i++){
    rb_ary_push(constraints,rb_float_new(VECTOR(res)[i]));
  }

  igraph_vector_destroy(&vidv);
  igraph_vector_destroy(&res);
  igraph_vector_destroy(&wght);
  igraph_vs_destroy(&vids);

  IGRAPH_FINALLY_CLEAN(3);

  return constraints;

}

int igraph_lapack_dgetrf(igraph_matrix_t *a, igraph_vector_int_t *ipiv, 
			 int *info) {
  int m=(int) igraph_matrix_nrow(a);
  int n=(int) igraph_matrix_ncol(a);
  int lda=m > 0 ? m : 1;
  igraph_vector_int_t *myipiv=ipiv, vipiv;

  if (!ipiv) {
    IGRAPH_CHECK(igraph_vector_int_init(&vipiv, m<n ? m : n));
    IGRAPH_FINALLY(igraph_vector_int_destroy, &vipiv);
    myipiv=&vipiv;
  }

  igraphdgetrf_(&m, &n, VECTOR(a->data), &lda, VECTOR(*myipiv), info);

  if (*info > 0) {
    IGRAPH_WARNING("LU: factor is exactly singular");
  } else if (*info < 0) {
    switch(*info) { 
    case -1:
      IGRAPH_ERROR("Invalid number of rows", IGRAPH_ELAPACK);
      break;
    case -2:
      IGRAPH_ERROR("Invalid number of columns", IGRAPH_ELAPACK);
      break;
    case -3:
      IGRAPH_ERROR("Invalid input matrix", IGRAPH_ELAPACK);
      break;
    case -4:
      IGRAPH_ERROR("Invalid LDA parameter", IGRAPH_ELAPACK);
      break;
    case -5:
      IGRAPH_ERROR("Invalid pivot vector", IGRAPH_ELAPACK);
      break;
    case -6:
      IGRAPH_ERROR("Invalid info argument", IGRAPH_ELAPACK);
      break;
    default:
      IGRAPH_ERROR("Unknown LAPACK error", IGRAPH_ELAPACK);
      break;
    }
  }

  if (!ipiv) {
    igraph_vector_int_destroy(&vipiv);
    IGRAPH_FINALLY_CLEAN(1);
  }
  
  return 0;
}