closest.c File Reference

#include <assert.h>
#include <limits.h>
#include <neatogen/kkutils.h>
#include <neatogen/closest.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <util/list.h>
#include <util/sort.h>

Include dependency graph for closest.c:

Go to the source code of this file.

Data Structures
struct	Pair
struct	PairHeap

Macros
#define	LT(p, q)   ((p).dist < (q).dist)
#define	EQ(p, q)   ((p).dist == (q).dist)
#define	sub(h, i)   (LIST_GET((h), (i)))
#define	left(i)   (2*(i))
#define	right(i)   (2*(i)+1)
#define	parent(i)   ((i)/2)
#define	insideHeap(h, i)   ((i)<h->heapSize)
#define	greaterPriority(h, i, j)    (LT(h->data[i],h->data[j]) || ((EQ(h->data[i],h->data[j])) && (rand()%2)))

Functions
typedef	LIST (Pair)
static bool	pop (pairs_t *s, Pair *x)
static void	heapify (PairHeap *h, size_t i)
static void	freeHeap (PairHeap *h)
static void	initHeap (PairHeap *h, double *place, size_t *ordering, size_t n)
static bool	extractMax (PairHeap *h, Pair *max)
static void	insert (PairHeap *h, Pair edge)
static int	cmp (const void *a, const void *b, void *context)
static void	find_closest_pairs (double *place, size_t n, int num_pairs, pairs_t *pairs_stack)
static void	add_edge (vtx_data *graph, int u, int v)
static vtx_data *	construct_graph (size_t n, pairs_t *edges_stack)
void	closest_pairs2graph (double *place, int n, int num_pairs, vtx_data **graph)

Macro Definition Documentation

EQ

#define EQ	(		p,
			q
	)		((p).dist == (q).dist)

Definition at line 38 of file closest.c.

greaterPriority

#define greaterPriority	(		h,
			i,
			j
	)		(LT(h->data[i],h->data[j]) || ((EQ(h->data[i],h->data[j])) && (rand()%2)))

Definition at line 75 of file closest.c.

insideHeap

#define insideHeap	(		h,
			i
	)		((i)<h->heapSize)

Definition at line 74 of file closest.c.

left

#define left

(

i

)

(2*(i))

Definition at line 71 of file closest.c.

LT

#define LT	(		p,
			q
	)		((p).dist < (q).dist)

Definition at line 37 of file closest.c.

parent

#define parent

(

i

)

((i)/2)

Definition at line 73 of file closest.c.

right

#define right

(

i

)

(2*(i)+1)

Definition at line 72 of file closest.c.

sub

#define sub	(		h,
			i
	)		(LIST_GET((h), (i)))

Definition at line 60 of file closest.c.

Function Documentation

add_edge()

static void add_edge ( vtx_data *  graph, int  u, int  v  )

static

Definition at line 235 of file closest.c.

References graph(), and NULL.

Referenced by construct_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

closest_pairs2graph()

void closest_pairs2graph	(	double *	place,
		int	n,
		int	num_pairs,
		vtx_data **	graph
	)

Definition at line 301 of file closest.c.

References construct_graph(), find_closest_pairs(), graph(), LIST_FREE, and num_pairs.

Referenced by iterativePCA_1D().

Here is the call graph for this function:

Here is the caller graph for this function:

cmp()

static int cmp ( const void *  a, const void *  b, void *  context  )

static

Definition at line 148 of file closest.c.

Referenced by find_closest_pairs().

Here is the caller graph for this function:

construct_graph()

static vtx_data * construct_graph ( size_t  n, pairs_t *  edges_stack  )

static

Definition at line 252 of file closest.c.

References add_edge(), vtx_data::edges, vtx_data::ewgts, free(), gv_calloc(), LIST_SIZE, vtx_data::nedges, pop(), sub, and top().

Referenced by closest_pairs2graph().

Here is the call graph for this function:

Here is the caller graph for this function:

extractMax()

static bool extractMax ( PairHeap *  h, Pair *  max  )

static

Definition at line 120 of file closest.c.

References PairHeap::data, heapify(), and PairHeap::heapSize.

Referenced by find_closest_pairs().

Here is the call graph for this function:

Here is the caller graph for this function:

find_closest_pairs()

static void find_closest_pairs ( double *  place, size_t  n, int  num_pairs, pairs_t *  pairs_stack  )

static

Definition at line 162 of file closest.c.

References cmp(), extractMax(), free(), freeHeap(), gv_calloc(), gv_sort(), initHeap(), insert(), left, neighbor, num_pairs, push(), and right.

Referenced by closest_pairs2graph().

Here is the call graph for this function:

Here is the caller graph for this function:

freeHeap()

static void freeHeap ( PairHeap *  h )

static

Definition at line 97 of file closest.c.

References PairHeap::data, and free().

Referenced by find_closest_pairs().

Here is the call graph for this function:

Here is the caller graph for this function:

heapify()

static void heapify ( PairHeap *  h, size_t  i  )

static

Definition at line 78 of file closest.c.

References PairHeap::data, greaterPriority, insideHeap, left, right, and SWAP.

Referenced by extractMax(), and initHeap().

Here is the caller graph for this function:

initHeap()

static void initHeap ( PairHeap *  h, double *  place, size_t *  ordering, size_t  n  )

static

Definition at line 102 of file closest.c.

References PairHeap::data, edge, gv_calloc(), heapify(), PairHeap::heapSize, PairHeap::maxSize, and SIZE_MAX.

Referenced by find_closest_pairs().

Here is the call graph for this function:

Here is the caller graph for this function:

insert()

static void insert ( PairHeap *  h, Pair  edge  )

static

Definition at line 132 of file closest.c.

References PairHeap::data, edge, greaterPriority, gv_recalloc(), PairHeap::heapSize, PairHeap::maxSize, parent, and SWAP.

Referenced by Blocks::Blocks(), find_closest_pairs(), Block::findMinInConstraint(), and Blocks::split().

Here is the call graph for this function:

Here is the caller graph for this function:

LIST()

typedef LIST

(

Pair

)

Definition at line 40 of file closest.c.

References LIST_PUSH_BACK.

pop()

static bool pop ( pairs_t *  s, Pair *  x  )

static

Definition at line 46 of file closest.c.

References LIST_BACK, LIST_DROP_BACK, and LIST_IS_EMPTY.