diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libcola/shortest_paths.h')
-rw-r--r-- | src/3rdparty/adaptagrams/libcola/shortest_paths.h | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libcola/shortest_paths.h b/src/3rdparty/adaptagrams/libcola/shortest_paths.h new file mode 100644 index 0000000..22b54e3 --- /dev/null +++ b/src/3rdparty/adaptagrams/libcola/shortest_paths.h @@ -0,0 +1,245 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libcola - A library providing force-directed network layout using the + * stress-majorization method subject to separation constraints. + * + * Copyright (C) 2006-2014 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * See the file LICENSE.LGPL distributed with the library. + * + * This library 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. + * + * Author(s): Tim Dwyer +*/ + +#ifndef SHORTEST_PATHS_H +#define SHORTEST_PATHS_H + +#include <vector> +#include <valarray> +#include <cfloat> +#include <cassert> +#include <algorithm> +#include <iostream> +#include <limits> + +#include "libcola/commondefs.h" +#include <libvpsc/pairing_heap.h> +#include <libvpsc/assertions.h> + +template <class T> +struct PairNode; + +namespace shortest_paths { + +template <typename T> +struct Node { + unsigned id; + T d; + Node* p; // predecessor + std::vector<Node<T>*> neighbours; + std::vector<T> nweights; + PairNode<Node<T>*>* qnode; +}; +template <typename T> +struct CompareNodes { + bool operator() (Node<T> *const &u, Node<T> *const &v) const { + if(u==v) return false; // with g++ 4.1.2 unless I have this explicit check + // it returns true for this case when using -O3 optimization + // CRAZY! + if(u->d < v->d) { + return true; + } + return false; + } +}; + +typedef std::pair<unsigned,unsigned> Edge; +template <typename T> +/** + * returns the adjacency matrix, 0 entries for non-adjacent nodes + * @param n total number of nodes + * @param D n*n matrix of shortest paths + * @param es edge pairs + * @param eweights edge weights, if empty then all weights will be taken as 1 + */ +void neighbours(unsigned const n, T** D, std::vector<Edge> const & es, + std::valarray<T> const & eweights = std::valarray<T>()); +/** + * find all pairs shortest paths, n^3 dynamic programming approach + * @param n total number of nodes + * @param D n*n matrix of shortest paths + * @param es edge pairs + * @param eweights edge weights, if empty then all weights will be taken as 1 + */ +template <typename T> +void floyd_warshall(unsigned const n, T** D, std::vector<Edge> const & es, + std::valarray<T> const & eweights = std::valarray<T>()); + +/** + * find all pairs shortest paths, faster, uses dijkstra + * @param n total number of nodes + * @param D n*n matrix of shortest paths + * @param es edge pairs + * @param eweights edge weights, if empty then all weights will be taken as 1 + */ +template <typename T> +void johnsons(unsigned const n, T** D, std::vector<Edge> const & es, + std::valarray<T> const & eweights = std::valarray<T>()); +/** + * find shortest path lengths from node s to all other nodes + * @param s starting node + * @param n total number of nodes + * @param d n vector of path lengths + * @param es edge pairs + * @param eweights edge weights, if empty then all weights will be taken as 1 + */ +template <typename T> +void dijkstra(unsigned const s, unsigned const n, T* d, + std::vector<Edge> const & es, + std::valarray<T> const & eweights = std::valarray<T>()); + + +//----------------------------------------------------------------------------- +// Implementation: + +// O(n^3) time dynamic programming approach. Slow, but fool proof. +// Use for testing. +template <typename T> +void floyd_warshall( + unsigned const n, + T** D, + std::vector<Edge> const & es, + std::valarray<T> const & eweights) +{ + COLA_ASSERT((eweights.size() == 0) || (eweights.size() == es.size())); + for(unsigned i=0;i<n;i++) { + for(unsigned j=0;j<n;j++) { + if(i==j) D[i][j]=0; + else D[i][j]=std::numeric_limits<T>::max(); + } + } + for(unsigned i=0;i<es.size();i++) { + unsigned u=es[i].first, v=es[i].second; + COLA_ASSERT(u<n&&v<n); + D[u][v] = D[v][u] = (eweights.size() > 0) ? eweights[i] : 1; + } + for(unsigned k=0; k<n; k++) { + for(unsigned i=0; i<n; i++) { + for(unsigned j=0; j<n; j++) { + D[i][j]=std::min(D[i][j],D[i][k]+D[k][j]); + } + } + } +} +// Simply returns the adjacency graph +template <typename T> +void neighbours( + unsigned const n, + T** D, + std::vector<Edge> const & es, + std::valarray<T> const & eweights) +{ + COLA_ASSERT((eweights.size() == 0) || (eweights.size() == es.size())); + for(unsigned i=0;i<n;i++) { + for(unsigned j=0;j<n;j++) { + D[i][j]=0; + } + } + for(unsigned i=0;i<es.size();i++) { + unsigned u=es[i].first, v=es[i].second; + COLA_ASSERT(u<n&&v<n); + D[u][v] = D[v][u] = (eweights.size() > 0) ? eweights[i] : 1; + } +} +template <typename T> +void dijkstra_init( + std::vector<Node<T> > & vs, + std::vector<Edge> const& es, + std::valarray<T> const & eweights) { + COLA_ASSERT((eweights.size() == 0) || (eweights.size() == es.size())); +#ifndef NDEBUG + const unsigned n=vs.size(); +#endif + for(unsigned i=0;i<es.size();i++) { + unsigned u=es[i].first, v=es[i].second; + COLA_ASSERT(u<n); + COLA_ASSERT(v<n); + T w = (eweights.size() > 0) ? eweights[i] : 1; + vs[u].neighbours.push_back(&vs[v]); + vs[u].nweights.push_back(w); + vs[v].neighbours.push_back(&vs[u]); + vs[v].nweights.push_back(w); + } +} +template <typename T> +void dijkstra( + unsigned const s, + std::vector<Node<T> > & vs, + T* d) +{ + const unsigned n=vs.size(); + COLA_ASSERT(s<n); + for(unsigned i=0;i<n;i++) { + vs[i].id=i; + vs[i].d=std::numeric_limits<T>::max(); + vs[i].p=nullptr; + } + vs[s].d=0; + PairingHeap<Node<T>*,CompareNodes<T> > Q; + for(unsigned i=0;i<n;i++) { + vs[i].qnode = Q.insert(&vs[i]); + } + while(!Q.isEmpty()) { + Node<T> *u=Q.extractMin(); + d[u->id]=u->d; + for(unsigned i=0;i<u->neighbours.size();i++) { + Node<T> *v=u->neighbours[i]; + T w=u->nweights[i]; + if(u->d!=std::numeric_limits<T>::max() + && v->d > u->d+w) { + v->p=u; + v->d=u->d+w; + Q.decreaseKey(v->qnode,v); + } + } + } +} +template <typename T> +void dijkstra( + unsigned const s, + unsigned const n, + T* d, + std::vector<Edge> const & es, + std::valarray<T> const & eweights) +{ + COLA_ASSERT((eweights.size() == 0) || (eweights.size() == es.size())); + COLA_ASSERT(s<n); + std::vector<Node<T> > vs(n); + dijkstra_init(vs,es,eweights); + dijkstra(s,vs,d); +} + +template <typename T> +void johnsons( + unsigned const n, + T** D, + std::vector<Edge> const & es, + std::valarray<T> const & eweights) +{ + std::vector<Node<T> > vs(n); + dijkstra_init(vs,es,eweights); + for(unsigned k=0;k<n;k++) { + dijkstra(k,vs,D[k]); + } +} + +} //namespace shortest_paths +#endif //SHORTEST_PATHS_H |