1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: See CVS logs. Details at http://www.graphviz.org/
9 *************************************************************************/
10
11#include "config.h"
12
13#include "general.h"
14#include "SparseMatrix.h"
15#include "nearest_neighbor_graph_ann.h"
16#include "nearest_neighbor_graph.h"
17
18SparseMatrix nearest_neighbor_graph(int nPts, int num_neigbors, int dim, double *x, double eps){
19 /* Gives a nearest neighbor graph of a list of dim-dimendional points. The result is a sparse matrix
20 of nPts x nPts, with num_neigbors entries per row.
21
22 nPts: number of points
23 num_neigbors: number of neighbors needed
24 dim: dimension
25 eps: error tolerance
26 x: nPts*dim vector. The i-th point is x[i*dim : i*dim + dim - 1]
27
28 */
29 int *irn = NULL, *jcn = NULL, nz;
30 real *val = NULL;
31 SparseMatrix A;
32 int k = num_neigbors;
33
34 /* need to *2 as we do two sweeps of neighbors, so could have repeats */
35 irn = MALLOC(sizeof(int)*nPts*k*2);
36 jcn = MALLOC(sizeof(int)*nPts*k*2);
37 val = MALLOC(sizeof(double)*nPts*k*2);
38
39#ifdef HAVE_ANN
40 nearest_neighbor_graph_ann(nPts, dim, num_neigbors, eps, x, &nz, &irn, &jcn, &val);
41
42 A = SparseMatrix_from_coordinate_arrays(nz, nPts, nPts, irn, jcn, (void *) val, MATRIX_TYPE_REAL, sizeof(real));
43#else
44 A = NULL;
45#endif
46
47 FREE(irn);
48 FREE(jcn);
49 FREE(val);
50
51 return A;
52
53
54}
55