1.1 --- a/src/lemon/concept/undir_graph.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,531 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * src/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