dijkstra.c File Reference

#include <assert.h>
#include <cgraph/alloc.h>
#include <cgraph/bitarray.h>
#include <float.h>
#include <neatogen/bfs.h>
#include <neatogen/dijkstra.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.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)
#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, dist)   (dist[h->data[i]]<dist[h->data[j]])
#define	assign(h, i, j, index)   {h->data[i]=h->data[j]; index[h->data[i]]=i;}
#define	exchange(h, i, j, index)

Typedefs
typedef DistType	Word

Functions
static void	heapify (heap *h, int i, int index[], Word dist[])
static void	freeHeap (heap *h)
static void	initHeap (heap *h, int startVertex, int index[], Word dist[], int n)
static bool	extractMax (heap *h, int *max, int index[], Word dist[])
static void	increaseKey (heap *h, int increasedVertex, Word newDist, int index[], Word dist[])
void	dijkstra (int vertex, vtx_data *graph, int n, DistType *dist)
static void	heapify_f (heap *h, int i, int index[], float dist[])
static void	initHeap_f (heap *h, int startVertex, int index[], float dist[], int n)
static bool	extractMax_f (heap *h, int *max, int index[], float dist[])
static void	increaseKey_f (heap *h, int increasedVertex, float newDist, int index[], 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

assign

#define assign	(		h,
			i,
			j,
			index
	)		{h->data[i]=h->data[j]; index[h->data[i]]=i;}

Definition at line 43 of file dijkstra.c.

exchange

#define exchange	(		h,
			i,
			j,
			index
	)

Value:

                {int temp; \
                temp=h->data[i]; \
                h->data[i]=h->data[j]; \
                h->data[j]=temp; \
                index[h->data[i]]=i; \
                index[h->data[j]]=j; \
}

Definition at line 44 of file dijkstra.c.

greaterPriority

#define greaterPriority	(		h,
			i,
			j,
			dist
	)		(dist[h->data[i]]<dist[h->data[j]])

Definition at line 42 of file dijkstra.c.

insideHeap

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

Definition at line 41 of file dijkstra.c.

left

#define left

(

i

)

(2*(i))

Definition at line 38 of file dijkstra.c.

MAX_DIST

#define MAX_DIST   ((DistType)INT_MAX)

Definition at line 32 of file dijkstra.c.

parent

#define parent

(

i

)

((i)/2)

Definition at line 40 of file dijkstra.c.

right

#define right

(

i

)

(2*(i)+1)

Definition at line 39 of file dijkstra.c.

Typedef Documentation

Word

typedef DistType Word

Definition at line 30 of file dijkstra.c.

Function Documentation

dijkstra()

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

Definition at line 140 of file dijkstra.c.

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

Here is the call graph for this function:

dijkstra_f()

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

Definition at line 258 of file dijkstra.c.

References dist(), extractMax_f(), free(), freeHeap(), graph(), gv_calloc(), 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 292 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, offset, and term_sgd::w.

Referenced by sgd().

Here is the call graph for this function:

Here is the caller graph for this function:

extractMax()

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

static

Definition at line 103 of file dijkstra.c.

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

Referenced by dijkstra().

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, int  index[], float  dist[]  )

static

Definition at line 217 of file dijkstra.c.

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

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 78 of file dijkstra.c.

References heap::data, and free().

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

Here is the call graph for this function:

Here is the caller graph for this function:

heapify()

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

static

Definition at line 57 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, int  index[], float  dist[]  )

static

Definition at line 177 of file dijkstra.c.

References dist(), exchange, greaterPriority, 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, int  index[], Word  dist[]  )

static

Definition at line 118 of file dijkstra.c.

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

Referenced by dijkstra().

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, int  index[], float  dist[]  )

static

Definition at line 232 of file dijkstra.c.

References assign, heap::data, dist(), 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 void initHeap ( heap *  h, int  startVertex, int  index[], Word  dist[], int  n  )

static

Definition at line 84 of file dijkstra.c.

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

Referenced by dijkstra().

Here is the call graph for this function:

Here is the caller graph for this function:

initHeap_f()

static void initHeap_f ( heap *  h, int  startVertex, int  index[], float  dist[], int  n  )

static

Definition at line 199 of file dijkstra.c.

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

Referenced by dijkstra_f(), and dijkstra_sgd().

Here is the call graph for this function:

Here is the caller graph for this function: