/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2005  Gabor Csardi <csardi@rmki.kfki.hu>
   MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
   
   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 "igraph.h"
#include "memory.h"

#include <stdarg.h>

/** 
 * \section about_generators
 *
 * <para>Graph generators create graphs.</para>
 * 
 * <para>Almost all functions which create graph objects are documented
 * here. The exceptions are \ref igraph_subgraph() and alike, these 
 * create graphs based on another graph.</para>
 */


/**
 * \ingroup generators
 * \function igraph_create
 * \brief Creates a graph with the specified edges.
 * 
 * \param graph An uninitialized graph object.
 * \param edges The edges to add, the first two elements are the first
 *        edge, etc.
 * \param n The number of vertices in the graph, if smaller or equal
 *        to the highest vertex id in the \p edges vector it
 *        will be increased automatically. So it is safe to give 0
 *        here.
 * \param directed Boolean, whether to create a directed graph or
 *        not. If yes, then the first edge points from the first
 *        vertex id in \p edges to the second, etc.
 * \return Error code:
 *         \c IGRAPH_EINVEVECTOR: invalid edges
 *         vector (odd number of vertices).
 *         \c IGRAPH_EINVVID: invalid (negative)
 *         vertex id. 
 *
 * Time complexity: O(|V|+|E|),
 * |V| is the number of vertices,
 * |E| the number of edges in the
 * graph. 
 */
int igraph_create(igraph_t *graph, const igraph_vector_t *edges, igraph_integer_t n, 
		  igraph_bool_t directed) {
  igraph_real_t max=igraph_vector_max(edges)+1;

  if (igraph_vector_size(edges) % 2 != 0) {
    IGRAPH_ERROR("Invalid (odd) edges vector", IGRAPH_EINVEVECTOR);
  }
  if (!igraph_vector_isininterval(edges, 0, max-1)) {
    IGRAPH_ERROR("Invalid (negative) vertex id", IGRAPH_EINVVID);
  }

  IGRAPH_CHECK(igraph_empty(graph, n, directed));
  IGRAPH_FINALLY(igraph_destroy, graph);
  if (igraph_vector_size(edges)>0) {
    igraph_integer_t vc=igraph_vcount(graph);
    if (vc < max) {
      IGRAPH_CHECK(igraph_add_vertices(graph, max-vc, 0));
    }
    IGRAPH_CHECK(igraph_add_edges(graph, edges, 0));
  }

  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

int igraph_i_adjacency_directed(igraph_matrix_t *adjmatrix, igraph_vector_t *edges) {
  
  long int no_of_nodes=igraph_matrix_nrow(adjmatrix);
  long int i, j, k;
  
  for (i=0; i<no_of_nodes; i++) {
    for (j=0; j<no_of_nodes; j++) {
      long int M=MATRIX(*adjmatrix, i, j);
      for (k=0; k<M; k++) {
	IGRAPH_CHECK(igraph_vector_push_back(edges, i));
	IGRAPH_CHECK(igraph_vector_push_back(edges, j));
      }
    }
  }
  
  return 0;
}

int igraph_i_adjacency_max(igraph_matrix_t *adjmatrix, igraph_vector_t *edges) {
  
  long int no_of_nodes=igraph_matrix_nrow(adjmatrix);
  long int i, j, k;
  
  for (i=0; i<no_of_nodes; i++) {
    for (j=i; j<no_of_nodes; j++) {
      long int M1=MATRIX(*adjmatrix, i, j);
      long int M2=MATRIX(*adjmatrix, j, i);
      if (M1<M2) { M1=M2; }
      for (k=0; k<M1; k++) {
	IGRAPH_CHECK(igraph_vector_push_back(edges, i));
	IGRAPH_CHECK(igraph_vector_push_back(edges, j));
      }
    }
  }
  
  return 0;
}

int igraph_i_adjacency_upper(igraph_matrix_t *adjmatrix, igraph_vector_t *edges) {
  
  long int no_of_nodes=igraph_matrix_nrow(adjmatrix);
  long int i, j, k;
  
  for (i=0; i<no_of_nodes; i++) {
    for (j=i; j<no_of_nodes; j++) {
      long int M=MATRIX(*adjmatrix, i, j);
      for (k=0; k<M; k++) {
	IGRAPH_CHECK(igraph_vector_push_back(edges, i));
	IGRAPH_CHECK(igraph_vector_push_back(edges, j));
      }
    }
  }
  return 0;
}

int igraph_i_adjacency_lower(igraph_matrix_t *adjmatrix, igraph_vector_t *edges) {

  long int no_of_nodes=igraph_matrix_nrow(adjmatrix);
  long int i, j, k;
  
  for (i=0; i<no_of_nodes; i++) {
    for (j=0; j<=i; j++) {
      long int M=MATRIX(*adjmatrix, i, j);
      for (k=0; k<M; k++) {
	IGRAPH_CHECK(igraph_vector_push_back(edges, i));
	IGRAPH_CHECK(igraph_vector_push_back(edges, j));
      }
    }
  }
  return 0;
}

int igraph_i_adjacency_min(igraph_matrix_t *adjmatrix, igraph_vector_t *edges) {
  
  long int no_of_nodes=igraph_matrix_nrow(adjmatrix);
  long int i, j, k;
  
  for (i=0; i<no_of_nodes; i++) {
    for (j=i; j<no_of_nodes; j++) {
      long int M1=MATRIX(*adjmatrix, i, j);
      long int M2=MATRIX(*adjmatrix, j, i);
      if (M1>M2) { M1=M2; }
      for (k=0; k<M1; k++) {
	IGRAPH_CHECK(igraph_vector_push_back(edges, i));
	IGRAPH_CHECK(igraph_vector_push_back(edges, j));
      }
    }
  }
  
  return 0;
}

/**
 * \ingroup generators
 * \function igraph_adjacency
 * \brief Creates a graph object from an adjacency matrix.
 * 
 * \param graph Pointer to an uninitialized graph object.
 * \param adjmatrix The adjacency matrix. How it is interpreted
 *        depends on the \p mode argument.
 * \param mode Constant to specify how the given matrix is interpreted
 *        as an adjacency matrix. Possible values
 *        (A(i,j) 
 *        is the element in row i and column
 *        j in the adjacency matrix
 *        (\p adjmatrix): 
 *        \clist
 *        \cli IGRAPH_ADJ_DIRECTED
 *          the graph will be directed and
 *          an element gives the number of edges between two vertex.
 *        \cli IGRAPH_ADJ_UNDIRECTED
 *          this is the same as \c IGRAPH_ADJ_MAX,
 *          for convenience. 
 *        \cli IGRAPH_ADJ_MAX
 *          undirected graph will be created
 *          and the number of edges between vertex
 *          i and 
 *          j is
 *          max(A(i,j), A(j,i)). 
 *        \cli IGRAPH_ADJ_MIN
 *          undirected graph will be created
 *          with min(A(i,j), A(j,i))
 *          edges between vertex 
 *          i and
 *          j. 
 *        \cli IGRAPH_ADJ_PLUS 
 *          undirected graph will be created 
 *          with A(i,j)+A(j,i) edges
 *          between vertex 
 *          i and
 *          j.  
 *        \cli IGRAPH_ADJ_UPPER 
 *          undirected graph will be created,
 *          only the upper right triangle (including the diagonal) is
 *          used for the number of edges.
 *        \cli IGRAPH_ADJ_LOWER 
 *          undirected graph will be created,
 *          only the lower left triangle (including the diagonal) is 
 *          used for creating the edges.
 *       \endclist
 * \return Error code,
 *         \c IGRAPH_NONSQUARE: non-square matrix.
 * 
 * Time complexity: O(|V||V|+|E|),
 * |V| and 
 * |E| are number of vertices and
 * edges in the graph. 
 */

int igraph_adjacency(igraph_t *graph, igraph_matrix_t *adjmatrix,
		     igraph_adjacency_t mode) {

  igraph_vector_t edges=IGRAPH_VECTOR_NULL;
  long int no_of_nodes;

  /* Some checks */
  if (igraph_matrix_nrow(adjmatrix) != igraph_matrix_ncol(adjmatrix)) {
    IGRAPH_ERROR("Non-square matrix", IGRAPH_NONSQUARE);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
  
  /* Collect the edges */
  no_of_nodes=igraph_matrix_nrow(adjmatrix);
  switch (mode) {
  case IGRAPH_ADJ_DIRECTED:
    IGRAPH_CHECK(igraph_i_adjacency_directed(adjmatrix, &edges));
    break;
  case IGRAPH_ADJ_MAX:
    IGRAPH_CHECK(igraph_i_adjacency_max(adjmatrix, &edges));
    break;
  case IGRAPH_ADJ_UPPER:
    IGRAPH_CHECK(igraph_i_adjacency_upper(adjmatrix, &edges));
    break;
  case IGRAPH_ADJ_LOWER:
    IGRAPH_CHECK(igraph_i_adjacency_lower(adjmatrix, &edges));
    break;
  case IGRAPH_ADJ_MIN:
    IGRAPH_CHECK(igraph_i_adjacency_min(adjmatrix, &edges));
    break;
  case IGRAPH_ADJ_PLUS:
    IGRAPH_CHECK(igraph_i_adjacency_directed(adjmatrix, &edges));
    break;
  }

  IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes, 
			     (mode == IGRAPH_ADJ_DIRECTED))); 
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  
  return 0;
}

/**
 * \ingroup generators
 * \function igraph_star
 * \brief Creates a \em star graph, every vertex connects only to
 * the center.
 *
 * \param graph Pointer to an uninitialized graph object, this will
 *        be the result.
 * \param n Integer constant, the number of vertices in the graph.
 * \param mode Constant, gives the type of the star graph to
 *        create. Possible values:
 *        \clist
 *        \cli IGRAPH_STAR_OUT
 *          directed star graph, edges point
 *          \em from the center to the other vertices.
 *        \cli IGRAPH_STAR_IN
 *          directed star graph, edges point
 *          \em to the center from the other vertices.
 *        \cli IGRAPH_STAR_UNDIRECTED 
 *          an undirected star graph is
 *          created. 
 *        \endclist
 * \param center Id of the vertex which will be the center of the
 *          graph. 
 * \return Error code:
 *         \clist
 *         \cli IGRAPH_EINVVID 
 *           invalid number of vertices.
 *         \cli IGRAPH_EINVAL 
 *           invalid center vertex.
 *         \cli IGRAPH_EINVMODE 
 *           invalid mode argument.
 *         \endclist
 * 
 * Time complexity: O(|V|), the
 * number of vertices in the graph.
 *
 * \sa \ref igraph_lattice(), \ref igraph_ring(), \ref igraph_tree()
 * for creating other regular structures.
 */

int igraph_star(igraph_t *graph, igraph_integer_t n, igraph_star_mode_t mode, 
		igraph_integer_t center) {

  igraph_vector_t edges=IGRAPH_VECTOR_NULL;
  long int i;

  if (n<0) { 
    IGRAPH_ERROR("Invalid number of vertices", IGRAPH_EINVVID);
  }
  if (center<0 || center >n-1) {
    IGRAPH_ERROR("Invalid center vertex", IGRAPH_EINVAL);
  }
  if (mode != IGRAPH_STAR_OUT && mode != IGRAPH_STAR_IN && 
      mode != IGRAPH_STAR_UNDIRECTED) {
    IGRAPH_ERROR("invalid mode", IGRAPH_EINVMODE);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&edges, (n-1)*2);
  
  if (mode == IGRAPH_STAR_OUT) {
    for (i=0; i<center; i++) {
      VECTOR(edges)[2*i]=center;
      VECTOR(edges)[2*i+1]=i;
    }
    for (i=center+1; i<n; i++) {
      VECTOR(edges)[2*(i-1)]=center;
      VECTOR(edges)[2*(i-1)+1]=i;
    }
  } else {
    for (i=0; i<center; i++) {
      VECTOR(edges)[2*i+1]=center;
      VECTOR(edges)[2*i]=i;
    }
    for (i=center+1; i<n; i++) {
      VECTOR(edges)[2*(i-1)+1]=center;
      VECTOR(edges)[2*(i-1)]=i;
    }
  }
  
  IGRAPH_CHECK(igraph_create(graph, &edges, 0, 
			     (mode != IGRAPH_STAR_UNDIRECTED)));
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  
  return 0;
}

/**
 * \ingroup generators 
 * \function igraph_lattice
 * \brief Creates most kind of lattices.
 *
 * \param graph An uninitialized graph object.
 * \param dimvector Vector giving the sizes of the lattice in each of
 *        its dimensions. Ie. the dimension of the lattice will be the
 *        same as the length of this vector.
 * \param nei Integer value giving the distance (number of steps)
 *        within which two vertices will be connected. Not implemented
 *        yet. 
 * \param directed Boolean, whether to create a directed graph. The
 *        direction of the edges is determined by the generation
 *        algorithm and is unlikely to suit you, so this isn't a very
 *        useful option.
 * \param mutual Boolean, if the graph is directed this gives whether
 *        to create all connections as mutual.
 * \param circular Boolean, defines whether the generated lattice is
 *        periodic.
 * \return Error code:
 *         \c IGRAPH_EINVAL: invalid (negative)
 *         dimension vector. 
 *
 * Time complexity: if \p nei is less than two then it is O(|V|+|E|) (as
 * far as i remember), |V| and |E| are the number of vertices 
 * and edges in the generated graph. Otherwise it is O(|V|*d^o+|E|), d
 * is the average degree of the graph, o is the \p nei argument.
 */
int igraph_lattice(igraph_t *graph, const igraph_vector_t *dimvector, igraph_integer_t nei, 
		   igraph_bool_t directed, igraph_bool_t mutual, igraph_bool_t circular) {

  long int dims=igraph_vector_size(dimvector);
  long int no_of_nodes=igraph_vector_prod(dimvector);
  igraph_vector_t edges=IGRAPH_VECTOR_NULL;
  long int *coords, *weights;
  long int i, j;
  int carry, pos;

  if (igraph_vector_any_smaller(dimvector, 0)) {
    IGRAPH_ERROR("Invalid dimension vector", IGRAPH_EINVAL);
  }

  /* init coords & weights */

  coords=Calloc(dims, long int);
  if (coords==0) {
    IGRAPH_ERROR("lattice failed", IGRAPH_ENOMEM);
  }
  IGRAPH_FINALLY(free, coords);	/* TODO: hack */
  weights=Calloc(dims, long int);
  if (weights == 0) {
    IGRAPH_ERROR("lattice failed", IGRAPH_ENOMEM);
  }
  IGRAPH_FINALLY(free, weights);
  weights[0]=1;
  for (i=1; i<dims; i++) {
    weights[i]=weights[i-1]*VECTOR(*dimvector)[i-1];
  }
  
  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
  IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_nodes*dims +
				     mutual*directed * no_of_nodes*dims));

  for (i=0; i<no_of_nodes; i++) {
    IGRAPH_ALLOW_INTERRUPTION();
    for (j=0; j<dims; j++) {
      if (circular || coords[j] != VECTOR(*dimvector)[j]-1) {
	long int new_nei;
	if (coords[j] != VECTOR(*dimvector)[j]-1) {
	  new_nei = i + weights[j] + 1;
	} else {
	  new_nei = i - (VECTOR(*dimvector)[j]-1) * weights[j] + 1;
	}
	if (new_nei != i+1 && (VECTOR(*dimvector)[j] != 2 || coords[j] != 1)) {
	  igraph_vector_push_back(&edges, i); /* reserved */
	  igraph_vector_push_back(&edges, new_nei-1); /* reserved */
	}
      } /* if circular || coords[j] */
      if (mutual && directed && (circular || coords[j] != 0)) {
	long int new_nei;
	if (coords[j]!=0) {
	  new_nei=i-weights[j]+1;
	} else {
	  new_nei=i+(VECTOR(*dimvector)[j]-1) * weights[j]+1;
	}
	if (VECTOR(*dimvector)[j] != 2 || coords[j] != 0) {
	  igraph_vector_push_back(&edges, i); /* reserved */
	  igraph_vector_push_back(&edges, new_nei-1); /* reserved */
	}
      } /* if circular || coords[0] */
    } /* for j<dims */
    
    /* increase coords */
    carry=1;
    pos=0;
    
    while (carry==1 && pos != dims) {
      if (coords[pos] != VECTOR(*dimvector)[pos]-1) {
	coords[pos]++;
	carry=0;
      } else {
	coords[pos]=0;
	pos++;
      }
    }
    
  } /* for i<no_of_nodes */

  IGRAPH_CHECK(igraph_create(graph, &edges, 0, directed));
  if (nei >= 2) {
    IGRAPH_CHECK(igraph_connect_neighborhood(graph, nei, IGRAPH_ALL));
  }

  /* clean up */
  Free(coords);
  Free(weights);
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(3);

  return 0;
}

/**
 * \ingroup generators
 * \function igraph_ring
 * \brief Creates a \em ring graph, a one dimensional lattice.
 * 
 * \param graph Pointer to an uninitialized graph object.
 * \param n The number of vertices in the ring.
 * \param directed Logical, whether to create a directed ring.
 * \param mutual Logical, whether to create mutual edges in a directed
 *        ring. It is ignored for undirected graphs.
 * \param circular Logical, if false, the ring will be open (this is
 *        not a real \em ring actually).
 * \return Error code:
 *         \c IGRAPH_EINVAL: invalid number of vertices.
 * 
 * Time complexity: O(|V|), the
 * number of vertices in the graph.
 *
 * \sa \ref igraph_lattice() for generating more general lattices.
 */

int igraph_ring(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_bool_t mutual,
		igraph_bool_t circular) {
  
  igraph_vector_t v=IGRAPH_VECTOR_NULL;

  if (n<0) {
    IGRAPH_ERROR("negative number of vertices", IGRAPH_EINVAL);
  }
  
  IGRAPH_VECTOR_INIT_FINALLY(&v, 1);
  VECTOR(v)[0]=n;
  
  IGRAPH_CHECK(igraph_lattice(graph, &v, 1, directed, mutual, circular));
  igraph_vector_destroy(&v);		 
  
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/**
 * \ingroup generators
 * \function igraph_tree
 * \brief Creates a tree in which almost all vertices have the same
 * number of children.
 *
 * \param graph Pointer to an uninitialized graph object.
 * \param n Integer, the number of vertices in the graph.
 * \param children Integer, the number of children of a vertex in the
 *        tree. 
 * \param type Constant, gives whether to create a directed tree, and
 *        if this is the case, also its orientation. Possible values:
 *        \clist
 *        \cli IGRAPH_TREE_OUT 
 *          directed tree, the edges point
 *          from the parents to their children,
 *        \cli IGRAPH_TREE_IN 
 *          directed tree, the edges point from
 *          the children to their parents.
 *        \cli IGRAPH_TREE_UNDIRECTED
 *          undirected tree.
 *        \endclist
 * \return Error code:
 *         \c IGRAPH_EINVAL: invalid number of vertices.
 *         \c IGRAPH_INVMODE: invalid mode argument.
 * 
 * Time complexity: O(|V|+|E|), the
 * number of vertices plus the number of edges in the graph.
 * 
 * \sa \ref igraph_lattice(), \ref igraph_star() for creating other regular
 * structures. 
 */

int igraph_tree(igraph_t *graph, igraph_integer_t n, igraph_integer_t children, 
		igraph_tree_mode_t type) {
  
  igraph_vector_t edges=IGRAPH_VECTOR_NULL;
  long int i, j;
  long int idx=0;
  long int to=1;

  if (n<0 || children<=0) {
    IGRAPH_ERROR("Invalid number of vertices or children", IGRAPH_EINVAL);
  }
  if (type != IGRAPH_TREE_OUT && type != IGRAPH_TREE_IN &&
      type != IGRAPH_TREE_UNDIRECTED) {
    IGRAPH_ERROR("Invalid mode argument", IGRAPH_EINVMODE);
  }
  
  IGRAPH_VECTOR_INIT_FINALLY(&edges, 2*(n-1));
  
  i=0;
  if (type == IGRAPH_TREE_OUT) {
    while (idx<2*(n-1)) {
      for (j=0; j<children && idx<2*(n-1); j++) {
	VECTOR(edges)[idx++]=i;
	VECTOR(edges)[idx++]=to++;
      }
      i++;
    }
  } else {
    while (idx<2*(n-1)) {
      for (j=0; j<children && idx<2*(n-1); j++) {
	VECTOR(edges)[idx++]=to++;
	VECTOR(edges)[idx++]=i;
      }
      i++;
    }
  }
      
  IGRAPH_CHECK(igraph_create(graph, &edges, 0, type!=IGRAPH_TREE_UNDIRECTED));
  
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/**
 * \ingroup generators
 * \function igraph_full
 * \brief Creates a full graph (directed or undirected, with or
 * without loops). 
 * 
 * </para><para>
 * In a full graph every possible edge is present, every vertex is
 * connected to every other vertex. 
 * 
 * \param graph Pointer to an uninitialized graph object.
 * \param n Integer, the number of vertices in the graph.
 * \param directed Logical, whether to create a directed graph.
 * \param loops Logical, whether to include self-edges (loops).
 * \return Error code:
 *         \c IGRAPH_EINVAL: invalid number of vertices.
 * 
 * Time complexity: O(|V|+|E|),
 * |V| is the number of vertices,
 * |E| the number of edges in the
 * graph. Of course this is the same as
 * O(|E|)=O(|V||V|) 
 * here. 
 * 
 * \sa \ref igraph_lattice(), \ref igraph_star(), \ref igraph_tree()
 * for creating other regular structures.
 */

int igraph_full(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_bool_t loops) {
  
  igraph_vector_t edges=IGRAPH_VECTOR_NULL;
  long int i, j;

  if (n<0) {
    IGRAPH_ERROR("invalid number of vertices", IGRAPH_EINVAL);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

  if (directed && loops) {
    IGRAPH_CHECK(igraph_vector_reserve(&edges, n*n));
    for (i=0; i<n; i++) {
      for (j=0; j<n; j++) {
	igraph_vector_push_back(&edges, i); /* reserved */
	igraph_vector_push_back(&edges, j); /* reserved */
      }
    }
  } else if (directed && !loops) {
    IGRAPH_CHECK(igraph_vector_reserve(&edges, n*(n-1)));
    for (i=0; i<n; i++) {
      for (j=0; j<i; j++) {
	igraph_vector_push_back(&edges, i); /* reserved */
	igraph_vector_push_back(&edges, j); /* reserved */
      }
      for (j=i+1; j<n; j++) {
	igraph_vector_push_back(&edges, i); /* reserved */
	igraph_vector_push_back(&edges, j); /* reserved */
      }
    }
  } else if (!directed && loops) {
    IGRAPH_CHECK(igraph_vector_reserve(&edges, n*(n+1)/2));
    for (i=0; i<n; i++) {
      for (j=i; j<n; j++) {
	igraph_vector_push_back(&edges, i); /* reserved */
	igraph_vector_push_back(&edges, j); /* reserved */
      }
    }
  } else {
    IGRAPH_CHECK(igraph_vector_reserve(&edges, n*(n-1)/2));
    for (i=0; i<n; i++) {
      for (j=i+1; j<n; j++) {
	igraph_vector_push_back(&edges, i); /* reserved */
	igraph_vector_push_back(&edges, j); /* resreved */
      }
    }
  }
  
  IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  
  return 0;
}

/**
 * \function igraph_small
 * \brief Shortand to create a short graph, giving the edges as agruments
 * 
 * </para><para>
 * This function is handy when a relatively small graph needs to be created. 
 * Instead giving the edges in vector, they are given simply as
 * arguments and a '-1' needs to be given after the last meaningful
 * edge argument. 
 * 
 * </para><para>Note that only graphs which have vertices less than
 * 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
 *        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 ... The additional arguments giving the edges of the
 *        graph. Don't forget to supply an additional '-1' after the last
 *        (meaningful) argument.
 * \return Error code.
 * 
 * Time complexity: O(|V|+|E|), the number of vertices plus the number
 * of edges in the graph to create.
 */

int igraph_small(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, 
		 ...) {
  igraph_vector_t edges;
  va_list ap;
  
  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
  
  va_start(ap, directed);
  while (1) {
    int num = va_arg(ap, int);
    if (num == -1) {
      break;
    }
    igraph_vector_push_back(&edges, num);
  }

  IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));
  
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;
}

/**
 * \function igraph_extended_chordal_ring
 * Create an extended chordal ring
 * 
 * An extended chordal ring is regular graph, each node has the same
 * degree. It can be obtained from a simple ring by adding some extra
 * edges specified by a matrix. Let p denote the number of columns in
 * the <parameter>W</parameter> matrix. The extra edges of vertex i
 * are added according to column (i mod p) in
 * <parameter>W</parameter>. The number of extra edges is the number
 * of rows in <parameter>W</parameter>: for each row j an edge
 * i->i+w[ij] is added if i+w[ij] is less than the number of total
 * nodes. 
 * 
 * </para><para>
 * See also Kotsis, G: Interconnection Topologies for Parallel Processing
 * Systems, PARS Mitteilungen 11, 1-6, 1993.
 * 
 * \param graph Pointer to an uninitialized graph object, the result
 *   will be stored here. The result is always an undirected graph.
 * \param nodes Integer constant, the number of vertices in the
 *   graph. It must be at least 3.
 * \param W The matrix specifying the extra edges. The number of
 *   columns should divide the number of total vertices.
 * \return Error code.
 * 
 * \sa \ref igraph_ring().
 * 
 * Time complexity: O(|V|+|E|), the number of vertices plus the number
 * of edges.
 */

int igraph_extended_chordal_ring(igraph_t *graph, igraph_integer_t nodes, 
				 const igraph_matrix_t *W) {

  igraph_vector_t edges;
  long int period=igraph_matrix_ncol(W);
  long int degree=igraph_matrix_nrow(W)+2;
  long int i, j, mpos=0, epos=0;
  
  if (nodes<3) {
    IGRAPH_ERROR("An extended chordal ring has at least 3 nodes",
		 IGRAPH_EINVAL);
  }
  
  if ((long int)nodes % period != 0) {
    IGRAPH_ERROR("The period (number of columns in W) should divide the " 
		 "number of nodes", IGRAPH_EINVAL);
  }

  IGRAPH_VECTOR_INIT_FINALLY(&edges, nodes*degree);

  for (i=0; i<nodes-1; i++) {
    VECTOR(edges)[epos++] = i;
    VECTOR(edges)[epos++] = i+1;
  }
  VECTOR(edges)[epos++] = 0;
  VECTOR(edges)[epos++] = nodes-1;
  
  if (degree > 2) {
    for (i=0; i<nodes; i++) {
      for (j=0; j<degree-2; j++) {
	long int offset=MATRIX(*W, j, mpos);
	if (i+offset < nodes) {
	  VECTOR(edges)[epos++] = i;
	  VECTOR(edges)[epos++] = i+offset;
	}
      }
      mpos++; if (mpos==period) { mpos=0; }
    }
  }
  
  igraph_vector_resize(&edges, epos);
  IGRAPH_CHECK(igraph_create(graph, &edges, nodes, IGRAPH_UNDIRECTED));
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  return 0;  
}

/**
 * \function igraph_connect_neighborhood
 * \brief Connects every vertex to its neighborhood
 * 
 * This function adds new edges to graph. For each vertex 
 * vertices reachable by at most \p order steps and not yet connected
 * to the vertex a new edge is created.
 * 
 * </para><para> Note that the input graph is modified in place, no
 * new graph is created, call \ref igraph_copy() if you want to keep
 * the original graph as well.
 * 
 * </para><para> For undirected graphs reachability is always
 * symmetric, if vertex A can be reached from vertex B in at
 * most \p order steps, then the opposite is also true. Only one
 * undirected (A,B) edge will be added in this case.
 * \param graph The input graph, this is the output graph as well.
 * \param order Integer constant, it gives the distance within which
 *    the vertices will be connected to the source vertex.
 * \param mode Constant, it specifies how the neighborhood search is
 *    performed for directed graphs. If \c IGRAPH_OUT then vertices
 *    reachable from the source vertex will be connected, \c IGRAPH_IN
 *    is the opposite. If \c IGRAPH_ALL then the directed graph is
 *    considered as an undirected one.
 * \return Error code.
 * 
 * \sa \ref igraph_lattice() uses this function to connect the
 * neighborhood of the vertices.
 * 
 * Time complexity: O(|V|*d^o), |V| is the number of vertices in the
 * graph, d is the average degree and o is the \p order argument.
 */

int igraph_connect_neighborhood(igraph_t *graph, igraph_integer_t order,
				igraph_neimode_t mode) {
  
  long int no_of_nodes=igraph_vcount(graph);
  igraph_dqueue_t q;
  igraph_vector_t edges;
  long int i, j, in;
  long int *added;
  igraph_vector_t neis;
  
  if (order<0) {
    IGRAPH_ERROR("Negative order, cannot connect neighborhood", IGRAPH_EINVAL);
  }

  if (order<2) { 
    IGRAPH_WARNING("Order smaller than two, graph will be unchanged");
  }

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

  IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
  added=Calloc(no_of_nodes, long int);
  if (added==0) {
    IGRAPH_ERROR("Cannot connect neighborhood", IGRAPH_ENOMEM);
  }
  IGRAPH_FINALLY(igraph_free, added);
  IGRAPH_DQUEUE_INIT_FINALLY(&q, 100);
  IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
  
  for (i=0; i<no_of_nodes; i++) {
    added[i]=i+1;
    igraph_neighbors(graph, &neis, i, mode);
    in=igraph_vector_size(&neis);
    if (order > 1) {
      for (j=0; j<in; j++) {
	long int nei=VECTOR(neis)[j];
	added[nei]=i+1;
	igraph_dqueue_push(&q, nei);
	igraph_dqueue_push(&q, 1);
      }
    }
    
    while (!igraph_dqueue_empty(&q)) {
      long int actnode=igraph_dqueue_pop(&q);
      long int actdist=igraph_dqueue_pop(&q);
      long int n;
      igraph_neighbors(graph, &neis, actnode, mode);
      n=igraph_vector_size(&neis);
      
      if (actdist<order-1) {
	for (j=0; j<n; j++) {
	  long int nei=VECTOR(neis)[j];
	  if (added[nei] != i+1) {
	    added[nei]=i+1;
	    IGRAPH_CHECK(igraph_dqueue_push(&q, nei));
	    IGRAPH_CHECK(igraph_dqueue_push(&q, actdist+1));
	    if (mode != IGRAPH_ALL || i < nei) {
	      if (mode == IGRAPH_IN) {
		IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));
		IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
	      } else {
		IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
		IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));
	      }
	    }
	  }
	}
      } else { 
	for (j=0; j<n; j++) {
	  long int nei=VECTOR(neis)[j];
	  if (added[nei] != i+1) {
	    added[nei]=i+1;
	    if (mode != IGRAPH_ALL || i < nei) {
	      if (mode == IGRAPH_IN) {
		IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));
		IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
	      } else {
		IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
		IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));
	      }
	    }
	  }
	}
      }
      
    } /* while q not empty */
  } /* for i < no_of_nodes */
  
  igraph_vector_destroy(&neis);
  igraph_dqueue_destroy(&q);
  igraph_free(added);
  IGRAPH_FINALLY_CLEAN(3);
  
  IGRAPH_CHECK(igraph_add_edges(graph, &edges, 0));
  
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(1);
  
  return 0;
}