diff -r d8475431bbbb -r 8e85e6bbefdf src/demo/min_route.cc --- a/src/demo/min_route.cc Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,114 +0,0 @@ -#include -#include - -#include -#include -#include -#include -#include - -#include - -#include - - -using namespace lemon; - -template -class PotentialMap { -public: - typedef double Value; - typedef typename CoordMap::Key Key; - - PotentialMap(const CoordMap& _coord, const xy& _target) - : coord(_coord), target(_target) {} - - double operator[](const Key& node) const { - return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) + - (coord[node].y - target.y) * (coord[node].y - target.y)); - } -private: - const CoordMap& coord; - xy target; -}; - -template -class ReducedLengthMap { -public: - typedef double Value; - typedef typename LengthMap::Key Key; - - ReducedLengthMap(const Graph& _graph, const LengthMap& _length, - const PotentialMap& _pot) - : graph(_graph), length(_length), pot(_pot) {} - - Value operator[](const Key& edge) const { - return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]); - } - -private: - const Graph& graph; - const LengthMap& length; - const PotentialMap& pot; -}; - -int main() { - typedef SmartGraph Graph; - - typedef Graph::Edge Edge; - typedef Graph::Node Node; - typedef Graph::EdgeIt EdgeIt; - typedef Graph::NodeIt NodeIt; - typedef Graph::EdgeMap LengthMap; - typedef Graph::NodeMap > CoordMap; - - SmartGraph graph; - - std::ifstream is("route.lgf"); - GraphReader reader(is, graph); - - CoordMap coord(graph); - XMap xcoord = xMap(coord); - reader.readNodeMap("coordinates_x", xcoord); - YMap ycoord = yMap(coord); - reader.readNodeMap("coordinates_y", ycoord); - - LengthMap length(graph); - reader.readEdgeMap("length", length); - - Node source, target; - reader.readNode("source", source); - reader.readNode("target", target); - - reader.run(); - - { - Timer timer; - Dijkstra dijkstra(graph, length); - dijkstra.init(); - dijkstra.addSource(source); - dijkstra.start(target); - - std::cout << dijkstra.dist(target) << std::endl; - std::cout << timer << std::endl; - } - { - Timer timer; - typedef PotentialMap Potential; - Potential potential(coord, coord[target]); - - typedef ReducedLengthMap ReducedLength; - ReducedLength reduced(graph, length, potential); - - Dijkstra dijkstra(graph, reduced); - - dijkstra.init(); - dijkstra.addSource(source); - dijkstra.start(target); - - std::cout << dijkstra.dist(target) + potential[source] << std::endl; - std::cout << timer << std::endl; - } - - return 0; -}