The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #include "test_tools.h"
20 #include <lemon/smart_graph.h>
21 #include <lemon/dijkstra.h>
22 #include <lemon/path.h>
23 #include <lemon/maps.h>
24 #include <lemon/concept/graph.h>
25 #include <lemon/concept/maps.h>
26 using namespace lemon;
28 const int PET_SIZE =5;
31 void check_Dijkstra_BinHeap_Compile()
34 typedef concept::StaticGraph Graph;
36 typedef Graph::Edge Edge;
37 typedef Graph::Node Node;
38 typedef Graph::EdgeIt EdgeIt;
39 typedef Graph::NodeIt NodeIt;
40 typedef concept::ReadMap<Edge,VType> LengthMap;
42 typedef Dijkstra<Graph, LengthMap> DType;
51 // DType::PredNodeMap pn(G);
54 DType dijkstra_test(G,cap);
58 l = dijkstra_test.dist(n);
59 e = dijkstra_test.predEdge(n);
60 n = dijkstra_test.predNode(n);
61 d = dijkstra_test.distMap();
62 p = dijkstra_test.predMap();
63 // pn = dijkstra_test.predNodeMap();
64 b = dijkstra_test.reached(n);
67 dijkstra_test.getPath(pp,n);
70 void check_Dijkstra_Function_Compile()
73 typedef concept::StaticGraph Graph;
75 typedef Graph::Edge Edge;
76 typedef Graph::Node Node;
77 typedef Graph::EdgeIt EdgeIt;
78 typedef Graph::NodeIt NodeIt;
79 typedef concept::ReadMap<Edge,VType> LengthMap;
81 dijkstra(Graph(),LengthMap(),Node()).run();
82 dijkstra(Graph(),LengthMap()).source(Node()).run();
83 dijkstra(Graph(),LengthMap())
84 .predMap(concept::WriteMap<Node,Edge>())
85 .distMap(concept::WriteMap<Node,VType>())
94 typedef SmartGraph Graph;
96 typedef Graph::Edge Edge;
97 typedef Graph::Node Node;
98 typedef Graph::EdgeIt EdgeIt;
99 typedef Graph::NodeIt NodeIt;
100 typedef Graph::EdgeMap<int> LengthMap;
105 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
107 for(int i=0;i<PET_SIZE;i++) {
110 cap[ps.chords[i]]=10;
115 Dijkstra<Graph, LengthMap>
116 dijkstra_test(G, cap);
117 dijkstra_test.run(s);
119 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
123 check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
124 check(p.length()==4,"getPath() found a wrong path.");
127 for(EdgeIt e(G); e!=INVALID; ++e) {
130 check( !dijkstra_test.reached(u) ||
131 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
132 "dist(target)-dist(source)- edge_length= "
133 << dijkstra_test.dist(v) - dijkstra_test.dist(u)
137 ///\bug This works only for integer lengths
138 for(NodeIt v(G); v!=INVALID; ++v){
139 check(dijkstra_test.reached(v),"Each node should be reached.");
140 if ( dijkstra_test.predEdge(v)!=INVALID ) {
141 Edge e=dijkstra_test.predEdge(v);
143 check(u==dijkstra_test.predNode(v),"Wrong tree.");
144 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
145 "Wrong distance! Difference: "
146 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
153 NullMap<Node,Edge> myPredMap;
154 dijkstra(G,cap).predMap(myPredMap).run(s);