1.1 --- a/src/lemon/concept/undir_graph.h Fri Dec 03 12:19:26 2004 +0000
1.2 +++ b/src/lemon/concept/undir_graph.h Mon Dec 06 00:30:44 2004 +0000
1.3 @@ -17,7 +17,7 @@
1.4 *
1.5 */
1.6
1.7 -///\ingroup concept
1.8 +///\ingroup graph_concepts
1.9 ///\file
1.10 ///\brief Undirected graphs and components of.
1.11
1.12 @@ -30,7 +30,62 @@
1.13 namespace lemon {
1.14 namespace concept {
1.15
1.16 - /// \todo to be done
1.17 + /// \addtogroup graph_concepts
1.18 + /// @{
1.19 +
1.20 +
1.21 + /// Skeleton class which describes an edge with direction in \ref
1.22 + /// UndirGraph "undirected graph".
1.23 + template <typename UndirEdge>
1.24 + class UndirGraphEdge : public UndirEdge {
1.25 + public:
1.26 +
1.27 + /// \e
1.28 + UndirGraphEdge() {}
1.29 +
1.30 + /// \e
1.31 + UndirGraphEdge(const UndirGraphEdge&) {}
1.32 +
1.33 + /// \e
1.34 + UndirGraphEdge(Invalid) {}
1.35 +
1.36 + /// \brief Constructs a directed version of an undirected edge
1.37 + ///
1.38 + /// \param forward If \c true the direction of the contructed edge
1.39 + /// is the same as the inherent direction of the \c undir_edge; if
1.40 + /// \c false --- the opposite.
1.41 + UndirGraphEdge(UndirEdge undir_edge, bool forward) {
1.42 + ignore_unused_variable_warning(undir_edge);
1.43 + ignore_unused_variable_warning(forward);
1.44 + }
1.45 +
1.46 + /// \e
1.47 + UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
1.48 +
1.49 + /// \e
1.50 + bool operator==(UndirGraphEdge) const { return true; }
1.51 + /// \e
1.52 + bool operator!=(UndirGraphEdge) const { return false; }
1.53 +
1.54 + /// \e
1.55 + bool operator<(UndirGraphEdge) const { return false; }
1.56 +
1.57 + template <typename Edge>
1.58 + struct Constraints {
1.59 + void constraints() {
1.60 + /// \bug This should be is_base_and_derived ...
1.61 + UndirEdge ue = e;
1.62 + ue = e;
1.63 + Edge forward(ue, true);
1.64 + Edge backward(ue, false);
1.65 +
1.66 + ignore_unused_variable_warning(forward);
1.67 + ignore_unused_variable_warning(backward);
1.68 + }
1.69 + Edge e;
1.70 + };
1.71 + };
1.72 +
1.73
1.74 struct BaseIterableUndirGraphConcept {
1.75
1.76 @@ -43,21 +98,29 @@
1.77
1.78 void constraints() {
1.79 checkConcept<BaseIterableGraphComponent, Graph>();
1.80 - checkConcept<GraphItem<'u'>, UndirEdge >();
1.81 + checkConcept<GraphItem<>, UndirEdge>();
1.82 + checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
1.83
1.84 - /// \bug this should be base_and_derived:
1.85 - UndirEdge ue = e;
1.86 - ue = e;
1.87 + graph.first(ue);
1.88 + graph.next(ue);
1.89
1.90 + const_constraints();
1.91 + }
1.92 + void const_constraints() {
1.93 Node n;
1.94 n = graph.target(ue);
1.95 n = graph.source(ue);
1.96 + n = graph.oppositeNode(n0, ue);
1.97
1.98 - graph.first(ue);
1.99 - graph.next(ue);
1.100 + bool b;
1.101 + b = graph.forward(e);
1.102 + ignore_unused_variable_warning(b);
1.103 }
1.104 - const Graph &graph;
1.105 +
1.106 + Graph graph;
1.107 Edge e;
1.108 + Node n0;
1.109 + UndirEdge ue;
1.110 };
1.111
1.112 };
1.113 @@ -76,10 +139,10 @@
1.114
1.115 typedef typename Graph::UndirEdge UndirEdge;
1.116 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
1.117 - typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
1.118 + typedef typename Graph::IncEdgeIt IncEdgeIt;
1.119
1.120 checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
1.121 - checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();
1.122 + checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
1.123 }
1.124 };
1.125
1.126 @@ -145,9 +208,228 @@
1.127
1.128 };
1.129
1.130 + /// Class describing the concept of Undirected Graphs.
1.131 +
1.132 + /// This class describes the common interface of all Undirected
1.133 + /// Graphs.
1.134 + ///
1.135 + /// As all concept describing classes it provides only interface
1.136 + /// without any sensible implementation. So any algorithm for
1.137 + /// undirected graph should compile with this class, but it will not
1.138 + /// run properly, of couse.
1.139 + ///
1.140 + /// In LEMON undirected graphs also fulfill the concept of directed
1.141 + /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
1.142 + /// explanation of this and more see also the page \ref undir_graphs,
1.143 + /// a tutorial about undirected graphs.
1.144 +
1.145 class UndirGraph {
1.146 public:
1.147
1.148 + /// Type describing a node in the graph
1.149 + typedef GraphNode Node;
1.150 +
1.151 + /// Type describing an undirected edge
1.152 + typedef GraphItem<'u'> UndirEdge;
1.153 +
1.154 + /// Type describing an UndirEdge with direction
1.155 +#ifndef DOXYGEN
1.156 + typedef UndirGraphEdge<UndirEdge> Edge;
1.157 +#else
1.158 + typedef UndirGraphEdge Edge;
1.159 +#endif
1.160 +
1.161 + /// Iterator type which iterates over all nodes
1.162 +#ifndef DOXYGEN
1.163 + typedef GraphIterator<UndirGraph, Node> NodeIt;
1.164 +#else
1.165 + typedef GraphIterator NodeIt;
1.166 +#endif
1.167 +
1.168 + /// Iterator type which iterates over all undirected edges
1.169 +#ifndef DOXYGEN
1.170 + typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
1.171 +#else
1.172 + typedef GraphIterator UndirEdgeIt;
1.173 +#endif
1.174 +
1.175 + /// Iterator type which iterates over all directed edges.
1.176 +
1.177 + /// Iterator type which iterates over all edges (each undirected
1.178 + /// edge occurs twice with both directions.
1.179 +#ifndef DOXYGEN
1.180 + typedef GraphIterator<UndirGraph, Edge> EdgeIt;
1.181 +#else
1.182 + typedef GraphIterator EdgeIt;
1.183 +#endif
1.184 +
1.185 +
1.186 + /// Iterator of undirected edges incident to a node
1.187 +#ifndef DOXYGEN
1.188 + typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
1.189 +#else
1.190 + typedef GraphIncIterator IncEdgeIt;
1.191 +#endif
1.192 +
1.193 + /// Iterator of edges incoming to a node
1.194 +#ifndef DOXYGEN
1.195 + typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
1.196 +#else
1.197 + typedef GraphIncIterator InEdgeIt;
1.198 +#endif
1.199 +
1.200 + /// Iterator of edges outgoing from a node
1.201 +#ifndef DOXYGEN
1.202 + typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
1.203 +#else
1.204 + typedef GraphIncIterator OutEdgeIt;
1.205 +#endif
1.206 +
1.207 + /// NodeMap template
1.208 +#ifdef DOXYGEN
1.209 + typedef GraphMap NodeMap<T>;
1.210 +#endif
1.211 +
1.212 + /// UndirEdgeMap template
1.213 +#ifdef DOXYGEN
1.214 + typedef GraphMap UndirEdgeMap<T>;
1.215 +#endif
1.216 +
1.217 + /// EdgeMap template
1.218 +#ifdef DOXYGEN
1.219 + typedef GraphMap EdgeMap<T>;
1.220 +#endif
1.221 +
1.222 + template <typename T>
1.223 + class NodeMap : public GraphMap<UndirGraph, Node, T> {
1.224 + typedef GraphMap<UndirGraph, Node, T> Parent;
1.225 + public:
1.226 +
1.227 + explicit NodeMap(const UndirGraph &g) : Parent(g) {}
1.228 + NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.229 + };
1.230 +
1.231 + template <typename T>
1.232 + class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
1.233 + typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
1.234 + public:
1.235 +
1.236 + explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
1.237 + UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.238 + };
1.239 +
1.240 + template <typename T>
1.241 + class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
1.242 + typedef GraphMap<UndirGraph, Edge, T> Parent;
1.243 + public:
1.244 +
1.245 + explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
1.246 + EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.247 + };
1.248 +
1.249 + /// Is the Edge oriented "forward"?
1.250 +
1.251 + /// Returns whether the given directed edge is same orientation as
1.252 + /// the corresponding undirected edge.
1.253 + ///
1.254 + /// \todo "What does the direction of an undirected edge mean?"
1.255 + bool forward(Edge) const { return true; }
1.256 +
1.257 + /// Opposite node on an edge
1.258 +
1.259 + /// \return the opposite of the given Node on the given Edge
1.260 + ///
1.261 + /// \todo What should we do if given Node and Edge are not incident?
1.262 + Node oppositeNode(Node, UndirEdge) const { return INVALID; }
1.263 +
1.264 + /// First node of the undirected edge.
1.265 +
1.266 + /// \return the first node of the given UndirEdge.
1.267 + ///
1.268 + /// Naturally undirectected edges don't have direction and thus
1.269 + /// don't have source and target node. But we use these two methods
1.270 + /// to query the two endnodes of the edge. The direction of the edge
1.271 + /// which arises this way is called the inherent direction of the
1.272 + /// undirected edge, and is used to define the "forward" direction
1.273 + /// of the directed versions of the edges.
1.274 + /// \sa forward
1.275 + Node source(UndirEdge) const { return INVALID; }
1.276 +
1.277 + /// Second node of the undirected edge.
1.278 + Node target(UndirEdge) const { return INVALID; }
1.279 +
1.280 + /// Source node of the directed edge.
1.281 + Node source(Edge) const { return INVALID; }
1.282 +
1.283 + /// Target node of the directed edge.
1.284 + Node target(Edge) const { return INVALID; }
1.285 +
1.286 + /// First node of the graph
1.287 +
1.288 + /// \note This method is part of so called \ref
1.289 + /// developpers_interface "Developpers' interface", so it shouldn't
1.290 + /// be used in an end-user program.
1.291 + void first(Node&) const {}
1.292 + /// Next node of the graph
1.293 +
1.294 + /// \note This method is part of so called \ref
1.295 + /// developpers_interface "Developpers' interface", so it shouldn't
1.296 + /// be used in an end-user program.
1.297 + void next(Node&) const {}
1.298 +
1.299 + /// First undirected edge of the graph
1.300 +
1.301 + /// \note This method is part of so called \ref
1.302 + /// developpers_interface "Developpers' interface", so it shouldn't
1.303 + /// be used in an end-user program.
1.304 + void first(UndirEdge&) const {}
1.305 + /// Next undirected edge of the graph
1.306 +
1.307 + /// \note This method is part of so called \ref
1.308 + /// developpers_interface "Developpers' interface", so it shouldn't
1.309 + /// be used in an end-user program.
1.310 + void next(UndirEdge&) const {}
1.311 +
1.312 + /// First directed edge of the graph
1.313 +
1.314 + /// \note This method is part of so called \ref
1.315 + /// developpers_interface "Developpers' interface", so it shouldn't
1.316 + /// be used in an end-user program.
1.317 + void first(Edge&) const {}
1.318 + /// Next directed edge of the graph
1.319 +
1.320 + /// \note This method is part of so called \ref
1.321 + /// developpers_interface "Developpers' interface", so it shouldn't
1.322 + /// be used in an end-user program.
1.323 + void next(Edge&) const {}
1.324 +
1.325 + /// First outgoing edge from a given node
1.326 +
1.327 + /// \note This method is part of so called \ref
1.328 + /// developpers_interface "Developpers' interface", so it shouldn't
1.329 + /// be used in an end-user program.
1.330 + void firstOut(Edge&, Node) const {}
1.331 + /// Next outgoing edge to a node
1.332 +
1.333 + /// \note This method is part of so called \ref
1.334 + /// developpers_interface "Developpers' interface", so it shouldn't
1.335 + /// be used in an end-user program.
1.336 + void nextOut(Edge&) const {}
1.337 +
1.338 + /// First incoming edge to a given node
1.339 +
1.340 + /// \note This method is part of so called \ref
1.341 + /// developpers_interface "Developpers' interface", so it shouldn't
1.342 + /// be used in an end-user program.
1.343 + void firstIn(Edge&, Node) const {}
1.344 + /// Next incoming edge to a node
1.345 +
1.346 + /// \note This method is part of so called \ref
1.347 + /// developpers_interface "Developpers' interface", so it shouldn't
1.348 + /// be used in an end-user program.
1.349 + void nextIn(Edge&) const {}
1.350 +
1.351 +
1.352 template <typename Graph>
1.353 struct Constraints {
1.354 void constraints() {
1.355 @@ -190,6 +472,8 @@
1.356
1.357 };
1.358
1.359 + /// @}
1.360 +
1.361 }
1.362
1.363 }