25 #include <lemon/bits/alteration_notifier.h> |
25 #include <lemon/bits/alteration_notifier.h> |
26 #include <lemon/bits/default_map.h> |
26 #include <lemon/bits/default_map.h> |
27 |
27 |
28 #include <lemon/bits/undir_graph_extender.h> |
28 #include <lemon/bits/undir_graph_extender.h> |
29 |
29 |
|
30 #include <lemon/xy.h> |
|
31 |
|
32 ///\ingroup graphs |
|
33 ///\file |
|
34 ///\brief GridGraph class. |
|
35 |
30 namespace lemon { |
36 namespace lemon { |
31 |
37 |
|
38 /// \brief Base graph for GridGraph. |
|
39 /// |
|
40 /// Base graph for grid graph. It describes some member functions |
|
41 /// which can be used in the GridGraph. |
|
42 /// |
|
43 /// \warning Always use the GridGraph instead of this. |
|
44 /// \see GridGraph |
32 class GridGraphBase { |
45 class GridGraphBase { |
33 |
46 |
34 public: |
47 public: |
35 |
48 |
36 typedef GridGraphBase Graph; |
49 typedef GridGraphBase Graph; |
354 /// |
367 /// |
355 /// The graph type is fully conform to the \ref concept::UndirGraph |
368 /// The graph type is fully conform to the \ref concept::UndirGraph |
356 /// "Undirected Graph" concept. |
369 /// "Undirected Graph" concept. |
357 /// |
370 /// |
358 /// \author Balazs Dezso |
371 /// \author Balazs Dezso |
|
372 /// \see GridGraphBase |
359 class GridGraph : public ExtendedGridGraphBase { |
373 class GridGraph : public ExtendedGridGraphBase { |
360 public: |
374 public: |
361 |
375 |
|
376 /// \brief Map to get the indices of the nodes as xy<int>. |
|
377 /// |
|
378 /// Map to get the indices of the nodes as xy<int>. |
|
379 class IndexMap { |
|
380 public: |
|
381 typedef True NeedCopy; |
|
382 /// \brief The key type of the map |
|
383 typedef GridGraph::Node Key; |
|
384 /// \brief The value type of the map |
|
385 typedef xy<int> Value; |
|
386 |
|
387 /// \brief Constructor |
|
388 /// |
|
389 /// Constructor |
|
390 IndexMap(const GridGraph& _graph) : graph(_graph) {} |
|
391 |
|
392 /// \brief The subscript operator |
|
393 /// |
|
394 /// The subscript operator. |
|
395 Value operator[](Key key) const { |
|
396 return xy<int>(graph.row(key), graph.col(key)); |
|
397 } |
|
398 |
|
399 private: |
|
400 const GridGraph& graph; |
|
401 }; |
|
402 |
|
403 /// \brief Map to get the row of the nodes. |
|
404 /// |
|
405 /// Map to get the row of the nodes. |
|
406 class RowMap { |
|
407 public: |
|
408 typedef True NeedCopy; |
|
409 /// \brief The key type of the map |
|
410 typedef GridGraph::Node Key; |
|
411 /// \brief The value type of the map |
|
412 typedef int Value; |
|
413 |
|
414 /// \brief Constructor |
|
415 /// |
|
416 /// Constructor |
|
417 RowMap(const GridGraph& _graph) : graph(_graph) {} |
|
418 |
|
419 /// \brief The subscript operator |
|
420 /// |
|
421 /// The subscript operator. |
|
422 Value operator[](Key key) const { |
|
423 return graph.row(key); |
|
424 } |
|
425 |
|
426 private: |
|
427 const GridGraph& graph; |
|
428 }; |
|
429 |
|
430 /// \brief Map to get the column of the nodes. |
|
431 /// |
|
432 /// Map to get the column of the nodes. |
|
433 class ColMap { |
|
434 public: |
|
435 typedef True NeedCopy; |
|
436 /// \brief The key type of the map |
|
437 typedef GridGraph::Node Key; |
|
438 /// \brief The value type of the map |
|
439 typedef int Value; |
|
440 |
|
441 /// \brief Constructor |
|
442 /// |
|
443 /// Constructor |
|
444 ColMap(const GridGraph& _graph) : graph(_graph) {} |
|
445 |
|
446 /// \brief The subscript operator |
|
447 /// |
|
448 /// The subscript operator. |
|
449 Value operator[](Key key) const { |
|
450 return graph.col(key); |
|
451 } |
|
452 |
|
453 private: |
|
454 const GridGraph& graph; |
|
455 }; |
|
456 |
362 GridGraph(int n, int m) { construct(n, m); } |
457 GridGraph(int n, int m) { construct(n, m); } |
363 |
458 |
364 /// \brief Gives back the edge goes down from the node. |
459 /// \brief Gives back the edge goes down from the node. |
365 /// |
460 /// |
366 /// Gives back the edge goes down from the node. If there is not |
461 /// Gives back the edge goes down from the node. If there is not |
396 UndirEdge ue = _left(n); |
491 UndirEdge ue = _left(n); |
397 return ue != INVALID ? direct(ue, false) : INVALID; |
492 return ue != INVALID ? direct(ue, false) : INVALID; |
398 } |
493 } |
399 |
494 |
400 }; |
495 }; |
|
496 |
|
497 /// \brief Index map of the grid graph |
|
498 /// |
|
499 /// Just returns an IndexMap for the grid graph. |
|
500 GridGraph::IndexMap indexMap(const GridGraph& graph) { |
|
501 return GridGraph::IndexMap(graph); |
|
502 } |
|
503 |
|
504 /// \brief Row map of the grid graph |
|
505 /// |
|
506 /// Just returns an RowMap for the grid graph. |
|
507 GridGraph::RowMap rowMap(const GridGraph& graph) { |
|
508 return GridGraph::RowMap(graph); |
|
509 } |
|
510 |
|
511 /// \brief Coloumn map of the grid graph |
|
512 /// |
|
513 /// Just returns an ColMap for the grid graph. |
|
514 GridGraph::ColMap colMap(const GridGraph& graph) { |
|
515 return GridGraph::ColMap(graph); |
|
516 } |
401 } |
517 } |
402 #endif |
518 #endif |