1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concept/undir_graph.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,531 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * lemon/concept/undir_graph_component.h - Part of LEMON, a generic
1.7 + * C++ optimization library
1.8 + *
1.9 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
1.10 + * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
1.11 + * EGRES).
1.12 + *
1.13 + * Permission to use, modify and distribute this software is granted
1.14 + * provided that this copyright notice appears in all copies. For
1.15 + * precise terms see the accompanying LICENSE file.
1.16 + *
1.17 + * This software is provided "AS IS" with no warranty of any kind,
1.18 + * express or implied, and with no claim as to its suitability for any
1.19 + * purpose.
1.20 + *
1.21 + */
1.22 +
1.23 +///\ingroup graph_concepts
1.24 +///\file
1.25 +///\brief Undirected graphs and components of.
1.26 +
1.27 +
1.28 +#ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
1.29 +#define LEMON_CONCEPT_UNDIR_GRAPH_H
1.30 +
1.31 +#include <lemon/concept/graph_component.h>
1.32 +
1.33 +namespace lemon {
1.34 + namespace concept {
1.35 +
1.36 + /// \addtogroup graph_concepts
1.37 + /// @{
1.38 +
1.39 +
1.40 + /// Skeleton class which describes an edge with direction in \ref
1.41 + /// UndirGraph "undirected graph".
1.42 + template <typename UndirGraph>
1.43 + class UndirGraphEdge : public UndirGraph::UndirEdge {
1.44 + typedef typename UndirGraph::UndirEdge UndirEdge;
1.45 + typedef typename UndirGraph::Node Node;
1.46 + public:
1.47 +
1.48 + /// \e
1.49 + UndirGraphEdge() {}
1.50 +
1.51 + /// \e
1.52 + UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {}
1.53 +
1.54 + /// \e
1.55 + UndirGraphEdge(Invalid) {}
1.56 +
1.57 + /// \brief Directed edge from undirected edge and a source node.
1.58 + ///
1.59 + /// Constructs a directed edge from undirected edge and a source node.
1.60 + ///
1.61 + /// \note You have to specify the graph for this constructor.
1.62 + UndirGraphEdge(const UndirGraph &g,
1.63 + UndirEdge undir_edge, Node n) {
1.64 + ignore_unused_variable_warning(undir_edge);
1.65 + ignore_unused_variable_warning(g);
1.66 + ignore_unused_variable_warning(n);
1.67 + }
1.68 +
1.69 + /// \e
1.70 + UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
1.71 +
1.72 + /// \e
1.73 + bool operator==(UndirGraphEdge) const { return true; }
1.74 + /// \e
1.75 + bool operator!=(UndirGraphEdge) const { return false; }
1.76 +
1.77 + /// \e
1.78 + bool operator<(UndirGraphEdge) const { return false; }
1.79 +
1.80 + template <typename Edge>
1.81 + struct Constraints {
1.82 + void constraints() {
1.83 + const_constraints();
1.84 + }
1.85 + void const_constraints() const {
1.86 + /// \bug This should be is_base_and_derived ...
1.87 + UndirEdge ue = e;
1.88 + ue = e;
1.89 +
1.90 + Edge e_with_source(graph,ue,n);
1.91 + ignore_unused_variable_warning(e_with_source);
1.92 + }
1.93 + Edge e;
1.94 + UndirEdge ue;
1.95 + UndirGraph graph;
1.96 + Node n;
1.97 + };
1.98 + };
1.99 +
1.100 +
1.101 + struct BaseIterableUndirGraphConcept {
1.102 +
1.103 + template <typename Graph>
1.104 + struct Constraints {
1.105 +
1.106 + typedef typename Graph::UndirEdge UndirEdge;
1.107 + typedef typename Graph::Edge Edge;
1.108 + typedef typename Graph::Node Node;
1.109 +
1.110 + void constraints() {
1.111 + checkConcept<BaseIterableGraphComponent, Graph>();
1.112 + checkConcept<GraphItem<>, UndirEdge>();
1.113 + checkConcept<UndirGraphEdge<Graph>, Edge>();
1.114 +
1.115 + graph.first(ue);
1.116 + graph.next(ue);
1.117 +
1.118 + const_constraints();
1.119 + }
1.120 + void const_constraints() {
1.121 + Node n;
1.122 + n = graph.target(ue);
1.123 + n = graph.source(ue);
1.124 + n = graph.oppositeNode(n0, ue);
1.125 +
1.126 + bool b;
1.127 + b = graph.forward(e);
1.128 + ignore_unused_variable_warning(b);
1.129 + }
1.130 +
1.131 + Graph graph;
1.132 + Edge e;
1.133 + Node n0;
1.134 + UndirEdge ue;
1.135 + };
1.136 +
1.137 + };
1.138 +
1.139 +
1.140 + struct IterableUndirGraphConcept {
1.141 +
1.142 + template <typename Graph>
1.143 + struct Constraints {
1.144 + void constraints() {
1.145 + /// \todo we don't need the iterable component to be base iterable
1.146 + /// Don't we really???
1.147 + //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
1.148 +
1.149 + checkConcept<IterableGraphComponent, Graph> ();
1.150 +
1.151 + typedef typename Graph::UndirEdge UndirEdge;
1.152 + typedef typename Graph::UndirEdgeIt UndirEdgeIt;
1.153 + typedef typename Graph::IncEdgeIt IncEdgeIt;
1.154 +
1.155 + checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
1.156 + checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
1.157 + }
1.158 + };
1.159 +
1.160 + };
1.161 +
1.162 + struct MappableUndirGraphConcept {
1.163 +
1.164 + template <typename Graph>
1.165 + struct Constraints {
1.166 +
1.167 + struct Dummy {
1.168 + int value;
1.169 + Dummy() : value(0) {}
1.170 + Dummy(int _v) : value(_v) {}
1.171 + };
1.172 +
1.173 + void constraints() {
1.174 + checkConcept<MappableGraphComponent, Graph>();
1.175 +
1.176 + typedef typename Graph::template UndirEdgeMap<int> IntMap;
1.177 + checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
1.178 + IntMap >();
1.179 +
1.180 + typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
1.181 + checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
1.182 + BoolMap >();
1.183 +
1.184 + typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
1.185 + checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
1.186 + DummyMap >();
1.187 + }
1.188 + };
1.189 +
1.190 + };
1.191 +
1.192 + struct ExtendableUndirGraphConcept {
1.193 +
1.194 + template <typename Graph>
1.195 + struct Constraints {
1.196 + void constraints() {
1.197 + node_a = graph.addNode();
1.198 + uedge = graph.addEdge(node_a, node_b);
1.199 + }
1.200 + typename Graph::Node node_a, node_b;
1.201 + typename Graph::UndirEdge uedge;
1.202 + Graph graph;
1.203 + };
1.204 +
1.205 + };
1.206 +
1.207 + struct ErasableUndirGraphConcept {
1.208 +
1.209 + template <typename Graph>
1.210 + struct Constraints {
1.211 + void constraints() {
1.212 + graph.erase(n);
1.213 + graph.erase(e);
1.214 + }
1.215 + Graph graph;
1.216 + typename Graph::Node n;
1.217 + typename Graph::UndirEdge e;
1.218 + };
1.219 +
1.220 + };
1.221 +
1.222 + /// Class describing the concept of Undirected Graphs.
1.223 +
1.224 + /// This class describes the common interface of all Undirected
1.225 + /// Graphs.
1.226 + ///
1.227 + /// As all concept describing classes it provides only interface
1.228 + /// without any sensible implementation. So any algorithm for
1.229 + /// undirected graph should compile with this class, but it will not
1.230 + /// run properly, of couse.
1.231 + ///
1.232 + /// In LEMON undirected graphs also fulfill the concept of directed
1.233 + /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
1.234 + /// explanation of this and more see also the page \ref undir_graphs,
1.235 + /// a tutorial about undirected graphs.
1.236 +
1.237 + class UndirGraph {
1.238 + public:
1.239 +
1.240 + /// Type describing a node in the graph
1.241 + typedef GraphNode Node;
1.242 +
1.243 + /// Type describing an undirected edge
1.244 + typedef GraphItem<'u'> UndirEdge;
1.245 +
1.246 + /// Type describing an UndirEdge with direction
1.247 +#ifndef DOXYGEN
1.248 + typedef UndirGraphEdge<UndirGraph> Edge;
1.249 +#else
1.250 + typedef UndirGraphEdge Edge;
1.251 +#endif
1.252 +
1.253 + /// Iterator type which iterates over all nodes
1.254 +#ifndef DOXYGEN
1.255 + typedef GraphIterator<UndirGraph, Node> NodeIt;
1.256 +#else
1.257 + typedef GraphIterator NodeIt;
1.258 +#endif
1.259 +
1.260 + /// Iterator type which iterates over all undirected edges
1.261 +#ifndef DOXYGEN
1.262 + typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
1.263 +#else
1.264 + typedef GraphIterator UndirEdgeIt;
1.265 +#endif
1.266 +
1.267 + /// Iterator type which iterates over all directed edges.
1.268 +
1.269 + /// Iterator type which iterates over all edges (each undirected
1.270 + /// edge occurs twice with both directions.
1.271 +#ifndef DOXYGEN
1.272 + typedef GraphIterator<UndirGraph, Edge> EdgeIt;
1.273 +#else
1.274 + typedef GraphIterator EdgeIt;
1.275 +#endif
1.276 +
1.277 +
1.278 + /// Iterator of undirected edges incident to a node
1.279 +#ifndef DOXYGEN
1.280 + typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
1.281 +#else
1.282 + typedef GraphIncIterator IncEdgeIt;
1.283 +#endif
1.284 +
1.285 + /// Iterator of edges incoming to a node
1.286 +#ifndef DOXYGEN
1.287 + typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
1.288 +#else
1.289 + typedef GraphIncIterator InEdgeIt;
1.290 +#endif
1.291 +
1.292 + /// Iterator of edges outgoing from a node
1.293 +#ifndef DOXYGEN
1.294 + typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
1.295 +#else
1.296 + typedef GraphIncIterator OutEdgeIt;
1.297 +#endif
1.298 +
1.299 + /// NodeMap template
1.300 +#ifdef DOXYGEN
1.301 + typedef GraphMap NodeMap<T>;
1.302 +#endif
1.303 +
1.304 + /// UndirEdgeMap template
1.305 +#ifdef DOXYGEN
1.306 + typedef GraphMap UndirEdgeMap<T>;
1.307 +#endif
1.308 +
1.309 + /// EdgeMap template
1.310 +#ifdef DOXYGEN
1.311 + typedef GraphMap EdgeMap<T>;
1.312 +#endif
1.313 +
1.314 + template <typename T>
1.315 + class NodeMap : public GraphMap<UndirGraph, Node, T> {
1.316 + typedef GraphMap<UndirGraph, Node, T> Parent;
1.317 + public:
1.318 +
1.319 + explicit NodeMap(const UndirGraph &g) : Parent(g) {}
1.320 + NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.321 + };
1.322 +
1.323 + template <typename T>
1.324 + class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
1.325 + typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
1.326 + public:
1.327 +
1.328 + explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
1.329 + UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.330 + };
1.331 +
1.332 + template <typename T>
1.333 + class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
1.334 + typedef GraphMap<UndirGraph, Edge, T> Parent;
1.335 + public:
1.336 +
1.337 + explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
1.338 + EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.339 + };
1.340 +
1.341 + /// Is the Edge oriented "forward"?
1.342 +
1.343 + /// Returns whether the given directed edge is same orientation as
1.344 + /// the corresponding undirected edge.
1.345 + ///
1.346 + /// \todo "What does the direction of an undirected edge mean?"
1.347 + bool forward(Edge) const { return true; }
1.348 +
1.349 + /// Opposite node on an edge
1.350 +
1.351 + /// \return the opposite of the given Node on the given Edge
1.352 + ///
1.353 + /// \todo What should we do if given Node and Edge are not incident?
1.354 + Node oppositeNode(Node, UndirEdge) const { return INVALID; }
1.355 +
1.356 + /// First node of the undirected edge.
1.357 +
1.358 + /// \return the first node of the given UndirEdge.
1.359 + ///
1.360 + /// Naturally undirectected edges don't have direction and thus
1.361 + /// don't have source and target node. But we use these two methods
1.362 + /// to query the two endnodes of the edge. The direction of the edge
1.363 + /// which arises this way is called the inherent direction of the
1.364 + /// undirected edge, and is used to define the "forward" direction
1.365 + /// of the directed versions of the edges.
1.366 + /// \sa forward
1.367 + Node source(UndirEdge) const { return INVALID; }
1.368 +
1.369 + /// Second node of the undirected edge.
1.370 + Node target(UndirEdge) const { return INVALID; }
1.371 +
1.372 + /// Source node of the directed edge.
1.373 + Node source(Edge) const { return INVALID; }
1.374 +
1.375 + /// Target node of the directed edge.
1.376 + Node target(Edge) const { return INVALID; }
1.377 +
1.378 + /// First node of the graph
1.379 +
1.380 + /// \note This method is part of so called \ref
1.381 + /// developpers_interface "Developpers' interface", so it shouldn't
1.382 + /// be used in an end-user program.
1.383 + void first(Node&) const {}
1.384 + /// Next node of the graph
1.385 +
1.386 + /// \note This method is part of so called \ref
1.387 + /// developpers_interface "Developpers' interface", so it shouldn't
1.388 + /// be used in an end-user program.
1.389 + void next(Node&) const {}
1.390 +
1.391 + /// First undirected edge of the graph
1.392 +
1.393 + /// \note This method is part of so called \ref
1.394 + /// developpers_interface "Developpers' interface", so it shouldn't
1.395 + /// be used in an end-user program.
1.396 + void first(UndirEdge&) const {}
1.397 + /// Next undirected edge of the graph
1.398 +
1.399 + /// \note This method is part of so called \ref
1.400 + /// developpers_interface "Developpers' interface", so it shouldn't
1.401 + /// be used in an end-user program.
1.402 + void next(UndirEdge&) const {}
1.403 +
1.404 + /// First directed edge of the graph
1.405 +
1.406 + /// \note This method is part of so called \ref
1.407 + /// developpers_interface "Developpers' interface", so it shouldn't
1.408 + /// be used in an end-user program.
1.409 + void first(Edge&) const {}
1.410 + /// Next directed edge of the graph
1.411 +
1.412 + /// \note This method is part of so called \ref
1.413 + /// developpers_interface "Developpers' interface", so it shouldn't
1.414 + /// be used in an end-user program.
1.415 + void next(Edge&) const {}
1.416 +
1.417 + /// First outgoing edge from a given node
1.418 +
1.419 + /// \note This method is part of so called \ref
1.420 + /// developpers_interface "Developpers' interface", so it shouldn't
1.421 + /// be used in an end-user program.
1.422 + void firstOut(Edge&, Node) const {}
1.423 + /// Next outgoing edge to a node
1.424 +
1.425 + /// \note This method is part of so called \ref
1.426 + /// developpers_interface "Developpers' interface", so it shouldn't
1.427 + /// be used in an end-user program.
1.428 + void nextOut(Edge&) const {}
1.429 +
1.430 + /// First incoming edge to a given node
1.431 +
1.432 + /// \note This method is part of so called \ref
1.433 + /// developpers_interface "Developpers' interface", so it shouldn't
1.434 + /// be used in an end-user program.
1.435 + void firstIn(Edge&, Node) const {}
1.436 + /// Next incoming edge to a node
1.437 +
1.438 + /// \note This method is part of so called \ref
1.439 + /// developpers_interface "Developpers' interface", so it shouldn't
1.440 + /// be used in an end-user program.
1.441 + void nextIn(Edge&) const {}
1.442 +
1.443 +
1.444 + /// Base node of the iterator
1.445 + ///
1.446 + /// Returns the base node (the source in this case) of the iterator
1.447 + Node baseNode(OutEdgeIt e) const {
1.448 + return source(e);
1.449 + }
1.450 + /// Running node of the iterator
1.451 + ///
1.452 + /// Returns the running node (the target in this case) of the
1.453 + /// iterator
1.454 + Node runningNode(OutEdgeIt e) const {
1.455 + return target(e);
1.456 + }
1.457 +
1.458 + /// Base node of the iterator
1.459 + ///
1.460 + /// Returns the base node (the target in this case) of the iterator
1.461 + Node baseNode(InEdgeIt e) const {
1.462 + return target(e);
1.463 + }
1.464 + /// Running node of the iterator
1.465 + ///
1.466 + /// Returns the running node (the source in this case) of the
1.467 + /// iterator
1.468 + Node runningNode(InEdgeIt e) const {
1.469 + return source(e);
1.470 + }
1.471 +
1.472 + /// Base node of the iterator
1.473 + ///
1.474 + /// Returns the base node of the iterator
1.475 + Node baseNode(IncEdgeIt) const {
1.476 + return INVALID;
1.477 + }
1.478 + /// Running node of the iterator
1.479 + ///
1.480 + /// Returns the running node of the iterator
1.481 + Node runningNode(IncEdgeIt) const {
1.482 + return INVALID;
1.483 + }
1.484 +
1.485 +
1.486 + template <typename Graph>
1.487 + struct Constraints {
1.488 + void constraints() {
1.489 + checkConcept<BaseIterableUndirGraphConcept, Graph>();
1.490 + checkConcept<IterableUndirGraphConcept, Graph>();
1.491 + checkConcept<MappableUndirGraphConcept, Graph>();
1.492 + }
1.493 + };
1.494 +
1.495 + };
1.496 +
1.497 + class ExtendableUndirGraph : public UndirGraph {
1.498 + public:
1.499 +
1.500 + template <typename Graph>
1.501 + struct Constraints {
1.502 + void constraints() {
1.503 + checkConcept<BaseIterableUndirGraphConcept, Graph>();
1.504 + checkConcept<IterableUndirGraphConcept, Graph>();
1.505 + checkConcept<MappableUndirGraphConcept, Graph>();
1.506 +
1.507 + checkConcept<UndirGraph, Graph>();
1.508 + checkConcept<ExtendableUndirGraphConcept, Graph>();
1.509 + checkConcept<ClearableGraphComponent, Graph>();
1.510 + }
1.511 + };
1.512 +
1.513 + };
1.514 +
1.515 + class ErasableUndirGraph : public ExtendableUndirGraph {
1.516 + public:
1.517 +
1.518 + template <typename Graph>
1.519 + struct Constraints {
1.520 + void constraints() {
1.521 + checkConcept<ExtendableUndirGraph, Graph>();
1.522 + checkConcept<ErasableUndirGraphConcept, Graph>();
1.523 + }
1.524 + };
1.525 +
1.526 + };
1.527 +
1.528 + /// @}
1.529 +
1.530 + }
1.531 +
1.532 +}
1.533 +
1.534 +#endif