1 // -*- c++ -*- |
|
2 #ifndef LEMON_NET_GRAPH_H |
|
3 #define LEMON_NET_GRAPH_H |
|
4 |
|
5 ///\file |
|
6 ///\brief Declaration of HierarchyGraph. |
|
7 |
|
8 #include <lemon/invalid.h> |
|
9 #include <lemon/maps.h> |
|
10 |
|
11 /// The namespace of LEMON |
|
12 namespace lemon |
|
13 { |
|
14 |
|
15 // @defgroup empty_graph The HierarchyGraph class |
|
16 // @{ |
|
17 |
|
18 /// A graph class in that a simple edge can represent a path. |
|
19 |
|
20 /// This class provides common features of a graph structure |
|
21 /// that represents a network. You can handle with it layers. This |
|
22 /// means that a node in one layer can be a complete network in a nother |
|
23 /// layer. |
|
24 |
|
25 template < class Gact, class Gsub > class HierarchyGraph |
|
26 { |
|
27 |
|
28 public: |
|
29 |
|
30 /// The actual layer |
|
31 Gact actuallayer; |
|
32 |
|
33 |
|
34 /// Map of the subnetworks in the sublayer |
|
35 /// The appropriate edge nodes are also stored here |
|
36 |
|
37 class SubNetwork |
|
38 { |
|
39 |
|
40 struct actedgesubnodestruct |
|
41 { |
|
42 typename Gact::Edge actedge; |
|
43 typename Gsub::Node subnode; |
|
44 }; |
|
45 |
|
46 int edgenumber; |
|
47 bool connectable; |
|
48 Gact *actuallayer; |
|
49 typename Gact::Node * actuallayernode; |
|
50 Gsub *subnetwork; |
|
51 actedgesubnodestruct *assignments; |
|
52 |
|
53 public: |
|
54 |
|
55 int addAssignment (typename Gact::Edge actedge, |
|
56 typename Gsub::Node subnode) |
|
57 { |
|
58 if (!(actuallayer->valid (actedge))) |
|
59 { |
|
60 cerr << "The given edge is not in the given network!" << endl; |
|
61 return -1; |
|
62 } |
|
63 else if ((actuallayer->id (actuallayer->source (actedge)) != |
|
64 actuallayer->id (*actuallayernode)) |
|
65 && (actuallayer->id (actuallayer->target (actedge)) != |
|
66 actuallayer->id (*actuallayernode))) |
|
67 { |
|
68 cerr << "The given edge does not connect to the given node!" << |
|
69 endl; |
|
70 return -1; |
|
71 } |
|
72 |
|
73 if (!(subnetwork->valid (subnode))) |
|
74 { |
|
75 cerr << "The given node is not in the given network!" << endl; |
|
76 return -1; |
|
77 } |
|
78 |
|
79 int i = 0; |
|
80 //while in the array there is valid note that is not equvivalent with the one that would be noted increase i |
|
81 while ((i < edgenumber) |
|
82 && (actuallayer->valid (assignments[i].actedge)) |
|
83 && (assignments[i].actedge != actedge)) |
|
84 i++; |
|
85 if (assignments[i].actedge == actedge) |
|
86 { |
|
87 cout << "Warning: Redefinement of assigment!!!" << endl; |
|
88 } |
|
89 if (i == edgenumber) |
|
90 { |
|
91 cout << |
|
92 "This case can't be!!! (because there should be the guven edge in the array already and the cycle had to stop)" |
|
93 << endl; |
|
94 } |
|
95 //if(!(actuallayer->valid(assignments[i].actedge))) //this condition is necessary if we do not obey redefinition |
|
96 { |
|
97 assignments[i].actedge = actedge; |
|
98 assignments[i].subnode = subnode; |
|
99 } |
|
100 |
|
101 /// If to all of the edges a subnode is assigned then the subnetwork is connectable (attachable?) |
|
102 /// We do not need to check for further attributes, because to notice an assignment we need |
|
103 /// all of them to be correctly initialised before. |
|
104 if (i == edgenumber - 1) |
|
105 connectable = 1; |
|
106 |
|
107 return 0; |
|
108 } |
|
109 |
|
110 int setSubNetwork (Gsub * sn) |
|
111 { |
|
112 subnetwork = sn; |
|
113 return 0; |
|
114 } |
|
115 |
|
116 int setActualLayer (Gact * al) |
|
117 { |
|
118 actuallayer = al; |
|
119 return 0; |
|
120 } |
|
121 |
|
122 int setActualLayerNode (typename Gact::Node * aln) |
|
123 { |
|
124 typename Gact::InEdgeIt iei; |
|
125 typename Gact::OutEdgeIt oei; |
|
126 |
|
127 actuallayernode = aln; |
|
128 |
|
129 edgenumber = 0; |
|
130 |
|
131 if (actuallayer) |
|
132 { |
|
133 for (iei = actuallayer->first (iei, (*actuallayernode)); |
|
134 ((actuallayer->valid (iei)) |
|
135 && (actuallayer->target (iei) == (*actuallayernode))); |
|
136 actuallayer->next (iei)) |
|
137 { |
|
138 cout << actuallayer->id (actuallayer-> |
|
139 source (iei)) << " " << actuallayer-> |
|
140 id (actuallayer->target (iei)) << endl; |
|
141 edgenumber++; |
|
142 } |
|
143 //cout << "Number of in-edges: " << edgenumber << endl; |
|
144 for (oei = actuallayer->first (oei, (*actuallayernode)); |
|
145 ((actuallayer->valid (oei)) |
|
146 && (actuallayer->source (oei) == (*actuallayernode))); |
|
147 actuallayer->next (oei)) |
|
148 { |
|
149 cout << actuallayer->id (actuallayer-> |
|
150 source (oei)) << " " << actuallayer-> |
|
151 id (actuallayer->target (oei)) << endl; |
|
152 edgenumber++; |
|
153 } |
|
154 //cout << "Number of in+out-edges: " << edgenumber << endl; |
|
155 assignments = new actedgesubnodestruct[edgenumber]; |
|
156 for (int i = 0; i < edgenumber; i++) |
|
157 { |
|
158 assignments[i].actedge = INVALID; |
|
159 assignments[i].subnode = INVALID; |
|
160 } |
|
161 } |
|
162 else |
|
163 { |
|
164 cerr << "There is no actual layer defined yet!" << endl; |
|
165 return -1; |
|
166 } |
|
167 |
|
168 return 0; |
|
169 } |
|
170 |
|
171 SubNetwork ():edgenumber (0), connectable (false), actuallayer (NULL), |
|
172 actuallayernode (NULL), subnetwork (NULL), |
|
173 assignments (NULL) |
|
174 { |
|
175 } |
|
176 |
|
177 }; |
|
178 |
|
179 typename Gact::template NodeMap < SubNetwork > subnetworks; |
|
180 |
|
181 |
|
182 /// Defalult constructor. |
|
183 /// We don't need any extra lines, because the actuallayer |
|
184 /// variable has run its constructor, when we have created this class |
|
185 /// So only the two maps has to be initialised here. |
|
186 HierarchyGraph ():subnetworks (actuallayer) |
|
187 { |
|
188 } |
|
189 |
|
190 |
|
191 ///Copy consructor. |
|
192 HierarchyGraph (const HierarchyGraph < Gact, Gsub > &HG):actuallayer (HG.actuallayer), |
|
193 subnetworks |
|
194 (actuallayer) |
|
195 { |
|
196 } |
|
197 |
|
198 |
|
199 /// The base type of the node iterators. |
|
200 |
|
201 /// This is the base type of each node iterators, |
|
202 /// thus each kind of node iterator will convert to this. |
|
203 /// The Node type of the HierarchyGraph is the Node type of the actual layer. |
|
204 typedef typename Gact::Node Node; |
|
205 |
|
206 |
|
207 /// This iterator goes through each node. |
|
208 |
|
209 /// Its usage is quite simple, for example you can count the number |
|
210 /// of nodes in graph \c G of type \c Graph like this: |
|
211 /// \code |
|
212 ///int count=0; |
|
213 ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; |
|
214 /// \endcode |
|
215 /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer. |
|
216 typedef typename Gact::NodeIt NodeIt; |
|
217 |
|
218 |
|
219 /// The base type of the edge iterators. |
|
220 /// The Edge type of the HierarchyGraph is the Edge type of the actual layer. |
|
221 typedef typename Gact::Edge Edge; |
|
222 |
|
223 |
|
224 /// This iterator goes trough the outgoing edges of a node. |
|
225 |
|
226 /// This iterator goes trough the \e outgoing edges of a certain node |
|
227 /// of a graph. |
|
228 /// Its usage is quite simple, for example you can count the number |
|
229 /// of outgoing edges of a node \c n |
|
230 /// in graph \c G of type \c Graph as follows. |
|
231 /// \code |
|
232 ///int count=0; |
|
233 ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
234 /// \endcode |
|
235 /// The OutEdgeIt type of the HierarchyGraph is the OutEdgeIt type of the actual layer. |
|
236 typedef typename Gact::OutEdgeIt OutEdgeIt; |
|
237 |
|
238 |
|
239 /// This iterator goes trough the incoming edges of a node. |
|
240 |
|
241 /// This iterator goes trough the \e incoming edges of a certain node |
|
242 /// of a graph. |
|
243 /// Its usage is quite simple, for example you can count the number |
|
244 /// of outgoing edges of a node \c n |
|
245 /// in graph \c G of type \c Graph as follows. |
|
246 /// \code |
|
247 ///int count=0; |
|
248 ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
249 /// \endcode |
|
250 /// The InEdgeIt type of the HierarchyGraph is the InEdgeIt type of the actual layer. |
|
251 typedef typename Gact::InEdgeIt InEdgeIt; |
|
252 |
|
253 |
|
254 /// This iterator goes through each edge. |
|
255 |
|
256 /// This iterator goes through each edge of a graph. |
|
257 /// Its usage is quite simple, for example you can count the number |
|
258 /// of edges in a graph \c G of type \c Graph as follows: |
|
259 /// \code |
|
260 ///int count=0; |
|
261 ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; |
|
262 /// \endcode |
|
263 /// The EdgeIt type of the HierarchyGraph is the EdgeIt type of the actual layer. |
|
264 typedef typename Gact::EdgeIt EdgeIt; |
|
265 |
|
266 |
|
267 /// First node of the graph. |
|
268 |
|
269 /// \retval i the first node. |
|
270 /// \return the first node. |
|
271 typename Gact::NodeIt & first (typename Gact::NodeIt & i) const |
|
272 { |
|
273 return actuallayer.first (i); |
|
274 } |
|
275 |
|
276 |
|
277 /// The first incoming edge. |
|
278 typename Gact::InEdgeIt & first (typename Gact::InEdgeIt & i, |
|
279 typename Gact::Node) const |
|
280 { |
|
281 return actuallayer.first (i); |
|
282 } |
|
283 |
|
284 |
|
285 /// The first outgoing edge. |
|
286 typename Gact::OutEdgeIt & first (typename Gact::OutEdgeIt & i, |
|
287 typename Gact::Node) const |
|
288 { |
|
289 return actuallayer.first (i); |
|
290 } |
|
291 |
|
292 |
|
293 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} |
|
294 /// The first edge of the Graph. |
|
295 typename Gact::EdgeIt & first (typename Gact::EdgeIt & i) const |
|
296 { |
|
297 return actuallayer.first (i); |
|
298 } |
|
299 |
|
300 |
|
301 // Node getNext(Node) const {} |
|
302 // InEdgeIt getNext(InEdgeIt) const {} |
|
303 // OutEdgeIt getNext(OutEdgeIt) const {} |
|
304 // //SymEdgeIt getNext(SymEdgeIt) const {} |
|
305 // EdgeIt getNext(EdgeIt) const {} |
|
306 |
|
307 |
|
308 /// Go to the next node. |
|
309 typename Gact::NodeIt & next (typename Gact::NodeIt & i) const |
|
310 { |
|
311 return actuallayer.next (i); |
|
312 } |
|
313 /// Go to the next incoming edge. |
|
314 typename Gact::InEdgeIt & next (typename Gact::InEdgeIt & i) const |
|
315 { |
|
316 return actuallayer.next (i); |
|
317 } |
|
318 /// Go to the next outgoing edge. |
|
319 typename Gact::OutEdgeIt & next (typename Gact::OutEdgeIt & i) const |
|
320 { |
|
321 return actuallayer.next (i); |
|
322 } |
|
323 //SymEdgeIt &next(SymEdgeIt &) const {} |
|
324 /// Go to the next edge. |
|
325 typename Gact::EdgeIt & next (typename Gact::EdgeIt & i) const |
|
326 { |
|
327 return actuallayer.next (i); |
|
328 } |
|
329 |
|
330 ///Gives back the target node of an edge. |
|
331 typename Gact::Node target (typename Gact::Edge edge) const |
|
332 { |
|
333 return actuallayer.target (edge); |
|
334 } |
|
335 ///Gives back the source node of an edge. |
|
336 typename Gact::Node source (typename Gact::Edge edge) const |
|
337 { |
|
338 return actuallayer.source (edge); |
|
339 } |
|
340 |
|
341 // Node aNode(InEdgeIt) const {} |
|
342 // Node aNode(OutEdgeIt) const {} |
|
343 // Node aNode(SymEdgeIt) const {} |
|
344 |
|
345 // Node bNode(InEdgeIt) const {} |
|
346 // Node bNode(OutEdgeIt) const {} |
|
347 // Node bNode(SymEdgeIt) const {} |
|
348 |
|
349 /// Checks if a node iterator is valid |
|
350 |
|
351 ///\todo Maybe, it would be better if iterator converted to |
|
352 ///bool directly, as Jacint prefers. |
|
353 bool valid (const typename Gact::Node & node) const |
|
354 { |
|
355 return actuallayer.valid (node); |
|
356 } |
|
357 /// Checks if an edge iterator is valid |
|
358 |
|
359 ///\todo Maybe, it would be better if iterator converted to |
|
360 ///bool directly, as Jacint prefers. |
|
361 bool valid (const typename Gact::Edge & edge) const |
|
362 { |
|
363 return actuallayer.valid (edge); |
|
364 } |
|
365 |
|
366 ///Gives back the \e id of a node. |
|
367 |
|
368 ///\warning Not all graph structures provide this feature. |
|
369 /// |
|
370 int id (const typename Gact::Node & node) const |
|
371 { |
|
372 return actuallayer.id (node); |
|
373 } |
|
374 ///Gives back the \e id of an edge. |
|
375 |
|
376 ///\warning Not all graph structures provide this feature. |
|
377 /// |
|
378 int id (const typename Gact::Edge & edge) const |
|
379 { |
|
380 return actuallayer.id (edge); |
|
381 } |
|
382 |
|
383 //void setInvalid(Node &) const {}; |
|
384 //void setInvalid(Edge &) const {}; |
|
385 |
|
386 ///Add a new node to the graph. |
|
387 |
|
388 /// \return the new node. |
|
389 /// |
|
390 typename Gact::Node addNode () |
|
391 { |
|
392 return actuallayer.addNode (); |
|
393 } |
|
394 ///Add a new edge to the graph. |
|
395 |
|
396 ///Add a new edge to the graph with source node \c source |
|
397 ///and target node \c target. |
|
398 ///\return the new edge. |
|
399 typename Gact::Edge addEdge (typename Gact::Node node1, |
|
400 typename Gact::Node node2) |
|
401 { |
|
402 return actuallayer.addEdge (node1, node2); |
|
403 } |
|
404 |
|
405 /// Resets the graph. |
|
406 |
|
407 /// This function deletes all edges and nodes of the graph. |
|
408 /// It also frees the memory allocated to store them. |
|
409 void clear () |
|
410 { |
|
411 actuallayer.clear (); |
|
412 } |
|
413 |
|
414 int nodeNum () const |
|
415 { |
|
416 return actuallayer.nodeNum (); |
|
417 } |
|
418 int edgeNum () const |
|
419 { |
|
420 return actuallayer.edgeNum (); |
|
421 } |
|
422 |
|
423 ///Read/write/reference map of the nodes to type \c T. |
|
424 |
|
425 ///Read/write/reference map of the nodes to type \c T. |
|
426 /// \sa MemoryMap |
|
427 /// \todo We may need copy constructor |
|
428 /// \todo We may need conversion from other nodetype |
|
429 /// \todo We may need operator= |
|
430 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
431 /// needs extra attention! |
|
432 |
|
433 template < class T > class NodeMap |
|
434 { |
|
435 public: |
|
436 typedef T Value; |
|
437 typedef Node Key; |
|
438 |
|
439 NodeMap (const HierarchyGraph &) |
|
440 { |
|
441 } |
|
442 NodeMap (const HierarchyGraph &, T) |
|
443 { |
|
444 } |
|
445 |
|
446 template < typename TT > NodeMap (const NodeMap < TT > &) |
|
447 { |
|
448 } |
|
449 |
|
450 /// Sets the value of a node. |
|
451 |
|
452 /// Sets the value associated with node \c i to the value \c t. |
|
453 /// |
|
454 void set (Node, T) |
|
455 { |
|
456 } |
|
457 // Gets the value of a node. |
|
458 //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary? |
|
459 T & operator[](Node) |
|
460 { |
|
461 return *(T *) 0; |
|
462 } |
|
463 const T & operator[] (Node) const |
|
464 { |
|
465 return *(T *) 0; |
|
466 } |
|
467 |
|
468 /// Updates the map if the graph has been changed |
|
469 |
|
470 /// \todo Do we need this? |
|
471 /// |
|
472 void update () |
|
473 { |
|
474 } |
|
475 void update (T a) |
|
476 { |
|
477 } //FIXME: Is it necessary |
|
478 }; |
|
479 |
|
480 ///Read/write/reference map of the edges to type \c T. |
|
481 |
|
482 ///Read/write/reference map of the edges to type \c T. |
|
483 ///It behaves exactly in the same way as \ref NodeMap. |
|
484 /// \sa NodeMap |
|
485 /// \sa MemoryMap |
|
486 /// \todo We may need copy constructor |
|
487 /// \todo We may need conversion from other edgetype |
|
488 /// \todo We may need operator= |
|
489 template < class T > class EdgeMap |
|
490 { |
|
491 public: |
|
492 typedef T Value; |
|
493 typedef Edge Key; |
|
494 |
|
495 EdgeMap (const HierarchyGraph &) |
|
496 { |
|
497 } |
|
498 EdgeMap (const HierarchyGraph &, T) |
|
499 { |
|
500 } |
|
501 |
|
502 ///\todo It can copy between different types. |
|
503 /// |
|
504 template < typename TT > EdgeMap (const EdgeMap < TT > &) |
|
505 { |
|
506 } |
|
507 |
|
508 void set (Edge, T) |
|
509 { |
|
510 } |
|
511 //T get(Edge) const {return *(T*)0;} |
|
512 T & operator[](Edge) |
|
513 { |
|
514 return *(T *) 0; |
|
515 } |
|
516 const T & operator[] (Edge) const |
|
517 { |
|
518 return *(T *) 0; |
|
519 } |
|
520 |
|
521 void update () |
|
522 { |
|
523 } |
|
524 void update (T a) |
|
525 { |
|
526 } //FIXME: Is it necessary |
|
527 }; |
|
528 }; |
|
529 |
|
530 /// An empty erasable graph class. |
|
531 |
|
532 /// This class provides all the common features of an \e erasable graph |
|
533 /// structure, |
|
534 /// however completely without implementations and real data structures |
|
535 /// behind the interface. |
|
536 /// All graph algorithms should compile with this class, but it will not |
|
537 /// run properly, of course. |
|
538 /// |
|
539 /// \todo This blabla could be replaced by a sepatate description about |
|
540 /// s. |
|
541 /// |
|
542 /// It can be used for checking the interface compatibility, |
|
543 /// or it can serve as a skeleton of a new graph structure. |
|
544 /// |
|
545 /// Also, you will find here the full documentation of a certain graph |
|
546 /// feature, the documentation of a real graph imlementation |
|
547 /// like @ref ListGraph or |
|
548 /// @ref SmartGraph will just refer to this structure. |
|
549 template < typename Gact, typename Gsub > class ErasableHierarchyGraph:public HierarchyGraph < Gact, |
|
550 Gsub |
|
551 > |
|
552 { |
|
553 public: |
|
554 /// Deletes a node. |
|
555 void erase (typename Gact::Node n) |
|
556 { |
|
557 actuallayer.erase (n); |
|
558 } |
|
559 /// Deletes an edge. |
|
560 void erase (typename Gact::Edge e) |
|
561 { |
|
562 actuallayer.erase (e); |
|
563 } |
|
564 |
|
565 /// Defalult constructor. |
|
566 ErasableHierarchyGraph () |
|
567 { |
|
568 } |
|
569 ///Copy consructor. |
|
570 ErasableHierarchyGraph (const HierarchyGraph < Gact, Gsub > &EPG) |
|
571 { |
|
572 } |
|
573 }; |
|
574 |
|
575 |
|
576 // @} |
|
577 |
|
578 } //namespace lemon |
|
579 |
|
580 |
|
581 #endif // LEMON_SKELETON_GRAPH_H |
|