1 // -*- c++ -*- |
|
2 #ifndef LEMON_NET_GRAPH_H |
|
3 #define LEMON_NET_GRAPH_H |
|
4 |
|
5 ///\file |
|
6 ///\brief Declaration of EdgePathGraph. |
|
7 |
|
8 #include <lemon/invalid.h> |
|
9 #include <lemon/maps.h> |
|
10 |
|
11 /// The namespace of LEMON |
|
12 namespace lemon { |
|
13 |
|
14 // @defgroup empty_graph The EdgePathGraph class |
|
15 // @{ |
|
16 |
|
17 /// A graph class in that a simple edge can represent a path. |
|
18 |
|
19 /// This class provides all the common features of a graph structure |
|
20 /// that represents a network. You can handle with it layers. This |
|
21 /// means that an edge in one layer can be a complete path in a nother |
|
22 /// layer. |
|
23 |
|
24 template <typename P, class Gact, class Gsub> |
|
25 class EdgePathGraph |
|
26 { |
|
27 |
|
28 public: |
|
29 |
|
30 /// The actual layer |
|
31 Gact actuallayer; |
|
32 |
|
33 |
|
34 /// The layer on which the edges in this layer can represent paths. |
|
35 Gsub * sublayer; |
|
36 |
|
37 |
|
38 /// Map of nodes that represent the nodes of this layer in the sublayer |
|
39 typename Gact::template NodeMap<typename Gsub::Node *> projection; |
|
40 |
|
41 |
|
42 /// Map of routes that are represented by some edges in this layer |
|
43 typename Gact::template EdgeMap<P *> edgepath; |
|
44 |
|
45 |
|
46 /// Defalult constructor. |
|
47 /// We don't need any extra lines, because the actuallayer |
|
48 /// variable has run its constructor, when we have created this class |
|
49 /// So only the two maps has to be initialised here. |
|
50 EdgePathGraph() : projection(actuallayer), edgepath(actuallayer) |
|
51 { |
|
52 } |
|
53 |
|
54 |
|
55 ///Copy consructor. |
|
56 EdgePathGraph(const EdgePathGraph<P, Gact, Gsub> & EPG ) : actuallayer(EPG.actuallayer) , edgepath(actuallayer), projection(actuallayer) |
|
57 { |
|
58 } |
|
59 |
|
60 |
|
61 /// Map adder |
|
62 |
|
63 /// This function gets two edgemaps. One belongs to the actual layer and the |
|
64 /// other belongs to the sublayer. |
|
65 /// The function iterates through all of the edges in the edgemap belonging to the actual layer. |
|
66 /// It gets the value that belongs to the actual edge, and adds it to the value of each edge in the |
|
67 /// path represented by itself in the edgemap that belongs to the sublayer. |
|
68 |
|
69 template <typename T1, typename T2> void addMap (typename Gact::EdgeMap<T1> & actmap, typename Gsub::EdgeMap<T2> & submap) |
|
70 { |
|
71 for(EdgeIt e(actuallayer);actuallayer.valid(e);actuallayer.next(e)) |
|
72 { |
|
73 typedef typename P::EdgeIt PEdgeIt; |
|
74 PEdgeIt f; |
|
75 |
|
76 //dep//cout << "Edge " << id(source(e)) << " - " << id(target(e)) << " in actual layer is"; |
|
77 T1 incr=actmap[e]; |
|
78 //cout << incr << endl; |
|
79 |
|
80 if(edgepath[e]) |
|
81 { |
|
82 //dep//cout << endl << "Path"; |
|
83 for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) |
|
84 { |
|
85 //dep//cout << " " << sublayer->id(sublayer->source(f)) << "-" << sublayer->id(sublayer->target(f)); |
|
86 submap[f]+=incr; |
|
87 } |
|
88 //dep////cout << EPGr2.id(EPGr2.target(f)) << endl; |
|
89 //dep//cout << endl; |
|
90 } |
|
91 else |
|
92 { |
|
93 //dep//cout << " itself." <<endl; |
|
94 } |
|
95 } |
|
96 |
|
97 }; |
|
98 |
|
99 |
|
100 /// Describe |
|
101 /// This function walks thorugh the edges of the actual layer |
|
102 /// and displays the path represented by the actual edge. |
|
103 void describe () |
|
104 { |
|
105 for(EdgeIt e(actuallayer);actuallayer.valid(e);actuallayer.next(e)) |
|
106 { |
|
107 typedef typename P::EdgeIt PEdgeIt; |
|
108 PEdgeIt f; |
|
109 |
|
110 cout << "Edge " << id(source(e)) << " - " << id(target(e)) << " in actual layer is"; |
|
111 if(edgepath[e]) |
|
112 { |
|
113 cout << endl << "Path"; |
|
114 for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) |
|
115 { |
|
116 cout << " " << sublayer->id(sublayer->source(f)) << "-" << sublayer->id(sublayer->target(f)); |
|
117 } |
|
118 //cout << EPGr2.id(EPGr2.target(f)) << endl; |
|
119 cout << endl; |
|
120 } |
|
121 else |
|
122 { |
|
123 cout << " itself." <<endl; |
|
124 } |
|
125 } |
|
126 |
|
127 }; |
|
128 |
|
129 |
|
130 |
|
131 |
|
132 /// The base type of the node iterators. |
|
133 |
|
134 /// This is the base type of each node iterators, |
|
135 /// thus each kind of node iterator will convert to this. |
|
136 /// The Node type of the EdgePathGraph is the Node type of the actual layer. |
|
137 typedef typename Gact::Node Node; |
|
138 |
|
139 |
|
140 /// This iterator goes through each node. |
|
141 |
|
142 /// Its usage is quite simple, for example you can count the number |
|
143 /// of nodes in graph \c G of type \c Graph like this: |
|
144 /// \code |
|
145 ///int count=0; |
|
146 ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; |
|
147 /// \endcode |
|
148 /// The NodeIt type of the EdgePathGraph is the NodeIt type of the actual layer. |
|
149 typedef typename Gact::NodeIt NodeIt; |
|
150 |
|
151 |
|
152 /// The base type of the edge iterators. |
|
153 /// The Edge type of the EdgePathGraph is the Edge type of the actual layer. |
|
154 typedef typename Gact::Edge Edge; |
|
155 |
|
156 |
|
157 /// This iterator goes trough the outgoing edges of a node. |
|
158 |
|
159 /// This iterator goes trough the \e outgoing edges of a certain node |
|
160 /// of a graph. |
|
161 /// Its usage is quite simple, for example you can count the number |
|
162 /// of outgoing edges of a node \c n |
|
163 /// in graph \c G of type \c Graph as follows. |
|
164 /// \code |
|
165 ///int count=0; |
|
166 ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
167 /// \endcode |
|
168 /// The OutEdgeIt type of the EdgePathGraph is the OutEdgeIt type of the actual layer. |
|
169 typedef typename Gact::OutEdgeIt OutEdgeIt; |
|
170 |
|
171 |
|
172 /// This iterator goes trough the incoming edges of a node. |
|
173 |
|
174 /// This iterator goes trough the \e incoming edges of a certain node |
|
175 /// of a graph. |
|
176 /// Its usage is quite simple, for example you can count the number |
|
177 /// of outgoing edges of a node \c n |
|
178 /// in graph \c G of type \c Graph as follows. |
|
179 /// \code |
|
180 ///int count=0; |
|
181 ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
182 /// \endcode |
|
183 /// The InEdgeIt type of the EdgePathGraph is the InEdgeIt type of the actual layer. |
|
184 typedef typename Gact::InEdgeIt InEdgeIt; |
|
185 |
|
186 |
|
187 /// This iterator goes through each edge. |
|
188 |
|
189 /// This iterator goes through each edge of a graph. |
|
190 /// Its usage is quite simple, for example you can count the number |
|
191 /// of edges in a graph \c G of type \c Graph as follows: |
|
192 /// \code |
|
193 ///int count=0; |
|
194 ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; |
|
195 /// \endcode |
|
196 /// The EdgeIt type of the EdgePathGraph is the EdgeIt type of the actual layer. |
|
197 typedef typename Gact::EdgeIt EdgeIt; |
|
198 |
|
199 |
|
200 /// First node of the graph. |
|
201 |
|
202 /// \retval i the first node. |
|
203 /// \return the first node. |
|
204 typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);} |
|
205 |
|
206 |
|
207 /// The first incoming edge. |
|
208 typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);} |
|
209 |
|
210 |
|
211 /// The first outgoing edge. |
|
212 typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);} |
|
213 |
|
214 |
|
215 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} |
|
216 /// The first edge of the Graph. |
|
217 typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);} |
|
218 |
|
219 |
|
220 // Node getNext(Node) const {} |
|
221 // InEdgeIt getNext(InEdgeIt) const {} |
|
222 // OutEdgeIt getNext(OutEdgeIt) const {} |
|
223 // //SymEdgeIt getNext(SymEdgeIt) const {} |
|
224 // EdgeIt getNext(EdgeIt) const {} |
|
225 |
|
226 |
|
227 /// Go to the next node. |
|
228 typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);} |
|
229 /// Go to the next incoming edge. |
|
230 typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);} |
|
231 /// Go to the next outgoing edge. |
|
232 typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);} |
|
233 //SymEdgeIt &next(SymEdgeIt &) const {} |
|
234 /// Go to the next edge. |
|
235 typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);} |
|
236 |
|
237 ///Gives back the target node of an edge. |
|
238 typename Gact::Node target(typename Gact::Edge edge) const { return actuallayer.target(edge); } |
|
239 ///Gives back the source node of an edge. |
|
240 typename Gact::Node source(typename Gact::Edge edge) const { return actuallayer.source(edge); } |
|
241 |
|
242 // Node aNode(InEdgeIt) const {} |
|
243 // Node aNode(OutEdgeIt) const {} |
|
244 // Node aNode(SymEdgeIt) const {} |
|
245 |
|
246 // Node bNode(InEdgeIt) const {} |
|
247 // Node bNode(OutEdgeIt) const {} |
|
248 // Node bNode(SymEdgeIt) const {} |
|
249 |
|
250 /// Checks if a node iterator is valid |
|
251 |
|
252 ///\todo Maybe, it would be better if iterator converted to |
|
253 ///bool directly, as Jacint prefers. |
|
254 bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);} |
|
255 /// Checks if an edge iterator is valid |
|
256 |
|
257 ///\todo Maybe, it would be better if iterator converted to |
|
258 ///bool directly, as Jacint prefers. |
|
259 bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);} |
|
260 |
|
261 ///Gives back the \e id of a node. |
|
262 |
|
263 ///\warning Not all graph structures provide this feature. |
|
264 /// |
|
265 int id(const typename Gact::Node & node) const { return actuallayer.id(node);} |
|
266 ///Gives back the \e id of an edge. |
|
267 |
|
268 ///\warning Not all graph structures provide this feature. |
|
269 /// |
|
270 int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);} |
|
271 |
|
272 //void setInvalid(Node &) const {}; |
|
273 //void setInvalid(Edge &) const {}; |
|
274 |
|
275 ///Add a new node to the graph. |
|
276 |
|
277 /// \return the new node. |
|
278 /// |
|
279 typename Gact::Node addNode() { return actuallayer.addNode();} |
|
280 ///Add a new edge to the graph. |
|
281 |
|
282 ///Add a new edge to the graph with source node \c source |
|
283 ///and target node \c target. |
|
284 ///\return the new edge. |
|
285 typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);} |
|
286 |
|
287 /// Resets the graph. |
|
288 |
|
289 /// This function deletes all edges and nodes of the graph. |
|
290 /// It also frees the memory allocated to store them. |
|
291 void clear() {actuallayer.clear();} |
|
292 |
|
293 int nodeNum() const { return actuallayer.nodeNum();} |
|
294 int edgeNum() const { return actuallayer.edgeNum();} |
|
295 |
|
296 ///Read/write/reference map of the nodes to type \c T. |
|
297 |
|
298 ///Read/write/reference map of the nodes to type \c T. |
|
299 /// \sa MemoryMap |
|
300 /// \todo We may need copy constructor |
|
301 /// \todo We may need conversion from other nodetype |
|
302 /// \todo We may need operator= |
|
303 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
304 /// needs extra attention! |
|
305 |
|
306 template<class T> class NodeMap |
|
307 { |
|
308 public: |
|
309 typedef T Value; |
|
310 typedef Node Key; |
|
311 |
|
312 NodeMap(const EdgePathGraph &) {} |
|
313 NodeMap(const EdgePathGraph &, T) {} |
|
314 |
|
315 template<typename TT> NodeMap(const NodeMap<TT> &) {} |
|
316 |
|
317 /// Sets the value of a node. |
|
318 |
|
319 /// Sets the value associated with node \c i to the value \c t. |
|
320 /// |
|
321 void set(Node, T) {} |
|
322 // Gets the value of a node. |
|
323 //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary? |
|
324 T &operator[](Node) {return *(T*)0;} |
|
325 const T &operator[](Node) const {return *(T*)0;} |
|
326 |
|
327 /// Updates the map if the graph has been changed |
|
328 |
|
329 /// \todo Do we need this? |
|
330 /// |
|
331 void update() {} |
|
332 void update(T a) {} //FIXME: Is it necessary |
|
333 }; |
|
334 |
|
335 ///Read/write/reference map of the edges to type \c T. |
|
336 |
|
337 ///Read/write/reference map of the edges to type \c T. |
|
338 ///It behaves exactly in the same way as \ref NodeMap. |
|
339 /// \sa NodeMap |
|
340 /// \sa MemoryMap |
|
341 /// \todo We may need copy constructor |
|
342 /// \todo We may need conversion from other edgetype |
|
343 /// \todo We may need operator= |
|
344 template<class T> class EdgeMap |
|
345 { |
|
346 public: |
|
347 typedef T Value; |
|
348 typedef Edge Key; |
|
349 |
|
350 EdgeMap(const EdgePathGraph &) {} |
|
351 EdgeMap(const EdgePathGraph &, T ) {} |
|
352 |
|
353 ///\todo It can copy between different types. |
|
354 /// |
|
355 template<typename TT> EdgeMap(const EdgeMap<TT> &) {} |
|
356 |
|
357 void set(Edge, T) {} |
|
358 //T get(Edge) const {return *(T*)0;} |
|
359 T &operator[](Edge) {return *(T*)0;} |
|
360 const T &operator[](Edge) const {return *(T*)0;} |
|
361 |
|
362 void update() {} |
|
363 void update(T a) {} //FIXME: Is it necessary |
|
364 }; |
|
365 }; |
|
366 |
|
367 /// An empty erasable graph class. |
|
368 |
|
369 /// This class provides all the common features of an \e erasable graph |
|
370 /// structure, |
|
371 /// however completely without implementations and real data structures |
|
372 /// behind the interface. |
|
373 /// All graph algorithms should compile with this class, but it will not |
|
374 /// run properly, of course. |
|
375 /// |
|
376 /// \todo This blabla could be replaced by a sepatate description about |
|
377 /// s. |
|
378 /// |
|
379 /// It can be used for checking the interface compatibility, |
|
380 /// or it can serve as a skeleton of a new graph structure. |
|
381 /// |
|
382 /// Also, you will find here the full documentation of a certain graph |
|
383 /// feature, the documentation of a real graph imlementation |
|
384 /// like @ref ListGraph or |
|
385 /// @ref SmartGraph will just refer to this structure. |
|
386 template <typename P, typename Gact, typename Gsub> |
|
387 class ErasableEdgePathGraph : public EdgePathGraph<P, Gact, Gsub> |
|
388 { |
|
389 public: |
|
390 /// Deletes a node. |
|
391 void erase(typename Gact::Node n) {actuallayer.erase(n);} |
|
392 /// Deletes an edge. |
|
393 void erase(typename Gact::Edge e) {actuallayer.erase(e);} |
|
394 |
|
395 /// Defalult constructor. |
|
396 ErasableEdgePathGraph() {} |
|
397 ///Copy consructor. |
|
398 ErasableEdgePathGraph(const EdgePathGraph<P, Gact, Gsub> &EPG) {} |
|
399 }; |
|
400 |
|
401 |
|
402 // @} |
|
403 |
|
404 } //namespace lemon |
|
405 |
|
406 |
|
407 #endif // LEMON_SKELETON_GRAPH_H |
|