/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2005-2012 Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA
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_constructors.h"
#include "igraph_structural.h"
#include "igraph_memory.h"
#include "igraph_interface.h"
#include "igraph_attributes.h"
#include "igraph_adjlist.h"
#include "igraph_interrupt_internal.h"
#include "igraph_dqueue.h"
#include "config.h"
#include <stdarg.h>
#include <math.h>
#include <string.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.
*
* \example examples/simple/igraph_create.c
*/
int igraph_create(igraph_t *graph, const igraph_vector_t *edges,
igraph_integer_t n, igraph_bool_t directed) {
igraph_bool_t has_edges = igraph_vector_size(edges) > 0;
igraph_real_t max = has_edges ? igraph_vector_max(edges) + 1 : 0;
if (igraph_vector_size(edges) % 2 != 0) {
IGRAPH_ERROR("Invalid (odd) edges vector", IGRAPH_EINVEVECTOR);
}
if (has_edges && !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 (has_edges) {
igraph_integer_t vc = igraph_vcount(graph);
if (vc < max) {
IGRAPH_CHECK(igraph_add_vertices(graph, (igraph_integer_t) (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);
int igraph_i_adjacency_max(igraph_matrix_t *adjmatrix,
igraph_vector_t *edges);
int igraph_i_adjacency_upper(igraph_matrix_t *adjmatrix,
igraph_vector_t *edges);
int igraph_i_adjacency_lower(igraph_matrix_t *adjmatrix,
igraph_vector_t *edges);
int igraph_i_adjacency_min(igraph_matrix_t *adjmatrix,
igraph_vector_t *edges);
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 = (long int) 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 = (long int) MATRIX(*adjmatrix, i, j);
long int M2 = (long int) 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 = (long int) 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 = (long int) 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 = (long int) MATRIX(*adjmatrix, i, j);
long int M2 = (long int) 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.
*
* The order of the vertices in the matrix is preserved, i.e. the vertex
* corresponding to the first row/column will be vertex with id 0, the
* next row is for vertex 1, etc.
* \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 vertices.
* \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 vertices
* 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 vertices
* i and
* j.
* \cli IGRAPH_ADJ_PLUS
* undirected graph will be created
* with A(i,j)+A(j,i) edges
* between vertices
* 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|),
* |V| is the number of vertices in the graph.
*
* \example examples/simple/igraph_adjacency.c
*/
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, (igraph_integer_t) no_of_nodes,
(mode == IGRAPH_ADJ_DIRECTED)));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
int igraph_i_weighted_adjacency_directed(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops);
int igraph_i_weighted_adjacency_plus(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops);
int igraph_i_weighted_adjacency_max(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops);
int igraph_i_weighted_adjacency_upper(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops);
int igraph_i_weighted_adjacency_lower(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops);
int igraph_i_weighted_adjacency_min(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops);
int igraph_i_weighted_adjacency_directed(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops) {
long int no_of_nodes = igraph_matrix_nrow(adjmatrix);
long int i, j;
for (i = 0; i < no_of_nodes; i++) {
for (j = 0; j < no_of_nodes; j++) {
igraph_real_t M = MATRIX(*adjmatrix, i, j);
if (M == 0.0) {
continue;
}
if (i == j && !loops) {
continue;
}
IGRAPH_CHECK(igraph_vector_push_back(edges, i));
IGRAPH_CHECK(igraph_vector_push_back(edges, j));
IGRAPH_CHECK(igraph_vector_push_back(weights, M));
}
}
return 0;
}
int igraph_i_weighted_adjacency_plus(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops) {
long int no_of_nodes = igraph_matrix_nrow(adjmatrix);
long int i, j;
for (i = 0; i < no_of_nodes; i++) {
for (j = i; j < no_of_nodes; j++) {
igraph_real_t M = MATRIX(*adjmatrix, i, j) + MATRIX(*adjmatrix, j, i);
if (M == 0.0) {
continue;
}
if (i == j && !loops) {
continue;
}
if (i == j) {
M /= 2;
}
IGRAPH_CHECK(igraph_vector_push_back(edges, i));
IGRAPH_CHECK(igraph_vector_push_back(edges, j));
IGRAPH_CHECK(igraph_vector_push_back(weights, M));
}
}
return 0;
}
int igraph_i_weighted_adjacency_max(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops) {
long int no_of_nodes = igraph_matrix_nrow(adjmatrix);
long int i, j;
for (i = 0; i < no_of_nodes; i++) {
for (j = i; j < no_of_nodes; j++) {
igraph_real_t M1 = MATRIX(*adjmatrix, i, j);
igraph_real_t M2 = MATRIX(*adjmatrix, j, i);
if (M1 < M2) {
M1 = M2;
}
if (M1 == 0.0) {
continue;
}
if (i == j && !loops) {
continue;
}
IGRAPH_CHECK(igraph_vector_push_back(edges, i));
IGRAPH_CHECK(igraph_vector_push_back(edges, j));
IGRAPH_CHECK(igraph_vector_push_back(weights, M1));
}
}
return 0;
}
int igraph_i_weighted_adjacency_upper(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops) {
long int no_of_nodes = igraph_matrix_nrow(adjmatrix);
long int i, j;
for (i = 0; i < no_of_nodes; i++) {
for (j = i; j < no_of_nodes; j++) {
igraph_real_t M = MATRIX(*adjmatrix, i, j);
if (M == 0.0) {
continue;
}
if (i == j && !loops) {
continue;
}
IGRAPH_CHECK(igraph_vector_push_back(edges, i));
IGRAPH_CHECK(igraph_vector_push_back(edges, j));
IGRAPH_CHECK(igraph_vector_push_back(weights, M));
}
}
return 0;
}
int igraph_i_weighted_adjacency_lower(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops) {
long int no_of_nodes = igraph_matrix_nrow(adjmatrix);
long int i, j;
for (i = 0; i < no_of_nodes; i++) {
for (j = 0; j <= i; j++) {
igraph_real_t M = MATRIX(*adjmatrix, i, j);
if (M == 0.0) {
continue;
}
if (i == j && !loops) {
continue;
}
IGRAPH_CHECK(igraph_vector_push_back(edges, i));
IGRAPH_CHECK(igraph_vector_push_back(edges, j));
IGRAPH_CHECK(igraph_vector_push_back(weights, M));
}
}
return 0;
}
int igraph_i_weighted_adjacency_min(const igraph_matrix_t *adjmatrix,
igraph_vector_t *edges,
igraph_vector_t *weights,
igraph_bool_t loops) {
long int no_of_nodes = igraph_matrix_nrow(adjmatrix);
long int i, j;
for (i = 0; i < no_of_nodes; i++) {
for (j = i; j < no_of_nodes; j++) {
igraph_real_t M1 = MATRIX(*adjmatrix, i, j);
igraph_real_t M2 = MATRIX(*adjmatrix, j, i);
if (M1 > M2) {
M1 = M2;
}
if (M1 == 0.0) {
continue;
}
if (i == j && !loops) {
continue;
}
IGRAPH_CHECK(igraph_vector_push_back(edges, i));
IGRAPH_CHECK(igraph_vector_push_back(edges, j));
IGRAPH_CHECK(igraph_vector_push_back(weights, M1));
}
}
return 0;
}
/**
* \ingroup generators
* \function igraph_weighted_adjacency
* \brief Creates a graph object from a weighted adjacency matrix.
*
* The order of the vertices in the matrix is preserved, i.e. the vertex
* corresponding to the first row/column will be vertex with id 0, the
* next row is for vertex 1, etc.
* \param graph Pointer to an uninitialized graph object.
* \param adjmatrix The weighted adjacency matrix. How it is interpreted
* depends on the \p mode argument. The common feature is that
* edges with zero weights are considered nonexistent (however,
* negative weights are permitted).
* \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 weight of the edge between two vertices.
* \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 weight of the edge between vertices
* i and
* j is
* max(A(i,j), A(j,i)).
* \cli IGRAPH_ADJ_MIN
* undirected graph will be created
* with edge weight min(A(i,j), A(j,i))
* between vertices
* i and
* j.
* \cli IGRAPH_ADJ_PLUS
* undirected graph will be created
* with edge weight A(i,j)+A(j,i)
* between vertices
* i and
* j.
* \cli IGRAPH_ADJ_UPPER
* undirected graph will be created,
* only the upper right triangle (including the diagonal) is
* used for the edge weights.
* \cli IGRAPH_ADJ_LOWER
* undirected graph will be created,
* only the lower left triangle (including the diagonal) is
* used for the edge weights.
* \endclist
* \param attr the name of the attribute that will store the edge weights.
* If \c NULL , it will use \c weight as the attribute name.
* \param loops Logical scalar, whether to ignore the diagonal elements
* in the adjacency matrix.
* \return Error code,
* \c IGRAPH_NONSQUARE: non-square matrix.
*
* Time complexity: O(|V||V|),
* |V| is the number of vertices in the graph.
*
* \example examples/simple/igraph_weighted_adjacency.c
*/
int igraph_weighted_adjacency(igraph_t *graph, igraph_matrix_t *adjmatrix,
igraph_adjacency_t mode, const char* attr,
igraph_bool_t loops) {
igraph_vector_t edges = IGRAPH_VECTOR_NULL;
igraph_vector_t weights = IGRAPH_VECTOR_NULL;
const char* default_attr = "weight";
igraph_vector_ptr_t attr_vec;
igraph_attribute_record_t attr_rec;
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);
IGRAPH_VECTOR_INIT_FINALLY(&weights, 0);
IGRAPH_VECTOR_PTR_INIT_FINALLY(&attr_vec, 1);
/* Collect the edges */
no_of_nodes = igraph_matrix_nrow(adjmatrix);
switch (mode) {
case IGRAPH_ADJ_DIRECTED:
IGRAPH_CHECK(igraph_i_weighted_adjacency_directed(adjmatrix, &edges,
&weights, loops));
break;
case IGRAPH_ADJ_MAX:
IGRAPH_CHECK(igraph_i_weighted_adjacency_max(adjmatrix, &edges,
&weights, loops));
break;
case IGRAPH_ADJ_UPPER:
IGRAPH_CHECK(igraph_i_weighted_adjacency_upper(adjmatrix, &edges,
&weights, loops));
break;
case IGRAPH_ADJ_LOWER:
IGRAPH_CHECK(igraph_i_weighted_adjacency_lower(adjmatrix, &edges,
&weights, loops));
break;
case IGRAPH_ADJ_MIN:
IGRAPH_CHECK(igraph_i_weighted_adjacency_min(adjmatrix, &edges,
&weights, loops));
break;
case IGRAPH_ADJ_PLUS:
IGRAPH_CHECK(igraph_i_weighted_adjacency_plus(adjmatrix, &edges,
&weights, loops));
break;
}
/* Prepare attribute record */
attr_rec.name = attr ? attr : default_attr;
attr_rec.type = IGRAPH_ATTRIBUTE_NUMERIC;
attr_rec.value = &weights;
VECTOR(attr_vec)[0] = &attr_rec;
/* Create graph */
IGRAPH_CHECK(igraph_empty(graph, (igraph_integer_t) no_of_nodes,
(mode == IGRAPH_ADJ_DIRECTED)));
IGRAPH_FINALLY(igraph_destroy, graph);
if (igraph_vector_size(&edges) > 0) {
IGRAPH_CHECK(igraph_add_edges(graph, &edges, &attr_vec));
}
IGRAPH_FINALLY_CLEAN(1);
/* Cleanup */
igraph_vector_destroy(&edges);
igraph_vector_destroy(&weights);
igraph_vector_ptr_destroy(&attr_vec);
IGRAPH_FINALLY_CLEAN(3);
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_MUTUAL
* directed star graph with mutual edges.
* \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.
*
* \example examples/simple/igraph_star.c
*/
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_MUTUAL && mode != IGRAPH_STAR_UNDIRECTED) {
IGRAPH_ERROR("invalid mode", IGRAPH_EINVMODE);
}
if (mode != IGRAPH_STAR_MUTUAL) {
IGRAPH_VECTOR_INIT_FINALLY(&edges, (n - 1) * 2);
} else {
IGRAPH_VECTOR_INIT_FINALLY(&edges, (n - 1) * 2 * 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 if (mode == IGRAPH_STAR_MUTUAL) {
for (i = 0; i < center; i++) {
VECTOR(edges)[4 * i] = center;
VECTOR(edges)[4 * i + 1] = i;
VECTOR(edges)[4 * i + 2] = i;
VECTOR(edges)[4 * i + 3] = center;
}
for (i = center + 1; i < n; i++) {
VECTOR(edges)[4 * i - 4] = center;
VECTOR(edges)[4 * i - 3] = i;
VECTOR(edges)[4 * i - 2] = i;
VECTOR(edges)[4 * i - 1] = center;
}
} 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 kinds 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.
* \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 = (long int) 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 = igraph_Calloc(dims, long int);
if (coords == 0) {
IGRAPH_ERROR("lattice failed", IGRAPH_ENOMEM);
}
IGRAPH_FINALLY(free, coords); /* TODO: hack */
weights = igraph_Calloc(dims, long int);
if (weights == 0) {
IGRAPH_ERROR("lattice failed", IGRAPH_ENOMEM);
}
IGRAPH_FINALLY(free, weights);
if (dims > 0) {
weights[0] = 1;
for (i = 1; i < dims; i++) {
weights[i] = weights[i - 1] * (long int) 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 - (long int) (VECTOR(*dimvector)[j] - 1) * weights[j] + 1;
}
if (new_nei != i + 1 &&
(VECTOR(*dimvector)[j] != 2 || coords[j] != 1 || directed)) {
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 + (long int) (VECTOR(*dimvector)[j] - 1) * weights[j] + 1;
}
if (new_nei != i + 1 &&
(VECTOR(*dimvector)[j] != 2 || !circular)) {
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, (igraph_integer_t) no_of_nodes,
directed));
if (nei >= 2) {
IGRAPH_CHECK(igraph_connect_neighborhood(graph, nei, IGRAPH_ALL));
}
/* clean up */
igraph_Free(coords);
igraph_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.
*
* An undirected (circular) ring on n vertices is commonly known in graph
* theory as the cycle graph C_n.
*
* \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.
*
* \example examples/simple/igraph_ring.c
*/
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; \ref igraph_from_prufer() for creating arbitrary trees;
* \ref igraph_tree_game() for uniform random sampling of trees.
*
* \example examples/simple/igraph_tree.c
*/
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, n, 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. A full graph in \c igraph should be
* distinguished from the concept of complete graphs as used in graph theory.
* If n is a positive integer, then the complete graph K_n on n vertices is
* the undirected simple graph with the following property. For any distinct
* pair (u,v) of vertices in K_n, uv (or equivalently vu) is an edge of K_n.
* In \c igraph, a full graph on n vertices can be K_n, a directed version of
* K_n, or K_n with at least one loop edge. In any case, if F is a full graph
* on n vertices as generated by \c igraph, then K_n is a subgraph of the
* undirected version of F.
*
* \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.
*
* \example examples/simple/igraph_full.c
*/
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); /* reserved */
}
}
}
IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_full_citation
* Creates a full citation graph
*
* This is a directed graph, where every <code>i->j</code> edge is
* present if and only if <code>j<i</code>.
* If the \c directed argument is zero then an undirected graph is
* created, and it is just a full graph.
* \param graph Pointer to an uninitialized graph object, the result
* is stored here.
* \param n The number of vertices.
* \param directed Whether to created a directed graph. If zero an
* undirected graph is created.
* \return Error code.
*
* Time complexity: O(|V|^2), as we have many edges.
*/
int igraph_full_citation(igraph_t *graph, igraph_integer_t n,
igraph_bool_t directed) {
igraph_vector_t edges;
long int i, j, ptr = 0;
IGRAPH_VECTOR_INIT_FINALLY(&edges, n * (n - 1));
for (i = 1; i < n; i++) {
for (j = 0; j < i; j++) {
VECTOR(edges)[ptr++] = i;
VECTOR(edges)[ptr++] = j;
}
}
IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_small
* \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.
* Instead of giving the edges as a 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; 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.
* \return Error code.
*
* Time complexity: O(|V|+|E|), the number of vertices plus the number
* of edges in the graph to create.
*
* \example examples/simple/igraph_small.c
*/
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 a cycle graph with additional chords
* connecting its vertices.
*
* Each row \c L of the matrix \p W specifies a set of chords to be
* inserted, in the following way: vertex \c i will connect to a vertex
* <code>L[(i mod p)]</code> steps ahead of it along the cycle, where
* \c p is the length of \c L.
* In other words, vertex \c i will be connected to vertex
* <code>(i + L[(i mod p)]) mod nodes</code>.
*
* </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.
* \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.
* \param directed Whether the graph should be directed.
* \return Error code.
*
* \sa \ref igraph_ring(), \ref igraph_lcf(), \ref igraph_lcf_vector()
*
* 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_bool_t directed) {
igraph_vector_t edges;
long int period = igraph_matrix_ncol(W);
long int nrow = igraph_matrix_nrow(W);
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, 2 * (nodes + nodes * nrow));
for (i = 0; i < nodes - 1; i++) {
VECTOR(edges)[epos++] = i;
VECTOR(edges)[epos++] = i + 1;
}
VECTOR(edges)[epos++] = nodes - 1;
VECTOR(edges)[epos++] = 0;
if (nrow > 0) {
for (i = 0; i < nodes; i++) {
for (j = 0; j < nrow; j++) {
long int offset = (long int) MATRIX(*W, j, mpos);
long int v = (i + offset) % nodes;
if (v < 0) {
v += nodes; /* handle negative offsets */
}
VECTOR(edges)[epos++] = i;
VECTOR(edges)[epos++] = v;
}
mpos++; if (mpos == period) {
mpos = 0;
}
}
}
IGRAPH_CHECK(igraph_create(graph, &edges, nodes, directed));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return IGRAPH_SUCCESS;
}
/**
* \function igraph_connect_neighborhood
* \brief Connects every vertex to its neighborhood
*
* This function adds new edges to the input graph. Each vertex is connected
* to all vertices reachable by at most \p order steps from it
* (unless a connection already existed). In other words, the \p order power of
* the graph is computed.
*
* </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^k), |V| is the number of vertices in the
* graph, d is the average degree and k 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 = igraph_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, (igraph_integer_t) i, mode);
in = igraph_vector_size(&neis);
if (order > 1) {
for (j = 0; j < in; j++) {
long int nei = (long int) 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 = (long int) igraph_dqueue_pop(&q);
long int actdist = (long int) igraph_dqueue_pop(&q);
long int n;
igraph_neighbors(graph, &neis, (igraph_integer_t) actnode, mode);
n = igraph_vector_size(&neis);
if (actdist < order - 1) {
for (j = 0; j < n; j++) {
long int nei = (long int) 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 = (long int) 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;
}
/**
* \function igraph_de_bruijn
* \brief Generate a de Bruijn graph.
*
* A de Bruijn graph represents relationships between strings. An alphabet
* of \c m letters are used and strings of length \c n are considered.
* A vertex corresponds to every possible string and there is a directed edge
* from vertex \c v to vertex \c w if the string of \c v can be transformed into
* the string of \c w by removing its first letter and appending a letter to it.
*
* </para><para>
* Please note that the graph will have \c m to the power \c n vertices and
* even more edges, so probably you don't want to supply too big numbers for
* \c m and \c n.
*
* </para><para>
* De Bruijn graphs have some interesting properties, please see another source,
* eg. Wikipedia for details.
*
* \param graph Pointer to an uninitialized graph object, the result will be
* stored here.
* \param m Integer, the number of letters in the alphabet.
* \param n Integer, the length of the strings.
* \return Error code.
*
* \sa \ref igraph_kautz().
*
* Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.
*/
int igraph_de_bruijn(igraph_t *graph, igraph_integer_t m, igraph_integer_t n) {
/* m - number of symbols */
/* n - length of strings */
long int no_of_nodes, no_of_edges;
igraph_vector_t edges;
long int i, j;
long int mm = m;
if (m < 0 || n < 0) {
IGRAPH_ERROR("`m' and `n' should be non-negative in a de Bruijn graph",
IGRAPH_EINVAL);
}
if (n == 0) {
return igraph_empty(graph, 1, IGRAPH_DIRECTED);
}
if (m == 0) {
return igraph_empty(graph, 0, IGRAPH_DIRECTED);
}
no_of_nodes = (long int) pow(m, n);
no_of_edges = no_of_nodes * m;
IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges * 2));
for (i = 0; i < no_of_nodes; i++) {
long int basis = (i * mm) % no_of_nodes;
for (j = 0; j < m; j++) {
igraph_vector_push_back(&edges, i);
igraph_vector_push_back(&edges, basis + j);
}
}
IGRAPH_CHECK(igraph_create(graph, &edges, (igraph_integer_t) no_of_nodes,
IGRAPH_DIRECTED));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_kautz
* \brief Generate a Kautz graph.
*
* A Kautz graph is a labeled graph, vertices are labeled by strings
* of length \c n+1 above an alphabet with \c m+1 letters, with
* the restriction that every two consecutive letters in the string
* must be different. There is a directed edge from a vertex \c v to
* another vertex \c w if it is possible to transform the string of
* \c v into the string of \c w by removing the first letter and
* appending a letter to it.
*
* </para><para>
* Kautz graphs have some interesting properties, see eg. Wikipedia
* for details.
*
* </para><para>
* Vincent Matossian wrote the first version of this function in R,
* thanks.
* \param graph Pointer to an uninitialized graph object, the result
* will be stored here.
* \param m Integer, \c m+1 is the number of letters in the alphabet.
* \param n Integer, \c n+1 is the length of the strings.
* \return Error code.
*
* \sa \ref igraph_de_bruijn().
*
* Time complexity: O(|V|* [(m+1)/m]^n +|E|), in practice it is more
* like O(|V|+|E|). |V| is the number of vertices, |E| is the number
* of edges and \c m and \c n are the corresponding arguments.
*/
int igraph_kautz(igraph_t *graph, igraph_integer_t m, igraph_integer_t n) {
/* m+1 - number of symbols */
/* n+1 - length of strings */
long int mm = m;
long int no_of_nodes, no_of_edges;
long int allstrings;
long int i, j, idx = 0;
igraph_vector_t edges;
igraph_vector_long_t digits, table;
igraph_vector_long_t index1, index2;
long int actb = 0;
long int actvalue = 0;
if (m < 0 || n < 0) {
IGRAPH_ERROR("`m' and `n' should be non-negative in a Kautz graph",
IGRAPH_EINVAL);
}
if (n == 0) {
return igraph_full(graph, m + 1, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
}
if (m == 0) {
return igraph_empty(graph, 0, IGRAPH_DIRECTED);
}
no_of_nodes = (long int) ((m + 1) * pow(m, n));
no_of_edges = no_of_nodes * m;
allstrings = (long int) pow(m + 1, n + 1);
IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
IGRAPH_CHECK(igraph_vector_long_init(&table, n + 1));
IGRAPH_FINALLY(igraph_vector_long_destroy, &table);
j = 1;
for (i = n; i >= 0; i--) {
VECTOR(table)[i] = j;
j *= (m + 1);
}
IGRAPH_CHECK(igraph_vector_long_init(&digits, n + 1));
IGRAPH_FINALLY(igraph_vector_long_destroy, &digits);
IGRAPH_CHECK(igraph_vector_long_init(&index1, (long int) pow(m + 1, n + 1)));
IGRAPH_FINALLY(igraph_vector_long_destroy, &index1);
IGRAPH_CHECK(igraph_vector_long_init(&index2, no_of_nodes));
IGRAPH_FINALLY(igraph_vector_long_destroy, &index2);
/* Fill the index tables*/
while (1) {
/* at the beginning of the loop, 0:actb contain the valid prefix */
/* we might need to fill it to get a valid string */
long int z = 0;
if (VECTOR(digits)[actb] == 0) {
z = 1;
}
for (actb++; actb <= n; actb++) {
VECTOR(digits)[actb] = z;
actvalue += z * VECTOR(table)[actb];
z = 1 - z;
}
actb = n;
/* ok, we have a valid string now */
VECTOR(index1)[actvalue] = idx + 1;
VECTOR(index2)[idx] = actvalue;
idx++;
/* finished? */
if (idx >= no_of_nodes) {
break;
}
/* not yet, we need a valid prefix now */
while (1) {
/* try to increase digits at position actb */
long int next = VECTOR(digits)[actb] + 1;
if (actb != 0 && VECTOR(digits)[actb - 1] == next) {
next++;
}
if (next <= m) {
/* ok, no problem */
actvalue += (next - VECTOR(digits)[actb]) * VECTOR(table)[actb];
VECTOR(digits)[actb] = next;
break;
} else {
/* bad luck, try the previous digit */
actvalue -= VECTOR(digits)[actb] * VECTOR(table)[actb];
actb--;
}
}
}
IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges * 2));
/* Now come the edges at last */
for (i = 0; i < no_of_nodes; i++) {
long int fromvalue = VECTOR(index2)[i];
long int lastdigit = fromvalue % (mm + 1);
long int basis = (fromvalue * (mm + 1)) % allstrings;
for (j = 0; j <= m; j++) {
long int tovalue, to;
if (j == lastdigit) {
continue;
}
tovalue = basis + j;
to = VECTOR(index1)[tovalue] - 1;
if (to < 0) {
continue;
}
igraph_vector_push_back(&edges, i);
igraph_vector_push_back(&edges, to);
}
}
igraph_vector_long_destroy(&index2);
igraph_vector_long_destroy(&index1);
igraph_vector_long_destroy(&digits);
igraph_vector_long_destroy(&table);
IGRAPH_FINALLY_CLEAN(4);
IGRAPH_CHECK(igraph_create(graph, &edges, (igraph_integer_t) no_of_nodes,
IGRAPH_DIRECTED));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_lcf_vector
* \brief Create a graph from LCF notation
*
* This function is essentially the same as \ref igraph_lcf(), only
* the way for giving the arguments is different. See \ref
* igraph_lcf() for details.
* \param graph Pointer to an uninitialized graph object.
* \param n Integer constant giving the number of vertices.
* \param shifts A vector giving the shifts.
* \param repeats An integer constant giving the number of repeats
* for the shifts.
* \return Error code.
*
* \sa \ref igraph_lcf(), \ref igraph_extended_chordal_ring()
*
* Time complexity: O(|V|+|E|), linear in the number of vertices plus
* the number of edges.
*/
int igraph_lcf_vector(igraph_t *graph, igraph_integer_t n,
const igraph_vector_t *shifts,
igraph_integer_t repeats) {
igraph_vector_t edges;
long int no_of_shifts = igraph_vector_size(shifts);
long int ptr = 0, i, sptr = 0;
long int no_of_nodes = n;
long int no_of_edges = n + no_of_shifts * repeats;
if (repeats < 0) {
IGRAPH_ERROR("number of repeats must be positive", IGRAPH_EINVAL);
}
IGRAPH_VECTOR_INIT_FINALLY(&edges, 2 * no_of_edges);
if (no_of_nodes > 0) {
/* Create a ring first */
for (i = 0; i < no_of_nodes; i++) {
VECTOR(edges)[ptr++] = i;
VECTOR(edges)[ptr++] = i + 1;
}
VECTOR(edges)[ptr - 1] = 0;
}
/* Then add the rest */
while (ptr < 2 * no_of_edges) {
long int sh = (long int) VECTOR(*shifts)[sptr % no_of_shifts];
long int from = sptr % no_of_nodes;
long int to = (no_of_nodes + sptr + sh) % no_of_nodes;
VECTOR(edges)[ptr++] = from;
VECTOR(edges)[ptr++] = to;
sptr++;
}
IGRAPH_CHECK(igraph_create(graph, &edges, (igraph_integer_t) no_of_nodes,
IGRAPH_UNDIRECTED));
IGRAPH_CHECK(igraph_simplify(graph, 1 /* true */, 1 /* true */, NULL));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_lcf
* \brief Create a graph from LCF notation
*
* </para><para>
* LCF is short for Lederberg-Coxeter-Frucht, it is a concise notation for
* 3-regular Hamiltonian graphs. It consists of three parameters: the
* number of vertices in the graph, a list of shifts giving additional
* edges to a cycle backbone, and another integer giving how many times
* the shifts should be performed. See
* http://mathworld.wolfram.com/LCFNotation.html for details.
*
* \param graph Pointer to an uninitialized graph object.
* \param n Integer, the number of vertices in the graph.
* \param ... The shifts and the number of repeats for the shifts,
* plus an additional 0 to mark the end of the arguments.
* \return Error code.
*
* \sa See \ref igraph_lcf_vector() for a similar function using a
* vector_t instead of the variable length argument list.
*
* Time complexity: O(|V|+|E|), the number of vertices plus the number
* of edges.
*
* \example examples/simple/igraph_lcf.c
*/
int igraph_lcf(igraph_t *graph, igraph_integer_t n, ...) {
igraph_vector_t shifts;
igraph_integer_t repeats;
va_list ap;
IGRAPH_VECTOR_INIT_FINALLY(&shifts, 0);
va_start(ap, n);
while (1) {
int num = va_arg(ap, int);
if (num == 0) {
break;
}
IGRAPH_CHECK(igraph_vector_push_back(&shifts, num));
}
if (igraph_vector_size(&shifts) == 0) {
repeats = 0;
} else {
repeats = (igraph_integer_t) igraph_vector_pop_back(&shifts);
}
IGRAPH_CHECK(igraph_lcf_vector(graph, n, &shifts, repeats));
igraph_vector_destroy(&shifts);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
const igraph_real_t igraph_i_famous_bull[] = {
5, 5, 0,
0, 1, 0, 2, 1, 2, 1, 3, 2, 4
};
const igraph_real_t igraph_i_famous_chvatal[] = {
12, 24, 0,
5, 6, 6, 7, 7, 8, 8, 9, 5, 9, 4, 5, 4, 8, 2, 8, 2, 6, 0, 6, 0, 9, 3, 9, 3, 7,
1, 7, 1, 5, 1, 10, 4, 10, 4, 11, 2, 11, 0, 10, 0, 11, 3, 11, 3, 10, 1, 2
};
const igraph_real_t igraph_i_famous_coxeter[] = {
28, 42, 0,
0, 1, 0, 2, 0, 7, 1, 4, 1, 13, 2, 3, 2, 8, 3, 6, 3, 9, 4, 5, 4, 12, 5, 6, 5,
11, 6, 10, 7, 19, 7, 24, 8, 20, 8, 23, 9, 14, 9, 22, 10, 15, 10, 21, 11, 16,
11, 27, 12, 17, 12, 26, 13, 18, 13, 25, 14, 17, 14, 18, 15, 18, 15, 19, 16, 19,
16, 20, 17, 20, 21, 23, 21, 26, 22, 24, 22, 27, 23, 25, 24, 26, 25, 27
};
const igraph_real_t igraph_i_famous_cubical[] = {
8, 12, 0,
0, 1, 1, 2, 2, 3, 0, 3, 4, 5, 5, 6, 6, 7, 4, 7, 0, 4, 1, 5, 2, 6, 3, 7
};
const igraph_real_t igraph_i_famous_diamond[] = {
4, 5, 0,
0, 1, 0, 2, 1, 2, 1, 3, 2, 3
};
const igraph_real_t igraph_i_famous_dodecahedron[] = {
20, 30, 0,
0, 1, 0, 4, 0, 5, 1, 2, 1, 6, 2, 3, 2, 7, 3, 4, 3, 8, 4, 9, 5, 10, 5, 11, 6,
10, 6, 14, 7, 13, 7, 14, 8, 12, 8, 13, 9, 11, 9, 12, 10, 15, 11, 16, 12, 17,
13, 18, 14, 19, 15, 16, 15, 19, 16, 17, 17, 18, 18, 19
};
const igraph_real_t igraph_i_famous_folkman[] = {
20, 40, 0,
0, 5, 0, 8, 0, 10, 0, 13, 1, 7, 1, 9, 1, 12, 1, 14, 2, 6, 2, 8, 2, 11, 2, 13,
3, 5, 3, 7, 3, 10, 3, 12, 4, 6, 4, 9, 4, 11, 4, 14, 5, 15, 5, 19, 6, 15, 6, 16,
7, 16, 7, 17, 8, 17, 8, 18, 9, 18, 9, 19, 10, 15, 10, 19, 11, 15, 11, 16, 12,
16, 12, 17, 13, 17, 13, 18, 14, 18, 14, 19
};
const igraph_real_t igraph_i_famous_franklin[] = {
12, 18, 0,
0, 1, 0, 2, 0, 6, 1, 3, 1, 7, 2, 4, 2, 10, 3, 5, 3, 11, 4, 5, 4, 6, 5, 7, 6, 8,
7, 9, 8, 9, 8, 11, 9, 10, 10, 11
};
const igraph_real_t igraph_i_famous_frucht[] = {
12, 18, 0,
0, 1, 0, 2, 0, 11, 1, 3, 1, 6, 2, 5, 2, 10, 3, 4, 3, 6, 4, 8, 4, 11, 5, 9, 5,
10, 6, 7, 7, 8, 7, 9, 8, 9, 10, 11
};
const igraph_real_t igraph_i_famous_grotzsch[] = {
11, 20, 0,
0, 1, 0, 2, 0, 7, 0, 10, 1, 3, 1, 6, 1, 9, 2, 4, 2, 6, 2, 8, 3, 4, 3, 8, 3, 10,
4, 7, 4, 9, 5, 6, 5, 7, 5, 8, 5, 9, 5, 10
};
const igraph_real_t igraph_i_famous_heawood[] = {
14, 21, 0,
0, 1, 0, 5, 0, 13, 1, 2, 1, 10, 2, 3, 2, 7, 3, 4, 3, 12, 4, 5, 4, 9, 5, 6, 6,
7, 6, 11, 7, 8, 8, 9, 8, 13, 9, 10, 10, 11, 11, 12, 12, 13
};
const igraph_real_t igraph_i_famous_herschel[] = {
11, 18, 0,
0, 2, 0, 3, 0, 4, 0, 5, 1, 2, 1, 3, 1, 6, 1, 7, 2, 10, 3, 9, 4, 8, 4, 9, 5, 8,
5, 10, 6, 8, 6, 9, 7, 8, 7, 10
};
const igraph_real_t igraph_i_famous_house[] = {
5, 6, 0,
0, 1, 0, 2, 1, 3, 2, 3, 2, 4, 3, 4
};
const igraph_real_t igraph_i_famous_housex[] = {
5, 8, 0,
0, 1, 0, 2, 0, 3, 1, 2, 1, 3, 2, 3, 2, 4, 3, 4
};
const igraph_real_t igraph_i_famous_icosahedron[] = {
12, 30, 0,
0, 1, 0, 2, 0, 3, 0, 4, 0, 8, 1, 2, 1, 6, 1, 7, 1, 8, 2, 4, 2, 5, 2, 6, 3, 4,
3, 8, 3, 9, 3, 11, 4, 5, 4, 11, 5, 6, 5, 10, 5, 11, 6, 7, 6, 10, 7, 8, 7, 9, 7,
10, 8, 9, 9, 10, 9, 11, 10, 11
};
const igraph_real_t igraph_i_famous_krackhardt_kite[] = {
10, 18, 0,
0, 1, 0, 2, 0, 3, 0, 5, 1, 3, 1, 4, 1, 6, 2, 3, 2, 5, 3, 4, 3, 5, 3, 6, 4, 6, 5, 6, 5, 7, 6, 7, 7, 8, 8, 9
};
const igraph_real_t igraph_i_famous_levi[] = {
30, 45, 0,
0, 1, 0, 7, 0, 29, 1, 2, 1, 24, 2, 3, 2, 11, 3, 4, 3, 16, 4, 5, 4, 21, 5, 6, 5,
26, 6, 7, 6, 13, 7, 8, 8, 9, 8, 17, 9, 10, 9, 22, 10, 11, 10, 27, 11, 12, 12,
13, 12, 19, 13, 14, 14, 15, 14, 23, 15, 16, 15, 28, 16, 17, 17, 18, 18, 19, 18,
25, 19, 20, 20, 21, 20, 29, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
28, 28, 29
};
const igraph_real_t igraph_i_famous_mcgee[] = {
24, 36, 0,
0, 1, 0, 7, 0, 23, 1, 2, 1, 18, 2, 3, 2, 14, 3, 4, 3, 10, 4, 5, 4, 21, 5, 6, 5,
17, 6, 7, 6, 13, 7, 8, 8, 9, 8, 20, 9, 10, 9, 16, 10, 11, 11, 12, 11, 23, 12,
13, 12, 19, 13, 14, 14, 15, 15, 16, 15, 22, 16, 17, 17, 18, 18, 19, 19, 20, 20,
21, 21, 22, 22, 23
};
const igraph_real_t igraph_i_famous_meredith[] = {
70, 140, 0,
0, 4, 0, 5, 0, 6, 1, 4, 1, 5, 1, 6, 2, 4, 2, 5, 2, 6, 3, 4, 3, 5, 3, 6, 7, 11,
7, 12, 7, 13, 8, 11, 8, 12, 8, 13, 9, 11, 9, 12, 9, 13, 10, 11, 10, 12, 10, 13,
14, 18, 14, 19, 14, 20, 15, 18, 15, 19, 15, 20, 16, 18, 16, 19, 16, 20, 17, 18,
17, 19, 17, 20, 21, 25, 21, 26, 21, 27, 22, 25, 22, 26, 22, 27, 23, 25, 23, 26,
23, 27, 24, 25, 24, 26, 24, 27, 28, 32, 28, 33, 28, 34, 29, 32, 29, 33, 29, 34,
30, 32, 30, 33, 30, 34, 31, 32, 31, 33, 31, 34, 35, 39, 35, 40, 35, 41, 36, 39,
36, 40, 36, 41, 37, 39, 37, 40, 37, 41, 38, 39, 38, 40, 38, 41, 42, 46, 42, 47,
42, 48, 43, 46, 43, 47, 43, 48, 44, 46, 44, 47, 44, 48, 45, 46, 45, 47, 45, 48,
49, 53, 49, 54, 49, 55, 50, 53, 50, 54, 50, 55, 51, 53, 51, 54, 51, 55, 52, 53,
52, 54, 52, 55, 56, 60, 56, 61, 56, 62, 57, 60, 57, 61, 57, 62, 58, 60, 58, 61,
58, 62, 59, 60, 59, 61, 59, 62, 63, 67, 63, 68, 63, 69, 64, 67, 64, 68, 64, 69,
65, 67, 65, 68, 65, 69, 66, 67, 66, 68, 66, 69, 2, 50, 1, 51, 9, 57, 8, 58, 16,
64, 15, 65, 23, 36, 22, 37, 30, 43, 29, 44, 3, 21, 7, 24, 14, 31, 0, 17, 10,
28, 38, 42, 35, 66, 59, 63, 52, 56, 45, 49
};
const igraph_real_t igraph_i_famous_noperfectmatching[] = {
16, 27, 0,
0, 1, 0, 2, 0, 3, 1, 2, 1, 3, 2, 3, 2, 4, 3, 4, 4, 5, 5, 6, 5, 7, 6, 12, 6, 13,
7, 8, 7, 9, 8, 9, 8, 10, 8, 11, 9, 10, 9, 11, 10, 11, 12, 13, 12, 14, 12, 15,
13, 14, 13, 15, 14, 15
};
const igraph_real_t igraph_i_famous_nonline[] = {
50, 72, 0,
0, 1, 0, 2, 0, 3, 4, 6, 4, 7, 5, 6, 5, 7, 6, 7, 7, 8, 9, 11, 9, 12, 9, 13, 10,
11, 10, 12, 10, 13, 11, 12, 11, 13, 12, 13, 14, 15, 15, 16, 15, 17, 16, 17, 16,
18, 17, 18, 18, 19, 20, 21, 20, 22, 20, 23, 21, 22, 21, 23, 21, 24, 22, 23, 22,
24, 24, 25, 26, 27, 26, 28, 26, 29, 27, 28, 27, 29, 27, 30, 27, 31, 28, 29, 28,
30, 28, 31, 30, 31, 32, 34, 32, 35, 32, 36, 33, 34, 33, 35, 33, 37, 34, 35, 36,
37, 38, 39, 38, 40, 38, 43, 39, 40, 39, 41, 39, 42, 39, 43, 40, 41, 41, 42, 42,
43, 44, 45, 44, 46, 45, 46, 45, 47, 46, 47, 46, 48, 47, 48, 47, 49, 48, 49
};
const igraph_real_t igraph_i_famous_octahedron[] = {
6, 12, 0,
0, 1, 0, 2, 1, 2, 3, 4, 3, 5, 4, 5, 0, 3, 0, 5, 1, 3, 1, 4, 2, 4, 2, 5
};
const igraph_real_t igraph_i_famous_petersen[] = {
10, 15, 0,
0, 1, 0, 4, 0, 5, 1, 2, 1, 6, 2, 3, 2, 7, 3, 4, 3, 8, 4, 9, 5, 7, 5, 8, 6, 8, 6, 9, 7, 9
};
const igraph_real_t igraph_i_famous_robertson[] = {
19, 38, 0,
0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12,
12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 0, 18, 0, 4, 4, 9, 9, 13, 13,
17, 2, 17, 2, 6, 6, 10, 10, 15, 0, 15, 1, 8, 8, 16, 5, 16, 5, 12, 1, 12, 7, 18,
7, 14, 3, 14, 3, 11, 11, 18
};
const igraph_real_t igraph_i_famous_smallestcyclicgroup[] = {
9, 15, 0,
0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 1, 2, 1, 3, 1, 7, 1, 8, 2, 5, 2, 6, 2, 7, 3, 8,
4, 5, 6, 7
};
const igraph_real_t igraph_i_famous_tetrahedron[] = {
4, 6, 0,
0, 3, 1, 3, 2, 3, 0, 1, 1, 2, 0, 2
};
const igraph_real_t igraph_i_famous_thomassen[] = {
34, 52, 0,
0, 2, 0, 3, 1, 3, 1, 4, 2, 4, 5, 7, 5, 8, 6, 8, 6, 9, 7, 9, 10, 12, 10, 13, 11,
13, 11, 14, 12, 14, 15, 17, 15, 18, 16, 18, 16, 19, 17, 19, 9, 19, 4, 14, 24,
25, 25, 26, 20, 26, 20, 21, 21, 22, 22, 23, 23, 27, 27, 28, 28, 29, 29, 30, 30,
31, 31, 32, 32, 33, 24, 33, 5, 24, 6, 25, 7, 26, 8, 20, 0, 20, 1, 21, 2, 22, 3,
23, 10, 27, 11, 28, 12, 29, 13, 30, 15, 30, 16, 31, 17, 32, 18, 33
};
const igraph_real_t igraph_i_famous_tutte[] = {
46, 69, 0,
0, 10, 0, 11, 0, 12, 1, 2, 1, 7, 1, 19, 2, 3, 2, 41, 3, 4, 3, 27, 4, 5, 4, 33,
5, 6, 5, 45, 6, 9, 6, 29, 7, 8, 7, 21, 8, 9, 8, 22, 9, 24, 10, 13, 10, 14, 11,
26, 11, 28, 12, 30, 12, 31, 13, 15, 13, 21, 14, 15, 14, 18, 15, 16, 16, 17, 16,
20, 17, 18, 17, 23, 18, 24, 19, 25, 19, 40, 20, 21, 20, 22, 22, 23, 23, 24, 25,
26, 25, 38, 26, 34, 27, 28, 27, 39, 28, 34, 29, 30, 29, 44, 30, 35, 31, 32, 31,
35, 32, 33, 32, 42, 33, 43, 34, 36, 35, 37, 36, 38, 36, 39, 37, 42, 37, 44, 38,
40, 39, 41, 40, 41, 42, 43, 43, 45, 44, 45
};
const igraph_real_t igraph_i_famous_uniquely3colorable[] = {
12, 22, 0,
0, 1, 0, 3, 0, 6, 0, 8, 1, 4, 1, 7, 1, 9, 2, 3, 2, 6, 2, 7, 2, 9, 2, 11, 3, 4,
3, 10, 4, 5, 4, 11, 5, 6, 5, 7, 5, 8, 5, 10, 8, 11, 9, 10
};
const igraph_real_t igraph_i_famous_walther[] = {
25, 31, 0,
0, 1, 1, 2, 1, 8, 2, 3, 2, 13, 3, 4, 3, 16, 4, 5, 5, 6, 5, 19, 6, 7, 6, 20, 7,
21, 8, 9, 8, 13, 9, 10, 9, 22, 10, 11, 10, 20, 11, 12, 13, 14, 14, 15, 14, 23,
15, 16, 15, 17, 17, 18, 18, 19, 18, 24, 20, 24, 22, 23, 23, 24
};
const igraph_real_t igraph_i_famous_zachary[] = {
34, 78, 0,
0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8,
0, 10, 0, 11, 0, 12, 0, 13, 0, 17, 0, 19, 0, 21, 0, 31,
1, 2, 1, 3, 1, 7, 1, 13, 1, 17, 1, 19, 1, 21, 1, 30,
2, 3, 2, 7, 2, 27, 2, 28, 2, 32, 2, 9, 2, 8, 2, 13,
3, 7, 3, 12, 3, 13, 4, 6, 4, 10, 5, 6, 5, 10, 5, 16,
6, 16, 8, 30, 8, 32, 8, 33, 9, 33, 13, 33, 14, 32, 14, 33,
15, 32, 15, 33, 18, 32, 18, 33, 19, 33, 20, 32, 20, 33,
22, 32, 22, 33, 23, 25, 23, 27, 23, 32, 23, 33, 23, 29,
24, 25, 24, 27, 24, 31, 25, 31, 26, 29, 26, 33, 27, 33,
28, 31, 28, 33, 29, 32, 29, 33, 30, 32, 30, 33, 31, 32, 31, 33,
32, 33
};
int igraph_i_famous(igraph_t *graph, const igraph_real_t *data);
int igraph_i_famous(igraph_t *graph, const igraph_real_t *data) {
long int no_of_nodes = (long int) data[0];
long int no_of_edges = (long int) data[1];
igraph_bool_t directed = (igraph_bool_t) data[2];
igraph_vector_t edges;
igraph_vector_view(&edges, data + 3, 2 * no_of_edges);
IGRAPH_CHECK(igraph_create(graph, &edges, (igraph_integer_t) no_of_nodes,
directed));
return 0;
}
/**
* \function igraph_famous
* \brief Create a famous graph by simply providing its name
*
* </para><para>
* The name of the graph can be simply supplied as a string.
* Note that this function creates graphs which don't take any parameters,
* there are separate functions for graphs with parameters, eg. \ref
* igraph_full() for creating a full graph.
*
* </para><para>
* The following graphs are supported:
* \clist
* \cli Bull
* The bull graph, 5 vertices, 5 edges, resembles the
* head of a bull if drawn properly.
* \cli Chvatal
* This is the smallest triangle-free graph that is
* both 4-chromatic and 4-regular. According to the Grunbaum
* conjecture there exists an m-regular, m-chromatic graph
* with n vertices for every m>1 and n>2. The Chvatal graph
* is an example for m=4 and n=12. It has 24 edges.
* \cli Coxeter
* A non-Hamiltonian cubic symmetric graph with 28
* vertices and 42 edges.
* \cli Cubical
* The Platonic graph of the cube. A convex regular
* polyhedron with 8 vertices and 12 edges.
* \cli Diamond
* A graph with 4 vertices and 5 edges, resembles a
* schematic diamond if drawn properly.
* \cli Dodecahedral, Dodecahedron
* Another Platonic solid
* with 20 vertices and 30 edges.
* \cli Folkman
* The semisymmetric graph with minimum number of
* vertices, 20 and 40 edges. A semisymmetric graph is
* regular, edge transitive and not vertex transitive.
* \cli Franklin
* This is a graph whose embedding to the Klein
* bottle can be colored with six colors, it is a
* counterexample to the necessity of the Heawood
* conjecture on a Klein bottle. It has 12 vertices and 18
* edges.
* \cli Frucht
* The Frucht Graph is the smallest cubical graph
* whose automorphism group consists only of the identity
* element. It has 12 vertices and 18 edges.
* \cli Grotzsch
* The Grötzsch graph is a triangle-free graph with
* 11 vertices, 20 edges, and chromatic number 4. It is named after
* German mathematician Herbert Grötzsch, and its existence
* demonstrates that the assumption of planarity is necessary in
* Grötzsch's theorem that every triangle-free planar
* graph is 3-colorable.
* \cli Heawood
* The Heawood graph is an undirected graph with 14
* vertices and 21 edges. The graph is cubic, and all cycles in the
* graph have six or more edges. Every smaller cubic graph has shorter
* cycles, so this graph is the 6-cage, the smallest cubic graph of
* girth 6.
* \cli Herschel
* The Herschel graph is the smallest
* nonhamiltonian polyhedral graph. It is the
* unique such graph on 11 nodes, and has 18 edges.
* \cli House
* The house graph is a 5-vertex, 6-edge graph, the
* schematic draw of a house if drawn properly, basically a
* triangle on top of a square.
* \cli HouseX
* The same as the house graph with an X in the square. 5
* vertices and 8 edges.
* \cli Icosahedral, Icosahedron
* A Platonic solid with 12
* vertices and 30 edges.
* \cli Krackhardt_Kite
* A social network with 10 vertices and 18 edges.
* Krackhardt, D. Assessing the Political Landscape:
* Structure, Cognition, and Power in Organizations.
* Admin. Sci. Quart. 35, 342-369, 1990.
* \cli Levi
* The graph is a 4-arc transitive cubic graph, it has
* 30 vertices and 45 edges.
* \cli McGee
* The McGee graph is the unique 3-regular 7-cage
* graph, it has 24 vertices and 36 edges.
* \cli Meredith
* The Meredith graph is a quartic graph on 70
* nodes and 140 edges that is a counterexample to the conjecture that
* every 4-regular 4-connected graph is Hamiltonian.
* \cli Noperfectmatching
* A connected graph with 16 vertices and
* 27 edges containing no perfect matching. A matching in a graph
* is a set of pairwise non-incident edges; that is, no two edges
* share a common vertex. A perfect matching is a matching
* which covers all vertices of the graph.
* \cli Nonline
* A graph whose connected components are the 9
* graphs whose presence as a vertex-induced subgraph in a
* graph makes a nonline graph. It has 50 vertices and 72 edges.
* \cli Octahedral, Octahedron
* Platonic solid with 6
* vertices and 12 edges.
* \cli Petersen
* A 3-regular graph with 10 vertices and 15 edges. It is
* the smallest hypohamiltonian graph, ie. it is
* non-hamiltonian but removing any single vertex from it makes it
* Hamiltonian.
* \cli Robertson
* The unique (4,5)-cage graph, ie. a 4-regular
* graph of girth 5. It has 19 vertices and 38 edges.
* \cli Smallestcyclicgroup
* A smallest nontrivial graph
* whose automorphism group is cyclic. It has 9 vertices and
* 15 edges.
* \cli Tetrahedral, Tetrahedron
* Platonic solid with 4
* vertices and 6 edges.
* \cli Thomassen
* The smallest hypotraceable graph,
* on 34 vertices and 52 edges. A hypotracable graph does
* not contain a Hamiltonian path but after removing any
* single vertex from it the remainder always contains a
* Hamiltonian path. A graph containing a Hamiltonian path
* is called traceable.
* \cli Tutte
* Tait's Hamiltonian graph conjecture states that
* every 3-connected 3-regular planar graph is Hamiltonian.
* This graph is a counterexample. It has 46 vertices and 69
* edges.
* \cli Uniquely3colorable
* Returns a 12-vertex, triangle-free
* graph with chromatic number 3 that is uniquely
* 3-colorable.
* \cli Walther
* An identity graph with 25 vertices and 31
* edges. An identity graph has a single graph automorphism,
* the trivial one.
* \cli Zachary
* Social network of friendships between 34 members of a
* karate club at a US university in the 1970s. See
* W. W. Zachary, An information flow model for conflict and
* fission in small groups, Journal of Anthropological
* Research 33, 452-473 (1977).
* \endclist
*
* \param graph Pointer to an uninitialized graph object.
* \param name Character constant, the name of the graph to be
* created, it is case insensitive.
* \return Error code, IGRAPH_EINVAL if there is no graph with the
* given name.
*
* \sa Other functions for creating graph structures:
* \ref igraph_ring(), \ref igraph_tree(), \ref igraph_lattice(), \ref
* igraph_full().
*
* Time complexity: O(|V|+|E|), the number of vertices plus the number
* of edges in the graph.
*/
int igraph_famous(igraph_t *graph, const char *name) {
if (!strcasecmp(name, "bull")) {
return igraph_i_famous(graph, igraph_i_famous_bull);
} else if (!strcasecmp(name, "chvatal")) {
return igraph_i_famous(graph, igraph_i_famous_chvatal);
} else if (!strcasecmp(name, "coxeter")) {
return igraph_i_famous(graph, igraph_i_famous_coxeter);
} else if (!strcasecmp(name, "cubical")) {
return igraph_i_famous(graph, igraph_i_famous_cubical);
} else if (!strcasecmp(name, "diamond")) {
return igraph_i_famous(graph, igraph_i_famous_diamond);
} else if (!strcasecmp(name, "dodecahedral") ||
!strcasecmp(name, "dodecahedron")) {
return igraph_i_famous(graph, igraph_i_famous_dodecahedron);
} else if (!strcasecmp(name, "folkman")) {
return igraph_i_famous(graph, igraph_i_famous_folkman);
} else if (!strcasecmp(name, "franklin")) {
return igraph_i_famous(graph, igraph_i_famous_franklin);
} else if (!strcasecmp(name, "frucht")) {
return igraph_i_famous(graph, igraph_i_famous_frucht);
} else if (!strcasecmp(name, "grotzsch")) {
return igraph_i_famous(graph, igraph_i_famous_grotzsch);
} else if (!strcasecmp(name, "heawood")) {
return igraph_i_famous(graph, igraph_i_famous_heawood);
} else if (!strcasecmp(name, "herschel")) {
return igraph_i_famous(graph, igraph_i_famous_herschel);
} else if (!strcasecmp(name, "house")) {
return igraph_i_famous(graph, igraph_i_famous_house);
} else if (!strcasecmp(name, "housex")) {
return igraph_i_famous(graph, igraph_i_famous_housex);
} else if (!strcasecmp(name, "icosahedral") ||
!strcasecmp(name, "icosahedron")) {
return igraph_i_famous(graph, igraph_i_famous_icosahedron);
} else if (!strcasecmp(name, "krackhardt_kite")) {
return igraph_i_famous(graph, igraph_i_famous_krackhardt_kite);
} else if (!strcasecmp(name, "levi")) {
return igraph_i_famous(graph, igraph_i_famous_levi);
} else if (!strcasecmp(name, "mcgee")) {
return igraph_i_famous(graph, igraph_i_famous_mcgee);
} else if (!strcasecmp(name, "meredith")) {
return igraph_i_famous(graph, igraph_i_famous_meredith);
} else if (!strcasecmp(name, "noperfectmatching")) {
return igraph_i_famous(graph, igraph_i_famous_noperfectmatching);
} else if (!strcasecmp(name, "nonline")) {
return igraph_i_famous(graph, igraph_i_famous_nonline);
} else if (!strcasecmp(name, "octahedral") ||
!strcasecmp(name, "octahedron")) {
return igraph_i_famous(graph, igraph_i_famous_octahedron);
} else if (!strcasecmp(name, "petersen")) {
return igraph_i_famous(graph, igraph_i_famous_petersen);
} else if (!strcasecmp(name, "robertson")) {
return igraph_i_famous(graph, igraph_i_famous_robertson);
} else if (!strcasecmp(name, "smallestcyclicgroup")) {
return igraph_i_famous(graph, igraph_i_famous_smallestcyclicgroup);
} else if (!strcasecmp(name, "tetrahedral") ||
!strcasecmp(name, "tetrahedron")) {
return igraph_i_famous(graph, igraph_i_famous_tetrahedron);
} else if (!strcasecmp(name, "thomassen")) {
return igraph_i_famous(graph, igraph_i_famous_thomassen);
} else if (!strcasecmp(name, "tutte")) {
return igraph_i_famous(graph, igraph_i_famous_tutte);
} else if (!strcasecmp(name, "uniquely3colorable")) {
return igraph_i_famous(graph, igraph_i_famous_uniquely3colorable);
} else if (!strcasecmp(name, "walther")) {
return igraph_i_famous(graph, igraph_i_famous_walther);
} else if (!strcasecmp(name, "zachary")) {
return igraph_i_famous(graph, igraph_i_famous_zachary);
} else {
IGRAPH_ERROR("Unknown graph, see documentation", IGRAPH_EINVAL);
}
return 0;
}
/**
* \function igraph_adjlist
* Create a graph from an adjacency list
*
* An adjacency list is a list of vectors, containing the neighbors
* of all vertices. For operations that involve many changes to the
* graph structure, it is recommended that you convert the graph into
* an adjacency list via \ref igraph_adjlist_init(), perform the
* modifications (these are cheap for an adjacency list) and then
* recreate the igraph graph via this function.
*
* \param graph Pointer to an uninitialized graph object.
* \param adjlist The adjacency list.
* \param mode Whether or not to create a directed graph. \c IGRAPH_ALL
* means an undirected graph, \c IGRAPH_OUT means a
* directed graph from an out-adjacency list (i.e. each
* list contains the successors of the corresponding
* vertices), \c IGRAPH_IN means a directed graph from an
* in-adjacency list
* \param duplicate Logical, for undirected graphs this specified
* whether each edge is included twice, in the vectors of
* both adjacent vertices. If this is false (0), then it is
* assumed that every edge is included only once. This argument
* is ignored for directed graphs.
* \return Error code.
*
* \sa \ref igraph_adjlist_init() for the opposite operation.
*
* Time complexity: O(|V|+|E|).
*
*/
int igraph_adjlist(igraph_t *graph, const igraph_adjlist_t *adjlist,
igraph_neimode_t mode, igraph_bool_t duplicate) {
long int no_of_nodes = igraph_adjlist_size(adjlist);
long int no_of_edges = 0;
long int i;
igraph_vector_t edges;
long int edgeptr = 0;
duplicate = duplicate && (mode == IGRAPH_ALL); /* only duplicate if undirected */
for (i = 0; i < no_of_nodes; i++) {
no_of_edges += igraph_vector_int_size(igraph_adjlist_get(adjlist, i));
}
if (duplicate) {
no_of_edges /= 2;
}
IGRAPH_VECTOR_INIT_FINALLY(&edges, 2 * no_of_edges);
for (i = 0; i < no_of_nodes; i++) {
igraph_vector_int_t *neis = igraph_adjlist_get(adjlist, i);
long int j, n = igraph_vector_int_size(neis);
long int loops = 0;
for (j = 0; j < n; j++) {
long int nei = (long int) VECTOR(*neis)[j];
if (nei == i) {
loops++;
} else {
if (! duplicate || nei > i) {
if (edgeptr + 2 > 2 * no_of_edges) {
IGRAPH_ERROR("Invalid adjacency list, most probably not correctly"
" duplicated edges for an undirected graph", IGRAPH_EINVAL);
}
if (mode == IGRAPH_IN) {
VECTOR(edges)[edgeptr++] = nei;
VECTOR(edges)[edgeptr++] = i;
} else {
VECTOR(edges)[edgeptr++] = i;
VECTOR(edges)[edgeptr++] = nei;
}
}
}
}
/* loops */
if (duplicate) {
loops = loops / 2;
}
if (edgeptr + 2 * loops > 2 * no_of_edges) {
IGRAPH_ERROR("Invalid adjacency list, most probably not correctly"
" duplicated edges for an undirected graph", IGRAPH_EINVAL);
}
for (j = 0; j < loops; j++) {
VECTOR(edges)[edgeptr++] = i;
VECTOR(edges)[edgeptr++] = i;
}
}
if (mode == IGRAPH_ALL)
IGRAPH_CHECK(igraph_create(graph, &edges,
(igraph_integer_t) no_of_nodes, 0));
else
IGRAPH_CHECK(igraph_create(graph, &edges,
(igraph_integer_t) no_of_nodes, 1));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \ingroup generators
* \function igraph_from_prufer
* \brief Generates a tree from a Prüfer sequence
*
* A Prüfer sequence is a unique sequence of integers associated
* with a labelled tree. A tree on n vertices can be represented by a
* sequence of n-2 integers, each between 0 and n-1 (inclusive).
*
* The algorithm used by this function is based on
* Paulius Micikevičius, Saverio Caminiti, Narsingh Deo:
* Linear-time Algorithms for Encoding Trees as Sequences of Node Labels
*
* \param graph Pointer to an uninitialized graph object.
* \param prufer The Prüfer sequence
* \return Error code:
* \clist
* \cli IGRAPH_ENOMEM
* there is not enough memory to perform the operation.
* \cli IGRAPH_EINVAL
* invalid Prüfer sequence given
* \endclist
*
* \sa \ref igraph_tree(), \ref igraph_tree_game()
*
*/
int igraph_from_prufer(igraph_t *graph, const igraph_vector_int_t *prufer) {
igraph_vector_int_t degree;
igraph_vector_t edges;
long n;
long i, k;
long u, v; /* vertices */
long ec;
n = igraph_vector_int_size(prufer) + 2;
IGRAPH_VECTOR_INT_INIT_FINALLY(°ree, n); /* initializes vector to zeros */
IGRAPH_VECTOR_INIT_FINALLY(&edges, 2 * (n - 1));
/* build out-degree vector (i.e. number of child vertices) and verify Prufer sequence */
for (i = 0; i < n - 2; ++i) {
long u = VECTOR(*prufer)[i];
if (u >= n || u < 0) {
IGRAPH_ERROR("Invalid Prufer sequence", IGRAPH_EINVAL);
}
VECTOR(degree)[u] += 1;
}
v = 0; /* initialize v now, in case Prufer sequence is empty */
k = 0; /* index into the Prufer vector */
ec = 0; /* index into the edges vector */
for (i = 0; i < n; ++i) {
u = i;
while (k < n - 2 && u <= i && (VECTOR(degree)[u] == 0)) {
/* u is a leaf here */
v = VECTOR(*prufer)[k]; /* parent of u */
/* add edge */
VECTOR(edges)[ec++] = v;
VECTOR(edges)[ec++] = u;
k += 1;
VECTOR(degree)[v] -= 1;
u = v;
}
if (k == n - 2) {
break;
}
}
/* find u for last edge, v is already set */
for (u = i + 1; u < n; ++u)
if ((VECTOR(degree)[u] == 0) && u != v) {
break;
}
/* add last edge */
VECTOR(edges)[ec++] = v;
VECTOR(edges)[ec++] = u;
IGRAPH_CHECK(igraph_create(graph, &edges, (igraph_integer_t) n, /* directed = */ 0));
igraph_vector_destroy(&edges);
igraph_vector_int_destroy(°ree);
IGRAPH_FINALLY_CLEAN(2);
return IGRAPH_SUCCESS;
}