1 // This file is part of libigl, a simple c++ geometry processing library.
2 //
3 // Copyright (C) 2016 Alec Jacobson <alecjacobson@gmail.com>
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public License
6 // v. 2.0. If a copy of the MPL was not distributed with this file, You can
7 // obtain one at http://mozilla.org/MPL/2.0/.
8 #include <igl/dijkstra.h>
9
10 template <typename IndexType, typename DerivedD, typename DerivedP>
dijkstra_compute_paths(const IndexType & source,const std::set<IndexType> & targets,const std::vector<std::vector<IndexType>> & VV,Eigen::PlainObjectBase<DerivedD> & min_distance,Eigen::PlainObjectBase<DerivedP> & previous)11 IGL_INLINE int igl::dijkstra_compute_paths(const IndexType &source,
12 const std::set<IndexType> &targets,
13 const std::vector<std::vector<IndexType> >& VV,
14 Eigen::PlainObjectBase<DerivedD> &min_distance,
15 Eigen::PlainObjectBase<DerivedP> &previous)
16 {
17 int numV = VV.size();
18 min_distance.setConstant(numV, 1, std::numeric_limits<typename DerivedD::Scalar>::infinity());
19 min_distance[source] = 0;
20 previous.setConstant(numV, 1, -1);
21 std::set<std::pair<typename DerivedD::Scalar, IndexType> > vertex_queue;
22 vertex_queue.insert(std::make_pair(min_distance[source], source));
23
24 while (!vertex_queue.empty())
25 {
26 typename DerivedD::Scalar dist = vertex_queue.begin()->first;
27 IndexType u = vertex_queue.begin()->second;
28 vertex_queue.erase(vertex_queue.begin());
29
30 if (targets.find(u)!= targets.end())
31 return u;
32
33 // Visit each edge exiting u
34 const std::vector<int> &neighbors = VV[u];
35 for (std::vector<int>::const_iterator neighbor_iter = neighbors.begin();
36 neighbor_iter != neighbors.end();
37 neighbor_iter++)
38 {
39 IndexType v = *neighbor_iter;
40 typename DerivedD::Scalar distance_through_u = dist + 1.;
41 if (distance_through_u < min_distance[v]) {
42 vertex_queue.erase(std::make_pair(min_distance[v], v));
43
44 min_distance[v] = distance_through_u;
45 previous[v] = u;
46 vertex_queue.insert(std::make_pair(min_distance[v], v));
47
48 }
49
50 }
51 }
52 //we should never get here
53 return -1;
54 }
55
56 template <typename IndexType, typename DerivedP>
dijkstra_get_shortest_path_to(const IndexType & vertex,const Eigen::PlainObjectBase<DerivedP> & previous,std::vector<IndexType> & path)57 IGL_INLINE void igl::dijkstra_get_shortest_path_to(const IndexType &vertex,
58 const Eigen::PlainObjectBase<DerivedP> &previous,
59 std::vector<IndexType> &path)
60 {
61 IndexType source = vertex;
62 path.clear();
63 for ( ; source != -1; source = previous[source])
64 path.push_back(source);
65 }
66
67 #ifdef IGL_STATIC_LIBRARY
68 // Explicit template instantiation
69 template int igl::dijkstra_compute_paths<int, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::Matrix<int, -1, 1, 0, -1, 1> >(int const&, std::set<int, std::less<int>, std::allocator<int> > const&, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, Eigen::PlainObjectBase<Eigen::Matrix<double, -1, 1, 0, -1, 1> >&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> >&);
70 template void igl::dijkstra_get_shortest_path_to<int, Eigen::Matrix<int, -1, 1, 0, -1, 1> >(int const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, std::vector<int, std::allocator<int> >&);
71 #endif
72