dijkstra.c File Reference

#include <assert.h>
#include <float.h>
#include <neatogen/bfs.h>
#include <neatogen/dijkstra.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <util/bitarray.h>

Include dependency graph for dijkstra.c:

Go to the source code of this file.

Data Structures
struct	heap

Macros
#define	MAX_DIST   ((DistType)INT_MAX)

Typedefs
typedef DistType	Word

Functions
static int	left (int i)
static int	right (int i)
static int	parent (int i)
static bool	insideHeap (const heap *h, int i)
static bool	greaterPriority (const heap *h, int i, int j, const Word *dist)
static bool	greaterPriority_f (const heap *h, int i, int j, const float *dist)
static void	assign (heap *h, int i, int j)
static void	exchange (heap *h, int i, int j)
static void	heapify (heap *h, int i, Word dist[])
static void	freeHeap (heap *h)
static heap	initHeap (int startVertex, Word dist[], int n)
static bool	extractMax (heap *h, int *max, Word dist[])
static void	increaseKey (heap *h, int increasedVertex, Word newDist, Word dist[])
void	ngdijkstra (int vertex, vtx_data *graph, int n, DistType *dist)
static void	heapify_f (heap *h, int i, float dist[])
static heap	initHeap_f (int startVertex, float dist[], int n)
static bool	extractMax_f (heap *h, int *max, float dist[])
static void	increaseKey_f (heap *h, int increasedVertex, float newDist, float dist[])
void	dijkstra_f (int vertex, vtx_data *graph, int n, float *dist)
int	dijkstra_sgd (graph_sgd *graph, int source, term_sgd *terms)

Macro Definition Documentation

MAX_DIST

#define MAX_DIST   ((DistType)INT_MAX)

Definition at line 33 of file dijkstra.c.

Typedef Documentation

Word

typedef DistType Word

Definition at line 31 of file dijkstra.c.

Function Documentation

assign()

static void assign ( heap *  h, int  i, int  j  )

static

Definition at line 61 of file dijkstra.c.

References heap::data, and heap::index.

Referenced by increaseKey(), and increaseKey_f().

Here is the caller graph for this function:

dijkstra_f()

void dijkstra_f	(	int	vertex,
		vtx_data *	graph,
		int	n,
		float *	dist
	)

Definition at line 265 of file dijkstra.c.

References dist(), extractMax_f(), freeHeap(), graph(), increaseKey_f(), initHeap_f(), and neighbor.

Referenced by compute_weighted_apsp_packed().

Here is the call graph for this function:

Here is the caller graph for this function:

dijkstra_sgd()

int dijkstra_sgd	(	graph_sgd *	graph,
		int	source,
		term_sgd *	terms
	)

Definition at line 296 of file dijkstra.c.

References bitarray_get(), term_sgd::d, extractMax_f(), free(), freeHeap(), graph(), gv_calloc(), term_sgd::i, increaseKey_f(), initHeap_f(), term_sgd::j, and term_sgd::w.

Referenced by sgd().

Here is the call graph for this function:

Here is the caller graph for this function:

exchange()

static void exchange ( heap *  h, int  i, int  j  )

static

Definition at line 66 of file dijkstra.c.

References heap::data, heap::index, and SWAP.

Referenced by heapify(), and heapify_f().

Here is the caller graph for this function:

extractMax()

static bool extractMax ( heap *  h, int *  max, Word  dist[]  )

static

Definition at line 120 of file dijkstra.c.

References heap::data, dist(), heapify(), heap::heapSize, and heap::index.

Referenced by ngdijkstra().

Here is the call graph for this function:

Here is the caller graph for this function:

extractMax_f()

static bool extractMax_f ( heap *  h, int *  max, float  dist[]  )

static

Definition at line 228 of file dijkstra.c.

References heap::data, dist(), heapify_f(), heap::heapSize, and heap::index.

Referenced by dijkstra_f(), and dijkstra_sgd().

Here is the call graph for this function:

Here is the caller graph for this function:

freeHeap()

static void freeHeap ( heap *  h )

static

Definition at line 92 of file dijkstra.c.

References heap::data, free(), and heap::index.

Referenced by dijkstra_f(), dijkstra_sgd(), and ngdijkstra().

Here is the call graph for this function:

Here is the caller graph for this function:

greaterPriority()

static bool greaterPriority ( const heap *  h, int  i, int  j, const Word *  dist  )

static

Definition at line 53 of file dijkstra.c.

References heap::data, and dist().

Here is the call graph for this function:

greaterPriority_f()

static bool greaterPriority_f ( const heap *  h, int  i, int  j, const float *  dist  )

static

Definition at line 57 of file dijkstra.c.

References heap::data, and dist().

Referenced by heapify_f().

Here is the call graph for this function:

Here is the caller graph for this function:

heapify()

static void heapify ( heap *  h, int  i, Word  dist[]  )

static

Definition at line 72 of file dijkstra.c.

References dist(), exchange(), greaterPriority, insideHeap, left, and right.

Referenced by extractMax(), and initHeap().

Here is the call graph for this function:

Here is the caller graph for this function:

heapify_f()

static void heapify_f ( heap *  h, int  i, float  dist[]  )

static

Definition at line 186 of file dijkstra.c.

References dist(), exchange(), greaterPriority_f(), insideHeap, left, and right.

Referenced by extractMax_f(), and initHeap_f().

Here is the call graph for this function:

Here is the caller graph for this function:

increaseKey()

static void increaseKey ( heap *  h, int  increasedVertex, Word  newDist, Word  dist[]  )

static

Definition at line 133 of file dijkstra.c.

References assign(), heap::data, dist(), heap::index, and parent.

Referenced by ngdijkstra().

Here is the call graph for this function:

Here is the caller graph for this function:

increaseKey_f()

static void increaseKey_f ( heap *  h, int  increasedVertex, float  newDist, float  dist[]  )

static

Definition at line 241 of file dijkstra.c.

References assign(), heap::data, dist(), heap::index, and parent.

Referenced by dijkstra_f(), and dijkstra_sgd().

Here is the call graph for this function:

Here is the caller graph for this function:

initHeap()

static heap initHeap ( int  startVertex, Word  dist[], int  n  )

static

Definition at line 98 of file dijkstra.c.

References heap::data, dist(), gv_calloc(), heapify(), and heap::index.

Referenced by ngdijkstra().

Here is the call graph for this function:

Here is the caller graph for this function:

initHeap_f()

static heap initHeap_f ( int  startVertex, float  dist[], int  n  )

static

Definition at line 206 of file dijkstra.c.

References heap::data, dist(), gv_calloc(), heapify_f(), and heap::index.

Referenced by dijkstra_f(), and dijkstra_sgd().

Here is the call graph for this function:

Here is the caller graph for this function:

insideHeap()

static bool insideHeap ( const heap *  h, int  i  )

static

Definition at line 51 of file dijkstra.c.

References heap::heapSize.

left()

static int left ( int  i )

static

Definition at line 39 of file dijkstra.c.

ngdijkstra()

void ngdijkstra	(	int	vertex,
		vtx_data *	graph,
		int	n,
		DistType *	dist
	)

Definition at line 153 of file dijkstra.c.

References dist(), extractMax(), freeHeap(), graph(), increaseKey(), initHeap(), MAX_DIST, and neighbor.

Referenced by compute_apsp_dijkstra(), embed_graph(), and sparse_stress_subspace_majorization_kD().

Here is the call graph for this function:

Here is the caller graph for this function:

parent()

static int parent ( int  i )

static

Definition at line 43 of file dijkstra.c.

right()

static int right ( int  i )

static

Definition at line 41 of file dijkstra.c.