1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2005-2021 The igraph development team
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301 USA
20
21 */
22
23 #include "igraph_constructors.h"
24
25 #include "igraph_operators.h"
26
27 /**
28 * \function igraph_lcf_vector
29 * \brief Creates a graph from LCF notation.
30 *
31 * This function is essentially the same as \ref igraph_lcf(), only
32 * the way for giving the arguments is different. See \ref
33 * igraph_lcf() for details.
34 * \param graph Pointer to an uninitialized graph object.
35 * \param n Integer constant giving the number of vertices.
36 * \param shifts A vector giving the shifts.
37 * \param repeats An integer constant giving the number of repeats
38 * for the shifts.
39 * \return Error code.
40 *
41 * \sa \ref igraph_lcf(), \ref igraph_extended_chordal_ring()
42 *
43 * Time complexity: O(|V|+|E|), linear in the number of vertices plus
44 * the number of edges.
45 */
igraph_lcf_vector(igraph_t * graph,igraph_integer_t n,const igraph_vector_t * shifts,igraph_integer_t repeats)46 int igraph_lcf_vector(igraph_t *graph, igraph_integer_t n,
47 const igraph_vector_t *shifts,
48 igraph_integer_t repeats) {
49
50 igraph_vector_t edges;
51 long int no_of_shifts = igraph_vector_size(shifts);
52 long int ptr = 0, i, sptr = 0;
53 long int no_of_nodes = n;
54 long int no_of_edges = n + no_of_shifts * repeats;
55
56 if (repeats < 0) {
57 IGRAPH_ERROR("number of repeats must be positive", IGRAPH_EINVAL);
58 }
59 IGRAPH_VECTOR_INIT_FINALLY(&edges, 2 * no_of_edges);
60
61 if (no_of_nodes > 0) {
62 /* Create a ring first */
63 for (i = 0; i < no_of_nodes; i++) {
64 VECTOR(edges)[ptr++] = i;
65 VECTOR(edges)[ptr++] = i + 1;
66 }
67 VECTOR(edges)[ptr - 1] = 0;
68 }
69
70 /* Then add the rest */
71 while (ptr < 2 * no_of_edges) {
72 long int sh = (long int) VECTOR(*shifts)[sptr % no_of_shifts];
73 long int from = sptr % no_of_nodes;
74 long int to = (no_of_nodes + sptr + sh) % no_of_nodes;
75 VECTOR(edges)[ptr++] = from;
76 VECTOR(edges)[ptr++] = to;
77 sptr++;
78 }
79
80 IGRAPH_CHECK(igraph_create(graph, &edges, (igraph_integer_t) no_of_nodes,
81 IGRAPH_UNDIRECTED));
82 IGRAPH_CHECK(igraph_simplify(graph, 1 /* true */, 1 /* true */, NULL));
83 igraph_vector_destroy(&edges);
84 IGRAPH_FINALLY_CLEAN(1);
85
86 return 0;
87 }
88
89 /**
90 * \function igraph_lcf
91 * \brief Creates a graph from LCF notation.
92 *
93 * </para><para>
94 * LCF is short for Lederberg-Coxeter-Frucht, it is a concise notation for
95 * 3-regular Hamiltonian graphs. It consists of three parameters: the
96 * number of vertices in the graph, a list of shifts giving additional
97 * edges to a cycle backbone, and another integer giving how many times
98 * the shifts should be performed. See
99 * http://mathworld.wolfram.com/LCFNotation.html for details.
100 *
101 * \param graph Pointer to an uninitialized graph object.
102 * \param n Integer, the number of vertices in the graph.
103 * \param ... The shifts and the number of repeats for the shifts,
104 * plus an additional 0 to mark the end of the arguments.
105 * \return Error code.
106 *
107 * \sa See \ref igraph_lcf_vector() for a similar function using a
108 * vector_t instead of the variable length argument list.
109 *
110 * Time complexity: O(|V|+|E|), the number of vertices plus the number
111 * of edges.
112 *
113 * \example examples/simple/igraph_lcf.c
114 */
igraph_lcf(igraph_t * graph,igraph_integer_t n,...)115 int igraph_lcf(igraph_t *graph, igraph_integer_t n, ...) {
116 igraph_vector_t shifts;
117 igraph_integer_t repeats;
118 va_list ap;
119
120 IGRAPH_VECTOR_INIT_FINALLY(&shifts, 0);
121
122 va_start(ap, n);
123 while (1) {
124 int num = va_arg(ap, int);
125 if (num == 0) {
126 break;
127 }
128 IGRAPH_CHECK(igraph_vector_push_back(&shifts, num));
129 }
130 if (igraph_vector_size(&shifts) == 0) {
131 repeats = 0;
132 } else {
133 repeats = (igraph_integer_t) igraph_vector_pop_back(&shifts);
134 }
135
136 IGRAPH_CHECK(igraph_lcf_vector(graph, n, &shifts, repeats));
137 igraph_vector_destroy(&shifts);
138 IGRAPH_FINALLY_CLEAN(1);
139
140 return 0;
141 }
142