17 for (
int ij = 0; ij < n_terms; ij++) {
18 const double dx = pos[2 * terms[ij].
i] - pos[2 * terms[ij].
j];
19 const double dy = pos[2 * terms[ij].i + 1] - pos[2 * terms[ij].j + 1];
20 const double r = hypot(
dx,
dy) - terms[ij].d;
21 stress += terms[ij].w * (r * r);
29 for (
int i = n_terms - 1; i >= 1; i--) {
32 SWAP(&terms[i], &terms[j]);
38 size_t n_nodes = 0, n_edges = 0;
40 assert(
ND_id(np) == n_nodes);
55 assert(n_edges <= INT_MAX);
58 n_nodes = 0, n_edges = 0;
60 assert(n_edges <= INT_MAX);
61 graph->sources[n_nodes] = n_edges;
70 graph->targets[n_edges] = (size_t)
ND_id(target);
72 assert(
graph->weights[n_edges] > 0);
77 assert(n_nodes ==
graph->n);
78 assert(n_edges <= INT_MAX);
80 graph->sources[n_nodes] = n_edges;
89 for (
size_t i = 0; i <
graph->n; i++) {
91 for (
size_t x =
graph->sources[i]; x <
graph->sources[i + 1]; x++) {
92 size_t j =
graph->targets[x];
98 for (
size_t x =
graph->sources[i]; x <
graph->sources[i + 1]; x++) {
99 size_t j =
graph->targets[x];
102 for (
size_t y =
graph->sources[j]; y <
graph->sources[j + 1]; y++) {
103 size_t k =
graph->targets[y];
113 assert(
graph->weights[x] > 0);
114 for (
size_t y =
graph->sources[j]; y <
graph->sources[j + 1]; y++) {
115 size_t k =
graph->targets[y];
119 for (
size_t x =
graph->sources[i]; x <
graph->sources[i + 1]; x++) {
120 size_t j =
graph->targets[x];
143 agwarningf(
"circuit model not yet supported in Gmode=sgd, reverting to "
144 "shortpath model\n");
148 agwarningf(
"mds model not yet supported in Gmode=sgd, reverting to "
149 "shortpath model\n");
155 fprintf(stderr,
"calculating shortest paths and setting up stress terms:");
159 int n_fixed = 0, n_terms = 0;
160 for (
int i = 0; i < n; i++) {
163 n_terms += n - n_fixed;
170 for (
int i = 0; i < n; i++) {
175 assert(offset == n_terms);
182 float w_min = terms[0].
w, w_max = terms[0].
w;
183 for (
int ij = 1; ij < n_terms; ij++) {
184 w_min = fminf(w_min, terms[ij].w);
185 w_max = fmaxf(w_max, terms[ij].w);
191 const double eta_max = 1.0 / w_min;
192 const double eta_min =
Epsilon / w_max;
193 const double lambda = log(eta_max / eta_min) / (
MaxIter - 1);
198 double *
const pos =
gv_calloc(2 * n,
sizeof(
double));
199 bool *unfixed =
gv_calloc(n,
sizeof(
bool));
200 for (
int i = 0; i < n; i++) {
209 fprintf(stderr,
"solving model:");
214 for (
int t = 0; t <
MaxIter; t++) {
216 const double eta = eta_max * exp(-lambda * t);
217 for (
int ij = 0; ij < n_terms; ij++) {
219 const double mu = fmin(eta * terms[ij].w, 1);
221 const double dx = pos[2 * terms[ij].
i] - pos[2 * terms[ij].
j];
222 const double dy = pos[2 * terms[ij].i + 1] - pos[2 * terms[ij].j + 1];
223 const double mag = hypot(
dx,
dy);
225 const double r = (
mu * (mag - terms[ij].d)) / (2 * mag);
226 const double r_x = r *
dx;
227 const double r_y = r *
dy;
229 if (unfixed[terms[ij].i]) {
230 pos[2 * terms[ij].i] -= r_x;
231 pos[2 * terms[ij].i + 1] -= r_y;
233 if (unfixed[terms[ij].j]) {
234 pos[2 * terms[ij].j] += r_x;
235 pos[2 * terms[ij].j + 1] += r_y;
243 fprintf(stderr,
"\nfinished in %.2f sec\n",
elapsed_sec());
248 for (
int i = 0; i < n; i++) {
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
API for compacted arrays of booleans.
static bitarray_t bitarray_new(size_t size_bits)
create an array of the given element length
static bool bitarray_get(bitarray_t self, size_t index)
get the value of the given element
static void bitarray_set(bitarray_t *self, size_t index, bool value)
set or clear the value of the given element
static void bitarray_reset(bitarray_t *self)
free underlying resources and leave a bit array empty
int agnnodes(Agraph_t *g)
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
void agwarningf(const char *fmt,...)
#define GD_neato_nlist(g)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
Agraph_t * graph(char *name)
Arithmetic helper functions.
int dijkstra_sgd(graph_sgd *graph, int source, term_sgd *terms)
NEATOPROCS_API void initial_positions(graph_t *, int)
unsigned long rk_interval(unsigned long max, rk_state *state)
void rk_seed(unsigned long seed, rk_state *state)
static void free_adjacency(graph_sgd *graph)
static void fisheryates_shuffle(term_sgd *terms, int n_terms, rk_state *rstate)
static double calculate_stress(double *pos, term_sgd *terms, int n_terms)
void sgd(graph_t *G, int model)
static graph_sgd * extract_adjacency(graph_t *G, int model)
static bool intersect(Ppoint_t a, Ppoint_t b, Ppoint_t c, Ppoint_t d)