#include <stdio.h>
#include <stdlib.h>
typedef struct llist
{
int index;
int length;
struct llist *next;
} LList;
typedef struct graphnode
{
int dist; // distance from source
LList *outList; // adjacency list
} GraphNode;
typedef struct g
{
GraphNode *nodes; // array of nodes
int size; // number of nodes in the g
} Graph;
Graph *graphNew(int size)
{
Graph *g;
if((g = (Graph*) calloc(1, sizeof(Graph))) == NULL)
{
fprintf(stderr, "Cannot allocate memory for g.\n");
return NULL;
}
if((g->nodes = (GraphNode*) calloc(size, sizeof(GraphNode))) == NULL)
{
fprintf(stderr, "Cannot allocate memory for nodes array.\n");
free(g);
return NULL;
}
g->size = size;
return g;
}
Graph *graphRead (char *filename)
{
FILE *fp;
// check for file, file format and g mem allocation
if ((fp = fopen(filename, "r")) == NULL) {
fprintf(stderr,"cannot open file %s\n", filename);
return NULL;
}
int numNodes, numEdges;
Graph *g;
LList *adjNode;
fscanf(fp, "%d %d%*[^1-9]", &numNodes, &numEdges);
g = graphNew(numNodes + 1);
for(int count = 1, src; count <= numEdges; ++count)
{
adjNode = (LList*)malloc(sizeof(LList));
fscanf(fp, "%d %d %d%*[^1-9]", &src, &(adjNode->index), &(adjNode->length));
adjNode->next = g->nodes[src].outList;
g->nodes[src].outList = adjNode;
}
fclose(fp);
return g;
}
// a fibonacci node within a circular, doubly-linked list
typedef struct fibnode
{
void *key; // pointer to key, application data
int degree; // size of children list
char mark; // set if a children was previously removed
struct fibnode *left;
struct fibnode *right;
struct fibnode *parent; // parent of this node, NULL if it is root
struct fibnode *children; // children of this node, NULL if it has no children
} FibNode;
// min fibonacci heap
typedef struct fibheap
{
FibNode *min; // minimum in this heap, NULL if heap is empty
int size; // number of nodes in this heap
} FibHeap;
// creates and returns a new, empty fibonacci heap
extern FibHeap *fibNewHeap();
// creates a node with the given key and inserts it in the heap
// returns a handle to the newly created node
// applications should free the memory of the returned nodes
extern FibNode *fibInsertKey(FibHeap *h, void *key);
// inserts an already created node
extern void fibInsertNode(FibHeap *h, FibNode *node);
// extracts a node off the heap, frees the node's memory
// returns a pointer to the node's key
extern void *fibExtractKey(FibHeap *h);
// same as above, does not free memory
// returned node can be inserted in another heap
extern FibNode *fibExtractNode(FibHeap *h);
// promotes node from a given heap
extern void fibPromoteNode(FibHeap *h, FibNode *n);
// frees a heap's memory, i.e. nodes in the heap; this does not affect the keys
extern void fibFreeMem(FibHeap *h);
// external function used to order the keys of nodes
// should return <0, 0, >0 iff x < y, x == y, x > y
extern int fibCompareKey(void *x, void *y);
static const int INFINITY = 0x7FFFFFFF;
int main(void)
{
Graph *g = graphRead("dijkstra.in");
// init priority queue, save nodes' handles
FibHeap *pq = fibNewHeap();
FibNode *fibNodes[g->size];
g->nodes[1].dist = 0;
fibNodes[1] = fibInsertKey(pq, g->nodes + 1);
for(int i = 2; i < g->size; ++i)
{
g->nodes[i].dist = INFINITY;
fibNodes[i] = fibInsertKey(pq, g->nodes + i);
}
// do dijkstra
GraphNode *min, *adjNode;
while(pq->min)
{
min = (GraphNode*)fibExtractKey(pq);
if(min->dist == INFINITY) break;
for(LList *list = min->outList; list; list = list->next)
{
adjNode = g->nodes + list->index;
if(adjNode->dist > min->dist + list->length)
{
adjNode->dist = min->dist + list->length;
fibPromoteNode(pq, fibNodes[list->index]);
}
}
}
// output results
FILE *out = fopen("dijkstra.out", "w");
for(int i = 2; i < g->size; ++i)
if(g->nodes[i].dist == INFINITY) fprintf(out, "0 ");
else fprintf(out, "%d ", g->nodes[i].dist);
fprintf(out, "\n"); fclose(out);
return 0;
}
int fibCompareKey(void *x, void *y)
{
return ((GraphNode*)x)->dist - ((GraphNode*)y)->dist;
}
// helper procedure, computes int log two of a number
static inline int logtwo(int x){ int log = 0; while(x >>= 1) log++; return log;}
// helper procedure for creating a single element circular dlinked list
static inline FibNode* dlistNew();
// helper procedure for inserting a list (or a node) in a dlinked list just
// before a dest node
static inline void dlistInsert(FibNode *dest, FibNode *list);
// helper procedure for removing a node from its circular dlinked list
// node is preserved, has no effect on a list with one item
static inline void dlistRemove(FibNode *n);
// helper procedure for creating a single element circular dlinked list
static inline FibNode* dlistNew();
// helper procedure for consolidating a fibonacci heap
// links trees in the root list so that there's at most one tree root with a
// particular degree
void fibConsolidate(FibHeap *h);
// helper procedure for linking two trees from a fibonacci heap
static inline void fibLink(FibNode *dest, FibNode *src);
// helper procedure for cutting a node from a fibonacci heap
static inline void fibCutNode(FibHeap *h, FibNode *n);
// helper procedure for freeing a tree of nodes
void fibFreeNodes(FibNode *n);
FibHeap *fibNewHeap()
{
FibHeap *heap = calloc(1, sizeof(FibHeap));
if(!heap)
{
fprintf(stderr, "fibNewHeap: Could not allocate memory for"
"Fibonacci heap\n");
exit(EXIT_FAILURE);
}
return heap;
}
// inserts a node with the given key in an existing heap
// returns a handle to the node
FibNode *fibInsertKey(FibHeap *h, void *key)
{
FibNode *n = dlistNew();
// set key, degree is 0, mark is false, parent is null
n->key = key;
fibInsertNode(h, n);
return n;
}
void fibInsertNode(FibHeap *h, FibNode *n)
{
// if the heap is empty, create first node in root list
// otherwise, add it to the root list, just before the minimum node
if(!h->min) h->min = n;
else dlistInsert(h->min, n);
h->size++;
if(fibCompareKey(n->key, h->min->key) < 0) h->min = n;
}
void *fibExtractKey(FibHeap *h)
{
FibNode *n = fibExtractNode(h);
void *result = n->key;
free(n);
return result;
}
// extracts the minimum node's key off the heap
FibNode *fibExtractNode(FibHeap *h)
{
if(!h->min) return NULL;
FibNode *min = h->min;
// place extracted node's children in the root list
FibNode *child = min->children;
if(child)
{
FibNode *end = child;
do
{
child->parent = NULL;
child = child->right;
} while (child != end);
dlistInsert(min, child);
}
dlistRemove(min);
// if heap is now empty, there's no minimum
// otherwise assign some temporary minimum and consolidate heap
if(min->right == min) h->min = NULL;
else
{
h->min = min->right;
fibConsolidate(h);
}
h->size--;
min->degree = min->mark = 0;
min->children = min->parent = NULL;
min->left = min->right = min;
return min;
}
// helper procedure for consolidating a fibonacci heap
// links trees in the root list so that there's at most one tree root with a
// particular degree
void fibConsolidate(FibHeap *h)
{
static const float LOG_BASE_CHANGE = 1.4413f;
// degrees[i] is a pointer to a root node with degree i
// the maximum degree of a node in a heap of size n is bounded by
// log_base_golden_ratio_n, which is ~ 1.4413 * log_base_two_n
int maxDegree = h->size;//(float)(logtwo(h->size) + 1) * LOG_BASE_CHANGE;
FibNode *degrees[maxDegree + 1];
for(int i = 0; i <= maxDegree; ++i) degrees[i] = NULL;
FibNode *iter = h->min, *end = iter;
FibNode *root, *other;
// iterate through the list of tree roots
do
{
root = iter;
// while there are tree roots with the same degree, make the greater tree
// the child of the smaller one
while((other = degrees[root->degree]))
{
if(fibCompareKey(other->key, root->key) < 0)
{
FibNode *aux = root;
root = other;
other = aux;
}
degrees[root->degree] = NULL;
// make other the child of root, careful if other was end of root list
// or if other is current root in iteration
if(other == iter) iter = iter->left;
if(other == end) end = end->right;
fibLink(root, other);
}
// this is where intermediate consolidated trees are placed, i.e. ones that
// are still in the root list, so check for new minimum
degrees[root->degree] = root;
if(fibCompareKey(root->key, h->min->key) <= 0) h->min = root;
// move to the next root in list
} while((iter = iter->right) != end);
}
void fibPromoteNode(FibHeap *h, FibNode *n)
{
// if node is not root and new key is less than its parent
// cut the node from its tree
if(n->parent && fibCompareKey(n->key, n->parent->key) < 0)
{
FibNode *cutNode = n, *cutParent;
do
{
// keep a pointer to this node's parent if it is marked
// because fibCutNode will mark parent anyway
cutParent = cutNode->parent->mark ? cutNode->parent : NULL;
fibCutNode(h, cutNode);
// cascade the cut while parent node was already marked and not root
} while((cutNode = cutParent) && cutNode->parent);
}
// update the minimum if required
// do this only now, so fibCutNode will have a valid root list of 'h'
if(fibCompareKey(n->key, h->min->key) < 0) h->min = n;
}
void fibFreeMem(FibHeap *h)
{
if(h->min) fibFreeNodes(h->min);
free(h);
}
void fibFreeNodes(FibNode *iter)
{
FibNode *next, *end = iter;
do
{
if(iter->children) fibFreeNodes(iter->children);
next = iter->right;
free(iter);
}
while((iter = next) != end);
}
static inline void fibLink(FibNode *dest, FibNode *src)
{
// remove tree root from root list, dest is now its parent
dlistRemove(src);
// isolate removed root
src->left = src->right = src;
src->parent = dest;
// special case, destination has no children, src will be the only child
if(!dest->children) dest->children = src;
else dlistInsert(dest->children, src);
dest->degree++;
src->mark = 0;
}
static inline void fibCutNode(FibHeap *h, FibNode *n)
{
FibNode *parent = n->parent;
// remove node from parent's children list
dlistRemove(n);
// update parent's children pointer accordingly
if(parent->children == n) parent->children = n->right == n ? NULL : n->right;
// mark parent, it has just lost a child
parent->mark = 1;
parent->degree--;
// isolate node and add to root list
n->left = n->right = n;
n->mark = 0;
n->parent = NULL;
dlistInsert(h->min, n);
}
// helper procedure for creating a single element circular dlinked list
static inline FibNode* dlistNew()
{
FibNode *node = calloc(1, sizeof(FibNode));
if(!node)
{
fprintf(stderr, "dlistNew: Could not allocate memory for Fibonacci node"
" list\n");
exit(EXIT_FAILURE);
}
node->left = node;
node->right = node;
return node;
}
// helper procedure for inserting a list (or a node) in a dlinked list just
// before a dest node
static inline void dlistInsert(FibNode *dest, FibNode *list)
{
FibNode *destEnd = dest->left;
FibNode *listEnd = list->left;
destEnd->right = list;
list->left = destEnd;
listEnd->right = dest;
dest->left = listEnd;
}
// helper procedure for removing a node from its circular dlinked list
// node is preserved, has no effect on a list with one item
static inline void dlistRemove(FibNode *n)
{
n->left->right = n->right;
n->right->left = n->left;
}