Link-State-Routing/lsDijkstra.h at master · Jabromen/Link-State-Routing · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/**
 * This file describes the functions used for finding the shortest path via Dijkstra's Algorithm
 *
 * @author Jeffrey Bromen
 * @date 4/17/17
 * @info Systems and Networks II
 * @info Project 3
 */

#ifndef _LSDIJKSTRA_H
#define _LSDIJKSTRA_H

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#include "lsGraph.h"

#define PARENT(i) (int) ((i - 1) / 2)
#define LCHILD(i) i * 2 + 1
#define RCHILD(i) i * 2 + 2

struct MinHeap
{
	int size;
	int cap;
	int *pos;
	struct HeapNode **array;
} MinHeap;

struct HeapNode
{
	int index;
	int cost;
} HeapNode;

/**
 * Initialize a new MinHeap structure.
 *
 * @param cap - capacity of min heap
 *
 * @return - pointer to MinHeap structure
 */
struct MinHeap *newMinHeap(int cap);

/**
 * Initializes a new HeapNode structure.
 *
 * @param index - index of graph node
 * @param cost  - cost to reach node
 *
 * @return - pointer to HeapNode structure
 */
struct HeapNode *newHeapNode(int index, int cost);

/**
 * Frees the memory allocated to a heap
 *
 * @param heap - min heap being freed
 */
void destroyHeap(struct MinHeap *heap);

/**
 * Fixes a min heap by sifting up from index
 *
 * @param heap  - min heap being fixed
 * @param index - starting index
 */
void siftUp(struct MinHeap *heap, int index);

/**
 * Fixes a min heap by sifting down from index
 *
 * @param heap  - min heap being fixed
 * @param index - starting index
 */
void siftdown(struct MinHeap *heap, int index);

/**
 * Swaps two HeapNode pointers. Helper function for heap operations.
 *
 * @param a - node #1 being swapped
 * @param b - node #2 being swapped
 */
void swap(struct HeapNode **a, struct HeapNode **b);

/**
 * Inserts a HeapNode into the correct place in a MinHeap
 *
 * @param heap - min heap being modified
 * @param node - node being inserted
 */
void insert(struct MinHeap *heap, struct HeapNode *node);

/**
 * Removes the node with the smallest cost from a MinHeap.
 *
 * @param heap - heap from which node is extracted
 *
 * @return - pointer to extracted node
 */
struct HeapNode *extract(struct MinHeap *heap);

/**
 * Updates the cost of a node in the heap and repairs the heap.
 *
 * @param heap  - heap being updated
 * @param index - index of node
 * @param cost  - new cost of node
 */
void updateHeap(struct MinHeap *heap, int index, int cost);

/**
 * Checks if a node is currently in the heap.
 *
 * @param heap  - heap being checked
 * @param index - index of node being searched for
 *
 * @return - 1 if in heap, 0 if not in heap
 */
int isInHeap(struct MinHeap *heap, int index);

/**
 * Checks to see if a heap is empty.
 *
 * @param heap - heap being checked
 *
 * @return - 1 if empty, 0 if not empty
 */
int isEmpty(struct MinHeap *heap);

/**
 * Computes the shortest path across a graph.
 *
 * @param graph  - graph being analyzed
 * @param source - label of starting node
 */
void dijkstra(struct Graph *graph, char source);

#endif // _LSDIJKSTRA_H