~ubuntu-branches/ubuntu/lucid/igraph/lucid

« back to all changes in this revision

Viewing changes to src/structure_generators.c

Committer: Bazaar Package Importer
Author(s): Mathieu Malaterre
Date: 2009-11-16 18:12:42 UTC
Revision ID: james.westby@ubuntu.com-20091116181242-mzv9p5fz9uj57xd1

Tags: upstream-0.5.3

Import upstream version 0.5.3

files added:

AUTHORS

COPYING

ChangeLog

INSTALL

Makefile.am

Makefile.in

NEWS

README

TODO

aclocal.m4

config.guess

config.h.in

config.sub

configure

configure.in

depcomp

doc/Makefile.in

doc/book

doc/book/Makefile.in

doc/igraph-docs.info

doc/igraph.3

examples

examples/simple

examples/simple/LINKS.NET

examples/simple/adjlist.c

examples/simple/ak-4102.max

examples/simple/bellman_ford.c

examples/simple/bellman_ford.out

examples/simple/cattributes.c

examples/simple/cattributes.out

examples/simple/cattributes2.c

examples/simple/cattributes2.out

examples/simple/d_indheap.c

examples/simple/d_indheap.out

examples/simple/dijkstra.c

examples/simple/dijkstra.out

examples/simple/dot.c

examples/simple/dot.out

examples/simple/dqueue.c

examples/simple/eigenvector_centrality.c

examples/simple/eigenvector_centrality.out

examples/simple/flow.c

examples/simple/foreign.c

examples/simple/foreign.out

examples/simple/gml.c

examples/simple/gml.out

examples/simple/graphml-hsa05010.xml

examples/simple/graphml.c

examples/simple/graphml.out

examples/simple/heap.c

examples/simple/igraph_add_edges.c

examples/simple/igraph_add_edges.out

examples/simple/igraph_add_vertices.c

examples/simple/igraph_adjacency.c

examples/simple/igraph_array.c

examples/simple/igraph_array.out

examples/simple/igraph_atlas.c

examples/simple/igraph_atlas.out

examples/simple/igraph_average_path_length.c

examples/simple/igraph_barabasi_game.c

examples/simple/igraph_bfs.c

examples/simple/igraph_bfs.out

examples/simple/igraph_bipartite_create.c

examples/simple/igraph_bipartite_create.out

examples/simple/igraph_bipartite_projection.c

examples/simple/igraph_cliques.c

examples/simple/igraph_cliques.out

examples/simple/igraph_cocitation.c

examples/simple/igraph_cocitation.out

examples/simple/igraph_community_edge_betweenness.c

examples/simple/igraph_community_edge_betweenness.out

examples/simple/igraph_community_fastgreedy.c

examples/simple/igraph_community_fastgreedy.out

examples/simple/igraph_community_label_propagation.c

examples/simple/igraph_community_label_propagation.out

examples/simple/igraph_community_leading_eigenvector.c

examples/simple/igraph_community_leading_eigenvector.out

examples/simple/igraph_complementer.c

examples/simple/igraph_complementer.out

examples/simple/igraph_compose.c

examples/simple/igraph_compose.out

examples/simple/igraph_convergence_degree.c

examples/simple/igraph_convergence_degree.out

examples/simple/igraph_convex_hull.c

examples/simple/igraph_convex_hull.out

examples/simple/igraph_copy.c

examples/simple/igraph_create.c

examples/simple/igraph_decompose.c

examples/simple/igraph_decompose.out

examples/simple/igraph_degree.c

examples/simple/igraph_degree.out

examples/simple/igraph_degree_sequence_game.c

examples/simple/igraph_delete_edges.c

examples/simple/igraph_delete_vertices.c

examples/simple/igraph_diameter.c

examples/simple/igraph_diameter.out

examples/simple/igraph_difference.c

examples/simple/igraph_difference.out

examples/simple/igraph_disjoint_union.c

examples/simple/igraph_disjoint_union.out

examples/simple/igraph_edge_betweenness.c

examples/simple/igraph_edge_betweenness.out

examples/simple/igraph_empty.c

examples/simple/igraph_erdos_renyi_game.c

examples/simple/igraph_es_adj.c

examples/simple/igraph_es_adj.out

examples/simple/igraph_es_fromto.c

examples/simple/igraph_es_fromto.out

examples/simple/igraph_es_pairs.c

examples/simple/igraph_es_path.c

examples/simple/igraph_full.c

examples/simple/igraph_get_eid.c

examples/simple/igraph_get_eid.out

examples/simple/igraph_get_eids.c

examples/simple/igraph_get_eids.out

examples/simple/igraph_get_shortest_paths.c

examples/simple/igraph_get_shortest_paths.out

examples/simple/igraph_get_shortest_paths_dijkstra.c

examples/simple/igraph_get_shortest_paths_dijkstra.out

examples/simple/igraph_girth.c

examples/simple/igraph_grg_game.c

examples/simple/igraph_growing_random_game.c

examples/simple/igraph_hashtable.c

examples/simple/igraph_hashtable.out

examples/simple/igraph_i_cutheap.c

examples/simple/igraph_i_cutheap.out

examples/simple/igraph_i_layout_sphere.c

examples/simple/igraph_independent_sets.c

examples/simple/igraph_independent_sets.out

examples/simple/igraph_intersection.c

examples/simple/igraph_intersection.out

examples/simple/igraph_is_directed.c

examples/simple/igraph_is_loop.c

examples/simple/igraph_is_loop.out

examples/simple/igraph_is_multiple.c

examples/simple/igraph_is_multiple.out

examples/simple/igraph_lattice.c

examples/simple/igraph_layout_lgl.c

examples/simple/igraph_layout_merge.c

examples/simple/igraph_layout_reingold_tilford.c

examples/simple/igraph_layout_reingold_tilford.in

examples/simple/igraph_lcf.c

examples/simple/igraph_local_transitivity.c

examples/simple/igraph_mincut.c

examples/simple/igraph_mincut.out

examples/simple/igraph_minimum_spanning_tree.c

examples/simple/igraph_minimum_spanning_tree.out

examples/simple/igraph_motifs_randesu.c

examples/simple/igraph_motifs_randesu.out

examples/simple/igraph_neighbors.c

examples/simple/igraph_neighbors.out

examples/simple/igraph_pagerank.c

examples/simple/igraph_pagerank.out

examples/simple/igraph_preference_game.c

examples/simple/igraph_psumtree.c

examples/simple/igraph_read_graph_graphdb.c

examples/simple/igraph_read_graph_graphdb.out

examples/simple/igraph_read_graph_lgl-1.lgl

examples/simple/igraph_read_graph_lgl-2.lgl

examples/simple/igraph_read_graph_lgl-3.lgl

examples/simple/igraph_read_graph_lgl.c

examples/simple/igraph_read_graph_lgl.out

examples/simple/igraph_reciprocity.c

examples/simple/igraph_rewire.c

examples/simple/igraph_rewire.out

examples/simple/igraph_ring.c

examples/simple/igraph_set.c

examples/simple/igraph_set.out

examples/simple/igraph_similarity.c

examples/simple/igraph_similarity.out

examples/simple/igraph_simplify.c

examples/simple/igraph_simplify.out

examples/simple/igraph_small.c

examples/simple/igraph_small.out

examples/simple/igraph_star.c

examples/simple/igraph_strvector.c

examples/simple/igraph_strvector.out

examples/simple/igraph_to_undirected.c

examples/simple/igraph_to_undirected.out

examples/simple/igraph_topological_sorting.c

examples/simple/igraph_topological_sorting.out

examples/simple/igraph_transitivity.c

examples/simple/igraph_tree.c

examples/simple/igraph_trie.c

examples/simple/igraph_trie.out

examples/simple/igraph_union.c

examples/simple/igraph_union.out

examples/simple/igraph_vs_nonadj.c

examples/simple/igraph_vs_nonadj.out

examples/simple/igraph_vs_seq.c

examples/simple/igraph_vs_seq.out

examples/simple/igraph_vs_vector.c

examples/simple/igraph_vs_vector.out

examples/simple/igraph_weighted_adjacency.c

examples/simple/igraph_weighted_adjacency.out

examples/simple/igraph_write_graph_lgl.c

examples/simple/igraph_write_graph_pajek.c

examples/simple/igraph_write_graph_pajek.out

examples/simple/indheap.c

examples/simple/iso_b03_m1000.A00

examples/simple/karate.gml

examples/simple/lineendings.c

examples/simple/lineendings.out

examples/simple/matrix.c

examples/simple/matrix.out

examples/simple/matrix2.c

examples/simple/matrix2.out

examples/simple/pajek1.net

examples/simple/pajek2.net

examples/simple/pajek3.net

examples/simple/pajek4.net

examples/simple/random_seed.c

examples/simple/spinglass.c

examples/simple/spmatrix.c

examples/simple/spmatrix.out

examples/simple/stack.c

examples/simple/test.gxl

examples/simple/topology.c

examples/simple/topology.out

examples/simple/vector.c

examples/simple/vector.out

examples/simple/vector2.c

examples/simple/vector2.out

examples/simple/vector_ptr.c

examples/simple/walktrap.c

examples/simple/walktrap.out

igraph.pc

igraph.pc.in

igraph_Info.plist.in

include

include/arpack.h

include/array.h

include/attributes.h

include/dqueue.h

include/error.h

include/heap.h

include/igraph.h

include/igraph_pmt.h

include/igraph_pmt_off.h

include/interrupt.h

include/matrix.h

include/stack.h

include/types.h

include/vector.h

install-sh

interfaces

interfaces/Makefile.am

interfaces/Makefile.in

interfaces/R

interfaces/R/DESCRIPTION.in

interfaces/R/Makefile.in

interfaces/R/configure.in.in

interfaces/R/src

interfaces/R/src/Makevars.win.in

interfaces/shell

interfaces/shell/Makefile.am

interfaces/shell/Makefile.in

interfaces/shell/interface.c

ltmain.sh

missing

src/DensityGrid.cpp

src/DensityGrid.h

src/DensityGrid_3d.cpp

src/DensityGrid_3d.h

src/Makefile.am

src/Makefile.in

src/NetDataTypes.cpp

src/NetDataTypes.h

src/NetRoutines.cpp

src/NetRoutines.h

src/adjlist.c

src/arpack

src/arpack.c

src/arpack.h

src/arpack/dgetv0.c

src/arpack/dlaqrb.c

src/arpack/dmout.c

src/arpack/dnaitr.c

src/arpack/dnapps.c

src/arpack/dnaup2.c

src/arpack/dnaupd.c

src/arpack/dnconv.c

src/arpack/dneigh.c

src/arpack/dneupd.c

src/arpack/dngets.c

src/arpack/dsaitr.c

src/arpack/dsapps.c

src/arpack/dsaup2.c

src/arpack/dsaupd.c

src/arpack/dsconv.c

src/arpack/dseigt.c

src/arpack/dsesrt.c

src/arpack/dseupd.c

src/arpack/dsgets.c

src/arpack/dsortc.c

src/arpack/dsortr.c

src/arpack/dstatn.c

src/arpack/dstats.c

src/arpack/dstqrb.c

src/arpack/dvout.c

src/arpack/ivout.c

src/arpack/second.c

src/arpack_internal.h

src/array.c

src/array.h

src/array.pmt

src/atlas-edges.h

src/atlas.c

src/attributes.c

src/attributes.h

src/basic_query.c

src/bfgs.c

src/bipartite.c

src/blas

src/blas/dasum.c

src/blas/daxpy.c

src/blas/dcopy.c

src/blas/ddot.c

src/blas/dgemv.c

src/blas/dger.c

src/blas/dnrm2.c

src/blas/drot.c

src/blas/dscal.c

src/blas/dswap.c

src/blas/dtrmm.c

src/blas/idamax.c

src/blas/lsame.c

src/bliss.cc

src/bliss_bignum.hh

src/bliss_defs.hh

src/bliss_eqrefhash.cc

src/bliss_eqrefhash.hh

src/bliss_graph.cc

src/bliss_graph.hh

src/bliss_heap.cc

src/bliss_heap.hh

src/bliss_kqueue.hh

src/bliss_kstack.hh

src/bliss_orbit.cc

src/bliss_orbit.hh

src/bliss_partition.cc

src/bliss_partition.hh

src/bliss_timer.cc

src/bliss_timer.hh

src/bliss_utils.cc

src/bliss_utils.hh

src/cattributes.c

src/centrality.c

src/cliques.c

src/clustertool.cpp

src/cocitation.c

src/community.c

src/components.c

src/conversion.c

src/cores.c

src/dqueue.c

src/dqueue.h

src/dqueue.pmt

src/drl_Node.h

src/drl_Node_3d.h

src/drl_graph.cpp

src/drl_graph.h

src/drl_graph_3d.cpp

src/drl_graph_3d.h

src/drl_layout.cpp

src/drl_layout.h

src/drl_layout_3d.cpp

src/drl_layout_3d.h

src/drl_parse.cpp

src/drl_parse.h

src/error.c

src/error.h

src/evolver_cit.c

src/f2c

src/f2c.h

src/f2c/d_lg10.c

src/f2c/d_sign.c

src/f2c/etime_.c

src/f2c/i_dnnt.c

src/f2c/pow_dd.c

src/f2c/pow_di.c

src/f2c/s_cmp.c

src/f2c/s_copy.c

src/fast_community.c

src/flow.c

src/foreign-gml-lexer.c

src/foreign-gml-lexer.l

src/foreign-gml-parser.c

src/foreign-gml-parser.h

src/foreign-gml-parser.y

src/foreign-graphml.c

src/foreign-lgl-lexer.c

src/foreign-lgl-lexer.l

src/foreign-lgl-parser.c

src/foreign-lgl-parser.h

src/foreign-lgl-parser.y

src/foreign-ncol-lexer.c

src/foreign-ncol-lexer.l

src/foreign-ncol-parser.c

src/foreign-ncol-parser.h

src/foreign-ncol-parser.y

src/foreign-pajek-lexer.c

src/foreign-pajek-lexer.l

src/foreign-pajek-parser.c

src/foreign-pajek-parser.h

src/foreign-pajek-parser.y

src/foreign.c

src/forestfire.c

src/games.c

src/gengraph_box_list.cpp

src/gengraph_box_list.h

src/gengraph_definitions.h

src/gengraph_degree_sequence.cpp

src/gengraph_degree_sequence.h

src/gengraph_graph_molloy_hash.cpp

src/gengraph_graph_molloy_hash.h

src/gengraph_graph_molloy_optimized.cpp

src/gengraph_graph_molloy_optimized.h

src/gengraph_hash.h

src/gengraph_header.h

src/gengraph_mr-connected.cpp

src/gengraph_powerlaw.cpp

src/gengraph_powerlaw.h

src/gengraph_qsort.h

src/gengraph_random.cpp

src/gengraph_random.h

src/gengraph_vertex_cover.h

src/gml_tree.c

src/gml_tree.h

src/heap.c

src/heap.h

src/heap.pmt

src/igraph.h

src/igraph_buckets.c

src/igraph_grid.c

src/igraph_hashtable.c

src/igraph_heap.c

src/igraph_math.h

src/igraph_pmt.h

src/igraph_pmt_off.h

src/igraph_psumtree.c

src/igraph_set.c

src/igraph_stack.c

src/igraph_strvector.c

src/igraph_trie.c

src/interrupt.c

src/interrupt.h

src/iterators.c

src/lapack

src/lapack/dgeqr2.c

src/lapack/dlabad.c

src/lapack/dlacon.c

src/lapack/dlacpy.c

src/lapack/dladiv.c

src/lapack/dlae2.c

src/lapack/dlaev2.c

src/lapack/dlaexc.c

src/lapack/dlahqr.c

src/lapack/dlaln2.c

src/lapack/dlamch.c

src/lapack/dlange.c

src/lapack/dlanhs.c

src/lapack/dlanst.c

src/lapack/dlanv2.c

src/lapack/dlapy2.c

src/lapack/dlarf.c

src/lapack/dlarfg.c

src/lapack/dlarfx.c

src/lapack/dlarnv.c

src/lapack/dlartg.c

src/lapack/dlaruv.c

src/lapack/dlascl.c

src/lapack/dlaset.c

src/lapack/dlasr.c

src/lapack/dlasrt.c

src/lapack/dlassq.c

src/lapack/dlasy2.c

src/lapack/dorm2r.c

src/lapack/dsteqr.c

src/lapack/dtrevc.c

src/lapack/dtrexc.c

src/lapack/dtrsen.c

src/lapack/dtrsyl.c

src/lapack/xerbla.c

src/layout.c

src/math.c

src/matrix.c

src/matrix.h

src/matrix.pmt

src/measure_dynamics.c

src/memory.c

src/memory.h

src/motifs.c

src/operators.c

src/other.c

src/pottsmodel_2.cpp

src/pottsmodel_2.h

src/progress.c

src/random.c

src/random.h

src/revolver_cit.c

src/revolver_grow.c

src/revolver_ml_cit.c

src/spectral_properties.c

src/spmatrix.c

src/stack.h

src/stack.pmt

src/structural_properties.c

src/structure_generators.c

src/topology.c

src/type_indexededgelist.c

src/types.h

src/vector.c

src/vector.h

src/vector.pmt

src/vector_ptr.c

src/visitors.c

src/walktrap.cpp

src/walktrap_communities.cpp

src/walktrap_communities.h

src/walktrap_graph.cpp

src/walktrap_graph.h

src/walktrap_heap.cpp

src/walktrap_heap.h

src/zeroin.c

tests

tests/Makefile.am

tests/Makefile.in

tests/arpack.at

tests/atlocal.in

tests/attributes.at

tests/basic.at

tests/bipartite.at

tests/cliques.at

tests/community.at

tests/components.at

tests/conversion.at

tests/eigen.at

tests/flow.at

tests/foreign.at

tests/iterators.at

tests/layout.at

tests/motifs.at

tests/operators.at

tests/other.at

tests/package.m4

tests/structural_properties.at

tests/structure_generators.at

tests/testsuite

tests/testsuite.at

tests/topology.at

tests/types.at

tests/visitors.at

ylwrap

Show diffs side-by-side

added added

removed removed

src/structure_generators.c

/* -*- mode: C -*- */

IGraph library.

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 "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.

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++) {

100

for (j=0; j<no_of_nodes; j++) {

101

long int M=MATRIX(*adjmatrix, i, j);

102

for (k=0; k<M; k++) {

103

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

104

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

105

}

106

}

107

}

108

109

return 0;

110

}

111

112

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

113

114

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

115

long int i, j, k;

116

117

for (i=0; i<no_of_nodes; i++) {

118

for (j=i; j<no_of_nodes; j++) {

119

long int M1=MATRIX(*adjmatrix, i, j);

120

long int M2=MATRIX(*adjmatrix, j, i);

121

if (M1<M2) { M1=M2; }

122

for (k=0; k<M1; k++) {

123

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

124

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

125

}

126

}

127

}

128

129

return 0;

130

}

131

132

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

133

134

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

135

long int i, j, k;

136

137

for (i=0; i<no_of_nodes; i++) {

138

for (j=i; j<no_of_nodes; j++) {

139

long int M=MATRIX(*adjmatrix, i, j);

140

for (k=0; k<M; k++) {

141

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

142

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

143

}

144

}

145

}

146

return 0;

147

}

148

149

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

150

151

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

152

long int i, j, k;

153

154

for (i=0; i<no_of_nodes; i++) {

155

for (j=0; j<=i; j++) {

156

long int M=MATRIX(*adjmatrix, i, j);

157

for (k=0; k<M; k++) {

158

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

159

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

160

}

161

}

162

}

163

return 0;

164

}

165

166

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

167

168

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

169

long int i, j, k;

170

171

for (i=0; i<no_of_nodes; i++) {

172

for (j=i; j<no_of_nodes; j++) {

173

long int M1=MATRIX(*adjmatrix, i, j);

174

long int M2=MATRIX(*adjmatrix, j, i);

175

if (M1>M2) { M1=M2; }

176

for (k=0; k<M1; k++) {

177

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

178

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

179

}

180

}

181

}

182

183

return 0;

184

}

185

186

/**

187

* \ingroup generators

188

* \function igraph_adjacency

189

* \brief Creates a graph object from an adjacency matrix.

190

191

* The order of the vertices in the matrix is preserved, i.e. the vertex

192

* corresponding to the first row/column will be vertex with id 0, the

193

* next row is for vertex 1, etc.

194

* \param graph Pointer to an uninitialized graph object.

195

* \param adjmatrix The adjacency matrix. How it is interpreted

196

* depends on the \p mode argument.

197

* \param mode Constant to specify how the given matrix is interpreted

198

* as an adjacency matrix. Possible values

199

* (A(i,j)

200

* is the element in row i and column

201

* j in the adjacency matrix

202

* (\p adjmatrix):

203

* \clist

204

* \cli IGRAPH_ADJ_DIRECTED

205

* the graph will be directed and

206

* an element gives the number of edges between two vertices.

207

* \cli IGRAPH_ADJ_UNDIRECTED

208

* this is the same as \c IGRAPH_ADJ_MAX,

209

* for convenience.

210

* \cli IGRAPH_ADJ_MAX

211

* undirected graph will be created

212

* and the number of edges between vertex

213

* i and

214

* j is

215

* max(A(i,j), A(j,i)).

216

* \cli IGRAPH_ADJ_MIN

217

* undirected graph will be created

218

* with min(A(i,j), A(j,i))

219

* edges between vertex

220

* i and

221

* j.

222

* \cli IGRAPH_ADJ_PLUS

223

* undirected graph will be created

224

* with A(i,j)+A(j,i) edges

225

* between vertex

226

* i and

227

* j.

228

* \cli IGRAPH_ADJ_UPPER

229

* undirected graph will be created,

230

* only the upper right triangle (including the diagonal) is

231

* used for the number of edges.

232

* \cli IGRAPH_ADJ_LOWER

233

* undirected graph will be created,

234

* only the lower left triangle (including the diagonal) is

235

* used for creating the edges.

236

* \endclist

237

* \return Error code,

238

* \c IGRAPH_NONSQUARE: non-square matrix.

239

240

* Time complexity: O(|V||V|),

241

* |V| is the number of vertices in the graph.

242

243

244

int igraph_adjacency(igraph_t *graph, igraph_matrix_t *adjmatrix,

245

igraph_adjacency_t mode) {

246

247

igraph_vector_t edges=IGRAPH_VECTOR_NULL;

248

long int no_of_nodes;

249

250

/* Some checks */

251

if (igraph_matrix_nrow(adjmatrix) != igraph_matrix_ncol(adjmatrix)) {

252

IGRAPH_ERROR("Non-square matrix", IGRAPH_NONSQUARE);

253

}

254

255

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

256

257

/* Collect the edges */

258

no_of_nodes=igraph_matrix_nrow(adjmatrix);

259

switch (mode) {

260

case IGRAPH_ADJ_DIRECTED:

261

IGRAPH_CHECK(igraph_i_adjacency_directed(adjmatrix, &edges));

262

break;

263

case IGRAPH_ADJ_MAX:

264

IGRAPH_CHECK(igraph_i_adjacency_max(adjmatrix, &edges));

265

break;

266

case IGRAPH_ADJ_UPPER:

267

IGRAPH_CHECK(igraph_i_adjacency_upper(adjmatrix, &edges));

268

break;

269

case IGRAPH_ADJ_LOWER:

270

IGRAPH_CHECK(igraph_i_adjacency_lower(adjmatrix, &edges));

271

break;

272

case IGRAPH_ADJ_MIN:

273

IGRAPH_CHECK(igraph_i_adjacency_min(adjmatrix, &edges));

274

break;

275

case IGRAPH_ADJ_PLUS:

276

IGRAPH_CHECK(igraph_i_adjacency_directed(adjmatrix, &edges));

277

break;

278

}

279

280

IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes,

281

(mode == IGRAPH_ADJ_DIRECTED)));

282

igraph_vector_destroy(&edges);

283

IGRAPH_FINALLY_CLEAN(1);

284

285

return 0;

286

}

287

288

int igraph_i_weighted_adjacency_directed(igraph_matrix_t *adjmatrix,

289

igraph_vector_t *edges, igraph_vector_t *weights) {

290

291

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

292

long int i, j;

293

294

for (i=0; i<no_of_nodes; i++) {

295

for (j=0; j<no_of_nodes; j++) {

296

igraph_real_t M=MATRIX(*adjmatrix, i, j);

297

if (M == 0.0) continue;

298

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

299

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

300

IGRAPH_CHECK(igraph_vector_push_back(weights, M));

301

}

302

}

303

304

return 0;

305

}

306

307

int igraph_i_weighted_adjacency_plus(igraph_matrix_t *adjmatrix,

308

igraph_vector_t *edges, igraph_vector_t *weights) {

309

310

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

311

long int i, j;

312

313

for (i=0; i<no_of_nodes; i++) {

314

for (j=i; j<no_of_nodes; j++) {

315

igraph_real_t M=MATRIX(*adjmatrix, i, j) + MATRIX(*adjmatrix, j, i);

316

if (M == 0.0) continue;

317

if (i == j) M /= 2;

318

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

319

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

320

IGRAPH_CHECK(igraph_vector_push_back(weights, M));

321

}

322

}

323

324

return 0;

325

}

326

327

int igraph_i_weighted_adjacency_max(igraph_matrix_t *adjmatrix,

328

igraph_vector_t *edges, igraph_vector_t *weights) {

329

330

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

331

long int i, j;

332

333

for (i=0; i<no_of_nodes; i++) {

334

for (j=i; j<no_of_nodes; j++) {

335

igraph_real_t M1=MATRIX(*adjmatrix, i, j);

336

igraph_real_t M2=MATRIX(*adjmatrix, j, i);

337

if (M1<M2) { M1=M2; }

338

if (M1 == 0.0) continue;

339

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

340

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

341

IGRAPH_CHECK(igraph_vector_push_back(weights, M1));

342

}

343

}

344

return 0;

345

}

346

347

int igraph_i_weighted_adjacency_upper(igraph_matrix_t *adjmatrix,

348

igraph_vector_t *edges, igraph_vector_t *weights) {

349

350

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

351

long int i, j;

352

353

for (i=0; i<no_of_nodes; i++) {

354

for (j=i; j<no_of_nodes; j++) {

355

igraph_real_t M=MATRIX(*adjmatrix, i, j);

356

if (M == 0.0) continue;

357

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

358

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

359

IGRAPH_CHECK(igraph_vector_push_back(weights, M));

360

}

361

}

362

return 0;

363

}

364

365

int igraph_i_weighted_adjacency_lower(igraph_matrix_t *adjmatrix,

366

igraph_vector_t *edges, igraph_vector_t *weights) {

367

368

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

369

long int i, j;

370

371

for (i=0; i<no_of_nodes; i++) {

372

for (j=0; j<=i; j++) {

373

igraph_real_t M=MATRIX(*adjmatrix, i, j);

374

if (M == 0.0) continue;

375

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

376

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

377

IGRAPH_CHECK(igraph_vector_push_back(weights, M));

378

}

379

}

380

return 0;

381

}

382

383

int igraph_i_weighted_adjacency_min(igraph_matrix_t *adjmatrix,

384

igraph_vector_t *edges, igraph_vector_t *weights) {

385

386

long int no_of_nodes=igraph_matrix_nrow(adjmatrix);

387

long int i, j;

388

389

for (i=0; i<no_of_nodes; i++) {

390

for (j=i; j<no_of_nodes; j++) {

391

igraph_real_t M1=MATRIX(*adjmatrix, i, j);

392

igraph_real_t M2=MATRIX(*adjmatrix, j, i);

393

if (M1>M2) { M1=M2; }

394

if (M1 == 0.0) continue;

395

IGRAPH_CHECK(igraph_vector_push_back(edges, i));

396

IGRAPH_CHECK(igraph_vector_push_back(edges, j));

397

IGRAPH_CHECK(igraph_vector_push_back(weights, M1));

398

}

399

}

400

401

return 0;

402

}

403

404

/**

405

* \ingroup generators

406

* \function igraph_weighted_adjacency

407

* \brief Creates a graph object from a weighted adjacency matrix.

408

409

* The order of the vertices in the matrix is preserved, i.e. the vertex

410

* corresponding to the first row/column will be vertex with id 0, the

411

* next row is for vertex 1, etc.

412

* \param graph Pointer to an uninitialized graph object.

413

* \param adjmatrix The weighted adjacency matrix. How it is interpreted

414

* depends on the \p mode argument. The common feature is that

415

* edges with zero weights are considered nonexistent (however,

416

* negative weights are permitted).

417

* \param mode Constant to specify how the given matrix is interpreted

418

* as an adjacency matrix. Possible values

419

* (A(i,j)

420

* is the element in row i and column

421

* j in the adjacency matrix

422

* (\p adjmatrix):

423

* \clist

424

* \cli IGRAPH_ADJ_DIRECTED

425

* the graph will be directed and

426

* an element gives the weight of the edge between two vertices.

427

* \cli IGRAPH_ADJ_UNDIRECTED

428

* this is the same as \c IGRAPH_ADJ_MAX,

429

* for convenience.

430

* \cli IGRAPH_ADJ_MAX

431

* undirected graph will be created

432

* and the weight of the edge between vertex

433

* i and

434

* j is

435

* max(A(i,j), A(j,i)).

436

* \cli IGRAPH_ADJ_MIN

437

* undirected graph will be created

438

* with edge weight min(A(i,j), A(j,i))

439

* between vertex

440

* i and

441

* j.

442

* \cli IGRAPH_ADJ_PLUS

443

* undirected graph will be created

444

* with edge weight A(i,j)+A(j,i)

445

* between vertex

446

* i and

447

* j.

448

* \cli IGRAPH_ADJ_UPPER

449

* undirected graph will be created,

450

* only the upper right triangle (including the diagonal) is

451

* used for the edge weights.

452

* \cli IGRAPH_ADJ_LOWER

453

* undirected graph will be created,

454

* only the lower left triangle (including the diagonal) is

455

* used for the edge weights.

456

* \endclist

457

* \param attr the name of the attribute that will store the edge weights.

458

* If \c NULL , it will use \c weight as the attribute name.

459

* \return Error code,

460

* \c IGRAPH_NONSQUARE: non-square matrix.

461

462

* Time complexity: O(|V||V|),

463

* |V| is the number of vertices in the graph.a

464

465

466

int igraph_weighted_adjacency(igraph_t *graph, igraph_matrix_t *adjmatrix,

467

igraph_adjacency_t mode, const char* attr) {

468

469

igraph_vector_t edges=IGRAPH_VECTOR_NULL;

470

igraph_vector_t weights=IGRAPH_VECTOR_NULL;

471

const char* default_attr = "weight";

472

igraph_vector_ptr_t attr_vec;

473

igraph_i_attribute_record_t attr_rec;

474

long int no_of_nodes;

475

476

/* Some checks */

477

if (igraph_matrix_nrow(adjmatrix) != igraph_matrix_ncol(adjmatrix)) {

478

IGRAPH_ERROR("Non-square matrix", IGRAPH_NONSQUARE);

479

}

480

481

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

482

IGRAPH_VECTOR_INIT_FINALLY(&weights, 0);

483

IGRAPH_VECTOR_PTR_INIT_FINALLY(&attr_vec, 1);

484

485

/* Collect the edges */

486

no_of_nodes=igraph_matrix_nrow(adjmatrix);

487

switch (mode) {

488

case IGRAPH_ADJ_DIRECTED:

489

IGRAPH_CHECK(igraph_i_weighted_adjacency_directed(adjmatrix, &edges, &weights));

490

break;

491

case IGRAPH_ADJ_MAX:

492

IGRAPH_CHECK(igraph_i_weighted_adjacency_max(adjmatrix, &edges, &weights));

493

break;

494

case IGRAPH_ADJ_UPPER:

495

IGRAPH_CHECK(igraph_i_weighted_adjacency_upper(adjmatrix, &edges, &weights));

496

break;

497

case IGRAPH_ADJ_LOWER:

498

IGRAPH_CHECK(igraph_i_weighted_adjacency_lower(adjmatrix, &edges, &weights));

499

break;

500

case IGRAPH_ADJ_MIN:

501

IGRAPH_CHECK(igraph_i_weighted_adjacency_min(adjmatrix, &edges, &weights));

502

break;

503

case IGRAPH_ADJ_PLUS:

504

IGRAPH_CHECK(igraph_i_weighted_adjacency_plus(adjmatrix, &edges, &weights));

505

break;

506

}

507

508

/* Prepare attribute record */

509

attr_rec.name = attr ? attr : default_attr;

510

attr_rec.type = IGRAPH_ATTRIBUTE_NUMERIC;

511

attr_rec.value = &weights;

512

VECTOR(attr_vec)[0] = &attr_rec;

513

514

/* Create graph */

515

IGRAPH_CHECK(igraph_empty(graph, no_of_nodes, (mode == IGRAPH_ADJ_DIRECTED)));

516

IGRAPH_FINALLY(igraph_destroy, graph);

517

if (igraph_vector_size(&edges)>0) {

518

IGRAPH_CHECK(igraph_add_edges(graph, &edges, &attr_vec));

519

}

520

IGRAPH_FINALLY_CLEAN(1);

521

522

/* Cleanup */

523

igraph_vector_destroy(&edges);

524

igraph_vector_destroy(&weights);

525

igraph_vector_ptr_destroy(&attr_vec);

526

IGRAPH_FINALLY_CLEAN(3);

527

528

return 0;

529

}

530

531

/**

532

* \ingroup generators

533

* \function igraph_star

534

* \brief Creates a \em star graph, every vertex connects only to the center.

535

536

* \param graph Pointer to an uninitialized graph object, this will

537

* be the result.

538

* \param n Integer constant, the number of vertices in the graph.

539

* \param mode Constant, gives the type of the star graph to

540

* create. Possible values:

541

* \clist

542

* \cli IGRAPH_STAR_OUT

543

* directed star graph, edges point

544

* \em from the center to the other vertices.

545

* \cli IGRAPH_STAR_IN

546

* directed star graph, edges point

547

* \em to the center from the other vertices.

548

* \cli IGRAPH_STAR_UNDIRECTED

549

* an undirected star graph is

550

* created.

551

* \endclist

552

* \param center Id of the vertex which will be the center of the

553

* graph.

554

* \return Error code:

555

* \clist

556

* \cli IGRAPH_EINVVID

557

* invalid number of vertices.

558

* \cli IGRAPH_EINVAL

559

* invalid center vertex.

560

* \cli IGRAPH_EINVMODE

561

* invalid mode argument.

562

* \endclist

563

564

* Time complexity: O(|V|), the

565

* number of vertices in the graph.

566

567

* \sa \ref igraph_lattice(), \ref igraph_ring(), \ref igraph_tree()

568

* for creating other regular structures.

569

570

571

int igraph_star(igraph_t *graph, igraph_integer_t n, igraph_star_mode_t mode,

572

igraph_integer_t center) {

573

574

igraph_vector_t edges=IGRAPH_VECTOR_NULL;

575

long int i;

576

577

if (n<0) {

578

IGRAPH_ERROR("Invalid number of vertices", IGRAPH_EINVVID);

579

}

580

if (center<0 || center >n-1) {

581

IGRAPH_ERROR("Invalid center vertex", IGRAPH_EINVAL);

582

}

583

if (mode != IGRAPH_STAR_OUT && mode != IGRAPH_STAR_IN &&

584

mode != IGRAPH_STAR_UNDIRECTED) {

585

IGRAPH_ERROR("invalid mode", IGRAPH_EINVMODE);

586

}

587

588

IGRAPH_VECTOR_INIT_FINALLY(&edges, (n-1)*2);

589

590

if (mode == IGRAPH_STAR_OUT) {

591

for (i=0; i<center; i++) {

592

VECTOR(edges)[2*i]=center;

593

VECTOR(edges)[2*i+1]=i;

594

}

595

for (i=center+1; i<n; i++) {

596

VECTOR(edges)[2*(i-1)]=center;

597

VECTOR(edges)[2*(i-1)+1]=i;

598

}

599

} else {

600

for (i=0; i<center; i++) {

601

VECTOR(edges)[2*i+1]=center;

602

VECTOR(edges)[2*i]=i;

603

}

604

for (i=center+1; i<n; i++) {

605

VECTOR(edges)[2*(i-1)+1]=center;

606

VECTOR(edges)[2*(i-1)]=i;

607

}

608

}

609

610

IGRAPH_CHECK(igraph_create(graph, &edges, 0,

611

(mode != IGRAPH_STAR_UNDIRECTED)));

612

igraph_vector_destroy(&edges);

613

IGRAPH_FINALLY_CLEAN(1);

614

615

return 0;

616

}

617

618

/**

619

* \ingroup generators

620

* \function igraph_lattice

621

* \brief Creates most kind of lattices.

622

623

* \param graph An uninitialized graph object.

624

* \param dimvector Vector giving the sizes of the lattice in each of

625

* its dimensions. Ie. the dimension of the lattice will be the

626

* same as the length of this vector.

627

* \param nei Integer value giving the distance (number of steps)

628

* within which two vertices will be connected. Not implemented

629

* yet.

630

* \param directed Boolean, whether to create a directed graph. The

631

* direction of the edges is determined by the generation

632

* algorithm and is unlikely to suit you, so this isn't a very

633

* useful option.

634

* \param mutual Boolean, if the graph is directed this gives whether

635

* to create all connections as mutual.

636

* \param circular Boolean, defines whether the generated lattice is

637

* periodic.

638

* \return Error code:

639

* \c IGRAPH_EINVAL: invalid (negative)

640

* dimension vector.

641

642

* Time complexity: if \p nei is less than two then it is O(|V|+|E|) (as

643

* far as i remember), |V| and |E| are the number of vertices

644

* and edges in the generated graph. Otherwise it is O(|V|*d^o+|E|), d

645

* is the average degree of the graph, o is the \p nei argument.

646

647

int igraph_lattice(igraph_t *graph, const igraph_vector_t *dimvector, igraph_integer_t nei,

648

igraph_bool_t directed, igraph_bool_t mutual, igraph_bool_t circular) {

649

650

long int dims=igraph_vector_size(dimvector);

651

long int no_of_nodes=igraph_vector_prod(dimvector);

652

igraph_vector_t edges=IGRAPH_VECTOR_NULL;

653

long int *coords, *weights;

654

long int i, j;

655

int carry, pos;

656

657

if (igraph_vector_any_smaller(dimvector, 0)) {

658

IGRAPH_ERROR("Invalid dimension vector", IGRAPH_EINVAL);

659

}

660

661

/* init coords & weights */

662

663

coords=igraph_Calloc(dims, long int);

664

if (coords==0) {

665

IGRAPH_ERROR("lattice failed", IGRAPH_ENOMEM);

666

}

667

IGRAPH_FINALLY(free, coords); /* TODO: hack */

668

weights=igraph_Calloc(dims, long int);

669

if (weights == 0) {

670

IGRAPH_ERROR("lattice failed", IGRAPH_ENOMEM);

671

}

672

IGRAPH_FINALLY(free, weights);

673

weights[0]=1;

674

for (i=1; i<dims; i++) {

675

weights[i]=weights[i-1]*VECTOR(*dimvector)[i-1];

676

}

677

678

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

679

IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_nodes*dims +

680

mutual*directed * no_of_nodes*dims));

681

682

for (i=0; i<no_of_nodes; i++) {

683

IGRAPH_ALLOW_INTERRUPTION();

684

for (j=0; j<dims; j++) {

685

if (circular || coords[j] != VECTOR(*dimvector)[j]-1) {

686

long int new_nei;

687

if (coords[j] != VECTOR(*dimvector)[j]-1) {

688

new_nei = i + weights[j] + 1;

689

} else {

690

new_nei = i - (VECTOR(*dimvector)[j]-1) * weights[j] + 1;

691

}

692

if (new_nei != i+1 && (VECTOR(*dimvector)[j] != 2 || coords[j] != 1)) {

693

igraph_vector_push_back(&edges, i); /* reserved */

694

igraph_vector_push_back(&edges, new_nei-1); /* reserved */

695

}

696

} /* if circular || coords[j] */

697

if (mutual && directed && (circular || coords[j] != 0)) {

698

long int new_nei;

699

if (coords[j]!=0) {

700

new_nei=i-weights[j]+1;

701

} else {

702

new_nei=i+(VECTOR(*dimvector)[j]-1) * weights[j]+1;

703

}

704

if (VECTOR(*dimvector)[j] != 2 || coords[j] != 0) {

705

igraph_vector_push_back(&edges, i); /* reserved */

706

igraph_vector_push_back(&edges, new_nei-1); /* reserved */

707

}

708

} /* if circular || coords[0] */

709

} /* for j<dims */

710

711

/* increase coords */

712

carry=1;

713

pos=0;

714

715

while (carry==1 && pos != dims) {

716

if (coords[pos] != VECTOR(*dimvector)[pos]-1) {

717

coords[pos]++;

718

carry=0;

719

} else {

720

coords[pos]=0;

721

pos++;

722

}

723

}

724

725

} /* for i<no_of_nodes */

726

727

IGRAPH_CHECK(igraph_create(graph, &edges, 0, directed));

728

if (nei >= 2) {

729

IGRAPH_CHECK(igraph_connect_neighborhood(graph, nei, IGRAPH_ALL));

730

}

731

732

/* clean up */

733

igraph_Free(coords);

734

igraph_Free(weights);

735

igraph_vector_destroy(&edges);

736

IGRAPH_FINALLY_CLEAN(3);

737

738

return 0;

739

}

740

741

/**

742

* \ingroup generators

743

* \function igraph_ring

744

* \brief Creates a \em ring graph, a one dimensional lattice.

745

746

* \param graph Pointer to an uninitialized graph object.

747

* \param n The number of vertices in the ring.

748

* \param directed Logical, whether to create a directed ring.

749

* \param mutual Logical, whether to create mutual edges in a directed

750

* ring. It is ignored for undirected graphs.

751

* \param circular Logical, if false, the ring will be open (this is

752

* not a real \em ring actually).

753

* \return Error code:

754

* \c IGRAPH_EINVAL: invalid number of vertices.

755

756

* Time complexity: O(|V|), the

757

* number of vertices in the graph.

758

759

* \sa \ref igraph_lattice() for generating more general lattices.

760

761

762

int igraph_ring(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_bool_t mutual,

763

igraph_bool_t circular) {

764

765

igraph_vector_t v=IGRAPH_VECTOR_NULL;

766

767

if (n<0) {

768

IGRAPH_ERROR("negative number of vertices", IGRAPH_EINVAL);

769

}

770

771

IGRAPH_VECTOR_INIT_FINALLY(&v, 1);

772

VECTOR(v)[0]=n;

773

774

IGRAPH_CHECK(igraph_lattice(graph, &v, 1, directed, mutual, circular));

775

igraph_vector_destroy(&v);

776

777

IGRAPH_FINALLY_CLEAN(1);

778

return 0;

779

}

780

781

/**

782

* \ingroup generators

783

* \function igraph_tree

784

* \brief Creates a tree in which almost all vertices have the same number of children.

785

786

* \param graph Pointer to an uninitialized graph object.

787

* \param n Integer, the number of vertices in the graph.

788

* \param children Integer, the number of children of a vertex in the

789

* tree.

790

* \param type Constant, gives whether to create a directed tree, and

791

* if this is the case, also its orientation. Possible values:

792

* \clist

793

* \cli IGRAPH_TREE_OUT

794

* directed tree, the edges point

795

* from the parents to their children,

796

* \cli IGRAPH_TREE_IN

797

* directed tree, the edges point from

798

* the children to their parents.

799

* \cli IGRAPH_TREE_UNDIRECTED

800

* undirected tree.

801

* \endclist

802

* \return Error code:

803

* \c IGRAPH_EINVAL: invalid number of vertices.

804

* \c IGRAPH_INVMODE: invalid mode argument.

805

806

* Time complexity: O(|V|+|E|), the

807

* number of vertices plus the number of edges in the graph.

808

809

* \sa \ref igraph_lattice(), \ref igraph_star() for creating other regular

810

* structures.

811

812

813

int igraph_tree(igraph_t *graph, igraph_integer_t n, igraph_integer_t children,

814

igraph_tree_mode_t type) {

815

816

igraph_vector_t edges=IGRAPH_VECTOR_NULL;

817

long int i, j;

818

long int idx=0;

819

long int to=1;

820

821

if (n<0 || children<=0) {

822

IGRAPH_ERROR("Invalid number of vertices or children", IGRAPH_EINVAL);

823

}

824

if (type != IGRAPH_TREE_OUT && type != IGRAPH_TREE_IN &&

825

type != IGRAPH_TREE_UNDIRECTED) {

826

IGRAPH_ERROR("Invalid mode argument", IGRAPH_EINVMODE);

827

}

828

829

IGRAPH_VECTOR_INIT_FINALLY(&edges, 2*(n-1));

830

831

i=0;

832

if (type == IGRAPH_TREE_OUT) {

833

while (idx<2*(n-1)) {

834

for (j=0; j<children && idx<2*(n-1); j++) {

835

VECTOR(edges)[idx++]=i;

836

VECTOR(edges)[idx++]=to++;

837

}

838

i++;

839

}

840

} else {

841

while (idx<2*(n-1)) {

842

for (j=0; j<children && idx<2*(n-1); j++) {

843

VECTOR(edges)[idx++]=to++;

844

VECTOR(edges)[idx++]=i;

845

}

846

i++;

847

}

848

}

849

850

IGRAPH_CHECK(igraph_create(graph, &edges, 0, type!=IGRAPH_TREE_UNDIRECTED));

851

852

igraph_vector_destroy(&edges);

853

IGRAPH_FINALLY_CLEAN(1);

854

return 0;

855

}

856

857

/**

858

* \ingroup generators

859

* \function igraph_full

860

* \brief Creates a full graph (directed or undirected, with or without loops).

861

862

* </para><para>

863

* In a full graph every possible edge is present, every vertex is

864

* connected to every other vertex.

865

866

* \param graph Pointer to an uninitialized graph object.

867

* \param n Integer, the number of vertices in the graph.

868

* \param directed Logical, whether to create a directed graph.

869

* \param loops Logical, whether to include self-edges (loops).

870

* \return Error code:

871

* \c IGRAPH_EINVAL: invalid number of vertices.

872

873

* Time complexity: O(|V|+|E|),

874

* |V| is the number of vertices,

875

* |E| the number of edges in the

876

* graph. Of course this is the same as

877

* O(|E|)=O(|V||V|)

878

* here.

879

880

* \sa \ref igraph_lattice(), \ref igraph_star(), \ref igraph_tree()

881

* for creating other regular structures.

882

883

884

int igraph_full(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_bool_t loops) {

885

886

igraph_vector_t edges=IGRAPH_VECTOR_NULL;

887

long int i, j;

888

889

if (n<0) {

890

IGRAPH_ERROR("invalid number of vertices", IGRAPH_EINVAL);

891

}

892

893

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

894

895

if (directed && loops) {

896

IGRAPH_CHECK(igraph_vector_reserve(&edges, n*n));

897

for (i=0; i<n; i++) {

898

for (j=0; j<n; j++) {

899

igraph_vector_push_back(&edges, i); /* reserved */

900

igraph_vector_push_back(&edges, j); /* reserved */

901

}

902

}

903

} else if (directed && !loops) {

904

IGRAPH_CHECK(igraph_vector_reserve(&edges, n*(n-1)));

905

for (i=0; i<n; i++) {

906

for (j=0; j<i; j++) {

907

igraph_vector_push_back(&edges, i); /* reserved */

908

igraph_vector_push_back(&edges, j); /* reserved */

909

}

910

for (j=i+1; j<n; j++) {

911

igraph_vector_push_back(&edges, i); /* reserved */

912

igraph_vector_push_back(&edges, j); /* reserved */

913

}

914

}

915

} else if (!directed && loops) {

916

IGRAPH_CHECK(igraph_vector_reserve(&edges, n*(n+1)/2));

917

for (i=0; i<n; i++) {

918

for (j=i; j<n; j++) {

919

igraph_vector_push_back(&edges, i); /* reserved */

920

igraph_vector_push_back(&edges, j); /* reserved */

921

}

922

}

923

} else {

924

IGRAPH_CHECK(igraph_vector_reserve(&edges, n*(n-1)/2));

925

for (i=0; i<n; i++) {

926

for (j=i+1; j<n; j++) {

927

igraph_vector_push_back(&edges, i); /* reserved */

928

igraph_vector_push_back(&edges, j); /* resreved */

929

}

930

}

931

}

932

933

IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));

934

igraph_vector_destroy(&edges);

935

IGRAPH_FINALLY_CLEAN(1);

936

937

return 0;

938

}

939

940

/**

941

* \function igraph_full_citation

942

* Creates a full citation graph

943

944

* This is a directed graph, where every <code>i->j</code> edge is

945

* present if and only if <code>j<i</code>.

946

* If the \c directed argument is zero then an undirected graph is

947

* created, and it is just a full graph.

948

* \param graph Pointer to an uninitialized graph object, the result

949

* is stored here.

950

* \param n The number of vertices.

951

* \param directed Whether to created a directed graph. If zero an

952

* undirected graph is created.

953

* \return Error code.

954

955

* Time complexity: O(|V|^2), as we have many edges.

956

957

958

int igraph_full_citation(igraph_t *graph, igraph_integer_t n,

959

igraph_bool_t directed) {

960

igraph_vector_t edges;

961

long int i, j, ptr=0;

962

963

IGRAPH_VECTOR_INIT_FINALLY(&edges, n*(n-1));

964

for (i=1; i<n; i++) {

965

for (j=0; j<i; j++) {

966

VECTOR(edges)[ptr++] = i;

967

VECTOR(edges)[ptr++] = j;

968

}

969

}

970

971

IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));

972

igraph_vector_destroy(&edges);

973

IGRAPH_FINALLY_CLEAN(1);

974

return 0;

975

}

976

977

/**

978

* \function igraph_small

979

* \brief Shortand to create a short graph, giving the edges as agruments

980

981

* </para><para>

982

* This function is handy when a relatively small graph needs to be created.

983

* Instead giving the edges in vector, they are given simply as

984

* arguments and a '-1' needs to be given after the last meaningful

985

* edge argument.

986

987

* </para><para>Note that only graphs which have vertices less than

988

* the highest value of the 'int' type can be created this way. If you

989

* give larger values then the result is undefined.

990

991

* \param graph Pointer to an uninitialized graph object, the result

992

* will be stored here.

993

* \param n The number of vertices in the graph, an integer.

994

* \param directed Logical constant, gives whether the graph should be

995

* directed.

996

* \param ... The additional arguments giving the edges of the

997

* graph. Don't forget to supply an additional '-1' after the last

998

* (meaningful) argument.

999

* \return Error code.

1000

1001

* Time complexity: O(|V|+|E|), the number of vertices plus the number

1002

* of edges in the graph to create.

1003

1004

1005

int igraph_small(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,

1006

...) {

1007

igraph_vector_t edges;

1008

va_list ap;

1009

1010

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

1011

1012

va_start(ap, directed);

1013

while (1) {

1014

int num = va_arg(ap, int);

1015

if (num == -1) {

1016

break;

1017

}

1018

igraph_vector_push_back(&edges, num);

1019

}

1020

1021

IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));

1022

1023

igraph_vector_destroy(&edges);

1024

IGRAPH_FINALLY_CLEAN(1);

1025

return 0;

1026

}

1027

1028

/**

1029

* \function igraph_extended_chordal_ring

1030

* Create an extended chordal ring

1031

1032

* An extended chordal ring is regular graph, each node has the same

1033

* degree. It can be obtained from a simple ring by adding some extra

1034

* edges specified by a matrix. Let p denote the number of columns in

1035

* the <parameter>W</parameter> matrix. The extra edges of vertex i

1036

* are added according to column (i mod p) in

1037

* <parameter>W</parameter>. The number of extra edges is the number

1038

* of rows in <parameter>W</parameter>: for each row j an edge

1039

* i->i+w[ij] is added if i+w[ij] is less than the number of total

1040

* nodes.

1041

1042

* </para><para>

1043

* See also Kotsis, G: Interconnection Topologies for Parallel Processing

1044

* Systems, PARS Mitteilungen 11, 1-6, 1993.

1045

1046

* \param graph Pointer to an uninitialized graph object, the result

1047

* will be stored here. The result is always an undirected graph.

1048

* \param nodes Integer constant, the number of vertices in the

1049

* graph. It must be at least 3.

1050

* \param W The matrix specifying the extra edges. The number of

1051

* columns should divide the number of total vertices.

1052

* \return Error code.

1053

1054

* \sa \ref igraph_ring().

1055

1056

* Time complexity: O(|V|+|E|), the number of vertices plus the number

1057

* of edges.

1058

1059

1060

int igraph_extended_chordal_ring(igraph_t *graph, igraph_integer_t nodes,

1061

const igraph_matrix_t *W) {

1062

1063

igraph_vector_t edges;

1064

long int period=igraph_matrix_ncol(W);

1065

long int degree=igraph_matrix_nrow(W)+2;

1066

long int i, j, mpos=0, epos=0;

1067

1068

if (nodes<3) {

1069

IGRAPH_ERROR("An extended chordal ring has at least 3 nodes",

1070

IGRAPH_EINVAL);

1071

}

1072

1073

if ((long int)nodes % period != 0) {

1074

IGRAPH_ERROR("The period (number of columns in W) should divide the "

1075

"number of nodes", IGRAPH_EINVAL);

1076

}

1077

1078

IGRAPH_VECTOR_INIT_FINALLY(&edges, nodes*degree);

1079

1080

for (i=0; i<nodes-1; i++) {

1081

VECTOR(edges)[epos++] = i;

1082

VECTOR(edges)[epos++] = i+1;

1083

}

1084

VECTOR(edges)[epos++] = 0;

1085

VECTOR(edges)[epos++] = nodes-1;

1086

1087

if (degree > 2) {

1088

for (i=0; i<nodes; i++) {

1089

for (j=0; j<degree-2; j++) {

1090

long int offset=MATRIX(*W, j, mpos);

1091

if (i+offset < nodes) {

1092

VECTOR(edges)[epos++] = i;

1093

VECTOR(edges)[epos++] = i+offset;

1094

}

1095

}

1096

mpos++; if (mpos==period) { mpos=0; }

1097

}

1098

}

1099

1100

igraph_vector_resize(&edges, epos);

1101

IGRAPH_CHECK(igraph_create(graph, &edges, nodes, IGRAPH_UNDIRECTED));

1102

igraph_vector_destroy(&edges);

1103

IGRAPH_FINALLY_CLEAN(1);

1104

return 0;

1105

}

1106

1107

/**

1108

* \function igraph_connect_neighborhood

1109

* \brief Connects every vertex to its neighborhood

1110

1111

* This function adds new edges to graph. For each vertex

1112

* vertices reachable by at most \p order steps and not yet connected

1113

* to the vertex a new edge is created.

1114

1115

* </para><para> Note that the input graph is modified in place, no

1116

* new graph is created, call \ref igraph_copy() if you want to keep

1117

* the original graph as well.

1118

1119

* </para><para> For undirected graphs reachability is always

1120

* symmetric, if vertex A can be reached from vertex B in at

1121

* most \p order steps, then the opposite is also true. Only one

1122

* undirected (A,B) edge will be added in this case.

1123

* \param graph The input graph, this is the output graph as well.

1124

* \param order Integer constant, it gives the distance within which

1125

* the vertices will be connected to the source vertex.

1126

* \param mode Constant, it specifies how the neighborhood search is

1127

* performed for directed graphs. If \c IGRAPH_OUT then vertices

1128

* reachable from the source vertex will be connected, \c IGRAPH_IN

1129

* is the opposite. If \c IGRAPH_ALL then the directed graph is

1130

* considered as an undirected one.

1131

* \return Error code.

1132

1133

* \sa \ref igraph_lattice() uses this function to connect the

1134

* neighborhood of the vertices.

1135

1136

* Time complexity: O(|V|*d^o), |V| is the number of vertices in the

1137

* graph, d is the average degree and o is the \p order argument.

1138

1139

1140

int igraph_connect_neighborhood(igraph_t *graph, igraph_integer_t order,

1141

igraph_neimode_t mode) {

1142

1143

long int no_of_nodes=igraph_vcount(graph);

1144

igraph_dqueue_t q;

1145

igraph_vector_t edges;

1146

long int i, j, in;

1147

long int *added;

1148

igraph_vector_t neis;

1149

1150

if (order<0) {

1151

IGRAPH_ERROR("Negative order, cannot connect neighborhood", IGRAPH_EINVAL);

1152

}

1153

1154

if (order<2) {

1155

IGRAPH_WARNING("Order smaller than two, graph will be unchanged");

1156

}

1157

1158

if (!igraph_is_directed(graph)) {

1159

mode=IGRAPH_ALL;

1160

}

1161

1162

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

1163

added=igraph_Calloc(no_of_nodes, long int);

1164

if (added==0) {

1165

IGRAPH_ERROR("Cannot connect neighborhood", IGRAPH_ENOMEM);

1166

}

1167

IGRAPH_FINALLY(igraph_free, added);

1168

IGRAPH_DQUEUE_INIT_FINALLY(&q, 100);

1169

IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);

1170

1171

for (i=0; i<no_of_nodes; i++) {

1172

added[i]=i+1;

1173

igraph_neighbors(graph, &neis, i, mode);

1174

in=igraph_vector_size(&neis);

1175

if (order > 1) {

1176

for (j=0; j<in; j++) {

1177

long int nei=VECTOR(neis)[j];

1178

added[nei]=i+1;

1179

igraph_dqueue_push(&q, nei);

1180

igraph_dqueue_push(&q, 1);

1181

}

1182

}

1183

1184

while (!igraph_dqueue_empty(&q)) {

1185

long int actnode=igraph_dqueue_pop(&q);

1186

long int actdist=igraph_dqueue_pop(&q);

1187

long int n;

1188

igraph_neighbors(graph, &neis, actnode, mode);

1189

n=igraph_vector_size(&neis);

1190

1191

if (actdist<order-1) {

1192

for (j=0; j<n; j++) {

1193

long int nei=VECTOR(neis)[j];

1194

if (added[nei] != i+1) {

1195

added[nei]=i+1;

1196

IGRAPH_CHECK(igraph_dqueue_push(&q, nei));

1197

IGRAPH_CHECK(igraph_dqueue_push(&q, actdist+1));

1198

if (mode != IGRAPH_ALL || i < nei) {

1199

if (mode == IGRAPH_IN) {

1200

IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));

1201

IGRAPH_CHECK(igraph_vector_push_back(&edges, i));

1202

} else {

1203

IGRAPH_CHECK(igraph_vector_push_back(&edges, i));

1204

IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));

1205

}

1206

}

1207

}

1208

}

1209

} else {

1210

for (j=0; j<n; j++) {

1211

long int nei=VECTOR(neis)[j];

1212

if (added[nei] != i+1) {

1213

added[nei]=i+1;

1214

if (mode != IGRAPH_ALL || i < nei) {

1215

if (mode == IGRAPH_IN) {

1216

IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));

1217

IGRAPH_CHECK(igraph_vector_push_back(&edges, i));

1218

} else {

1219

IGRAPH_CHECK(igraph_vector_push_back(&edges, i));

1220

IGRAPH_CHECK(igraph_vector_push_back(&edges, nei));

1221

}

1222

}

1223

}

1224

}

1225

}

1226

1227

} /* while q not empty */

1228

} /* for i < no_of_nodes */

1229

1230

igraph_vector_destroy(&neis);

1231

igraph_dqueue_destroy(&q);

1232

igraph_free(added);

1233

IGRAPH_FINALLY_CLEAN(3);

1234

1235

IGRAPH_CHECK(igraph_add_edges(graph, &edges, 0));

1236

1237

igraph_vector_destroy(&edges);

1238

IGRAPH_FINALLY_CLEAN(1);

1239

1240

return 0;

1241

}

1242

1243

/**

1244

* \function igraph_de_bruijn

1245

* \brief Generate a de Bruijn graph.

1246

1247

* A de Bruijn graph represents relationships between strings. An alphabet

1248

* of \c m letters are used and strings of length \c n are considered.

1249

* A vertex corresponds to every possible string and there is a directed edge

1250

* from vertex \c v to vertex \c w if the string of \c v can be transformed into

1251

* the string of \c w by removing its first letter and appending a letter to it.

1252

1253

* </para><para>

1254

* Please note that the graph will have \c m to the power \c n vertices and

1255

* even more edges, so probably you don't want to supply too big numbers for

1256

* \c m and \c n.

1257

1258

* </para><para>

1259

* De Bruijn graphs have some interesting properties, please see another source,

1260

* eg. Wikipedia for details.

1261

1262

* \param graph Pointer to an uninitialized graph object, the result will be

1263

* stored here.

1264

* \param m Integer, the number of letters in the alphabet.

1265

* \param n Integer, the length of the strings.

1266

* \return Error code.

1267

1268

* \sa \ref igraph_kautz().

1269

1270

* Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

1271

1272

1273

int igraph_de_bruijn(igraph_t *graph, igraph_integer_t m, igraph_integer_t n) {

1274

1275

/* m - number of symbols */

1276

/* n - length of strings */

1277

1278

long int no_of_nodes, no_of_edges;

1279

igraph_vector_t edges;

1280

long int i, j;

1281

long int mm=m;

1282

1283

if (m<0 || n<0) {

1284

IGRAPH_ERROR("`m' and `n' should be non-negative in a de Bruijn graph",

1285

IGRAPH_EINVAL);

1286

}

1287

1288

if (n==0) {

1289

return igraph_empty(graph, 1, IGRAPH_DIRECTED);

1290

}

1291

if (m==0) {

1292

return igraph_empty(graph, 0, IGRAPH_DIRECTED);

1293

}

1294

1295

no_of_nodes=pow(m, n);

1296

no_of_edges=no_of_nodes*m;

1297

1298

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

1299

IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges*2));

1300

1301

for (i=0; i<no_of_nodes; i++) {

1302

long int basis=(i*mm) % no_of_nodes;

1303

for (j=0; j<m; j++) {

1304

igraph_vector_push_back(&edges, i);

1305

igraph_vector_push_back(&edges, basis+j);

1306

}

1307

}

1308

1309

IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes, IGRAPH_DIRECTED));

1310

1311

igraph_vector_destroy(&edges);

1312

IGRAPH_FINALLY_CLEAN(1);

1313

1314

return 0;

1315

}

1316

1317

/**

1318

* \function igraph_kautz

1319

* \brief Generate a Kautz graph.

1320

1321

* A Kautz graph is a labeled graph, vertices are labeled by strings

1322

* of length \c n+1 above an alphabet with \c m+1 letters, with

1323

* the restriction that every two consecutive letters in the string

1324

* must be different. There is a directed edge from a vertex \c v to

1325

* another vertex \c w if it is possible to transform the string of

1326

* \c v into the string of \c w by removing the first letter and

1327

* appending a letter to it.

1328

1329

* </para><para>

1330

* Kautz graphs have some interesting properties, see eg. Wikipedia

1331

* for details.

1332

1333

* </para><para>

1334

* Vincent Matossian wrote the first version of this function in R,

1335

* thanks.

1336

* \param graph Pointer to an uninitialized graph object, the result

1337

* will be stored here.

1338

* \param m Integer, \c m+1 is the number of letters in the alphabet.

1339

* \param n Integer, \c n+1 is the length of the strings.

1340

* \return Error code.

1341

1342

* \sa \ref igraph_de_bruijn().

1343

1344

* Time complexity: O(|V|* [(m+1)/m]^n +|E|), in practice it is more

1345

* like O(|V|+|E|). |V| is the number of vertices, |E| is the number

1346

* of edges and \c m and \c n are the corresponding arguments.

1347

1348

1349

int igraph_kautz(igraph_t *graph, igraph_integer_t m, igraph_integer_t n) {

1350

1351

/* m+1 - number of symbols */

1352

/* n+1 - length of strings */

1353

1354

long int mm=m;

1355

long int no_of_nodes, no_of_edges;

1356

long int allstrings;

1357

long int i, j, idx=0;

1358

igraph_vector_t edges;

1359

igraph_vector_long_t digits, table;

1360

igraph_vector_long_t index, index2;

1361

long int actb=0;

1362

long int actvalue=0;

1363

1364

if (m<0 || n<0) {

1365

IGRAPH_ERROR("`m' and `n' should be non-negative in a Kautz graph",

1366

IGRAPH_EINVAL);

1367

}

1368

1369

if (n==0) {

1370

return igraph_full(graph, m+1, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);

1371

}

1372

if (m==0) {

1373

return igraph_empty(graph, 0, IGRAPH_DIRECTED);

1374

}

1375

1376

no_of_nodes=(m+1)*pow(m, n);

1377

no_of_edges=no_of_nodes*m;

1378

allstrings=pow(m+1, n+1);

1379

1380

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

1381

1382

IGRAPH_CHECK(igraph_vector_long_init(&table, n+1));

1383

IGRAPH_FINALLY(igraph_vector_long_destroy, &table);

1384

j=1;

1385

for (i=n; i>=0; i--) {

1386

VECTOR(table)[i]=j;

1387

j *= (m+1);

1388

}

1389

1390

IGRAPH_CHECK(igraph_vector_long_init(&digits, n+1));

1391

IGRAPH_FINALLY(igraph_vector_long_destroy, &digits);

1392

IGRAPH_CHECK(igraph_vector_long_init(&index, pow(m+1, n+1)));

1393

IGRAPH_FINALLY(igraph_vector_long_destroy, &index);

1394

IGRAPH_CHECK(igraph_vector_long_init(&index2, no_of_nodes));

1395

IGRAPH_FINALLY(igraph_vector_long_destroy, &index2);

1396

1397

/* Fill the index tables*/

1398

while (1) {

1399

/* at the beginning of the loop, 0:actb contain the valid prefix */

1400

/* we might need to fill it to get a valid string */

1401

long int z=0;

1402

if (VECTOR(digits)[actb]==0) { z=1; }

1403

for (actb++; actb<=n; actb++) {

1404

VECTOR(digits)[actb]=z;

1405

actvalue += z*VECTOR(table)[actb];

1406

z=1-z;

1407

}

1408

actb=n;

1409

1410

/* ok, we have a valid string now */

1411

VECTOR(index)[actvalue]=idx+1;

1412

VECTOR(index2)[idx]=actvalue;

1413

idx++;

1414

1415

/* finished? */

1416

if (idx >= no_of_nodes) { break; }

1417

1418

/* not yet, we need a valid prefix now */

1419

while (1) {

1420

/* try to increase digits at position actb */

1421

long int next=VECTOR(digits)[actb]+1;

1422

if (actb != 0 && VECTOR(digits)[actb-1]==next) { next++; }

1423

if (next <= m) {

1424

/* ok, no problem */

1425

actvalue += (next-VECTOR(digits)[actb])*VECTOR(table)[actb];

1426

VECTOR(digits)[actb]=next;

1427

break;

1428

} else {

1429

/* bad luck, try the previous digit */

1430

actvalue -= VECTOR(digits)[actb]*VECTOR(table)[actb];

1431

actb--;

1432

}

1433

}

1434

}

1435

1436

IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges*2));

1437

1438

/* Now come the edges at last */

1439

for (i=0; i<no_of_nodes; i++) {

1440

long int fromvalue=VECTOR(index2)[i];

1441

long int lastdigit=fromvalue % (mm+1);

1442

long int basis=(fromvalue * (mm+1)) % allstrings;

1443

for (j=0; j<=m; j++) {

1444

long int tovalue, to;

1445

if (j==lastdigit) { continue; }

1446

tovalue=basis+j;

1447

to=VECTOR(index)[tovalue]-1;

1448

if (to<0) { continue; }

1449

igraph_vector_push_back(&edges, i);

1450

igraph_vector_push_back(&edges, to);

1451

}

1452

}

1453

1454

igraph_vector_long_destroy(&index2);

1455

igraph_vector_long_destroy(&index);

1456

igraph_vector_long_destroy(&digits);

1457

igraph_vector_long_destroy(&table);

1458

IGRAPH_FINALLY_CLEAN(4);

1459

1460

IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes, IGRAPH_DIRECTED));

1461

igraph_vector_destroy(&edges);

1462

IGRAPH_FINALLY_CLEAN(1);

1463

1464

return 0;

1465

}

1466

1467

/**

1468

* \function igraph_lcf_vector

1469

* \brief Create a graph from LCF notation

1470

1471

* This function is essentially the same as \ref igraph_lcf(), only

1472

* the way for giving the arguments is different. See \ref

1473

* igraph_lcf() for details.

1474

* \param graph Pointer to an uninitialized graph object.

1475

* \param n Integer constant giving the number of vertices.

1476

* \param shifts A vector giving the shifts.

1477

* \param repeats An integer constant giving the number of repeats

1478

* for the shifts.

1479

* \return Error code.

1480

1481

* \sa \ref igraph_lcf()

1482

1483

* Time complexity: O(|V|+|E|), linear in the number of vertices plus

1484

* the number of edges.

1485

1486

1487

int igraph_lcf_vector(igraph_t *graph, igraph_integer_t n,

1488

const igraph_vector_t *shifts,

1489

igraph_integer_t repeats) {

1490

1491

igraph_vector_t edges;

1492

long int no_of_shifts=igraph_vector_size(shifts);

1493

long int ptr=0, i, sptr=0;

1494

long int no_of_nodes=n;

1495

long int no_of_edges=n+no_of_shifts*repeats/2;

1496

1497

if (repeats<0) IGRAPH_ERROR("number of repeats must be positive", IGRAPH_EINVAL);

1498

IGRAPH_VECTOR_INIT_FINALLY(&edges, 2*no_of_edges);

1499

1500

/* Create a ring first */

1501

for (i=0; i<no_of_nodes; i++) {

1502

VECTOR(edges)[ptr++]=i;

1503

VECTOR(edges)[ptr++]=i+1;

1504

}

1505

VECTOR(edges)[ptr-1]=0;

1506

1507

/* Then add the rest */

1508

while (ptr<2*no_of_edges) {

1509

long int sh=VECTOR(*shifts)[sptr % no_of_shifts];

1510

long int from=sptr % no_of_nodes;

1511

long int to=(no_of_nodes+sptr+sh) % no_of_nodes;

1512

if (from < to) {

1513

VECTOR(edges)[ptr++]=from;

1514

VECTOR(edges)[ptr++]=to;

1515

}

1516

sptr++;

1517

}

1518

1519

IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes, IGRAPH_UNDIRECTED));

1520

igraph_vector_destroy(&edges);

1521

IGRAPH_FINALLY_CLEAN(1);

1522

1523

return 0;

1524

}

1525

1526

/**

1527

* \function igraph_lcf

1528

* \brief Create a graph from LCF notation

1529

1530

* </para><para>

1531

* LCF is short for Lederberg-Coxeter-Frucht, it is a concise notation for

1532

* 3-regular Hamiltonian graphs. It consists of three parameters, the

1533

* number of vertices in the graph, a list of shifts giving additional

1534

* edges to a cycle backbone and another integer giving how many times

1535

* the shifts should be performed. See

1536

* http://mathworld.wolfram.com/LCFNotation.html for details.

1537

1538

* \param graph Pointer to an uninitialized graph object.

1539

* \param n Integer, the number of vertices in the graph.

1540

* \param ... The shifts and the number of repeats for the shifts,

1541

* plus an additional 0 to mark the end of the arguments.

1542

* \return Error code.

1543

1544

* \sa See \ref igraph_lcf_vector() for a similar function using a

1545

* vector_t instead of the variable length argument list.

1546

1547

* Time complexity: O(|V|+|E|), the number of vertices plus the number

1548

* of edges.

1549

1550

1551

int igraph_lcf(igraph_t *graph, igraph_integer_t n, ...) {

1552

igraph_vector_t shifts;

1553

igraph_integer_t repeats;

1554

va_list ap;

1555

1556

IGRAPH_VECTOR_INIT_FINALLY(&shifts, 0);

1557

1558

va_start(ap, n);

1559

while (1) {

1560

int num=va_arg(ap, int);

1561

if (num==0) {

1562

break;

1563

}

1564

IGRAPH_CHECK(igraph_vector_push_back(&shifts, num));

1565

}

1566

if (igraph_vector_size(&shifts)==0) {

1567

repeats=0;

1568

} else {

1569

repeats=igraph_vector_pop_back(&shifts);

1570

}

1571

1572

IGRAPH_CHECK(igraph_lcf_vector(graph, n, &shifts, repeats));

1573

igraph_vector_destroy(&shifts);

1574

IGRAPH_FINALLY_CLEAN(1);

1575

1576

return 0;

1577

}

1578

1579

igraph_real_t igraph_i_famous_bull[] = {

1580

5, 5, 0,

1581

0,1,0,2,1,2,1,3,2,4

1582

};

1583

1584

igraph_real_t igraph_i_famous_chvatal[] = {

1585

12, 24, 0,

1586

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,

1587

1, 7, 1, 5, 1, 10, 4, 10, 4, 11, 2, 11, 0, 10, 0, 11, 3, 11, 3, 10, 1, 2

1588

};

1589

1590

igraph_real_t igraph_i_famous_coxeter[] = {

1591

28, 42, 0,

1592

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,

1593

11, 6, 10, 7, 19, 7, 24, 8, 20, 8, 23, 9, 14, 9, 22, 10, 15, 10, 21, 11, 16,

1594

11, 27, 12, 17, 12, 26, 13, 18, 13, 25, 14, 17, 14, 18, 15, 18, 15, 19, 16, 19,

1595

16, 20, 17, 20, 21, 23, 21, 26, 22, 24, 22, 27, 23, 25, 24, 26, 25, 27

1596

};

1597

1598

igraph_real_t igraph_i_famous_cubical[] = {

1599

8, 12, 0,

1600

0, 1, 1, 2, 2, 3, 0, 3, 4, 5, 5, 6, 6, 7, 4, 7, 0, 4, 1, 5, 2, 6, 3, 7

1601

};

1602

1603

igraph_real_t igraph_i_famous_diamond[] = {

1604

4, 5, 0,

1605

0,1,0,2,1,2,1,3,2,3

1606

};

1607

1608

igraph_real_t igraph_i_famous_dodecahedron[] = {

1609

20, 30, 0,

1610

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,

1611

10, 6, 14, 7, 13, 7, 14, 8, 12, 8, 13, 9, 11, 9, 12, 10, 15, 11, 16, 12, 17,

1612

13, 18, 14, 19, 15, 16, 15, 19, 16, 17, 17, 18, 18, 19

1613

};

1614

1615

igraph_real_t igraph_i_famous_folkman[] = {

1616

20, 40, 0,

1617

0, 5, 0, 8, 0, 10, 0, 13, 1, 7, 1, 9, 1, 12, 1, 14, 2, 6, 2, 8, 2, 11, 2, 13,

1618

3, 5, 3, 7, 3, 10, 3, 12, 4, 6, 4, 9, 4, 11, 4, 14, 5, 15, 5, 19, 6, 15, 6, 16,

1619

7, 16, 7, 17, 8, 17, 8, 18, 9, 18, 9, 19, 10, 15, 10, 19, 11, 15, 11, 16, 12,

1620

16, 12, 17, 13, 17, 13, 18, 14, 18, 14, 19

1621

};

1622

1623

igraph_real_t igraph_i_famous_franklin[] = {

1624

12, 18, 0,

1625

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,

1626

7, 9, 8, 9, 8, 11, 9, 10, 10, 11

1627

};

1628

1629

igraph_real_t igraph_i_famous_frucht[] = {

1630

12, 18, 0,

1631

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,

1632

10, 6, 7, 7, 8, 7, 9, 8, 9, 10, 11

1633

};

1634

1635

igraph_real_t igraph_i_famous_grotzsch[] = {

1636

11, 20, 0,

1637

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,

1638

4, 7, 4, 9, 5, 6, 5, 7, 5, 8, 5, 9, 5, 10

1639

};

1640

1641

igraph_real_t igraph_i_famous_heawood[] = {

1642

14, 21, 0,

1643

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,

1644

7, 6, 11, 7, 8, 8, 9, 8, 13, 9, 10, 10, 11, 11, 12, 12, 13

1645

};

1646

1647

igraph_real_t igraph_i_famous_herschel[] = {

1648

11, 18, 0,

1649

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,

1650

5, 10, 6, 8, 6, 9, 7, 8, 7, 10

1651

};

1652

1653

igraph_real_t igraph_i_famous_house[] = {

1654

5, 6, 0,

1655

0,1,0,2,1,3,2,3,2,4,3,4

1656

};

1657

1658

igraph_real_t igraph_i_famous_housex[] = {

1659

5, 8, 0,

1660

0,1,0,2,0,3,1,2,1,3,2,3,2,4,3,4

1661

};

1662

1663

igraph_real_t igraph_i_famous_icosahedron[] = {

1664

12, 30, 0,

1665

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,

1666

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,

1667

10, 8, 9, 9, 10, 9, 11, 10, 11

1668

};

1669

1670

igraph_real_t igraph_i_famous_krackhardt_kite[] = {

1671

10,18,0,

1672

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

1673

};

1674

1675

igraph_real_t igraph_i_famous_levi[] = {

1676

30, 45, 0,

1677

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,

1678

26, 6, 7, 6, 13, 7, 8, 8, 9, 8, 17, 9, 10, 9, 22, 10, 11, 10, 27, 11, 12, 12,

1679

13, 12, 19, 13, 14, 14, 15, 14, 23, 15, 16, 15, 28, 16, 17, 17, 18, 18, 19, 18,

1680

25, 19, 20, 20, 21, 20, 29, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,

1681

28, 28, 29

1682

};

1683

1684

igraph_real_t igraph_i_famous_mcgee[] = {

1685

24, 36, 0,

1686

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,

1687

17, 6, 7, 6, 13, 7, 8, 8, 9, 8, 20, 9, 10, 9, 16, 10, 11, 11, 12, 11, 23, 12,

1688

13, 12, 19, 13, 14, 14, 15, 15, 16, 15, 22, 16, 17, 17, 18, 18, 19, 19, 20, 20,

1689

21, 21, 22, 22, 23

1690

};

1691

1692

igraph_real_t igraph_i_famous_meredith[] = {

1693

70, 140, 0,

1694

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,

1695

7, 12, 7, 13, 8, 11, 8, 12, 8, 13, 9, 11, 9, 12, 9, 13, 10, 11, 10, 12, 10, 13,

1696

14, 18, 14, 19, 14, 20, 15, 18, 15, 19, 15, 20, 16, 18, 16, 19, 16, 20, 17, 18,

1697

17, 19, 17, 20, 21, 25, 21, 26, 21, 27, 22, 25, 22, 26, 22, 27, 23, 25, 23, 26,

1698

23, 27, 24, 25, 24, 26, 24, 27, 28, 32, 28, 33, 28, 34, 29, 32, 29, 33, 29, 34,

1699

30, 32, 30, 33, 30, 34, 31, 32, 31, 33, 31, 34, 35, 39, 35, 40, 35, 41, 36, 39,

1700

36, 40, 36, 41, 37, 39, 37, 40, 37, 41, 38, 39, 38, 40, 38, 41, 42, 46, 42, 47,

1701

42, 48, 43, 46, 43, 47, 43, 48, 44, 46, 44, 47, 44, 48, 45, 46, 45, 47, 45, 48,

1702

49, 53, 49, 54, 49, 55, 50, 53, 50, 54, 50, 55, 51, 53, 51, 54, 51, 55, 52, 53,

1703

52, 54, 52, 55, 56, 60, 56, 61, 56, 62, 57, 60, 57, 61, 57, 62, 58, 60, 58, 61,

1704

58, 62, 59, 60, 59, 61, 59, 62, 63, 67, 63, 68, 63, 69, 64, 67, 64, 68, 64, 69,

1705

65, 67, 65, 68, 65, 69, 66, 67, 66, 68, 66, 69, 2, 50, 1, 51, 9, 57, 8, 58, 16,

1706

64, 15, 65, 23, 36, 22, 37, 30, 43, 29, 44, 3, 21, 7, 24, 14, 31, 0, 17, 10,

1707

28, 38, 42, 35, 66, 59, 63, 52, 56, 45, 49

1708

};

1709

1710

igraph_real_t igraph_i_famous_noperfectmatching[] = {

1711

16, 27, 0,

1712

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,

1713

7, 8, 7, 9, 8, 9, 8, 10, 8, 11, 9, 10, 9, 11, 10, 11, 12, 13, 12, 14, 12, 15,

1714

13, 14, 13, 15, 14, 15

1715

};

1716

1717

igraph_real_t igraph_i_famous_nonline[] = {

1718

50, 72, 0,

1719

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,

1720

11, 10, 12, 10, 13, 11, 12, 11, 13, 12, 13, 14, 15, 15, 16, 15, 17, 16, 17, 16,

1721

18, 17, 18, 18, 19, 20, 21, 20, 22, 20, 23, 21, 22, 21, 23, 21, 24, 22, 23, 22,

1722

24, 24, 25, 26, 27, 26, 28, 26, 29, 27, 28, 27, 29, 27, 30, 27, 31, 28, 29, 28,

1723

30, 28, 31, 30, 31, 32, 34, 32, 35, 32, 36, 33, 34, 33, 35, 33, 37, 34, 35, 36,

1724

37, 38, 39, 38, 40, 38, 43, 39, 40, 39, 41, 39, 42, 39, 43, 40, 41, 41, 42, 42,

1725

43, 44, 45, 44, 46, 45, 46, 45, 47, 46, 47, 46, 48, 47, 48, 47, 49, 48, 49

1726

};

1727

1728

igraph_real_t igraph_i_famous_octahedron[] = {

1729

6, 12, 0,

1730

0, 1, 0, 2, 1, 2, 3, 4, 3, 5, 4, 5, 0, 3, 0, 5, 1, 3, 1, 4, 2, 4, 2, 5

1731

};

1732

1733

igraph_real_t igraph_i_famous_petersen[] = {

1734

10, 15, 0,

1735

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

1736

};

1737

1738

igraph_real_t igraph_i_famous_robertson[] = {

1739

19, 38, 0,

1740

0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12,

1741

12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 0, 18, 0, 4, 4, 9, 9, 13, 13,

1742

17, 2, 17, 2, 6, 6, 10, 10, 15, 0, 15, 1, 8, 8, 16, 5, 16, 5, 12, 1, 12, 7, 18,

1743

7, 14, 3, 14, 3, 11, 11, 18

1744

};

1745

1746

igraph_real_t igraph_i_famous_smallestcyclicgroup[] = {

1747

9, 15, 0,

1748

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,

1749

4, 5, 6, 7

1750

};

1751

1752

igraph_real_t igraph_i_famous_tetrahedron[] = {

1753

4, 6, 0,

1754

0, 3, 1, 3, 2, 3, 0, 1, 1, 2, 0, 2

1755

};

1756

1757

igraph_real_t igraph_i_famous_thomassen[] = {

1758

34, 52, 0,

1759

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,

1760

13, 11, 14, 12, 14, 15, 17, 15, 18, 16, 18, 16, 19, 17, 19, 9, 19, 4, 14, 24,

1761

25, 25, 26, 20, 26, 20, 21, 21, 22, 22, 23, 23, 27, 27, 28, 28, 29, 29, 30, 30,

1762

31, 31, 32, 32, 33, 24, 33, 5, 24, 6, 25, 7, 26, 8, 20, 0, 20, 1, 21, 2, 22, 3,

1763

23, 10, 27, 11, 28, 12, 29, 13, 30, 15, 30, 16, 31, 17, 32, 18, 33

1764

};

1765

1766

igraph_real_t igraph_i_famous_tutte[] = {

1767

46, 69, 0,

1768

0, 10, 0, 11, 0, 12, 1, 2, 1, 7, 1, 19, 2, 3, 2, 41, 3, 4, 3, 27, 4, 5, 4, 33,

1769

5, 6, 5, 45, 6, 9, 6, 29, 7, 8, 7, 21, 8, 9, 8, 22, 9, 24, 10, 13, 10, 14, 11,

1770

26, 11, 28, 12, 30, 12, 31, 13, 15, 13, 21, 14, 15, 14, 18, 15, 16, 16, 17, 16,

1771

20, 17, 18, 17, 23, 18, 24, 19, 25, 19, 40, 20, 21, 20, 22, 22, 23, 23, 24, 25,

1772

26, 25, 38, 26, 34, 27, 28, 27, 39, 28, 34, 29, 30, 29, 44, 30, 35, 31, 32, 31,

1773

35, 32, 33, 32, 42, 33, 43, 34, 36, 35, 37, 36, 38, 36, 39, 37, 42, 37, 44, 38,

1774

40, 39, 41, 40, 41, 42, 43, 43, 45, 44, 45

1775

};

1776

1777

igraph_real_t igraph_i_famous_uniquely3colorable[] = {

1778

12, 22, 0,

1779

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,

1780

3, 10, 4, 5, 4, 11, 5, 6, 5, 7, 5, 8, 5, 10, 8, 11, 9, 10

1781

};

1782

1783

igraph_real_t igraph_i_famous_walther[] = {

1784

25, 31, 0,

1785

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,

1786

21, 8, 9, 8, 13, 9, 10, 9, 22, 10, 11, 10, 20, 11, 12, 13, 14, 14, 15, 14, 23,

1787

15, 16, 15, 17, 17, 18, 18, 19, 18, 24, 20, 24, 22, 23, 23, 24

1788

};

1789

1790

int igraph_i_famous(igraph_t *graph, igraph_real_t *data) {

1791

long int no_of_nodes=data[0];

1792

long int no_of_edges=data[1];

1793

igraph_bool_t directed=data[2];

1794

igraph_vector_t edges;

1795

1796

igraph_vector_view(&edges, data+3, 2*no_of_edges);

1797

IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes, directed));

1798

return 0;

1799

}

1800

1801

/**

1802

* \function igraph_famous

1803

* \brief Create a famous graph by simply providing its name

1804

1805

* </para><para>

1806

* The name of the graph can be simply supplied as a string.

1807

* Note that this function creates graphs which don't take any parameters,

1808

* there are separate functions for graphs with parameters, eg. \ref

1809

* igraph_full() for creating a full graph.

1810

1811

* </para><para>

1812

* The following graphs are supported:

1813

* \clist

1814

* \cli Bull

1815

* The bull graph, 5 vertices, 5 edges, resembles to the

1816

* head of a bull if drawn properly.

1817

* \cli Chvatal

1818

* This is the smallest triangle-free graph that is

1819

* both 4-chromatic and 4-regular. According to the Grunbaum

1820

* conjecture there exists an m-regular, m-chromatic graph

1821

* with n vertices for every m>1 and n>2. The Chvatal graph

1822

* is an example for m=4 and n=12. It has 24 edges.

1823

* \cli Coxeter

1824

* A non-Hamiltonian cubic symmetric graph with 28

1825

* vertices and 42 edges.

1826

* \cli Cubical

1827

* The Platonic graph of the cube. A convex regular

1828

* polyhedron with 8 vertices and 12 edges.

1829

* \cli Diamond

1830

* A graph with 4 vertices and 5 edges, resembles to a

1831

* schematic diamond if drawn properly.

1832

* \cli Dodecahedral, Dodecahedron

1833

* Another Platonic solid

1834

* with 20 vertices and 30 edges.

1835

* \cli Folkman

1836

* The semisymmetric graph with minimum number of

1837

* vertices, 20 and 40 edges. A semisymmetric graph is

1838

* regular, edge transitive and not vertex transitive.

1839

* \cli Franklin

1840

* This is a graph whose embedding to the Klein

1841

* bottle can be colored with six colors, it is a

1842

* counterexample to the neccessity of the Heawood

1843

* conjecture on a Klein bottle. It has 12 vertices and 18

1844

* edges.

1845

* \cli Frucht

1846

* The Frucht Graph is the smallest cubical graph

1847

* whose automorphism group consists only of the identity

1848

* element. It has 12 vertices and 18 edges.

1849

* \cli Grotzsch

1850

* The Grötzsch graph is a triangle-free graph with

1851

* 11 vertices, 20 edges, and chromatic number 4. It is named after

1852

* German mathematician Herbert Grötzsch, and its existence

1853

* demonstrates that the assumption of planarity is necessary in

1854

* Grötzsch's theorem that every triangle-free planar

1855

* graph is 3-colorable.

1856

* \cli Heawood

1857

* The Heawood graph is an undirected graph with 14

1858

* vertices and 21 edges. The graph is cubic, and all cycles in the

1859

* graph have six or more edges. Every smaller cubic graph has shorter

1860

* cycles, so this graph is the 6-cage, the smallest cubic graph of

1861

* girth 6.

1862

* \cli Herschel

1863

* The Herschel graph is the smallest

1864

* nonhamiltonian polyhedral graph. It is the

1865

* unique such graph on 11 nodes, and has 18 edges.

1866

* \cli House

1867

* The house graph is a 5-vertex, 6-edge graph, the

1868

* schematic draw of a house if drawn properly, basicly a

1869

* triangle of the top of a square.

1870

* \cli HouseX

1871

* The same as the house graph with an X in the square. 5

1872

* vertices and 8 edges.

1873

* \cli Icosahedral, Icosahedron

1874

* A Platonic solid with 12

1875

* vertices and 30 edges.

1876

* \cli Krackhardt_Kite

1877

* A social network with 10 vertices and 18 edges.

1878

* Krackhardt, D. Assessing the Political Landscape:

1879

* Structure, Cognition, and Power in Organizations.

1880

* Admin. Sci. Quart. 35, 342-369, 1990.

1881

* \cli Levi

1882

* The graph is a 4-arc transitive cubic graph, it has

1883

* 30 vertices and 45 edges.

1884

* \cli McGee

1885

* The McGee graph is the unique 3-regular 7-cage

1886

* graph, it has 24 vertices and 36 edges.

1887

* \cli Meredith

1888

* The Meredith graph is a quartic graph on 70

1889

* nodes and 140 edges that is a counterexample to the conjecture that

1890

* every 4-regular 4-connected graph is Hamiltonian.

1891

* \cli Noperfectmatching

1892

* A connected graph with 16 vertices and

1893

* 27 edges containing no perfect matching. A matching in a graph

1894

* is a set of pairwise non-adjacent edges; that is, no two edges

1895

* share a common vertex. A perfect matching is a matching

1896

* which covers all vertices of the graph.

1897

* \cli Nonline

1898

* A graph whose connected components are the 9

1899

* graphs whose presence as a vertex-induced subgraph in a

1900

* graph makes a nonline graph. It has 50 vertices and 72 edges.

1901

* \cli Octahedral, Octahedron

1902

* Platonic solid with 6

1903

* vertices and 12 edges.

1904

* \cli Petersen

1905

* A 3-regular graph with 10 vertices and 15 edges. It is

1906

* the smallest hypohamiltonian graph, ie. it is

1907

* non-hamiltonian but removing any single vertex from it makes it

1908

* Hamiltonian.

1909

* \cli Robertson

1910

* The unique (4,5)-cage graph, ie. a 4-regular

1911

* graph of girth 5. It has 19 vertices and 38 edges.

1912

* \cli Smallestcyclicgroup

1913

* A smallest nontrivial graph

1914

* whose automorphism group is cyclic. It has 9 vertices and

1915

* 15 edges.

1916

* \cli Tetrahedral, Tetrahedron

1917

* Platonic solid with 4

1918

* vertices and 6 edges.

1919

* \cli Thomassen

1920

* The smallest hypotraceable graph,

1921

* on 34 vertices and 52 edges. A hypotracable graph does

1922

* not contain a Hamiltonian path but after removing any

1923

* single vertex from it the remainder always contains a

1924

* Hamiltonian path. A graph containing a Hamiltonian path

1925

* is called tracable.

1926

* \cli Tutte

1927

* Tait's Hamiltonian graph conjecture states that

1928

* every 3-connected 3-regular planar graph is Hamiltonian.

1929

* This graph is a counterexample. It has 46 vertices and 69

1930

* edges.

1931

* \cli Uniquely3colorable

1932

* Returns a 12-vertex, triangle-free

1933

* graph with chromatic number 3 that is uniquely

1934

* 3-colorable.

1935

* \cli Walther

1936

* An identity graph with 25 vertices and 31

1937

* edges. An identity graph has a single graph automorphism,

1938

* the trivial one.

1939

* \endclist

1940

1941

* \param graph Pointer to an unitialized graph object.

1942

* \param name Character constant, the name of the graph to be

1943

* created, it is case insensitive.

1944

* \return Error code, IGRAPH_EINVAL if there is no graph with the

1945

* given name.

1946

1947

* \sa Other functions for creating graph structures:

1948

* \ref igraph_ring(), \ref igraph_tree(), \ref igraph_lattice(), \ref

1949

* igraph_full().

1950

1951

* Time complexity: O(|V|+|E|), the number of vertices plus the number

1952

* of edges in the graph.

1953

1954

1955

int igraph_famous(igraph_t *graph, const char *name) {

1956

1957

if (!strcasecmp(name, "bull")) {

1958

return igraph_i_famous(graph, igraph_i_famous_bull);

1959

} else if (!strcasecmp(name, "chvatal")) {

1960

return igraph_i_famous(graph, igraph_i_famous_chvatal);

1961

} else if (!strcasecmp(name, "coxeter")) {

1962

return igraph_i_famous(graph, igraph_i_famous_coxeter);

1963

} else if (!strcasecmp(name, "cubical")) {

1964

return igraph_i_famous(graph, igraph_i_famous_cubical);

1965

} else if (!strcasecmp(name, "diamond")) {

1966

return igraph_i_famous(graph, igraph_i_famous_diamond);

1967

} else if (!strcasecmp(name, "dodecahedral") ||

1968

!strcasecmp(name, "dodecahedron")) {

1969

return igraph_i_famous(graph, igraph_i_famous_dodecahedron);

1970

} else if (!strcasecmp(name, "folkman")) {

1971

return igraph_i_famous(graph, igraph_i_famous_folkman);

1972

} else if (!strcasecmp(name, "franklin")) {

1973

return igraph_i_famous(graph, igraph_i_famous_franklin);

1974

} else if (!strcasecmp(name, "frucht")) {

1975

return igraph_i_famous(graph, igraph_i_famous_frucht);

1976

} else if (!strcasecmp(name, "grotzsch")) {

1977

return igraph_i_famous(graph, igraph_i_famous_grotzsch);

1978

} else if (!strcasecmp(name, "heawood")) {

1979

return igraph_i_famous(graph, igraph_i_famous_heawood);

1980

} else if (!strcasecmp(name, "herschel")) {

1981

return igraph_i_famous(graph, igraph_i_famous_herschel);

1982

} else if (!strcasecmp(name, "house")) {

1983

return igraph_i_famous(graph, igraph_i_famous_house);

1984

} else if (!strcasecmp(name, "housex")) {

1985

return igraph_i_famous(graph, igraph_i_famous_housex);

1986

} else if (!strcasecmp(name, "icosahedral") ||

1987

!strcasecmp(name, "icosahedron")) {

1988

return igraph_i_famous(graph, igraph_i_famous_icosahedron);

1989

} else if (!strcasecmp(name, "krackhardt_kite")) {

1990

return igraph_i_famous(graph, igraph_i_famous_krackhardt_kite);

1991

} else if (!strcasecmp(name, "levi")) {

1992

return igraph_i_famous(graph, igraph_i_famous_levi);

1993

} else if (!strcasecmp(name, "mcgee")) {

1994

return igraph_i_famous(graph, igraph_i_famous_mcgee);

1995

} else if (!strcasecmp(name, "meredith")) {

1996

return igraph_i_famous(graph, igraph_i_famous_meredith);

1997

} else if (!strcasecmp(name, "noperfectmatching")) {

1998

return igraph_i_famous(graph, igraph_i_famous_noperfectmatching);

1999

} else if (!strcasecmp(name, "nonline")) {

2000

return igraph_i_famous(graph, igraph_i_famous_nonline);

2001

} else if (!strcasecmp(name, "octahedral") ||

2002

!strcasecmp(name, "octahedron")) {

2003

return igraph_i_famous(graph, igraph_i_famous_octahedron);

2004

} else if (!strcasecmp(name, "petersen")) {

2005

return igraph_i_famous(graph, igraph_i_famous_petersen);

2006

} else if (!strcasecmp(name, "robertson")) {

2007

return igraph_i_famous(graph, igraph_i_famous_robertson);

2008

} else if (!strcasecmp(name, "smallestcyclicgroup")) {

2009

return igraph_i_famous(graph, igraph_i_famous_smallestcyclicgroup);

2010

} else if (!strcasecmp(name, "tetrahedral") ||

2011

!strcasecmp(name, "tetrahedron")) {

2012

return igraph_i_famous(graph, igraph_i_famous_tetrahedron);

2013

} else if (!strcasecmp(name, "thomassen")) {

2014

return igraph_i_famous(graph, igraph_i_famous_thomassen);

2015

} else if (!strcasecmp(name, "tutte")) {

2016

return igraph_i_famous(graph, igraph_i_famous_tutte);

2017

} else if (!strcasecmp(name, "uniquely3colorable")) {

2018

return igraph_i_famous(graph, igraph_i_famous_uniquely3colorable);

2019

} else if (!strcasecmp(name, "walther")) {

2020

return igraph_i_famous(graph, igraph_i_famous_walther);

2021

} else {

2022

IGRAPH_ERROR("Unknown graph, see documentation", IGRAPH_EINVAL);

2023

}

2024

2025

return 0;

2026

}

2027

2028

/**

2029

* \function igraph_adjlist

2030

* Create a graph from an adjacency list

2031

2032

* An adjacency list is list of vectors, containing the neighbors

2033

* of all vertices. For operations that involve many changes of the

2034

* graph structure, it is recommended that you convert the graph into

2035

* and adjacency list via \ref igraph_adjlist_init(), perform the

2036

* modifications (these are cheap for an adjacency list) and then

2037

* recreate the igraph graph via this function.

2038

2039

* \param graph Pointer to an uninitialized graph object.

2040

* \param adjlist The adjacency list.

2041

* \param directed Logical, whether or not to create a directed graph.

2042

* \param duplicate Logical, for undirected graphs this specified

2043

* whether each edge is included twice, in the vectors of

2044

* both adjacenct vertices. If this is false (0), then it is

2045

* assumed that every edge is included only once. This argument

2046

* is ignored for directed graphs.

2047

* \return Error code.

2048

2049

* \sa \ref igraph_adjlist_init() for the opposite operation.

2050

2051

* Time complexity: O(|V|+|E|).

2052

2053

2054

2055

int igraph_adjlist(igraph_t *graph, const igraph_adjlist_t *adjlist,

2056

igraph_bool_t directed, igraph_bool_t duplicate) {

2057

2058

long int no_of_nodes=igraph_adjlist_size(adjlist);

2059

long int no_of_edges=0;

2060

long int i;

2061

2062

igraph_vector_t edges;

2063

long int edgeptr=0;

2064

2065

duplicate = duplicate && !directed; /* only duplicate if undirected */

2066

2067

for (i=0; i<no_of_nodes; i++) {

2068

no_of_edges += igraph_vector_size(igraph_adjlist_get(adjlist, i));

2069

}

2070

2071

if (duplicate) {

2072

no_of_edges /= 2;

2073

}

2074

2075

IGRAPH_VECTOR_INIT_FINALLY(&edges, 2*no_of_edges);

2076

2077

for (i=0; i<no_of_nodes; i++) {

2078

igraph_vector_t *neis=igraph_adjlist_get(adjlist, i);

2079

long int j, n=igraph_vector_size(neis);

2080

long int loops=0;

2081

for (j=0; j<n; j++) {

2082

long int nei=VECTOR(*neis)[j];

2083

if (nei==i) {

2084

loops++;

2085

} else {

2086

if (! duplicate || nei > i) {

2087

if (edgeptr+2 > 2*no_of_edges) {

2088

IGRAPH_ERROR("Invalid adjacency list, most probably not correctly"

2089

" duplicated edges for an undirected graph", IGRAPH_EINVAL);

2090

}

2091

VECTOR(edges)[edgeptr++] = i;

2092

VECTOR(edges)[edgeptr++] = nei;

2093

}

2094

}

2095

}

2096

/* loops */

2097

if (duplicate) { loops=loops/2; }

2098

if (edgeptr+2*loops > 2*no_of_edges) {

2099

IGRAPH_ERROR("Invalid adjacency list, most probably not correctly"

2100

" duplicated edges for an undirected graph", IGRAPH_EINVAL);

2101

}

2102

for (j=0; j<loops; j++) {

2103

VECTOR(edges)[edgeptr++] = i;

2104

VECTOR(edges)[edgeptr++] = i;

2105

}

2106

}

2107

2108

IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes, directed));

2109

igraph_vector_destroy(&edges);

2110

IGRAPH_FINALLY_CLEAN(1);

2111

2112

return 0;

2113

}

Older »