deba@1358: #include deba@1358: #include deba@1358: deba@1342: #include deba@1342: #include deba@1342: #include deba@1342: #include deba@1342: #include deba@1342: deba@1342: #include deba@1342: deba@1342: #include deba@1342: deba@1358: deba@1342: using namespace lemon; deba@1342: deba@1342: template deba@1342: class PotentialMap { deba@1342: public: deba@1342: typedef double Value; deba@1342: typedef typename CoordMap::Key Key; deba@1342: deba@1342: PotentialMap(const CoordMap& _coord, const xy& _target) deba@1342: : coord(_coord), target(_target) {} deba@1342: deba@1342: double operator[](const Key& node) const { deba@1342: return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) + deba@1342: (coord[node].y - target.y) * (coord[node].y - target.y)); deba@1342: } deba@1342: private: deba@1358: const CoordMap& coord; deba@1342: xy target; deba@1342: }; deba@1342: deba@1342: template deba@1342: class ReducedLengthMap { deba@1342: public: deba@1342: typedef double Value; deba@1342: typedef typename LengthMap::Key Key; deba@1342: deba@1342: ReducedLengthMap(const Graph& _graph, const LengthMap& _length, deba@1342: const PotentialMap& _pot) deba@1342: : graph(_graph), length(_length), pot(_pot) {} deba@1342: deba@1342: Value operator[](const Key& edge) const { deba@1342: return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]); deba@1342: } deba@1342: deba@1342: private: deba@1342: const Graph& graph; deba@1342: const LengthMap& length; deba@1342: const PotentialMap& pot; deba@1342: }; deba@1342: deba@1342: int main() { deba@1342: typedef SmartGraph Graph; deba@1342: deba@1342: typedef Graph::Edge Edge; deba@1342: typedef Graph::Node Node; deba@1342: typedef Graph::EdgeIt EdgeIt; deba@1342: typedef Graph::NodeIt NodeIt; deba@1342: typedef Graph::EdgeMap LengthMap; deba@1342: typedef Graph::NodeMap > CoordMap; deba@1342: deba@1342: SmartGraph graph; deba@1342: deba@1358: std::ifstream is("route.lgf"); deba@1358: GraphReader reader(is, graph); deba@1342: deba@1342: CoordMap coord(graph); deba@1342: XMap xcoord = xMap(coord); deba@1394: reader.readNodeMap("coordinates_x", xcoord); deba@1342: YMap ycoord = yMap(coord); deba@1394: reader.readNodeMap("coordinates_y", ycoord); deba@1342: deba@1342: LengthMap length(graph); deba@1394: reader.readEdgeMap("length", length); deba@1342: deba@1342: Node source, target; deba@1394: reader.readNode("source", source); deba@1394: reader.readNode("target", target); deba@1342: deba@1342: reader.run(); deba@1342: deba@1342: { deba@1342: Timer timer; deba@1342: Dijkstra dijkstra(graph, length); deba@1342: dijkstra.init(); deba@1342: dijkstra.addSource(source); deba@1342: dijkstra.start(target); deba@1342: deba@1342: std::cout << dijkstra.dist(target) << std::endl; deba@1342: std::cout << timer << std::endl; deba@1342: } deba@1342: { deba@1342: Timer timer; deba@1342: typedef PotentialMap Potential; deba@1342: Potential potential(coord, coord[target]); deba@1342: deba@1342: typedef ReducedLengthMap ReducedLength; deba@1342: ReducedLength reduced(graph, length, potential); deba@1342: deba@1342: Dijkstra dijkstra(graph, reduced); deba@1342: deba@1342: dijkstra.init(); deba@1342: dijkstra.addSource(source); deba@1342: dijkstra.start(target); deba@1342: deba@1342: std::cout << dijkstra.dist(target) + potential[source] << std::endl; deba@1342: std::cout << timer << std::endl; deba@1342: } deba@1342: deba@1342: return 0; deba@1342: }