int igraph_i_eigen_matrix_lapack_common(const igraph_matrix_t *A,
					const igraph_eigen_which_t *which, 
					igraph_vector_complex_t *values,
					igraph_matrix_complex_t *vectors) {

  igraph_vector_t valuesreal, valuesimag;
  igraph_matrix_t vectorsright, *myvectors= vectors ? &vectorsright : 0;
  int n=(int) igraph_matrix_nrow(A);
  int info=1;

  IGRAPH_VECTOR_INIT_FINALLY(&valuesreal, n);
  IGRAPH_VECTOR_INIT_FINALLY(&valuesimag, n);
  if (vectors) { IGRAPH_MATRIX_INIT_FINALLY(&vectorsright, n, n); }
  IGRAPH_CHECK(igraph_lapack_dgeev(A, &valuesreal, &valuesimag, 
				   /*vectorsleft=*/ 0, myvectors, &info));

  IGRAPH_CHECK(igraph_i_eigen_matrix_lapack_reorder(&valuesreal, 
						    &valuesimag, 
						    myvectors, which, values,
						    vectors));
  
  if (vectors) { 
    igraph_matrix_destroy(&vectorsright);
    IGRAPH_FINALLY_CLEAN(1);
  }
  
  igraph_vector_destroy(&valuesimag);
  igraph_vector_destroy(&valuesreal);
  IGRAPH_FINALLY_CLEAN(2);

  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_2dgrid_init(igraph_2dgrid_t *grid, igraph_matrix_t *coords,
                       igraph_real_t minx, igraph_real_t maxx, igraph_real_t deltax,
                       igraph_real_t miny, igraph_real_t maxy, igraph_real_t deltay) {
    long int i;

    grid->coords=coords;
    grid->minx=minx;
    grid->maxx=maxx;
    grid->deltax=deltax;
    grid->miny=miny;
    grid->maxy=maxy;
    grid->deltay=deltay;

    grid->stepsx=(long int) ceil((maxx-minx)/deltax);
    grid->stepsy=(long int) ceil((maxy-miny)/deltay);

    IGRAPH_CHECK(igraph_matrix_init(&grid->startidx,
                                    grid->stepsx, grid->stepsy));
    IGRAPH_FINALLY(igraph_matrix_destroy, &grid->startidx);
    IGRAPH_VECTOR_INIT_FINALLY(&grid->next, igraph_matrix_nrow(coords));
    IGRAPH_VECTOR_INIT_FINALLY(&grid->prev, igraph_matrix_nrow(coords));

    for (i=0; i<igraph_vector_size(&grid->next); i++) {
        VECTOR(grid->next)[i]=-1;
    }

    grid->massx=0;
    grid->massy=0;
    grid->vertices=0;

    IGRAPH_FINALLY_CLEAN(3);
    return 0;
}

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_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_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_similarity_inverse_log_weighted(const igraph_t *graph,
  igraph_matrix_t *res, const igraph_vs_t vids, igraph_neimode_t mode) {
  igraph_vector_t weights;
  igraph_neimode_t mode0;
  long int i, no_of_nodes;

  switch (mode) {
    case IGRAPH_OUT: mode0 = IGRAPH_IN; break;
    case IGRAPH_IN: mode0 = IGRAPH_OUT; break;
    default: mode0 = IGRAPH_ALL;
  }

  no_of_nodes = igraph_vcount(graph);

  IGRAPH_VECTOR_INIT_FINALLY(&weights, no_of_nodes);
  IGRAPH_CHECK(igraph_degree(graph, &weights, igraph_vss_all(), mode0, 1));
  for (i=0; i < no_of_nodes; i++) {
    if (VECTOR(weights)[i] > 1)
      VECTOR(weights)[i] = 1.0 / log(VECTOR(weights)[i]);
  }

  IGRAPH_CHECK(igraph_cocitation_real(graph, res, vids, mode0, &weights));
  igraph_vector_destroy(&weights);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/**
 * \ingroup structural
 * \function igraph_similarity_jaccard_es
 * \brief Jaccard similarity coefficient for a given edge selector.
 *
 * </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 the endpoints of edges in a given edge
 * selector.
 *
 * \param graph The graph object to analyze
 * \param res Pointer to a vector, the result of the calculation will
 *        be stored here. The number of elements is the same as the number
 *        of edges in \p es.
 * \param es An edge selector that specifies the edges to be included in the
 *        result.
 * \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(nd), n is the number of edges in the edge selector, d is
 * the (maximum) degree of the vertices in the graph.
 *
 * \sa \ref igraph_similarity_jaccard() and \ref igraph_similarity_jaccard_pairs()
 *   to calculate the Jaccard similarity between all pairs of a vertex set or
 *   some selected vertex pairs, or \ref igraph_similarity_dice(),
 *   \ref igraph_similarity_dice_pairs() and \ref igraph_similarity_dice_es() for a
 *   measure very similar to the Jaccard coefficient
 * 
 * \example examples/simple/igraph_similarity.c
 */
int igraph_similarity_jaccard_es(const igraph_t *graph, igraph_vector_t *res,
	const igraph_es_t es, igraph_neimode_t mode, igraph_bool_t loops) {
  igraph_vector_t v;
  igraph_eit_t eit;

  IGRAPH_VECTOR_INIT_FINALLY(&v, 0);

  IGRAPH_CHECK(igraph_eit_create(graph, es, &eit));
  IGRAPH_FINALLY(igraph_eit_destroy, &eit);

  while (!IGRAPH_EIT_END(eit)) {
    long int eid = IGRAPH_EIT_GET(eit);
    igraph_vector_push_back(&v, IGRAPH_FROM(graph, eid));
    igraph_vector_push_back(&v, IGRAPH_TO(graph, eid));
    IGRAPH_EIT_NEXT(eit);
  }

  igraph_eit_destroy(&eit);
  IGRAPH_FINALLY_CLEAN(1);

  IGRAPH_CHECK(igraph_similarity_jaccard_pairs(graph, res, &v, mode, loops));
  igraph_vector_destroy(&v);
  IGRAPH_FINALLY_CLEAN(1);

  return IGRAPH_SUCCESS;
}

/* removes multiple edges and returns new edge id's for each edge in |E|log|E| */
int igraph_i_multilevel_simplify_multiple(igraph_t *graph, igraph_vector_t *eids) {
  long int ecount = igraph_ecount(graph);
  long int i, l = -1, last_from = -1, last_to = -1;
  igraph_bool_t directed = igraph_is_directed(graph);
  igraph_integer_t from, to;
  igraph_vector_t edges;
  igraph_i_multilevel_link *links;

  /* Make sure there's enough space in eids to store the new edge IDs */
  IGRAPH_CHECK(igraph_vector_resize(eids, ecount));

  links = igraph_Calloc(ecount, igraph_i_multilevel_link);
  if (links == 0) {
    IGRAPH_ERROR("multi-level community structure detection failed", IGRAPH_ENOMEM);
  }
  IGRAPH_FINALLY(free, links);

  for (i = 0; i < ecount; i++) {
    igraph_edge(graph, (igraph_integer_t) i, &from, &to);
    links[i].from = from;
    links[i].to = to;
    links[i].id = i;
  }  

  qsort((void*)links, (size_t) ecount, sizeof(igraph_i_multilevel_link),
      igraph_i_multilevel_link_cmp);

  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
  for (i = 0; i < ecount; i++) {
    if (links[i].from == last_from && links[i].to == last_to) {
      VECTOR(*eids)[links[i].id] = l;
      continue;
    }

    last_from = links[i].from;
    last_to = links[i].to;

    igraph_vector_push_back(&edges, last_from);
    igraph_vector_push_back(&edges, last_to);

    l++;

    VECTOR(*eids)[links[i].id] = l;
  }

  free(links);
  IGRAPH_FINALLY_CLEAN(1);

  igraph_destroy(graph);
  IGRAPH_CHECK(igraph_create(graph, &edges, igraph_vcount(graph), directed));

  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);

  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_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_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_vector_order1(const igraph_vector_t* v,
			 igraph_vector_t* res, igraph_real_t nodes) {
  long int edges=igraph_vector_size(v);
  igraph_vector_t ptr;
  igraph_vector_t rad;
  long int i, j;

  assert(v!=NULL);
  assert(v->stor_begin != NULL);

  IGRAPH_VECTOR_INIT_FINALLY(&ptr, nodes+1);
  IGRAPH_VECTOR_INIT_FINALLY(&rad, edges);
  IGRAPH_CHECK(igraph_vector_resize(res, edges));
  
  for (i=0; i<edges; i++) {
    long int radix=v->stor_begin[i];
    if (VECTOR(ptr)[radix]!=0) {
      VECTOR(rad)[i]=VECTOR(ptr)[radix];
    }
    VECTOR(ptr)[radix]=i+1;
  }
  
  j=0;
  for (i=0; i<nodes+1; i++) {
    if (VECTOR(ptr)[i] != 0) {
      long int next=VECTOR(ptr)[i]-1;
      res->stor_begin[j++]=next;
      while (VECTOR(rad)[next] != 0) {
	next=VECTOR(rad)[next]-1;
	res->stor_begin[j++]=next;
      }
    }
  }
  
  igraph_vector_destroy(&ptr);
  igraph_vector_destroy(&rad);
  IGRAPH_FINALLY_CLEAN(2);
  
  return 0;
}

/** 
 * \ingroup interface
 * \function igraph_empty_attrs
 * \brief Creates an empty graph with some vertices, no edges and some graph attributes.
 *
 * </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 
 * 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
 *          integer number is expected.
 * \param directed Whether the graph is directed or not.
 * \param attr The attributes. 
 * \return Error code:
 *         \c IGRAPH_EINVAL: invalid number of vertices.
 * 
 * Time complexity: O(|V|) for a graph with
 * |V| vertices (and no edges).
 */
int igraph_empty_attrs(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, void* attr) {

  if (n<0) {
    IGRAPH_ERROR("cannot create empty graph with negative number of vertices",
		  IGRAPH_EINVAL);
  }
  
  if (!IGRAPH_FINITE(n)) {
    IGRAPH_ERROR("number of vertices is not finite (NA, NaN or Inf)", IGRAPH_EINVAL);
  }

  graph->n=0;
  graph->directed=directed;
  IGRAPH_VECTOR_INIT_FINALLY(&graph->from, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&graph->to, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&graph->oi, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&graph->ii, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&graph->os, 1);
  IGRAPH_VECTOR_INIT_FINALLY(&graph->is, 1);

  VECTOR(graph->os)[0]=0;
  VECTOR(graph->is)[0]=0;

  /* init attributes */
  graph->attr=0;
  IGRAPH_CHECK(igraph_i_attribute_init(graph, attr));

  /* add the vertices */
  IGRAPH_CHECK(igraph_add_vertices(graph, n, 0));
  
  IGRAPH_FINALLY_CLEAN(6);
  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;
}

int igraph_dot_product_game(igraph_t *graph, const igraph_matrix_t *vecs,
			    igraph_bool_t directed) {

  igraph_integer_t nrow=igraph_matrix_nrow(vecs);
  igraph_integer_t ncol=igraph_matrix_ncol(vecs);
  int i, j;
  igraph_vector_t edges;
  igraph_bool_t warned_neg=0, warned_big=0;
  
  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
    
  RNG_BEGIN();

  for (i = 0; i < ncol; i++) {
    int from=directed ? 0 : i+1;
    igraph_vector_t v1;
    igraph_vector_view(&v1, &MATRIX(*vecs, 0, i), nrow);
    for (j = from; j < ncol; j++) {
      igraph_real_t prob;
      igraph_vector_t v2;
      if (i==j) { continue; }
      igraph_vector_view(&v2, &MATRIX(*vecs, 0, j), nrow);
      igraph_lapack_ddot(&v1, &v2, &prob);
      if (prob < 0 && ! warned_neg) {
	warned_neg=1;
	IGRAPH_WARNING("Negative connection probability in "
		       "dot-product graph");
      } else if (prob > 1 && ! warned_big) {
	warned_big=1;
	IGRAPH_WARNING("Greater than 1 connection probability in "
		       "dot-product graph");
	IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
	IGRAPH_CHECK(igraph_vector_push_back(&edges, j));
      } else if (RNG_UNIF01() < prob) { 
	IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
	IGRAPH_CHECK(igraph_vector_push_back(&edges, j));
      }
    }
  }

  RNG_END();
  
  igraph_create(graph, &edges, ncol, directed);
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);

  return 0;
}

/*
 * Converts a Java VertexSet to an igraph_vs_t
 * @return:  zero if everything went fine, 1 if a null pointer was passed
 */
int Java_net_sf_igraph_VertexSet_to_igraph_vs(JNIEnv *env, jobject jobj, igraph_vs_t *result) {
  jint typeHint;
  jobject idArray;

  if (jobj == 0) {
    IGRAPH_CHECK(igraph_vs_all(result));
	return IGRAPH_SUCCESS;
  }

  typeHint = (*env)->CallIntMethod(env, jobj, net_sf_igraph_VertexSet_getTypeHint_mid);
  if (typeHint != 1 && typeHint != 2) {
    IGRAPH_CHECK(igraph_vs_all(result));
    return IGRAPH_SUCCESS;
  }
  
  idArray = (*env)->CallObjectMethod(env, jobj, net_sf_igraph_VertexSet_getIdArray_mid);
  if ((*env)->ExceptionCheck(env)) {
	return IGRAPH_EINVAL;
  }

  if (typeHint == 1) {
    /* Single vertex */
	jlong id[1];
	(*env)->GetLongArrayRegion(env, idArray, 0, 1, id);
	IGRAPH_CHECK(igraph_vs_1(result, (igraph_integer_t)id[0]));
  } else if (typeHint == 2) {
    /* List of vertices */
	jlong* ids;
	igraph_vector_t vec;
	long i, n;

	ids = (*env)->GetLongArrayElements(env, idArray, 0);
	n = (*env)->GetArrayLength(env, idArray);

	IGRAPH_VECTOR_INIT_FINALLY(&vec, n);
	for (i = 0; i < n; i++)
		VECTOR(vec)[i] = ids[i];
	IGRAPH_CHECK(igraph_vs_vector_copy(result, &vec));
	igraph_vector_destroy(&vec);
	IGRAPH_FINALLY_CLEAN(1);

	(*env)->ReleaseLongArrayElements(env, idArray, ids, JNI_ABORT);
  }

  (*env)->DeleteLocalRef(env, idArray);

  return IGRAPH_SUCCESS;
}

/* 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_disjoint_union_many(igraph_t *res, 
			       const igraph_vector_ptr_t *graphs) {
  long int no_of_graphs=igraph_vector_ptr_size(graphs);
  igraph_bool_t directed=1;
  igraph_vector_t edges;
  long int no_of_edges=0;
  long int shift=0;
  igraph_t *graph;
  long int i, j;
  igraph_integer_t from, to;
  
  if (no_of_graphs != 0) {
    graph=VECTOR(*graphs)[0];
    directed=igraph_is_directed(graph);
    for (i=0; i<no_of_graphs; i++) {      
      graph=VECTOR(*graphs)[i];
      no_of_edges += igraph_ecount(graph);
      if (directed != igraph_is_directed(graph)) {
	IGRAPH_ERROR("Cannot union directed and undirected graphs", 
		     IGRAPH_EINVAL);
      }
    }
  }
  
  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
  IGRAPH_CHECK(igraph_vector_reserve(&edges, 2*no_of_edges));
  
  for (i=0; i<no_of_graphs; i++) {
    long int ec;
    graph=VECTOR(*graphs)[i];    
    ec=igraph_ecount(graph);
    for (j=0; j<ec; j++) {
      igraph_edge(graph, (igraph_integer_t) j, &from, &to);
      igraph_vector_push_back(&edges, from+shift);
      igraph_vector_push_back(&edges, to+shift);
    }
    shift += igraph_vcount(graph);
  }
  
  IGRAPH_CHECK(igraph_create(res, &edges, (igraph_integer_t) shift, directed));
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}