Solve conflict.
2 * src/test/dijkstra_test.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #include "test_tools.h"
18 #include <lemon/smart_graph.h>
19 #include <lemon/dijkstra.h>
20 #include <lemon/maps.h>
21 #include <lemon/concept/graph.h>
22 #include <lemon/concept/maps.h>
23 using namespace lemon;
25 const int PET_SIZE =5;
28 void check_Dijkstra_BinHeap_Compile()
31 typedef concept::StaticGraph Graph;
33 typedef Graph::Edge Edge;
34 typedef Graph::Node Node;
35 typedef Graph::EdgeIt EdgeIt;
36 typedef Graph::NodeIt NodeIt;
37 typedef concept::ReadMap<Edge,VType> LengthMap;
39 typedef Dijkstra<Graph, LengthMap> DType;
48 // DType::PredNodeMap pn(G);
51 DType dijkstra_test(G,cap);
55 l = dijkstra_test.dist(n);
56 e = dijkstra_test.pred(n);
57 n = dijkstra_test.predNode(n);
58 d = dijkstra_test.distMap();
59 p = dijkstra_test.predMap();
60 // pn = dijkstra_test.predNodeMap();
61 b = dijkstra_test.reached(n);
68 typedef SmartGraph Graph;
70 typedef Graph::Edge Edge;
71 typedef Graph::Node Node;
72 typedef Graph::EdgeIt EdgeIt;
73 typedef Graph::NodeIt NodeIt;
74 typedef Graph::EdgeMap<int> LengthMap;
79 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
81 for(int i=0;i<PET_SIZE;i++) {
89 Dijkstra<Graph, LengthMap>
90 dijkstra_test(G, cap);
93 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
96 for(EdgeIt e(G); e!=INVALID; ++e) {
99 check( !dijkstra_test.reached(u) ||
100 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
101 "dist(target)-dist(source)- edge_length= "
102 << dijkstra_test.dist(v) - dijkstra_test.dist(u)
106 ///\bug This works only for integer lengths
107 for(NodeIt v(G); v!=INVALID; ++v){
108 check(dijkstra_test.reached(v),"Each node should be reached.");
109 if ( dijkstra_test.pred(v)!=INVALID ) {
110 Edge e=dijkstra_test.pred(v);
112 check(u==dijkstra_test.predNode(v),"Wrong tree.");
113 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
114 "Wrong distance! Difference: "
115 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
122 NullMap<Node,Node> myPredNodeMap;
123 dijkstra(G,cap).predNodeMap(myPredNodeMap).run(s);