1 /* -*- mode: C -*- */
2 /* vim:set ts=4 sw=4 sts=4 et: */
3 /*
4 IGraph library.
5 Copyright (C) 2003-2020 The igraph development team
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #include "igraph_layout.h"
25
26 #include "igraph_interface.h"
27
28 #include "core/interruption.h"
29 #include "core/math.h"
30
31 /**
32 * \ingroup layout
33 * \function igraph_layout_circle
34 * \brief Places the vertices uniformly on a circle, in the order of vertex ids.
35 *
36 * \param graph Pointer to an initialized graph object.
37 * \param res Pointer to an initialized matrix object. This will
38 * contain the result and will be resized as needed.
39 * \param order The order of the vertices on the circle. The vertices
40 * not included here, will be placed at (0,0). Supply
41 * \ref igraph_vss_all() here for all vertices, in the order of
42 * their vertex ids.
43 * \return Error code.
44 *
45 * Time complexity: O(|V|), the
46 * number of vertices.
47 */
igraph_layout_circle(const igraph_t * graph,igraph_matrix_t * res,igraph_vs_t order)48 int igraph_layout_circle(const igraph_t *graph, igraph_matrix_t *res,
49 igraph_vs_t order) {
50
51 long int no_of_nodes = igraph_vcount(graph);
52 igraph_integer_t vs_size;
53 long int i;
54 igraph_vit_t vit;
55
56 IGRAPH_CHECK(igraph_vs_size(graph, &order, &vs_size));
57
58 IGRAPH_CHECK(igraph_matrix_resize(res, no_of_nodes, 2));
59 igraph_matrix_null(res);
60
61 igraph_vit_create(graph, order, &vit);
62 for (i = 0; !IGRAPH_VIT_END(vit); IGRAPH_VIT_NEXT(vit), i++) {
63 igraph_real_t phi = 2 * M_PI / vs_size * i;
64 int idx = IGRAPH_VIT_GET(vit);
65 MATRIX(*res, idx, 0) = cos(phi);
66 MATRIX(*res, idx, 1) = sin(phi);
67 }
68 igraph_vit_destroy(&vit);
69
70 return 0;
71 }
72
73 /**
74 * \function igraph_layout_star
75 * \brief Generates a star-like layout.
76 *
77 * \param graph The input graph. Its edges are ignored by this function.
78 * \param res Pointer to an initialized matrix object. This will
79 * contain the result and will be resized as needed.
80 * \param center The id of the vertex to put in the center.
81 * \param order A numeric vector giving the order of the vertices
82 * (including the center vertex!). If a null pointer, then the
83 * vertices are placed in increasing vertex id order.
84 * \return Error code.
85 *
86 * Time complexity: O(|V|), linear in the number of vertices.
87 *
88 * \sa \ref igraph_layout_circle() and other layout generators.
89 */
igraph_layout_star(const igraph_t * graph,igraph_matrix_t * res,igraph_integer_t center,const igraph_vector_t * order)90 int igraph_layout_star(const igraph_t *graph, igraph_matrix_t *res,
91 igraph_integer_t center, const igraph_vector_t *order) {
92
93 long int no_of_nodes = igraph_vcount(graph);
94 long int c = center;
95 long int i;
96 igraph_real_t step;
97 igraph_real_t phi;
98
99 if (center < 0 || center >= no_of_nodes) {
100 IGRAPH_ERROR("The given center is not a vertex of the graph.", IGRAPH_EINVAL);
101 }
102 if (order && igraph_vector_size(order) != no_of_nodes) {
103 IGRAPH_ERROR("Invalid order vector length.", IGRAPH_EINVAL);
104 }
105
106 IGRAPH_CHECK(igraph_matrix_resize(res, no_of_nodes, 2));
107
108 if (no_of_nodes == 1) {
109 MATRIX(*res, 0, 0) = MATRIX(*res, 0, 1) = 0.0;
110 } else {
111 for (i = 0, step = 2 * M_PI / (no_of_nodes - 1), phi = 0;
112 i < no_of_nodes; i++) {
113 long int node = order ? (long int) VECTOR(*order)[i] : i;
114 if (order && (node < 0 || node >= no_of_nodes)) {
115 IGRAPH_ERROR("Elements in the order vector are not all vertices of the graph.", IGRAPH_EINVAL);
116 }
117 if (node != c) {
118 MATRIX(*res, node, 0) = cos(phi);
119 MATRIX(*res, node, 1) = sin(phi);
120 phi += step;
121 } else {
122 MATRIX(*res, node, 0) = MATRIX(*res, node, 1) = 0.0;
123 }
124 }
125 }
126
127 return 0;
128 }
129
130 /**
131 * \function igraph_layout_sphere
132 * \brief Places vertices (more or less) uniformly on a sphere.
133 *
134 * </para><para>
135 * The algorithm was described in the following paper:
136 * Distributing many points on a sphere by E.B. Saff and
137 * A.B.J. Kuijlaars, \emb Mathematical Intelligencer \eme 19.1 (1997)
138 * 5--11.
139 *
140 * \param graph Pointer to an initialized graph object.
141 * \param res Pointer to an initialized matrix object. This will
142 * contain the result and will be resized as needed.
143 * \return Error code. The current implementation always returns with
144 * success.
145 *
146 * Added in version 0.2.</para><para>
147 *
148 * Time complexity: O(|V|), the number of vertices in the graph.
149 */
igraph_layout_sphere(const igraph_t * graph,igraph_matrix_t * res)150 int igraph_layout_sphere(const igraph_t *graph, igraph_matrix_t *res) {
151
152 long int no_of_nodes = igraph_vcount(graph);
153 long int i;
154 igraph_real_t h;
155
156 IGRAPH_CHECK(igraph_matrix_resize(res, no_of_nodes, 3));
157
158 if (no_of_nodes != 0) {
159 MATRIX(*res, 0, 0) = M_PI;
160 MATRIX(*res, 0, 1) = 0;
161 }
162 for (i = 1; i < no_of_nodes - 1; i++) {
163 h = -1 + 2 * i / (double)(no_of_nodes - 1);
164 MATRIX(*res, i, 0) = acos(h);
165 MATRIX(*res, i, 1) = fmod((MATRIX(*res, i - 1, 1) +
166 3.6 / sqrt(no_of_nodes * (1 - h * h))), 2 * M_PI);
167 IGRAPH_ALLOW_INTERRUPTION();
168 }
169 if (no_of_nodes >= 2) {
170 MATRIX(*res, no_of_nodes - 1, 0) = 0;
171 MATRIX(*res, no_of_nodes - 1, 1) = 0;
172 }
173
174 for (i = 0; i < no_of_nodes; i++) {
175 igraph_real_t x = cos(MATRIX(*res, i, 1)) * sin(MATRIX(*res, i, 0));
176 igraph_real_t y = sin(MATRIX(*res, i, 1)) * sin(MATRIX(*res, i, 0));
177 igraph_real_t z = cos(MATRIX(*res, i, 0));
178 MATRIX(*res, i, 0) = x;
179 MATRIX(*res, i, 1) = y;
180 MATRIX(*res, i, 2) = z;
181 IGRAPH_ALLOW_INTERRUPTION();
182 }
183
184 return 0;
185 }
186