33 |
33 |
34 /// \addtogroup graph_concepts |
34 /// \addtogroup graph_concepts |
35 /// @{ |
35 /// @{ |
36 |
36 |
37 |
37 |
38 /// Class describing the concept of Undirected Graphs. |
38 /// \brief Class describing the concept of Undirected Graphs. |
39 |
39 /// |
40 /// This class describes the common interface of all Undirected |
40 /// This class describes the common interface of all Undirected |
41 /// Graphs. |
41 /// Graphs. |
42 /// |
42 /// |
43 /// As all concept describing classes it provides only interface |
43 /// As all concept describing classes it provides only interface |
44 /// without any sensible implementation. So any algorithm for |
44 /// without any sensible implementation. So any algorithm for |
45 /// undirected graph should compile with this class, but it will not |
45 /// undirected graph should compile with this class, but it will not |
46 /// run properly, of couse. |
46 /// run properly, of course. |
47 /// |
47 /// |
48 /// In LEMON undirected graphs also fulfill the concept of directed |
48 /// The LEMON undirected graphs also fulfill the concept of |
49 /// graphs (\ref lemon::concept::Graph "Graph Concept"). For |
49 /// directed graphs (\ref lemon::concept::Graph "Graph |
50 /// explanation of this and more see also the page \ref graphs, |
50 /// Concept"). Each undirected edges can be seen as two opposite |
51 /// a tutorial about graphs. |
51 /// directed edge and consequently the undirected graph can be |
|
52 /// seen as the direceted graph of these directed edges. The |
|
53 /// UGraph has the UEdge inner class for the undirected edges and |
|
54 /// the Edge type for the directed edges. The Edge type is |
|
55 /// convertible to UEdge or inherited from it so from a directed |
|
56 /// edge we can get the represented undirected edge. |
52 /// |
57 /// |
53 /// You can assume that all undirected graph can be handled |
58 /// In the sense of the LEMON each undirected edge has a default |
54 /// as a directed graph. This way it is fully conform |
59 /// direction (it should be in every computer implementation, |
55 /// to the Graph concept. |
60 /// because the order of undirected edge's nodes defines an |
56 |
61 /// orientation). With the default orientation we can define that |
|
62 /// the directed edge is forward or backward directed. With the \c |
|
63 /// direction() and \c direct() function we can get the direction |
|
64 /// of the directed edge and we can direct an undirected edge. |
|
65 /// |
|
66 /// The UEdgeIt is an iterator for the undirected edges. We can use |
|
67 /// the UEdgeMap to map values for the undirected edges. The InEdgeIt and |
|
68 /// OutEdgeIt iterates on the same undirected edges but with opposite |
|
69 /// direction. The IncEdgeIt iterates also on the same undirected edges |
|
70 /// as the OutEdgeIt and InEdgeIt but it is not convertible to Edge just |
|
71 /// to UEdge. |
57 class UGraph { |
72 class UGraph { |
58 public: |
73 public: |
59 ///\e |
74 /// \brief The undirected graph should be tagged by the |
60 |
75 /// UndirectedTag. |
61 ///\todo undocumented |
76 /// |
62 /// |
77 /// The undirected graph should be tagged by the UndirectedTag. This |
|
78 /// tag helps the enable_if technics to make compile time |
|
79 /// specializations for undirected graphs. |
63 typedef True UndirectedTag; |
80 typedef True UndirectedTag; |
64 |
81 |
65 /// \brief The base type of node iterators, |
82 /// \brief The base type of node iterators, |
66 /// or in other words, the trivial node iterator. |
83 /// or in other words, the trivial node iterator. |
67 /// |
84 /// |
560 }; |
578 }; |
561 |
579 |
562 /// \brief Direct the given undirected edge. |
580 /// \brief Direct the given undirected edge. |
563 /// |
581 /// |
564 /// Direct the given undirected edge. The returned edge source |
582 /// Direct the given undirected edge. The returned edge source |
565 /// will be the given edge. |
583 /// will be the given node. |
566 Edge direct(const UEdge&, const Node&) const { |
584 Edge direct(const UEdge&, const Node&) const { |
567 return INVALID; |
585 return INVALID; |
568 } |
586 } |
569 |
587 |
570 /// \brief Direct the given undirected edge. |
588 /// \brief Direct the given undirected edge. |
571 /// |
589 /// |
572 /// Direct the given undirected edge. The returned edge source |
590 /// Direct the given undirected edge. The returned edge |
573 /// will be the source of the undirected edge if the given bool |
591 /// represents the given undireted edge and the direction comes |
574 /// is true. |
592 /// from the given bool. The source of the undirected edge and |
|
593 /// the directed edge is the same when the given bool is true. |
575 Edge direct(const UEdge&, bool) const { |
594 Edge direct(const UEdge&, bool) const { |
576 return INVALID; |
595 return INVALID; |
577 } |
596 } |
578 |
597 |
579 /// \brief Returns true if the edge has default orientation. |
598 /// \brief Returns true if the edge has default orientation. |
580 /// |
599 /// |
581 /// Returns whether the given directed edge is same orientation as |
600 /// Returns whether the given directed edge is same orientation as |
582 /// the corresponding undirected edge. |
601 /// the corresponding undirected edge's default orientation. |
583 bool direction(Edge) const { return true; } |
602 bool direction(Edge) const { return true; } |
584 |
603 |
585 /// \brief Returns the opposite directed edge. |
604 /// \brief Returns the opposite directed edge. |
586 /// |
605 /// |
587 /// Returns the opposite directed edge. |
606 /// Returns the opposite directed edge. |
588 Edge oppositeEdge(Edge) const { return INVALID; } |
607 Edge oppositeEdge(Edge) const { return INVALID; } |
589 |
608 |
590 /// \brief Opposite node on an edge |
609 /// \brief Opposite node on an edge |
591 /// |
610 /// |
592 /// \return the opposite of the given Node on the given Edge |
611 /// \return the opposite of the given Node on the given UEdge |
593 Node oppositeNode(Node, UEdge) const { return INVALID; } |
612 Node oppositeNode(Node, UEdge) const { return INVALID; } |
594 |
613 |
595 /// \brief First node of the undirected edge. |
614 /// \brief First node of the undirected edge. |
596 /// |
615 /// |
597 /// \return the first node of the given UEdge. |
616 /// \return the first node of the given UEdge. |
598 /// |
617 /// |
599 /// Naturally uectected edges don't have direction and thus |
618 /// Naturally undirected edges don't have direction and thus |
600 /// don't have source and target node. But we use these two methods |
619 /// don't have source and target node. But we use these two methods |
601 /// to query the two endnodes of the edge. The direction of the edge |
620 /// to query the two nodes of the edge. The direction of the edge |
602 /// which arises this way is called the inherent direction of the |
621 /// which arises this way is called the inherent direction of the |
603 /// undirected edge, and is used to define the "default" direction |
622 /// undirected edge, and is used to define the "default" direction |
604 /// of the directed versions of the edges. |
623 /// of the directed versions of the edges. |
605 /// \sa direction |
624 /// \sa direction |
606 Node source(UEdge) const { return INVALID; } |
625 Node source(UEdge) const { return INVALID; } |