alpar@906: /* -*- C++ -*- ladanyi@1435: * test/dijkstra_test.cc - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@578: #include "test_tools.h" alpar@921: #include alpar@921: #include alpar@1283: #include alpar@1148: #include klao@959: #include klao@959: #include alpar@921: using namespace lemon; alpar@568: alpar@568: const int PET_SIZE =5; alpar@568: alpar@570: alpar@793: void check_Dijkstra_BinHeap_Compile() alpar@570: { alpar@570: typedef int VType; klao@959: typedef concept::StaticGraph Graph; alpar@570: alpar@570: typedef Graph::Edge Edge; alpar@570: typedef Graph::Node Node; alpar@570: typedef Graph::EdgeIt EdgeIt; alpar@570: typedef Graph::NodeIt NodeIt; klao@959: typedef concept::ReadMap LengthMap; alpar@570: alpar@570: typedef Dijkstra DType; alpar@570: alpar@570: Graph G; alpar@570: Node n; alpar@570: Edge e; alpar@570: VType l; alpar@570: bool b; alpar@570: DType::DistMap d(G); alpar@570: DType::PredMap p(G); alpar@1148: // DType::PredNodeMap pn(G); alpar@793: LengthMap cap; alpar@570: alpar@570: DType dijkstra_test(G,cap); alpar@570: alpar@570: dijkstra_test.run(n); alpar@570: alpar@570: l = dijkstra_test.dist(n); deba@1763: e = dijkstra_test.predEdge(n); alpar@570: n = dijkstra_test.predNode(n); alpar@570: d = dijkstra_test.distMap(); alpar@570: p = dijkstra_test.predMap(); alpar@1148: // pn = dijkstra_test.predNodeMap(); alpar@570: b = dijkstra_test.reached(n); alpar@1283: alpar@1283: DirPath pp(G); alpar@1283: dijkstra_test.getPath(pp,n); alpar@570: } alpar@570: alpar@1220: void check_Dijkstra_Function_Compile() alpar@1220: { alpar@1220: typedef int VType; alpar@1220: typedef concept::StaticGraph Graph; alpar@1220: alpar@1220: typedef Graph::Edge Edge; alpar@1220: typedef Graph::Node Node; alpar@1220: typedef Graph::EdgeIt EdgeIt; alpar@1220: typedef Graph::NodeIt NodeIt; alpar@1220: typedef concept::ReadMap LengthMap; alpar@1220: alpar@1220: dijkstra(Graph(),LengthMap(),Node()).run(); alpar@1220: dijkstra(Graph(),LengthMap()).source(Node()).run(); alpar@1220: dijkstra(Graph(),LengthMap()) alpar@1220: .predMap(concept::WriteMap()) alpar@1220: .distMap(concept::WriteMap()) alpar@1220: .run(Node()); alpar@1220: alpar@1220: } alpar@1220: alpar@1220: alpar@568: int main() alpar@568: { alpar@568: alpar@568: typedef SmartGraph Graph; alpar@568: alpar@568: typedef Graph::Edge Edge; alpar@568: typedef Graph::Node Node; alpar@568: typedef Graph::EdgeIt EdgeIt; alpar@568: typedef Graph::NodeIt NodeIt; alpar@568: typedef Graph::EdgeMap LengthMap; alpar@568: alpar@568: Graph G; alpar@568: Node s, t; alpar@568: LengthMap cap(G); alpar@568: PetStruct ps = addPetersen(G,PET_SIZE); alpar@578: alpar@568: for(int i=0;i alpar@568: dijkstra_test(G, cap); alpar@568: dijkstra_test.run(s); alpar@568: alpar@568: check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path."); alpar@585: alpar@585: alpar@1283: DirPath p(G); alpar@1283: check(dijkstra_test.getPath(p,t),"getPath() failed to set the path."); alpar@1283: check(p.length()==4,"getPath() found a wrong path."); alpar@1283: alpar@1283: hegyi@776: for(EdgeIt e(G); e!=INVALID; ++e) { alpar@986: Node u=G.source(e); alpar@986: Node v=G.target(e); alpar@585: check( !dijkstra_test.reached(u) || alpar@585: (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]), alpar@986: "dist(target)-dist(source)- edge_length= " alpar@585: << dijkstra_test.dist(v) - dijkstra_test.dist(u) alpar@585: - cap[e]); alpar@585: } alpar@585: alpar@585: ///\bug This works only for integer lengths alpar@780: for(NodeIt v(G); v!=INVALID; ++v){ alpar@780: check(dijkstra_test.reached(v),"Each node should be reached."); deba@1763: if ( dijkstra_test.predEdge(v)!=INVALID ) { deba@1763: Edge e=dijkstra_test.predEdge(v); alpar@986: Node u=G.source(e); alpar@780: check(u==dijkstra_test.predNode(v),"Wrong tree."); alpar@585: check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e], alpar@780: "Wrong distance! Difference: " alpar@585: << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) alpar@585: - cap[e])); alpar@585: } alpar@780: } alpar@1148: alpar@1148: alpar@1148: { alpar@1218: NullMap myPredMap; alpar@1218: dijkstra(G,cap).predMap(myPredMap).run(s); alpar@1148: } alpar@1148: return 0; alpar@568: }