From 3aee2fd43e3059a699af2b63c6f2395e5a55e515 Mon Sep 17 00:00:00 2001 From: KatolaZ Date: Wed, 27 Sep 2017 15:06:31 +0100 Subject: First commit on github -- NetBunch 1.0 --- src/dijkstra/dijkstra.c | 242 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 242 insertions(+) create mode 100644 src/dijkstra/dijkstra.c (limited to 'src/dijkstra/dijkstra.c') diff --git a/src/dijkstra/dijkstra.c b/src/dijkstra/dijkstra.c new file mode 100644 index 0000000..4e8a63f --- /dev/null +++ b/src/dijkstra/dijkstra.c @@ -0,0 +1,242 @@ +/** + * This program is free software: you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation, either version 3 of the + * License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * This file is part of NetBunch, a package for complex network + * analysis and modelling. For more information please visit: + * + * http://www.complex-networks.net/ + * + * If you use this software, please add a reference to + * + * V. Latora, V. Nicosia, G. Russo + * "Complex Networks: Principles, Methods and Applications" + * Cambridge University Press (2017) + * ISBN: 9781107103184 + * + *********************************************************************** + * + * + * This program implements the Dijkstra's algorithm to find the + * shortest paths from a given node (source) to all the other nodes + * of a weighted graph given as input. + * + * References: + * + * [1] E. W. Dijkstra. "A Note on Two Problems in Connexion with + * Graphs". Num. Math. 1 (1959), 269-271. + * + */ + + +#include +#include +#include +#include + +#include "utils.h" +#include "gen_pqueue.h" + +#include "node_w_funs.h" + +#define INFINITY DBL_MAX + + +void usage(char *argv[]){ + printf("********************************************************************\n" + "** **\n" + "** -*- dijkstra -*- **\n" + "** **\n" + "** Compute the distance from the given 'node' to all the other **\n" + "** nodes of a weighted graph. The first parameter 'graph_in' **\n" + "** is the name of the file containing the edge list of the **\n" + "** graph. The second parameter 'node' is the label of the node **\n" + "** for which we want to compute the distances to all the other **\n" + "** nodes. **\n" + "** **\n" + "** If 'graph_in' is equal to '-' (dash), read the edge list **\n" + "** from standard input (STDIN) **\n" + "** **\n" + "** The program prints on output a row of values: **\n" + "** **\n" + "** d0 d1 d2 d3 d4...... **\n" + "** **\n" + "** where d0 is the distance between 'node' and '0', 'd1' is the **\n" + "** distance between 'node' and '1', and so on. If a node is **\n" + "** not reachable from , the corresponding distance is set **\n" + "** to 'inf'. **\n" + "** **\n" + "** **\n" + "********************************************************************\n" + " This is Free Software - You can use and distribute it under \n" + " the terms of the GNU General Public License, version 3 or later\n\n" + " Please visit http://www.complex-networks.net for more information\n\n" + " (c) Vincenzo Nicosia 2010-2017 (v.nicosia@qmul.ac.uk)\n" + "********************************************************************\n\n" + ); + printf("Usage: %s \n\n" , argv[0]); +} + + + +void init_prio_queue(gen_pqueue_t **q, unsigned int N){ + + gen_pqueue_func_t *funs; + + funs = malloc(sizeof(gen_pqueue_func_t)); + (*funs).compare = compare_node_w; + (*funs).alloc_vector = alloc_vector_node_w; + (*funs).dealloc_vector = dealloc_vector_node_w; + (*funs).dealloc_elem = dealloc_elem_node_w; + (*funs).print_elem = print_elem_node_w; + (*funs).get_id = get_id_node_w; + (*funs).set_key = set_key_node_w; + (*funs).get_key = get_key_node_w; + (*funs).compare_to_key = compare_to_key_node_w; + + *q = gen_pqueue_init(N, MIN_QUEUE, funs); + free(funs); +} + +void flatten_pqueue_to_array(gen_pqueue_t *q, double *v, unsigned int N){ + + int i; + double *val; + + for(i=0; ii = i; + if (i != s) + elem->w = INFINITY; + else + elem->w = 0.0; + gen_pqueue_insert(qdist, elem); + prev[i] = -1; + dist[i] = INFINITY; + } + + + while (!gen_pqueue_delete(qdist, (void**)&elem)){ /* get the node with minimum distance */ + cur_node = qdist->funs.get_id(elem); + dist_cur_node = *((double*) qdist->funs.get_key(elem)); + if (dist_cur_node == INFINITY){ /* No more nodes are reachable from the origin */ + free(elem); + gen_pqueue_destroy(qdist); + return; + } + dist[cur_node] = dist_cur_node; + for(i=r_slap[cur_node]; i= dist_neigh_node){ + /* now we call gen_pqueue_change_key, which updates the key of node n */ + gen_pqueue_change_key(qdist, gen_pqueue_get_handle(qdist, n), &dist_neigh_node); + prev[n] = cur_node; + } + } + free(elem); + } + gen_pqueue_destroy(qdist); +} + + +void dump_dists(double *v, unsigned int N){ + + int i; + + for(i=0; i= N){ + fprintf(stderr, "Error!!! Source node index should be in the range [0:%d]\n", + N-1); + exit(3); + } + + dists = malloc(N * sizeof(double)); + prev = malloc(N * sizeof(int)); + + dijkstra(N, K, r_slap, J_slap, W_slap, s, dists, prev); + dump_dists(dists, N); + free(J_slap); + free(r_slap); + free(W_slap); + free(dists); + free(prev); +} -- cgit v1.2.3