1.1 --- a/lemon/concept/undir_graph.h Thu Aug 11 15:24:24 2005 +0000
1.2 +++ b/lemon/concept/undir_graph.h Thu Aug 11 15:55:17 2005 +0000
1.3 @@ -119,7 +119,10 @@
1.4 n = graph.oppositeNode(n0, ue);
1.5
1.6 bool b;
1.7 - b = graph.forward(e);
1.8 + b = graph.direction(e);
1.9 + Edge e = graph.direct(UndirEdge(), true);
1.10 + e = graph.direct(UndirEdge(), n);
1.11 +
1.12 ignore_unused_variable_warning(b);
1.13 }
1.14
1.15 @@ -232,8 +235,12 @@
1.16 /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
1.17 /// explanation of this and more see also the page \ref undir_graphs,
1.18 /// a tutorial about undirected graphs.
1.19 + ///
1.20 + /// You can assume that all undirected graph can be handled
1.21 + /// as a static directed graph. This way it is fully conform
1.22 + /// to the StaticGraph concept.
1.23
1.24 - class UndirGraph : public StaticGraph {
1.25 + class UndirGraph {
1.26 public:
1.27 ///\e
1.28
1.29 @@ -241,8 +248,105 @@
1.30 ///
1.31 typedef True UndirTag;
1.32
1.33 + /// The base type of node iterators,
1.34 + /// or in other words, the trivial node iterator.
1.35 +
1.36 + /// This is the base type of each node iterator,
1.37 + /// thus each kind of node iterator converts to this.
1.38 + /// More precisely each kind of node iterator should be inherited
1.39 + /// from the trivial node iterator.
1.40 + class Node {
1.41 + public:
1.42 + /// Default constructor
1.43 +
1.44 + /// @warning The default constructor sets the iterator
1.45 + /// to an undefined value.
1.46 + Node() { }
1.47 + /// Copy constructor.
1.48 +
1.49 + /// Copy constructor.
1.50 + ///
1.51 + Node(const Node&) { }
1.52 +
1.53 + /// Invalid constructor \& conversion.
1.54 +
1.55 + /// This constructor initializes the iterator to be invalid.
1.56 + /// \sa Invalid for more details.
1.57 + Node(Invalid) { }
1.58 + /// Equality operator
1.59 +
1.60 + /// Two iterators are equal if and only if they point to the
1.61 + /// same object or both are invalid.
1.62 + bool operator==(Node) const { return true; }
1.63 +
1.64 + /// Inequality operator
1.65 +
1.66 + /// \sa operator==(Node n)
1.67 + ///
1.68 + bool operator!=(Node) const { return true; }
1.69 +
1.70 + /// Artificial ordering operator.
1.71 +
1.72 + /// To allow the use of graph descriptors as key type in std::map or
1.73 + /// similar associative container we require this.
1.74 + ///
1.75 + /// \note This operator only have to define some strict ordering of
1.76 + /// the items; this order has nothing to do with the iteration
1.77 + /// ordering of the items.
1.78 + ///
1.79 + /// \bug This is a technical requirement. Do we really need this?
1.80 + bool operator<(Node) const { return false; }
1.81 +
1.82 + };
1.83 +
1.84 + /// This iterator goes through each node.
1.85 +
1.86 + /// This iterator goes through each node.
1.87 + /// Its usage is quite simple, for example you can count the number
1.88 + /// of nodes in graph \c g of type \c Graph like this:
1.89 + /// \code
1.90 + /// int count=0;
1.91 + /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.92 + /// \endcode
1.93 + class NodeIt : public Node {
1.94 + public:
1.95 + /// Default constructor
1.96 +
1.97 + /// @warning The default constructor sets the iterator
1.98 + /// to an undefined value.
1.99 + NodeIt() { }
1.100 + /// Copy constructor.
1.101 +
1.102 + /// Copy constructor.
1.103 + ///
1.104 + NodeIt(const NodeIt& n) : Node(n) { }
1.105 + /// Invalid constructor \& conversion.
1.106 +
1.107 + /// Initialize the iterator to be invalid.
1.108 + /// \sa Invalid for more details.
1.109 + NodeIt(Invalid) { }
1.110 + /// Sets the iterator to the first node.
1.111 +
1.112 + /// Sets the iterator to the first node of \c g.
1.113 + ///
1.114 + NodeIt(const UndirGraph&) { }
1.115 + /// Node -> NodeIt conversion.
1.116 +
1.117 + /// Sets the iterator to the node of \c the graph pointed by
1.118 + /// the trivial iterator.
1.119 + /// This feature necessitates that each time we
1.120 + /// iterate the edge-set, the iteration order is the same.
1.121 + NodeIt(const UndirGraph&, const Node&) { }
1.122 + /// Next node.
1.123 +
1.124 + /// Assign the iterator to the next node.
1.125 + ///
1.126 + NodeIt& operator++() { return *this; }
1.127 + };
1.128 +
1.129 +
1.130 /// The base type of the undirected edge iterators.
1.131 -
1.132 +
1.133 /// The base type of the undirected edge iterators.
1.134 ///
1.135 class UndirEdge {
1.136 @@ -257,11 +361,6 @@
1.137 /// Copy constructor.
1.138 ///
1.139 UndirEdge(const UndirEdge&) { }
1.140 - /// Edge -> UndirEdge conversion
1.141 -
1.142 - /// Edge -> UndirEdge conversion
1.143 - ///
1.144 - UndirEdge(const Edge&) { }
1.145 /// Initialize the iterator to be invalid.
1.146
1.147 /// Initialize the iterator to be invalid.
1.148 @@ -278,18 +377,24 @@
1.149 ///
1.150 bool operator!=(UndirEdge) const { return true; }
1.151
1.152 - ///\e
1.153 + /// Artificial ordering operator.
1.154 +
1.155 + /// To allow the use of graph descriptors as key type in std::map or
1.156 + /// similar associative container we require this.
1.157 + ///
1.158 + /// \note This operator only have to define some strict ordering of
1.159 + /// the items; this order has nothing to do with the iteration
1.160 + /// ordering of the items.
1.161 + ///
1.162 + /// \bug This is a technical requirement. Do we really need this?
1.163 + bool operator<(UndirEdge) const { return false; }
1.164 + };
1.165
1.166 - ///\todo Do we need this?
1.167 - ///
1.168 - bool operator<(const UndirEdge &that) const { return true; }
1.169 - };
1.170 -
1.171 /// This iterator goes through each undirected edge.
1.172
1.173 /// This iterator goes through each undirected edge of a graph.
1.174 /// Its usage is quite simple, for example you can count the number
1.175 - /// of edges in a graph \c g of type \c Graph as follows:
1.176 + /// of undirected edges in a graph \c g of type \c Graph as follows:
1.177 /// \code
1.178 /// int count=0;
1.179 /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
1.180 @@ -297,12 +402,12 @@
1.181 class UndirEdgeIt : public UndirEdge {
1.182 public:
1.183 /// Default constructor
1.184 -
1.185 +
1.186 /// @warning The default constructor sets the iterator
1.187 /// to an undefined value.
1.188 UndirEdgeIt() { }
1.189 /// Copy constructor.
1.190 -
1.191 +
1.192 /// Copy constructor.
1.193 ///
1.194 UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
1.195 @@ -311,24 +416,26 @@
1.196 /// Initialize the iterator to be invalid.
1.197 ///
1.198 UndirEdgeIt(Invalid) { }
1.199 - /// This constructor sets the iterator to the first edge.
1.200 + /// This constructor sets the iterator to the first undirected edge.
1.201
1.202 - /// This constructor sets the iterator to the first edge of \c g.
1.203 + /// This constructor sets the iterator to the first undirected edge.
1.204 UndirEdgeIt(const UndirGraph&) { }
1.205 /// UndirEdge -> UndirEdgeIt conversion
1.206
1.207 - /// Sets the iterator to the value of the trivial iterator \c e.
1.208 - /// This feature necessitates that each time we
1.209 - /// iterate the edge-set, the iteration order is the same.
1.210 + /// Sets the iterator to the value of the trivial iterator.
1.211 + /// This feature necessitates that each time we
1.212 + /// iterate the undirected edge-set, the iteration order is the
1.213 + /// same.
1.214 UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
1.215 - ///Next edge
1.216 + /// Next undirected edge
1.217
1.218 - /// Assign the iterator to the next edge.
1.219 + /// Assign the iterator to the next undirected edge.
1.220 UndirEdgeIt& operator++() { return *this; }
1.221 };
1.222
1.223 - /// This iterator goes trough the incident undirected edges of a node.
1.224 -
1.225 + /// \brief This iterator goes trough the incident undirected
1.226 + /// edges of a node.
1.227 + ///
1.228 /// This iterator goes trough the incident undirected edges
1.229 /// of a certain node
1.230 /// of a graph.
1.231 @@ -375,6 +482,237 @@
1.232 IncEdgeIt& operator++() { return *this; }
1.233 };
1.234
1.235 + /// The directed edge type.
1.236 +
1.237 + /// The directed edge type. It can be converted to the
1.238 + /// undirected edge.
1.239 + class Edge : public UndirEdge {
1.240 + public:
1.241 + /// Default constructor
1.242 +
1.243 + /// @warning The default constructor sets the iterator
1.244 + /// to an undefined value.
1.245 + Edge() { }
1.246 + /// Copy constructor.
1.247 +
1.248 + /// Copy constructor.
1.249 + ///
1.250 + Edge(const Edge& e) : UndirEdge(e) { }
1.251 + /// Initialize the iterator to be invalid.
1.252 +
1.253 + /// Initialize the iterator to be invalid.
1.254 + ///
1.255 + Edge(Invalid) { }
1.256 + /// Equality operator
1.257 +
1.258 + /// Two iterators are equal if and only if they point to the
1.259 + /// same object or both are invalid.
1.260 + bool operator==(Edge) const { return true; }
1.261 + /// Inequality operator
1.262 +
1.263 + /// \sa operator==(Edge n)
1.264 + ///
1.265 + bool operator!=(Edge) const { return true; }
1.266 +
1.267 + /// Artificial ordering operator.
1.268 +
1.269 + /// To allow the use of graph descriptors as key type in std::map or
1.270 + /// similar associative container we require this.
1.271 + ///
1.272 + /// \note This operator only have to define some strict ordering of
1.273 + /// the items; this order has nothing to do with the iteration
1.274 + /// ordering of the items.
1.275 + ///
1.276 + /// \bug This is a technical requirement. Do we really need this?
1.277 + bool operator<(Edge) const { return false; }
1.278 +
1.279 + };
1.280 + /// This iterator goes through each directed edge.
1.281 +
1.282 + /// This iterator goes through each edge of a graph.
1.283 + /// Its usage is quite simple, for example you can count the number
1.284 + /// of edges in a graph \c g of type \c Graph as follows:
1.285 + /// \code
1.286 + /// int count=0;
1.287 + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.288 + /// \endcode
1.289 + class EdgeIt : public Edge {
1.290 + public:
1.291 + /// Default constructor
1.292 +
1.293 + /// @warning The default constructor sets the iterator
1.294 + /// to an undefined value.
1.295 + EdgeIt() { }
1.296 + /// Copy constructor.
1.297 +
1.298 + /// Copy constructor.
1.299 + ///
1.300 + EdgeIt(const EdgeIt& e) : Edge(e) { }
1.301 + /// Initialize the iterator to be invalid.
1.302 +
1.303 + /// Initialize the iterator to be invalid.
1.304 + ///
1.305 + EdgeIt(Invalid) { }
1.306 + /// This constructor sets the iterator to the first edge.
1.307 +
1.308 + /// This constructor sets the iterator to the first edge of \c g.
1.309 + ///@param g the graph
1.310 + EdgeIt(const UndirGraph&) { }
1.311 + /// Edge -> EdgeIt conversion
1.312 +
1.313 + /// Sets the iterator to the value of the trivial iterator \c e.
1.314 + /// This feature necessitates that each time we
1.315 + /// iterate the edge-set, the iteration order is the same.
1.316 + EdgeIt(const UndirGraph&, const Edge&) { }
1.317 + ///Next edge
1.318 +
1.319 + /// Assign the iterator to the next edge.
1.320 + EdgeIt& operator++() { return *this; }
1.321 + };
1.322 +
1.323 + /// This iterator goes trough the outgoing directed edges of a node.
1.324 +
1.325 + /// This iterator goes trough the \e outgoing edges of a certain node
1.326 + /// of a graph.
1.327 + /// Its usage is quite simple, for example you can count the number
1.328 + /// of outgoing edges of a node \c n
1.329 + /// in graph \c g of type \c Graph as follows.
1.330 + /// \code
1.331 + /// int count=0;
1.332 + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.333 + /// \endcode
1.334 +
1.335 + class OutEdgeIt : public Edge {
1.336 + public:
1.337 + /// Default constructor
1.338 +
1.339 + /// @warning The default constructor sets the iterator
1.340 + /// to an undefined value.
1.341 + OutEdgeIt() { }
1.342 + /// Copy constructor.
1.343 +
1.344 + /// Copy constructor.
1.345 + ///
1.346 + OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
1.347 + /// Initialize the iterator to be invalid.
1.348 +
1.349 + /// Initialize the iterator to be invalid.
1.350 + ///
1.351 + OutEdgeIt(Invalid) { }
1.352 + /// This constructor sets the iterator to the first outgoing edge.
1.353 +
1.354 + /// This constructor sets the iterator to the first outgoing edge of
1.355 + /// the node.
1.356 + ///@param n the node
1.357 + ///@param g the graph
1.358 + OutEdgeIt(const UndirGraph&, const Node&) { }
1.359 + /// Edge -> OutEdgeIt conversion
1.360 +
1.361 + /// Sets the iterator to the value of the trivial iterator.
1.362 + /// This feature necessitates that each time we
1.363 + /// iterate the edge-set, the iteration order is the same.
1.364 + OutEdgeIt(const UndirGraph&, const Edge&) { }
1.365 + ///Next outgoing edge
1.366 +
1.367 + /// Assign the iterator to the next
1.368 + /// outgoing edge of the corresponding node.
1.369 + OutEdgeIt& operator++() { return *this; }
1.370 + };
1.371 +
1.372 + /// This iterator goes trough the incoming directed edges of a node.
1.373 +
1.374 + /// This iterator goes trough the \e incoming edges of a certain node
1.375 + /// of a graph.
1.376 + /// Its usage is quite simple, for example you can count the number
1.377 + /// of outgoing edges of a node \c n
1.378 + /// in graph \c g of type \c Graph as follows.
1.379 + /// \code
1.380 + /// int count=0;
1.381 + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.382 + /// \endcode
1.383 +
1.384 + class InEdgeIt : public Edge {
1.385 + public:
1.386 + /// Default constructor
1.387 +
1.388 + /// @warning The default constructor sets the iterator
1.389 + /// to an undefined value.
1.390 + InEdgeIt() { }
1.391 + /// Copy constructor.
1.392 +
1.393 + /// Copy constructor.
1.394 + ///
1.395 + InEdgeIt(const InEdgeIt& e) : Edge(e) { }
1.396 + /// Initialize the iterator to be invalid.
1.397 +
1.398 + /// Initialize the iterator to be invalid.
1.399 + ///
1.400 + InEdgeIt(Invalid) { }
1.401 + /// This constructor sets the iterator to first incoming edge.
1.402 +
1.403 + /// This constructor set the iterator to the first incoming edge of
1.404 + /// the node.
1.405 + ///@param n the node
1.406 + ///@param g the graph
1.407 + InEdgeIt(const UndirGraph&, const Node&) { }
1.408 + /// Edge -> InEdgeIt conversion
1.409 +
1.410 + /// Sets the iterator to the value of the trivial iterator \c e.
1.411 + /// This feature necessitates that each time we
1.412 + /// iterate the edge-set, the iteration order is the same.
1.413 + InEdgeIt(const UndirGraph&, const Edge&) { }
1.414 + /// Next incoming edge
1.415 +
1.416 + /// Assign the iterator to the next inedge of the corresponding node.
1.417 + ///
1.418 + InEdgeIt& operator++() { return *this; }
1.419 + };
1.420 +
1.421 + /// \brief Read write map of the nodes to type \c T.
1.422 + ///
1.423 + /// ReadWrite map of the nodes to type \c T.
1.424 + /// \sa Reference
1.425 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.426 + /// needs some extra attention!
1.427 + template<class T>
1.428 + class NodeMap : public ReadWriteMap< Node, T >
1.429 + {
1.430 + public:
1.431 +
1.432 + ///\e
1.433 + NodeMap(const UndirGraph&) { }
1.434 + ///\e
1.435 + NodeMap(const UndirGraph&, T) { }
1.436 +
1.437 + ///Copy constructor
1.438 + NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.439 + ///Assignment operator
1.440 + NodeMap& operator=(const NodeMap&) { return *this; }
1.441 + // \todo fix this concept
1.442 + };
1.443 +
1.444 + /// \brief Read write map of the directed edges to type \c T.
1.445 + ///
1.446 + /// Reference map of the directed edges to type \c T.
1.447 + /// \sa Reference
1.448 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.449 + /// needs some extra attention!
1.450 + template<class T>
1.451 + class EdgeMap : public ReadWriteMap<Edge,T>
1.452 + {
1.453 + public:
1.454 +
1.455 + ///\e
1.456 + EdgeMap(const UndirGraph&) { }
1.457 + ///\e
1.458 + EdgeMap(const UndirGraph&, T) { }
1.459 + ///Copy constructor
1.460 + EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
1.461 + ///Assignment operator
1.462 + EdgeMap& operator=(const EdgeMap&) { return *this; }
1.463 + // \todo fix this concept
1.464 + };
1.465 +
1.466 /// Read write map of the undirected edges to type \c T.
1.467
1.468 /// Reference map of the edges to type \c T.
1.469 @@ -391,122 +729,140 @@
1.470 ///\e
1.471 UndirEdgeMap(const UndirGraph&, T) { }
1.472 ///Copy constructor
1.473 - UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
1.474 + UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {}
1.475 ///Assignment operator
1.476 UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
1.477 // \todo fix this concept
1.478 };
1.479
1.480 - /// Is the Edge oriented "forward"?
1.481 + /// \brief Direct the given undirected edge.
1.482 + ///
1.483 + /// Direct the given undirected edge. The returned edge source
1.484 + /// will be the given edge.
1.485 + Edge direct(const UndirEdge&, const Node&) const {
1.486 + return INVALID;
1.487 + }
1.488
1.489 + /// \brief Direct the given undirected edge.
1.490 + ///
1.491 + /// Direct the given undirected edge. The returned edge source
1.492 + /// will be the source of the undirected edge if the given bool
1.493 + /// is true.
1.494 + Edge direct(const UndirEdge&, bool) const {
1.495 + return INVALID;
1.496 + }
1.497 +
1.498 + /// \brief Returns true if the edge has default orientation.
1.499 + ///
1.500 /// Returns whether the given directed edge is same orientation as
1.501 /// the corresponding undirected edge.
1.502 + bool direction(Edge) const { return true; }
1.503 +
1.504 + /// \brief Returns the opposite directed edge.
1.505 ///
1.506 - /// \todo "What does the direction of an undirected edge mean?"
1.507 - bool forward(Edge) const { return true; }
1.508 + /// Returns the opposite directed edge.
1.509 + Edge oppositeEdge(Edge) const { return INVALID; }
1.510
1.511 - /// Opposite node on an edge
1.512 -
1.513 + /// \brief Opposite node on an edge
1.514 + ///
1.515 /// \return the opposite of the given Node on the given Edge
1.516 - ///
1.517 - /// \todo What should we do if given Node and Edge are not incident?
1.518 Node oppositeNode(Node, UndirEdge) const { return INVALID; }
1.519
1.520 - /// First node of the undirected edge.
1.521 -
1.522 + /// \brief First node of the undirected edge.
1.523 + ///
1.524 /// \return the first node of the given UndirEdge.
1.525 ///
1.526 /// Naturally undirectected edges don't have direction and thus
1.527 /// don't have source and target node. But we use these two methods
1.528 /// to query the two endnodes of the edge. The direction of the edge
1.529 /// which arises this way is called the inherent direction of the
1.530 - /// undirected edge, and is used to define the "forward" direction
1.531 + /// undirected edge, and is used to define the "default" direction
1.532 /// of the directed versions of the edges.
1.533 - /// \sa forward
1.534 + /// \sa direction
1.535 Node source(UndirEdge) const { return INVALID; }
1.536
1.537 - /// Second node of the undirected edge.
1.538 + /// \brief Second node of the undirected edge.
1.539 Node target(UndirEdge) const { return INVALID; }
1.540
1.541 - /// Source node of the directed edge.
1.542 + /// \brief Source node of the directed edge.
1.543 Node source(Edge) const { return INVALID; }
1.544
1.545 - /// Target node of the directed edge.
1.546 + /// \brief Target node of the directed edge.
1.547 Node target(Edge) const { return INVALID; }
1.548
1.549 - /// First node of the graph
1.550 -
1.551 + /// \brief First node of the graph
1.552 + ///
1.553 /// \note This method is part of so called \ref
1.554 /// developpers_interface "Developpers' interface", so it shouldn't
1.555 /// be used in an end-user program.
1.556 void first(Node&) const {}
1.557 - /// Next node of the graph
1.558 -
1.559 + /// \brief Next node of the graph
1.560 + ///
1.561 /// \note This method is part of so called \ref
1.562 /// developpers_interface "Developpers' interface", so it shouldn't
1.563 /// be used in an end-user program.
1.564 void next(Node&) const {}
1.565
1.566 - /// First undirected edge of the graph
1.567 -
1.568 + /// \brief First undirected edge of the graph
1.569 + ///
1.570 /// \note This method is part of so called \ref
1.571 /// developpers_interface "Developpers' interface", so it shouldn't
1.572 /// be used in an end-user program.
1.573 void first(UndirEdge&) const {}
1.574 - /// Next undirected edge of the graph
1.575 -
1.576 + /// \brief Next undirected edge of the graph
1.577 + ///
1.578 /// \note This method is part of so called \ref
1.579 /// developpers_interface "Developpers' interface", so it shouldn't
1.580 /// be used in an end-user program.
1.581 void next(UndirEdge&) const {}
1.582
1.583 - /// First directed edge of the graph
1.584 -
1.585 + /// \brief First directed edge of the graph
1.586 + ///
1.587 /// \note This method is part of so called \ref
1.588 /// developpers_interface "Developpers' interface", so it shouldn't
1.589 /// be used in an end-user program.
1.590 void first(Edge&) const {}
1.591 - /// Next directed edge of the graph
1.592 -
1.593 + /// \brief Next directed edge of the graph
1.594 + ///
1.595 /// \note This method is part of so called \ref
1.596 /// developpers_interface "Developpers' interface", so it shouldn't
1.597 /// be used in an end-user program.
1.598 void next(Edge&) const {}
1.599
1.600 - /// First outgoing edge from a given node
1.601 -
1.602 + /// \brief First outgoing edge from a given node
1.603 + ///
1.604 /// \note This method is part of so called \ref
1.605 /// developpers_interface "Developpers' interface", so it shouldn't
1.606 /// be used in an end-user program.
1.607 void firstOut(Edge&, Node) const {}
1.608 - /// Next outgoing edge to a node
1.609 -
1.610 + /// \brief Next outgoing edge to a node
1.611 + ///
1.612 /// \note This method is part of so called \ref
1.613 /// developpers_interface "Developpers' interface", so it shouldn't
1.614 /// be used in an end-user program.
1.615 void nextOut(Edge&) const {}
1.616
1.617 - /// First incoming edge to a given node
1.618 -
1.619 + /// \brief First incoming edge to a given node
1.620 + ///
1.621 /// \note This method is part of so called \ref
1.622 /// developpers_interface "Developpers' interface", so it shouldn't
1.623 /// be used in an end-user program.
1.624 void firstIn(Edge&, Node) const {}
1.625 - /// Next incoming edge to a node
1.626 -
1.627 + /// \brief Next incoming edge to a node
1.628 + ///
1.629 /// \note This method is part of so called \ref
1.630 /// developpers_interface "Developpers' interface", so it shouldn't
1.631 /// be used in an end-user program.
1.632 void nextIn(Edge&) const {}
1.633
1.634
1.635 - /// Base node of the iterator
1.636 + /// \brief Base node of the iterator
1.637 ///
1.638 /// Returns the base node (the source in this case) of the iterator
1.639 Node baseNode(OutEdgeIt e) const {
1.640 return source(e);
1.641 }
1.642 - /// Running node of the iterator
1.643 + /// \brief Running node of the iterator
1.644 ///
1.645 /// Returns the running node (the target in this case) of the
1.646 /// iterator
1.647 @@ -514,13 +870,13 @@
1.648 return target(e);
1.649 }
1.650
1.651 - /// Base node of the iterator
1.652 + /// \brief Base node of the iterator
1.653 ///
1.654 /// Returns the base node (the target in this case) of the iterator
1.655 Node baseNode(InEdgeIt e) const {
1.656 return target(e);
1.657 }
1.658 - /// Running node of the iterator
1.659 + /// \brief Running node of the iterator
1.660 ///
1.661 /// Returns the running node (the source in this case) of the
1.662 /// iterator
1.663 @@ -528,20 +884,20 @@
1.664 return source(e);
1.665 }
1.666
1.667 - /// Base node of the iterator
1.668 + /// \brief Base node of the iterator
1.669 ///
1.670 /// Returns the base node of the iterator
1.671 Node baseNode(IncEdgeIt) const {
1.672 return INVALID;
1.673 }
1.674 - /// Running node of the iterator
1.675 +
1.676 + /// \brief Running node of the iterator
1.677 ///
1.678 /// Returns the running node of the iterator
1.679 Node runningNode(IncEdgeIt) const {
1.680 return INVALID;
1.681 }
1.682
1.683 -
1.684 template <typename Graph>
1.685 struct Constraints {
1.686 void constraints() {
1.687 @@ -553,8 +909,30 @@
1.688
1.689 };
1.690
1.691 + /// \brief An empty non-static undirected graph class.
1.692 + ///
1.693 + /// This class provides everything that \ref UndirGraph does.
1.694 + /// Additionally it enables building graphs from scratch.
1.695 class ExtendableUndirGraph : public UndirGraph {
1.696 public:
1.697 +
1.698 + /// \brief Add a new node to the graph.
1.699 + ///
1.700 + /// Add a new node to the graph.
1.701 + /// \return the new node.
1.702 + Node addNode();
1.703 +
1.704 + /// \brief Add a new undirected edge to the graph.
1.705 + ///
1.706 + /// Add a new undirected edge to the graph.
1.707 + /// \return the new edge.
1.708 + UndirEdge addEdge(const Node& from, const Node& to);
1.709 +
1.710 + /// \brief Resets the graph.
1.711 + ///
1.712 + /// This function deletes all undirected edges and nodes of the graph.
1.713 + /// It also frees the memory allocated to store them.
1.714 + void clear() { }
1.715
1.716 template <typename Graph>
1.717 struct Constraints {
1.718 @@ -571,9 +949,24 @@
1.719
1.720 };
1.721
1.722 + /// \brief An empty erasable undirected graph class.
1.723 + ///
1.724 + /// This class is an extension of \ref ExtendableUndirGraph. It makes it
1.725 + /// possible to erase undirected edges or nodes.
1.726 class ErasableUndirGraph : public ExtendableUndirGraph {
1.727 public:
1.728
1.729 + /// \brief Deletes a node.
1.730 + ///
1.731 + /// Deletes a node.
1.732 + ///
1.733 + void erase(Node) { }
1.734 + /// \brief Deletes an undirected edge.
1.735 + ///
1.736 + /// Deletes an undirected edge.
1.737 + ///
1.738 + void erase(UndirEdge) { }
1.739 +
1.740 template <typename Graph>
1.741 struct Constraints {
1.742 void constraints() {