84 lines
2.3 KiB
C++
84 lines
2.3 KiB
C++
/*
|
||
* © Copyright 2014 – Urheberrechtshinweis
|
||
* Alle Rechte vorbehalten / All Rights Reserved
|
||
*
|
||
* Programmcode ist urheberrechtlich geschuetzt.
|
||
* Das Urheberrecht liegt, soweit nicht ausdruecklich anders gekennzeichnet, bei Frank Ebner.
|
||
* Keine Verwendung ohne explizite Genehmigung.
|
||
* (vgl. § 106 ff UrhG / § 97 UrhG)
|
||
*/
|
||
|
||
#ifndef DIJKSTRANODE_H
|
||
#define DIJKSTRANODE_H
|
||
|
||
/**
|
||
* wrapper around a user data structure
|
||
* adds additional fields needed for dijkstra calculation
|
||
*/
|
||
template <typename T> struct DijkstraNode {
|
||
|
||
/** pos infinity */
|
||
static constexpr float INF = +99999999;
|
||
|
||
/** the user-element this node describes */
|
||
const T* element;
|
||
|
||
/** the previous dijkstra node (navigation path) */
|
||
DijkstraNode<T>* previous;
|
||
|
||
/** the weight from the start up to this element */
|
||
float cumWeight;
|
||
|
||
/** whether we already enqueued this node into the processing list (do NOT examing nodes twice) */
|
||
bool enqueued;
|
||
|
||
|
||
/** ctor */
|
||
DijkstraNode(const T* element) : element(element), previous(), cumWeight(INF), enqueued(false) {;}
|
||
|
||
};
|
||
|
||
/**
|
||
* data structure describing the connection between two nodes.
|
||
* NOTE: only used to track already processed connections!
|
||
*/
|
||
template <typename T> struct DijkstraEdge {
|
||
|
||
/** the edge's source */
|
||
const DijkstraNode<T>* src;
|
||
|
||
/** the edge's destination */
|
||
const DijkstraNode<T>* dst;
|
||
|
||
/** ctor */
|
||
DijkstraEdge(const DijkstraNode<T>* src, const DijkstraNode<T>* dst) : src(src), dst(dst) {;}
|
||
|
||
/** equal? (bi-directional! edge direction does NOT matter) */
|
||
bool operator == (const DijkstraEdge& other) const {
|
||
return ((dst == other.dst) && (src == other.src)) ||
|
||
((src == other.dst) && (dst == other.src));
|
||
}
|
||
|
||
// std::set was slower than std::unordered_set
|
||
// bool operator < (const DijkstraEdge& other) const {
|
||
// return ((size_t)src * (size_t)dst) < ((size_t)other.src * (size_t)other.dst);
|
||
// }
|
||
|
||
};
|
||
|
||
/** allows adding DijkstraEdge<T> to hash-maps */
|
||
namespace std {
|
||
template <typename T> struct hash<DijkstraEdge<T>>{
|
||
size_t operator()(const DijkstraEdge<T>& e) const {
|
||
|
||
// dunno why but this one provided the fastet results even though
|
||
// this should lead to the most hash-collissions?!
|
||
return hash<size_t>()( std::min((size_t)e.src, (size_t)e.dst) );
|
||
//return hash<size_t>()( (size_t)e.src * (size_t)e.dst );
|
||
|
||
}
|
||
};
|
||
}
|
||
|
||
#endif // DIJKSTRANODE_H
|