Tracore
KShortestPaths.h
1 //
2 // Created by wrede on 25.05.16.
3 //
4 
5 #ifndef GBMOT_KSHORTESTPATHS_H
6 #define GBMOT_KSHORTESTPATHS_H
7 
8 #include "../graph/Definitions.h"
9 #include "../core/ObjectData.h"
10 #include "../core/Tracklet.h"
11 
12 namespace algo
13 {
18  {
19  private:
23  DirectedGraph original_graph_;
24 
28  DirectedGraph copied_graph_;
29 
34  const Vertex source_;
35 
40  const Vertex sink_;
41 
46  std::unordered_map<Vertex, Vertex> original_to_copy_;
47 
52  std::unordered_map<Vertex, Vertex> copy_to_original_;
53 
58  std::vector<std::unordered_map<Vertex, double>> i_distances_;
59 
64  std::vector<MultiPredecessorMap> i_shortest_paths_;
65 
70  void CopyOriginalGraph();
71 
79  void ExtendGraph(size_t i);
80 
81  //TODO comment
82  void TransformEdgeCosts(size_t i, bool original);
83 
88  double OverallCosts(size_t i);
89 
95  void Interlace(size_t i);
96 
104  void FindAndAugmentPath(size_t i, bool original);
105 
111  std::vector<std::pair<std::pair<Vertex, Vertex>, double>> edges_to_add_;
112 
118  std::vector<std::pair<Vertex, Vertex>> edges_to_remove_;
119 
126  void QueueRemoveEdge(Vertex source, Vertex target);
127 
136  void QueueAddEdge(Vertex source, Vertex target, double weight);
137 
142  void UpdateEdges();
143  public:
152  KShortestPaths(DirectedGraph graph, Vertex source, Vertex sink);
153 
160  MultiPredecessorMap Run(size_t max_path_count);
161  };
162 }
163 
164 
165 #endif //GBMOT_KSHORTESTPATHS_H
KShortestPaths(DirectedGraph graph, Vertex source, Vertex sink)
Definition: KShortestPaths.cpp:14
Definition: Berclaz.cpp:13
Definition: KShortestPaths.h:17
MultiPredecessorMap Run(size_t max_path_count)
Definition: KShortestPaths.cpp:19