1.1 --- a/demo/coloring.cc Wed Jun 28 16:27:44 2006 +0000
1.2 +++ b/demo/coloring.cc Fri Jun 30 12:14:36 2006 +0000
1.3 @@ -29,7 +29,7 @@
1.4
1.5 #include <iostream>
1.6
1.7 -#include <lemon/smart_graph.h>
1.8 +#include <lemon/smart_ugraph.h>
1.9 #include <lemon/bucket_heap.h>
1.10 #include <lemon/graph_reader.h>
1.11 #include <lemon/graph_to_eps.h>
2.1 --- a/demo/strongly_connected_orientation.cc Wed Jun 28 16:27:44 2006 +0000
2.2 +++ b/demo/strongly_connected_orientation.cc Fri Jun 30 12:14:36 2006 +0000
2.3 @@ -18,7 +18,7 @@
2.4
2.5 #include <iostream>
2.6
2.7 -#include <lemon/smart_graph.h>
2.8 +#include <lemon/smart_ugraph.h>
2.9 #include <lemon/graph_reader.h>
2.10 #include <lemon/ugraph_adaptor.h>
2.11 #include <lemon/graph_to_eps.h>
3.1 --- a/demo/topology_demo.cc Wed Jun 28 16:27:44 2006 +0000
3.2 +++ b/demo/topology_demo.cc Fri Jun 30 12:14:36 2006 +0000
3.3 @@ -17,6 +17,7 @@
3.4 */
3.5
3.6 #include <lemon/list_graph.h>
3.7 +#include <lemon/list_ugraph.h>
3.8 #include <lemon/topology.h>
3.9 #include <lemon/graph_to_eps.h>
3.10 #include <lemon/graph_reader.h>
4.1 --- a/doc/graphs.dox Wed Jun 28 16:27:44 2006 +0000
4.2 +++ b/doc/graphs.dox Fri Jun 30 12:14:36 2006 +0000
4.3 @@ -9,20 +9,20 @@
4.4 The primary data structures of LEMON are the graph classes. They all
4.5 provide a node list - edge list interface, i.e. they have
4.6 functionalities to list the nodes and the edges of the graph as well
4.7 -as incoming and outgoing edges of a given node.
4.8 +as incoming and outgoing edges of a given node. This functionalities
4.9 +are defined in the \ref lemon::concept::Graph "Graph" concept.
4.10
4.11 -Each graph should meet the \ref lemon::concept::Graph "Graph" concept.
4.12 -This concept does not make it possible to change the graph (i.e. it is
4.13 -not possible to add or delete edges or nodes). Most of the graph
4.14 -algorithms will run on these graphs.
4.15 +The next important graph type concept is the undirected graph concept
4.16 +what is defined in the \ref lemon::concept::UGraph "UGraph" concept class.
4.17 +Each undirected graphs provide node - undirected edge list interfaces.
4.18 +In addition the undirected graphs can be used as directed graphs so
4.19 +they are also conform to the \ref lemon::concept::Graph "Graph" concept.
4.20
4.21 +Usually the graphs can be sorted to two group, the first is the
4.22 +general topology graph types which can store any graph and the second
4.23 +are the special topology graphs like the \ref FullUGraph or the \ref
4.24 +GridUGraph.
4.25
4.26 -In case of graphs meeting the full feature
4.27 -\ref lemon::concept::ErasableGraph "ErasableGraph"
4.28 -concept
4.29 -you can also erase individual edges and nodes in arbitrary order.
4.30 -
4.31 -The implemented graph structures are the following.
4.32 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
4.33 the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
4.34 and it also has some convenient extra features.
5.1 --- a/lemon/Makefile.am Wed Jun 28 16:27:44 2006 +0000
5.2 +++ b/lemon/Makefile.am Fri Jun 30 12:14:36 2006 +0000
5.3 @@ -43,7 +43,9 @@
5.4 lemon/fib_heap.h \
5.5 lemon/floyd_warshall.h \
5.6 lemon/fredman_tarjan.h \
5.7 + lemon/full_bpugraph.h \
5.8 lemon/full_graph.h \
5.9 + lemon/full_ugraph.h \
5.10 lemon/graph_adaptor.h \
5.11 lemon/graph_reader.h \
5.12 lemon/graph_to_eps.h \
5.13 @@ -56,7 +58,9 @@
5.14 lemon/kruskal.h \
5.15 lemon/lemon_reader.h \
5.16 lemon/lemon_writer.h \
5.17 + lemon/list_bpugraph.h \
5.18 lemon/list_graph.h \
5.19 + lemon/list_ugraph.h \
5.20 lemon/lp.h \
5.21 lemon/lp_base.h \
5.22 lemon/lp_cplex.h \
5.23 @@ -77,7 +81,9 @@
5.24 lemon/radix_sort.h \
5.25 lemon/refptr.h \
5.26 lemon/simann.h \
5.27 + lemon/smart_bpugraph.h \
5.28 lemon/smart_graph.h \
5.29 + lemon/smart_ugraph.h \
5.30 lemon/sub_graph.h \
5.31 lemon/suurballe.h \
5.32 lemon/tabu_search.h \
5.33 @@ -92,6 +98,7 @@
5.34 lemon/bits/alteration_notifier.h \
5.35 lemon/bits/array_map.h \
5.36 lemon/bits/base_extender.h \
5.37 + lemon/bits/bpugraph_extender.h \
5.38 lemon/bits/default_map.h \
5.39 lemon/bits/edge_set_extender.h \
5.40 lemon/bits/graph_adaptor_extender.h \
5.41 @@ -103,6 +110,7 @@
5.42 lemon/bits/mingw32_rand.h \
5.43 lemon/bits/mingw32_time.h \
5.44 lemon/bits/traits.h \
5.45 + lemon/bits/ugraph_extender.h \
5.46 lemon/bits/utility.h \
5.47 lemon/bits/vector_map.h
5.48
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/bits/bpugraph_extender.h Fri Jun 30 12:14:36 2006 +0000
6.3 @@ -0,0 +1,838 @@
6.4 +/* -*- C++ -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library
6.7 + *
6.8 + * Copyright (C) 2003-2006
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#ifndef LEMON_BITS_BPUGRAPH_EXTENDER_H
6.23 +#define LEMON_BITS_BPUGRAPH_EXTENDER_H
6.24 +
6.25 +#include <lemon/bits/invalid.h>
6.26 +#include <lemon/error.h>
6.27 +
6.28 +#include <lemon/bits/map_extender.h>
6.29 +#include <lemon/bits/default_map.h>
6.30 +
6.31 +#include <lemon/concept_check.h>
6.32 +#include <lemon/concept/maps.h>
6.33 +
6.34 +///\ingroup graphbits
6.35 +///\file
6.36 +///\brief Extenders for the graph types
6.37 +namespace lemon {
6.38 +
6.39 + /// \ingroup graphbits
6.40 + ///
6.41 + /// \brief Extender for the BpUGraphs
6.42 + template <typename Base>
6.43 + class BpUGraphExtender : public Base {
6.44 + public:
6.45 + typedef Base Parent;
6.46 + typedef BpUGraphExtender Graph;
6.47 +
6.48 + typedef typename Parent::Node Node;
6.49 + typedef typename Parent::UEdge UEdge;
6.50 +
6.51 +
6.52 + using Parent::first;
6.53 + using Parent::next;
6.54 +
6.55 + using Parent::id;
6.56 +
6.57 + class ANode : public Node {
6.58 + friend class BpUGraphExtender;
6.59 + public:
6.60 + ANode() {}
6.61 + ANode(const Node& node) : Node(node) {
6.62 + LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
6.63 + typename Parent::NodeSetError());
6.64 + }
6.65 + ANode(Invalid) : Node(INVALID) {}
6.66 + };
6.67 +
6.68 + void first(ANode& node) const {
6.69 + Parent::firstANode(static_cast<Node&>(node));
6.70 + }
6.71 + void next(ANode& node) const {
6.72 + Parent::nextANode(static_cast<Node&>(node));
6.73 + }
6.74 +
6.75 + int id(const ANode& node) const {
6.76 + return Parent::aNodeId(node);
6.77 + }
6.78 +
6.79 + class BNode : public Node {
6.80 + friend class BpUGraphExtender;
6.81 + public:
6.82 + BNode() {}
6.83 + BNode(const Node& node) : Node(node) {
6.84 + LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
6.85 + typename Parent::NodeSetError());
6.86 + }
6.87 + BNode(Invalid) : Node(INVALID) {}
6.88 + };
6.89 +
6.90 + void first(BNode& node) const {
6.91 + Parent::firstBNode(static_cast<Node&>(node));
6.92 + }
6.93 + void next(BNode& node) const {
6.94 + Parent::nextBNode(static_cast<Node&>(node));
6.95 + }
6.96 +
6.97 + int id(const BNode& node) const {
6.98 + return Parent::aNodeId(node);
6.99 + }
6.100 +
6.101 + Node source(const UEdge& edge) const {
6.102 + return aNode(edge);
6.103 + }
6.104 + Node target(const UEdge& edge) const {
6.105 + return bNode(edge);
6.106 + }
6.107 +
6.108 + void firstInc(UEdge& edge, bool& direction, const Node& node) const {
6.109 + if (Parent::aNode(node)) {
6.110 + Parent::firstFromANode(edge, node);
6.111 + direction = true;
6.112 + } else {
6.113 + Parent::firstFromBNode(edge, node);
6.114 + direction = static_cast<UEdge&>(edge) == INVALID;
6.115 + }
6.116 + }
6.117 + void nextInc(UEdge& edge, bool& direction) const {
6.118 + if (direction) {
6.119 + Parent::nextFromANode(edge);
6.120 + } else {
6.121 + Parent::nextFromBNode(edge);
6.122 + if (edge == INVALID) direction = true;
6.123 + }
6.124 + }
6.125 +
6.126 + class Edge : public UEdge {
6.127 + friend class BpUGraphExtender;
6.128 + protected:
6.129 + bool forward;
6.130 +
6.131 + Edge(const UEdge& edge, bool _forward)
6.132 + : UEdge(edge), forward(_forward) {}
6.133 +
6.134 + public:
6.135 + Edge() {}
6.136 + Edge (Invalid) : UEdge(INVALID), forward(true) {}
6.137 + bool operator==(const Edge& i) const {
6.138 + return UEdge::operator==(i) && forward == i.forward;
6.139 + }
6.140 + bool operator!=(const Edge& i) const {
6.141 + return UEdge::operator!=(i) || forward != i.forward;
6.142 + }
6.143 + bool operator<(const Edge& i) const {
6.144 + return UEdge::operator<(i) ||
6.145 + (!(i.forward<forward) && UEdge(*this)<UEdge(i));
6.146 + }
6.147 + };
6.148 +
6.149 + void first(Edge& edge) const {
6.150 + Parent::first(static_cast<UEdge&>(edge));
6.151 + edge.forward = true;
6.152 + }
6.153 +
6.154 + void next(Edge& edge) const {
6.155 + if (!edge.forward) {
6.156 + Parent::next(static_cast<UEdge&>(edge));
6.157 + }
6.158 + edge.forward = !edge.forward;
6.159 + }
6.160 +
6.161 + void firstOut(Edge& edge, const Node& node) const {
6.162 + if (Parent::aNode(node)) {
6.163 + Parent::firstFromANode(edge, node);
6.164 + edge.forward = true;
6.165 + } else {
6.166 + Parent::firstFromBNode(edge, node);
6.167 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
6.168 + }
6.169 + }
6.170 + void nextOut(Edge& edge) const {
6.171 + if (edge.forward) {
6.172 + Parent::nextFromANode(edge);
6.173 + } else {
6.174 + Parent::nextFromBNode(edge);
6.175 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
6.176 + }
6.177 + }
6.178 +
6.179 + void firstIn(Edge& edge, const Node& node) const {
6.180 + if (Parent::bNode(node)) {
6.181 + Parent::firstFromBNode(edge, node);
6.182 + edge.forward = true;
6.183 + } else {
6.184 + Parent::firstFromANode(edge, node);
6.185 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
6.186 + }
6.187 + }
6.188 + void nextIn(Edge& edge) const {
6.189 + if (edge.forward) {
6.190 + Parent::nextFromBNode(edge);
6.191 + } else {
6.192 + Parent::nextFromANode(edge);
6.193 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
6.194 + }
6.195 + }
6.196 +
6.197 + Node source(const Edge& edge) const {
6.198 + return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
6.199 + }
6.200 + Node target(const Edge& edge) const {
6.201 + return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
6.202 + }
6.203 +
6.204 + int id(const Edge& edge) const {
6.205 + return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
6.206 + (edge.forward ? 0 : 1);
6.207 + }
6.208 + Edge edgeFromId(int id) const {
6.209 + return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
6.210 + }
6.211 + int maxEdgeId() const {
6.212 + return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
6.213 + }
6.214 +
6.215 + bool direction(const Edge& edge) const {
6.216 + return edge.forward;
6.217 + }
6.218 +
6.219 + Edge direct(const UEdge& edge, bool direction) const {
6.220 + return Edge(edge, direction);
6.221 + }
6.222 +
6.223 + int edgeNum() const {
6.224 + return 2 * Parent::uEdgeNum();
6.225 + }
6.226 +
6.227 + int uEdgeNum() const {
6.228 + return Parent::uEdgeNum();
6.229 + }
6.230 +
6.231 + Node oppositeNode(const UEdge& edge, const Node& node) const {
6.232 + return source(edge) == node ?
6.233 + target(edge) : source(edge);
6.234 + }
6.235 +
6.236 + Edge direct(const UEdge& edge, const Node& node) const {
6.237 + return Edge(edge, node == Parent::source(edge));
6.238 + }
6.239 +
6.240 + Edge oppositeEdge(const Edge& edge) const {
6.241 + return Parent::direct(edge, !Parent::direction(edge));
6.242 + }
6.243 +
6.244 +
6.245 + int maxId(Node) const {
6.246 + return Parent::maxNodeId();
6.247 + }
6.248 + int maxId(BNode) const {
6.249 + return Parent::maxBNodeId();
6.250 + }
6.251 + int maxId(ANode) const {
6.252 + return Parent::maxANodeId();
6.253 + }
6.254 + int maxId(Edge) const {
6.255 + return maxEdgeId();
6.256 + }
6.257 + int maxId(UEdge) const {
6.258 + return Parent::maxUEdgeId();
6.259 + }
6.260 +
6.261 +
6.262 + Node fromId(int id, Node) const {
6.263 + return Parent::nodeFromId(id);
6.264 + }
6.265 + ANode fromId(int id, ANode) const {
6.266 + return Parent::fromANodeId(id);
6.267 + }
6.268 + BNode fromId(int id, BNode) const {
6.269 + return Parent::fromBNodeId(id);
6.270 + }
6.271 + Edge fromId(int id, Edge) const {
6.272 + return Parent::edgeFromId(id);
6.273 + }
6.274 + UEdge fromId(int id, UEdge) const {
6.275 + return Parent::uEdgeFromId(id);
6.276 + }
6.277 +
6.278 + typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
6.279 + typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
6.280 + typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
6.281 + typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
6.282 + typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
6.283 +
6.284 + protected:
6.285 +
6.286 + mutable ANodeNotifier anode_notifier;
6.287 + mutable BNodeNotifier bnode_notifier;
6.288 + mutable NodeNotifier node_notifier;
6.289 + mutable EdgeNotifier edge_notifier;
6.290 + mutable UEdgeNotifier uedge_notifier;
6.291 +
6.292 + public:
6.293 +
6.294 + NodeNotifier& getNotifier(Node) const {
6.295 + return node_notifier;
6.296 + }
6.297 +
6.298 + ANodeNotifier& getNotifier(ANode) const {
6.299 + return anode_notifier;
6.300 + }
6.301 +
6.302 + BNodeNotifier& getNotifier(BNode) const {
6.303 + return bnode_notifier;
6.304 + }
6.305 +
6.306 + EdgeNotifier& getNotifier(Edge) const {
6.307 + return edge_notifier;
6.308 + }
6.309 +
6.310 + UEdgeNotifier& getNotifier(UEdge) const {
6.311 + return uedge_notifier;
6.312 + }
6.313 +
6.314 + class NodeIt : public Node {
6.315 + const Graph* graph;
6.316 + public:
6.317 +
6.318 + NodeIt() { }
6.319 +
6.320 + NodeIt(Invalid i) : Node(INVALID) { }
6.321 +
6.322 + explicit NodeIt(const Graph& _graph) : graph(&_graph) {
6.323 + graph->first(static_cast<Node&>(*this));
6.324 + }
6.325 +
6.326 + NodeIt(const Graph& _graph, const Node& node)
6.327 + : Node(node), graph(&_graph) { }
6.328 +
6.329 + NodeIt& operator++() {
6.330 + graph->next(*this);
6.331 + return *this;
6.332 + }
6.333 +
6.334 + };
6.335 +
6.336 + class ANodeIt : public Node {
6.337 + friend class BpUGraphExtender;
6.338 + const Graph* graph;
6.339 + public:
6.340 +
6.341 + ANodeIt() { }
6.342 +
6.343 + ANodeIt(Invalid i) : Node(INVALID) { }
6.344 +
6.345 + explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
6.346 + graph->firstANode(static_cast<Node&>(*this));
6.347 + }
6.348 +
6.349 + ANodeIt(const Graph& _graph, const Node& node)
6.350 + : Node(node), graph(&_graph) {}
6.351 +
6.352 + ANodeIt& operator++() {
6.353 + graph->nextANode(*this);
6.354 + return *this;
6.355 + }
6.356 + };
6.357 +
6.358 + class BNodeIt : public Node {
6.359 + friend class BpUGraphExtender;
6.360 + const Graph* graph;
6.361 + public:
6.362 +
6.363 + BNodeIt() { }
6.364 +
6.365 + BNodeIt(Invalid i) : Node(INVALID) { }
6.366 +
6.367 + explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
6.368 + graph->firstBNode(static_cast<Node&>(*this));
6.369 + }
6.370 +
6.371 + BNodeIt(const Graph& _graph, const Node& node)
6.372 + : Node(node), graph(&_graph) {}
6.373 +
6.374 + BNodeIt& operator++() {
6.375 + graph->nextBNode(*this);
6.376 + return *this;
6.377 + }
6.378 + };
6.379 +
6.380 + class EdgeIt : public Edge {
6.381 + friend class BpUGraphExtender;
6.382 + const Graph* graph;
6.383 + public:
6.384 +
6.385 + EdgeIt() { }
6.386 +
6.387 + EdgeIt(Invalid i) : Edge(INVALID) { }
6.388 +
6.389 + explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
6.390 + graph->first(static_cast<Edge&>(*this));
6.391 + }
6.392 +
6.393 + EdgeIt(const Graph& _graph, const Edge& edge)
6.394 + : Edge(edge), graph(&_graph) { }
6.395 +
6.396 + EdgeIt& operator++() {
6.397 + graph->next(*this);
6.398 + return *this;
6.399 + }
6.400 +
6.401 + };
6.402 +
6.403 + class UEdgeIt : public UEdge {
6.404 + friend class BpUGraphExtender;
6.405 + const Graph* graph;
6.406 + public:
6.407 +
6.408 + UEdgeIt() { }
6.409 +
6.410 + UEdgeIt(Invalid i) : UEdge(INVALID) { }
6.411 +
6.412 + explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
6.413 + graph->first(static_cast<UEdge&>(*this));
6.414 + }
6.415 +
6.416 + UEdgeIt(const Graph& _graph, const UEdge& edge)
6.417 + : UEdge(edge), graph(&_graph) { }
6.418 +
6.419 + UEdgeIt& operator++() {
6.420 + graph->next(*this);
6.421 + return *this;
6.422 + }
6.423 + };
6.424 +
6.425 + class OutEdgeIt : public Edge {
6.426 + friend class BpUGraphExtender;
6.427 + const Graph* graph;
6.428 + public:
6.429 +
6.430 + OutEdgeIt() { }
6.431 +
6.432 + OutEdgeIt(Invalid i) : Edge(i) { }
6.433 +
6.434 + OutEdgeIt(const Graph& _graph, const Node& node)
6.435 + : graph(&_graph) {
6.436 + graph->firstOut(*this, node);
6.437 + }
6.438 +
6.439 + OutEdgeIt(const Graph& _graph, const Edge& edge)
6.440 + : Edge(edge), graph(&_graph) {}
6.441 +
6.442 + OutEdgeIt& operator++() {
6.443 + graph->nextOut(*this);
6.444 + return *this;
6.445 + }
6.446 +
6.447 + };
6.448 +
6.449 +
6.450 + class InEdgeIt : public Edge {
6.451 + friend class BpUGraphExtender;
6.452 + const Graph* graph;
6.453 + public:
6.454 +
6.455 + InEdgeIt() { }
6.456 +
6.457 + InEdgeIt(Invalid i) : Edge(i) { }
6.458 +
6.459 + InEdgeIt(const Graph& _graph, const Node& node)
6.460 + : graph(&_graph) {
6.461 + graph->firstIn(*this, node);
6.462 + }
6.463 +
6.464 + InEdgeIt(const Graph& _graph, const Edge& edge) :
6.465 + Edge(edge), graph(&_graph) {}
6.466 +
6.467 + InEdgeIt& operator++() {
6.468 + graph->nextIn(*this);
6.469 + return *this;
6.470 + }
6.471 +
6.472 + };
6.473 +
6.474 + /// \brief Base node of the iterator
6.475 + ///
6.476 + /// Returns the base node (ie. the source in this case) of the iterator
6.477 + Node baseNode(const OutEdgeIt &e) const {
6.478 + return Parent::source((Edge&)e);
6.479 + }
6.480 + /// \brief Running node of the iterator
6.481 + ///
6.482 + /// Returns the running node (ie. the target in this case) of the
6.483 + /// iterator
6.484 + Node runningNode(const OutEdgeIt &e) const {
6.485 + return Parent::target((Edge&)e);
6.486 + }
6.487 +
6.488 + /// \brief Base node of the iterator
6.489 + ///
6.490 + /// Returns the base node (ie. the target in this case) of the iterator
6.491 + Node baseNode(const InEdgeIt &e) const {
6.492 + return Parent::target((Edge&)e);
6.493 + }
6.494 + /// \brief Running node of the iterator
6.495 + ///
6.496 + /// Returns the running node (ie. the source in this case) of the
6.497 + /// iterator
6.498 + Node runningNode(const InEdgeIt &e) const {
6.499 + return Parent::source((Edge&)e);
6.500 + }
6.501 +
6.502 + class IncEdgeIt : public Parent::UEdge {
6.503 + friend class BpUGraphExtender;
6.504 + const Graph* graph;
6.505 + bool direction;
6.506 + public:
6.507 +
6.508 + IncEdgeIt() { }
6.509 +
6.510 + IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
6.511 +
6.512 + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
6.513 + graph->firstInc(*this, direction, n);
6.514 + }
6.515 +
6.516 + IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
6.517 + : graph(&_graph), UEdge(ue) {
6.518 + direction = (graph->source(ue) == n);
6.519 + }
6.520 +
6.521 + IncEdgeIt& operator++() {
6.522 + graph->nextInc(*this, direction);
6.523 + return *this;
6.524 + }
6.525 + };
6.526 +
6.527 +
6.528 + /// Base node of the iterator
6.529 + ///
6.530 + /// Returns the base node of the iterator
6.531 + Node baseNode(const IncEdgeIt &e) const {
6.532 + return e.direction ? source(e) : target(e);
6.533 + }
6.534 +
6.535 + /// Running node of the iterator
6.536 + ///
6.537 + /// Returns the running node of the iterator
6.538 + Node runningNode(const IncEdgeIt &e) const {
6.539 + return e.direction ? target(e) : source(e);
6.540 + }
6.541 +
6.542 + template <typename _Value>
6.543 + class ANodeMap
6.544 + : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
6.545 + public:
6.546 + typedef BpUGraphExtender Graph;
6.547 + typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
6.548 +
6.549 + ANodeMap(const Graph& graph)
6.550 + : Parent(graph) {}
6.551 + ANodeMap(const Graph& graph, const _Value& value)
6.552 + : Parent(graph, value) {}
6.553 +
6.554 + ANodeMap& operator=(const ANodeMap& cmap) {
6.555 + return operator=<ANodeMap>(cmap);
6.556 + }
6.557 +
6.558 + template <typename CMap>
6.559 + ANodeMap& operator=(const CMap& cmap) {
6.560 + Parent::operator=(cmap);
6.561 + return *this;
6.562 + }
6.563 +
6.564 + };
6.565 +
6.566 + template <typename _Value>
6.567 + class BNodeMap
6.568 + : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
6.569 + public:
6.570 + typedef BpUGraphExtender Graph;
6.571 + typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
6.572 +
6.573 + BNodeMap(const Graph& graph)
6.574 + : Parent(graph) {}
6.575 + BNodeMap(const Graph& graph, const _Value& value)
6.576 + : Parent(graph, value) {}
6.577 +
6.578 + BNodeMap& operator=(const BNodeMap& cmap) {
6.579 + return operator=<BNodeMap>(cmap);
6.580 + }
6.581 +
6.582 + template <typename CMap>
6.583 + BNodeMap& operator=(const CMap& cmap) {
6.584 + Parent::operator=(cmap);
6.585 + return *this;
6.586 + }
6.587 +
6.588 + };
6.589 +
6.590 + public:
6.591 +
6.592 + template <typename _Value>
6.593 + class NodeMap {
6.594 + public:
6.595 + typedef BpUGraphExtender Graph;
6.596 +
6.597 + typedef Node Key;
6.598 + typedef _Value Value;
6.599 +
6.600 + /// The reference type of the map;
6.601 + typedef typename ANodeMap<_Value>::Reference Reference;
6.602 + /// The const reference type of the map;
6.603 + typedef typename ANodeMap<_Value>::ConstReference ConstReference;
6.604 +
6.605 + typedef True ReferenceMapTag;
6.606 +
6.607 + NodeMap(const Graph& _graph)
6.608 + : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
6.609 + NodeMap(const Graph& _graph, const _Value& _value)
6.610 + : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
6.611 +
6.612 + NodeMap& operator=(const NodeMap& cmap) {
6.613 + return operator=<NodeMap>(cmap);
6.614 + }
6.615 +
6.616 + template <typename CMap>
6.617 + NodeMap& operator=(const CMap& cmap) {
6.618 + checkConcept<concept::ReadMap<Node, _Value>, CMap>();
6.619 + const typename Parent::Notifier* notifier = Parent::getNotifier();
6.620 + Edge it;
6.621 + for (graph.first(it); it != INVALID; graph.next(it)) {
6.622 + Parent::set(it, cmap[it]);
6.623 + }
6.624 + return *this;
6.625 + }
6.626 +
6.627 + ConstReference operator[](const Key& node) const {
6.628 + if (Parent::aNode(node)) {
6.629 + return aNodeMap[node];
6.630 + } else {
6.631 + return bNodeMap[node];
6.632 + }
6.633 + }
6.634 +
6.635 + Reference operator[](const Key& node) {
6.636 + if (Parent::aNode(node)) {
6.637 + return aNodeMap[node];
6.638 + } else {
6.639 + return bNodeMap[node];
6.640 + }
6.641 + }
6.642 +
6.643 + void set(const Key& node, const Value& value) {
6.644 + if (Parent::aNode(node)) {
6.645 + aNodeMap.set(node, value);
6.646 + } else {
6.647 + bNodeMap.set(node, value);
6.648 + }
6.649 + }
6.650 +
6.651 + class MapIt : public NodeIt {
6.652 + public:
6.653 +
6.654 + typedef NodeIt Parent;
6.655 +
6.656 + explicit MapIt(NodeMap& _map)
6.657 + : Parent(_map.graph), map(_map) {}
6.658 +
6.659 + typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
6.660 + return map[*this];
6.661 + }
6.662 +
6.663 + typename MapTraits<NodeMap>::ReturnValue operator*() {
6.664 + return map[*this];
6.665 + }
6.666 +
6.667 + void set(const Value& value) {
6.668 + map.set(*this, value);
6.669 + }
6.670 +
6.671 + private:
6.672 + NodeMap& map;
6.673 + };
6.674 +
6.675 + class ConstMapIt : public NodeIt {
6.676 + public:
6.677 +
6.678 + typedef NodeIt Parent;
6.679 +
6.680 + explicit ConstMapIt(const NodeMap& _map)
6.681 + : Parent(_map.graph), map(_map) {}
6.682 +
6.683 + typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
6.684 + return map[*this];
6.685 + }
6.686 +
6.687 + private:
6.688 + const NodeMap& map;
6.689 + };
6.690 +
6.691 + class ItemIt : public NodeIt {
6.692 + public:
6.693 +
6.694 + typedef NodeIt Parent;
6.695 +
6.696 + explicit ItemIt(const NodeMap& _map)
6.697 + : Parent(_map.graph) {}
6.698 +
6.699 + };
6.700 +
6.701 + private:
6.702 + const Graph& graph;
6.703 + ANodeMap<_Value> aNodeMap;
6.704 + BNodeMap<_Value> bNodeMap;
6.705 + };
6.706 +
6.707 +
6.708 + template <typename _Value>
6.709 + class EdgeMap
6.710 + : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
6.711 + public:
6.712 + typedef BpUGraphExtender Graph;
6.713 + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
6.714 +
6.715 + EdgeMap(const Graph& graph)
6.716 + : Parent(graph) {}
6.717 + EdgeMap(const Graph& graph, const _Value& value)
6.718 + : Parent(graph, value) {}
6.719 +
6.720 + EdgeMap& operator=(const EdgeMap& cmap) {
6.721 + return operator=<EdgeMap>(cmap);
6.722 + }
6.723 +
6.724 + template <typename CMap>
6.725 + EdgeMap& operator=(const CMap& cmap) {
6.726 + Parent::operator=(cmap);
6.727 + return *this;
6.728 + }
6.729 + };
6.730 +
6.731 + template <typename _Value>
6.732 + class UEdgeMap
6.733 + : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
6.734 + public:
6.735 + typedef BpUGraphExtender Graph;
6.736 + typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
6.737 +
6.738 + UEdgeMap(const Graph& graph)
6.739 + : Parent(graph) {}
6.740 + UEdgeMap(const Graph& graph, const _Value& value)
6.741 + : Parent(graph, value) {}
6.742 +
6.743 + UEdgeMap& operator=(const UEdgeMap& cmap) {
6.744 + return operator=<UEdgeMap>(cmap);
6.745 + }
6.746 +
6.747 + template <typename CMap>
6.748 + UEdgeMap& operator=(const CMap& cmap) {
6.749 + Parent::operator=(cmap);
6.750 + return *this;
6.751 + }
6.752 + };
6.753 +
6.754 +
6.755 + Node addANode() {
6.756 + Node node = Parent::addANode();
6.757 + getNotifier(ANode()).add(node);
6.758 + getNotifier(Node()).add(node);
6.759 + return node;
6.760 + }
6.761 +
6.762 + Node addBNode() {
6.763 + Node node = Parent::addBNode();
6.764 + getNotifier(BNode()).add(node);
6.765 + getNotifier(Node()).add(node);
6.766 + return node;
6.767 + }
6.768 +
6.769 + UEdge addEdge(const Node& source, const Node& target) {
6.770 + UEdge uedge = Parent::addEdge(source, target);
6.771 + getNotifier(UEdge()).add(uedge);
6.772 +
6.773 + std::vector<Edge> edges;
6.774 + edges.push_back(direct(uedge, true));
6.775 + edges.push_back(direct(uedge, false));
6.776 + getNotifier(Edge()).add(edges);
6.777 +
6.778 + return uedge;
6.779 + }
6.780 +
6.781 + void clear() {
6.782 + getNotifier(Edge()).clear();
6.783 + getNotifier(UEdge()).clear();
6.784 + getNotifier(Node()).clear();
6.785 + getNotifier(BNode()).clear();
6.786 + getNotifier(ANode()).clear();
6.787 + Parent::clear();
6.788 + }
6.789 +
6.790 + void erase(const Node& node) {
6.791 + UEdge uedge;
6.792 + if (Parent::aNode(node)) {
6.793 + Parent::firstFromANode(uedge, node);
6.794 + while (uedge != INVALID) {
6.795 + erase(uedge);
6.796 + Parent::firstFromANode(uedge, node);
6.797 + }
6.798 + } else {
6.799 + Parent::firstFromBNode(uedge, node);
6.800 + while (uedge != INVALID) {
6.801 + erase(uedge);
6.802 + Parent::firstFromBNode(uedge, node);
6.803 + }
6.804 + }
6.805 +
6.806 + getNotifier(Node()).erase(node);
6.807 + Parent::erase(node);
6.808 + }
6.809 +
6.810 + void erase(const UEdge& uedge) {
6.811 + std::vector<Edge> edges;
6.812 + edges.push_back(direct(uedge, true));
6.813 + edges.push_back(direct(uedge, false));
6.814 + getNotifier(Edge()).erase(edges);
6.815 + getNotifier(UEdge()).erase(uedge);
6.816 + Parent::erase(uedge);
6.817 + }
6.818 +
6.819 +
6.820 + BpUGraphExtender() {
6.821 + anode_notifier.setContainer(*this);
6.822 + bnode_notifier.setContainer(*this);
6.823 + node_notifier.setContainer(*this);
6.824 + edge_notifier.setContainer(*this);
6.825 + uedge_notifier.setContainer(*this);
6.826 + }
6.827 +
6.828 + ~BpUGraphExtender() {
6.829 + uedge_notifier.clear();
6.830 + edge_notifier.clear();
6.831 + node_notifier.clear();
6.832 + anode_notifier.clear();
6.833 + bnode_notifier.clear();
6.834 + }
6.835 +
6.836 +
6.837 + };
6.838 +
6.839 +}
6.840 +
6.841 +#endif
7.1 --- a/lemon/bits/graph_extender.h Wed Jun 28 16:27:44 2006 +0000
7.2 +++ b/lemon/bits/graph_extender.h Fri Jun 30 12:14:36 2006 +0000
7.3 @@ -20,14 +20,10 @@
7.4 #define LEMON_BITS_GRAPH_EXTENDER_H
7.5
7.6 #include <lemon/bits/invalid.h>
7.7 -#include <lemon/error.h>
7.8
7.9 #include <lemon/bits/map_extender.h>
7.10 #include <lemon/bits/default_map.h>
7.11
7.12 -#include <lemon/concept_check.h>
7.13 -#include <lemon/concept/maps.h>
7.14 -
7.15 ///\ingroup graphbits
7.16 ///\file
7.17 ///\brief Extenders for the graph types
7.18 @@ -318,1212 +314,6 @@
7.19 }
7.20 };
7.21
7.22 - /// \ingroup graphbits
7.23 - ///
7.24 - /// \brief Extender for the UGraphs
7.25 - template <typename Base>
7.26 - class UGraphExtender : public Base {
7.27 - public:
7.28 -
7.29 - typedef Base Parent;
7.30 - typedef UGraphExtender Graph;
7.31 -
7.32 - typedef typename Parent::Node Node;
7.33 - typedef typename Parent::Edge Edge;
7.34 - typedef typename Parent::UEdge UEdge;
7.35 -
7.36 - // UGraph extension
7.37 -
7.38 - int maxId(Node) const {
7.39 - return Parent::maxNodeId();
7.40 - }
7.41 -
7.42 - int maxId(Edge) const {
7.43 - return Parent::maxEdgeId();
7.44 - }
7.45 -
7.46 - int maxId(UEdge) const {
7.47 - return Parent::maxUEdgeId();
7.48 - }
7.49 -
7.50 - Node fromId(int id, Node) const {
7.51 - return Parent::nodeFromId(id);
7.52 - }
7.53 -
7.54 - Edge fromId(int id, Edge) const {
7.55 - return Parent::edgeFromId(id);
7.56 - }
7.57 -
7.58 - UEdge fromId(int id, UEdge) const {
7.59 - return Parent::uEdgeFromId(id);
7.60 - }
7.61 -
7.62 - Node oppositeNode(const Node &n, const UEdge &e) const {
7.63 - if( n == Parent::source(e))
7.64 - return Parent::target(e);
7.65 - else if( n == Parent::target(e))
7.66 - return Parent::source(e);
7.67 - else
7.68 - return INVALID;
7.69 - }
7.70 -
7.71 - Edge oppositeEdge(const Edge &e) const {
7.72 - return Parent::direct(e, !Parent::direction(e));
7.73 - }
7.74 -
7.75 - using Parent::direct;
7.76 - Edge direct(const UEdge &ue, const Node &s) const {
7.77 - return Parent::direct(ue, Parent::source(ue) == s);
7.78 - }
7.79 -
7.80 - // Alterable extension
7.81 -
7.82 - typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
7.83 - typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
7.84 - typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
7.85 -
7.86 -
7.87 - protected:
7.88 -
7.89 - mutable NodeNotifier node_notifier;
7.90 - mutable EdgeNotifier edge_notifier;
7.91 - mutable UEdgeNotifier uedge_notifier;
7.92 -
7.93 - public:
7.94 -
7.95 - NodeNotifier& getNotifier(Node) const {
7.96 - return node_notifier;
7.97 - }
7.98 -
7.99 - EdgeNotifier& getNotifier(Edge) const {
7.100 - return edge_notifier;
7.101 - }
7.102 -
7.103 - UEdgeNotifier& getNotifier(UEdge) const {
7.104 - return uedge_notifier;
7.105 - }
7.106 -
7.107 -
7.108 -
7.109 - class NodeIt : public Node {
7.110 - const Graph* graph;
7.111 - public:
7.112 -
7.113 - NodeIt() {}
7.114 -
7.115 - NodeIt(Invalid i) : Node(i) { }
7.116 -
7.117 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
7.118 - _graph.first(static_cast<Node&>(*this));
7.119 - }
7.120 -
7.121 - NodeIt(const Graph& _graph, const Node& node)
7.122 - : Node(node), graph(&_graph) {}
7.123 -
7.124 - NodeIt& operator++() {
7.125 - graph->next(*this);
7.126 - return *this;
7.127 - }
7.128 -
7.129 - };
7.130 -
7.131 -
7.132 - class EdgeIt : public Edge {
7.133 - const Graph* graph;
7.134 - public:
7.135 -
7.136 - EdgeIt() { }
7.137 -
7.138 - EdgeIt(Invalid i) : Edge(i) { }
7.139 -
7.140 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
7.141 - _graph.first(static_cast<Edge&>(*this));
7.142 - }
7.143 -
7.144 - EdgeIt(const Graph& _graph, const Edge& e) :
7.145 - Edge(e), graph(&_graph) { }
7.146 -
7.147 - EdgeIt& operator++() {
7.148 - graph->next(*this);
7.149 - return *this;
7.150 - }
7.151 -
7.152 - };
7.153 -
7.154 -
7.155 - class OutEdgeIt : public Edge {
7.156 - const Graph* graph;
7.157 - public:
7.158 -
7.159 - OutEdgeIt() { }
7.160 -
7.161 - OutEdgeIt(Invalid i) : Edge(i) { }
7.162 -
7.163 - OutEdgeIt(const Graph& _graph, const Node& node)
7.164 - : graph(&_graph) {
7.165 - _graph.firstOut(*this, node);
7.166 - }
7.167 -
7.168 - OutEdgeIt(const Graph& _graph, const Edge& edge)
7.169 - : Edge(edge), graph(&_graph) {}
7.170 -
7.171 - OutEdgeIt& operator++() {
7.172 - graph->nextOut(*this);
7.173 - return *this;
7.174 - }
7.175 -
7.176 - };
7.177 -
7.178 -
7.179 - class InEdgeIt : public Edge {
7.180 - const Graph* graph;
7.181 - public:
7.182 -
7.183 - InEdgeIt() { }
7.184 -
7.185 - InEdgeIt(Invalid i) : Edge(i) { }
7.186 -
7.187 - InEdgeIt(const Graph& _graph, const Node& node)
7.188 - : graph(&_graph) {
7.189 - _graph.firstIn(*this, node);
7.190 - }
7.191 -
7.192 - InEdgeIt(const Graph& _graph, const Edge& edge) :
7.193 - Edge(edge), graph(&_graph) {}
7.194 -
7.195 - InEdgeIt& operator++() {
7.196 - graph->nextIn(*this);
7.197 - return *this;
7.198 - }
7.199 -
7.200 - };
7.201 -
7.202 -
7.203 - class UEdgeIt : public Parent::UEdge {
7.204 - const Graph* graph;
7.205 - public:
7.206 -
7.207 - UEdgeIt() { }
7.208 -
7.209 - UEdgeIt(Invalid i) : UEdge(i) { }
7.210 -
7.211 - explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
7.212 - _graph.first(static_cast<UEdge&>(*this));
7.213 - }
7.214 -
7.215 - UEdgeIt(const Graph& _graph, const UEdge& e) :
7.216 - UEdge(e), graph(&_graph) { }
7.217 -
7.218 - UEdgeIt& operator++() {
7.219 - graph->next(*this);
7.220 - return *this;
7.221 - }
7.222 -
7.223 - };
7.224 -
7.225 - class IncEdgeIt : public Parent::UEdge {
7.226 - friend class UGraphExtender;
7.227 - const Graph* graph;
7.228 - bool direction;
7.229 - public:
7.230 -
7.231 - IncEdgeIt() { }
7.232 -
7.233 - IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
7.234 -
7.235 - IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
7.236 - _graph.firstInc(*this, direction, n);
7.237 - }
7.238 -
7.239 - IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
7.240 - : graph(&_graph), UEdge(ue) {
7.241 - direction = (_graph.source(ue) == n);
7.242 - }
7.243 -
7.244 - IncEdgeIt& operator++() {
7.245 - graph->nextInc(*this, direction);
7.246 - return *this;
7.247 - }
7.248 - };
7.249 -
7.250 - /// \brief Base node of the iterator
7.251 - ///
7.252 - /// Returns the base node (ie. the source in this case) of the iterator
7.253 - Node baseNode(const OutEdgeIt &e) const {
7.254 - return Parent::source((Edge)e);
7.255 - }
7.256 - /// \brief Running node of the iterator
7.257 - ///
7.258 - /// Returns the running node (ie. the target in this case) of the
7.259 - /// iterator
7.260 - Node runningNode(const OutEdgeIt &e) const {
7.261 - return Parent::target((Edge)e);
7.262 - }
7.263 -
7.264 - /// \brief Base node of the iterator
7.265 - ///
7.266 - /// Returns the base node (ie. the target in this case) of the iterator
7.267 - Node baseNode(const InEdgeIt &e) const {
7.268 - return Parent::target((Edge)e);
7.269 - }
7.270 - /// \brief Running node of the iterator
7.271 - ///
7.272 - /// Returns the running node (ie. the source in this case) of the
7.273 - /// iterator
7.274 - Node runningNode(const InEdgeIt &e) const {
7.275 - return Parent::source((Edge)e);
7.276 - }
7.277 -
7.278 - /// Base node of the iterator
7.279 - ///
7.280 - /// Returns the base node of the iterator
7.281 - Node baseNode(const IncEdgeIt &e) const {
7.282 - return e.direction ? source(e) : target(e);
7.283 - }
7.284 - /// Running node of the iterator
7.285 - ///
7.286 - /// Returns the running node of the iterator
7.287 - Node runningNode(const IncEdgeIt &e) const {
7.288 - return e.direction ? target(e) : source(e);
7.289 - }
7.290 -
7.291 - // Mappable extension
7.292 -
7.293 - template <typename _Value>
7.294 - class NodeMap
7.295 - : public MapExtender<DefaultMap<Graph, Node, _Value> > {
7.296 - public:
7.297 - typedef UGraphExtender Graph;
7.298 - typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
7.299 -
7.300 - NodeMap(const Graph& graph)
7.301 - : Parent(graph) {}
7.302 - NodeMap(const Graph& graph, const _Value& value)
7.303 - : Parent(graph, value) {}
7.304 -
7.305 - NodeMap& operator=(const NodeMap& cmap) {
7.306 - return operator=<NodeMap>(cmap);
7.307 - }
7.308 -
7.309 - template <typename CMap>
7.310 - NodeMap& operator=(const CMap& cmap) {
7.311 - Parent::operator=(cmap);
7.312 - return *this;
7.313 - }
7.314 -
7.315 - };
7.316 -
7.317 - template <typename _Value>
7.318 - class EdgeMap
7.319 - : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
7.320 - public:
7.321 - typedef UGraphExtender Graph;
7.322 - typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.323 -
7.324 - EdgeMap(const Graph& graph)
7.325 - : Parent(graph) {}
7.326 - EdgeMap(const Graph& graph, const _Value& value)
7.327 - : Parent(graph, value) {}
7.328 -
7.329 - EdgeMap& operator=(const EdgeMap& cmap) {
7.330 - return operator=<EdgeMap>(cmap);
7.331 - }
7.332 -
7.333 - template <typename CMap>
7.334 - EdgeMap& operator=(const CMap& cmap) {
7.335 - Parent::operator=(cmap);
7.336 - return *this;
7.337 - }
7.338 - };
7.339 -
7.340 -
7.341 - template <typename _Value>
7.342 - class UEdgeMap
7.343 - : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
7.344 - public:
7.345 - typedef UGraphExtender Graph;
7.346 - typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
7.347 -
7.348 - UEdgeMap(const Graph& graph)
7.349 - : Parent(graph) {}
7.350 -
7.351 - UEdgeMap(const Graph& graph, const _Value& value)
7.352 - : Parent(graph, value) {}
7.353 -
7.354 - UEdgeMap& operator=(const UEdgeMap& cmap) {
7.355 - return operator=<UEdgeMap>(cmap);
7.356 - }
7.357 -
7.358 - template <typename CMap>
7.359 - UEdgeMap& operator=(const CMap& cmap) {
7.360 - Parent::operator=(cmap);
7.361 - return *this;
7.362 - }
7.363 -
7.364 - };
7.365 -
7.366 - // Alteration extension
7.367 -
7.368 - Node addNode() {
7.369 - Node node = Parent::addNode();
7.370 - getNotifier(Node()).add(node);
7.371 - return node;
7.372 - }
7.373 -
7.374 - UEdge addEdge(const Node& from, const Node& to) {
7.375 - UEdge uedge = Parent::addEdge(from, to);
7.376 - getNotifier(UEdge()).add(uedge);
7.377 - getNotifier(Edge()).add(Parent::direct(uedge, true));
7.378 - getNotifier(Edge()).add(Parent::direct(uedge, false));
7.379 - return uedge;
7.380 - }
7.381 -
7.382 - void clear() {
7.383 - getNotifier(Edge()).clear();
7.384 - getNotifier(UEdge()).clear();
7.385 - getNotifier(Node()).clear();
7.386 - Parent::clear();
7.387 - }
7.388 -
7.389 - void erase(const Node& node) {
7.390 - Edge edge;
7.391 - Parent::firstOut(edge, node);
7.392 - while (edge != INVALID ) {
7.393 - erase(edge);
7.394 - Parent::firstOut(edge, node);
7.395 - }
7.396 -
7.397 - Parent::firstIn(edge, node);
7.398 - while (edge != INVALID ) {
7.399 - erase(edge);
7.400 - Parent::firstIn(edge, node);
7.401 - }
7.402 -
7.403 - getNotifier(Node()).erase(node);
7.404 - Parent::erase(node);
7.405 - }
7.406 -
7.407 - void erase(const UEdge& uedge) {
7.408 - getNotifier(Edge()).erase(Parent::direct(uedge, true));
7.409 - getNotifier(Edge()).erase(Parent::direct(uedge, false));
7.410 - getNotifier(UEdge()).erase(uedge);
7.411 - Parent::erase(uedge);
7.412 - }
7.413 -
7.414 - UGraphExtender() {
7.415 - node_notifier.setContainer(*this);
7.416 - edge_notifier.setContainer(*this);
7.417 - uedge_notifier.setContainer(*this);
7.418 - }
7.419 -
7.420 - ~UGraphExtender() {
7.421 - uedge_notifier.clear();
7.422 - edge_notifier.clear();
7.423 - node_notifier.clear();
7.424 - }
7.425 -
7.426 - };
7.427 -
7.428 - /// \ingroup graphbits
7.429 - ///
7.430 - /// \brief Extender for the BpUGraphs
7.431 - template <typename Base>
7.432 - class BpUGraphExtender : public Base {
7.433 - public:
7.434 - typedef Base Parent;
7.435 - typedef BpUGraphExtender Graph;
7.436 -
7.437 - typedef typename Parent::Node Node;
7.438 - typedef typename Parent::UEdge UEdge;
7.439 -
7.440 -
7.441 - using Parent::first;
7.442 - using Parent::next;
7.443 -
7.444 - using Parent::id;
7.445 -
7.446 - class ANode : public Node {
7.447 - friend class BpUGraphExtender;
7.448 - public:
7.449 - ANode() {}
7.450 - ANode(const Node& node) : Node(node) {
7.451 - LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
7.452 - typename Parent::NodeSetError());
7.453 - }
7.454 - ANode(Invalid) : Node(INVALID) {}
7.455 - };
7.456 -
7.457 - void first(ANode& node) const {
7.458 - Parent::firstANode(static_cast<Node&>(node));
7.459 - }
7.460 - void next(ANode& node) const {
7.461 - Parent::nextANode(static_cast<Node&>(node));
7.462 - }
7.463 -
7.464 - int id(const ANode& node) const {
7.465 - return Parent::aNodeId(node);
7.466 - }
7.467 -
7.468 - class BNode : public Node {
7.469 - friend class BpUGraphExtender;
7.470 - public:
7.471 - BNode() {}
7.472 - BNode(const Node& node) : Node(node) {
7.473 - LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
7.474 - typename Parent::NodeSetError());
7.475 - }
7.476 - BNode(Invalid) : Node(INVALID) {}
7.477 - };
7.478 -
7.479 - void first(BNode& node) const {
7.480 - Parent::firstBNode(static_cast<Node&>(node));
7.481 - }
7.482 - void next(BNode& node) const {
7.483 - Parent::nextBNode(static_cast<Node&>(node));
7.484 - }
7.485 -
7.486 - int id(const BNode& node) const {
7.487 - return Parent::aNodeId(node);
7.488 - }
7.489 -
7.490 - Node source(const UEdge& edge) const {
7.491 - return aNode(edge);
7.492 - }
7.493 - Node target(const UEdge& edge) const {
7.494 - return bNode(edge);
7.495 - }
7.496 -
7.497 - void firstInc(UEdge& edge, bool& direction, const Node& node) const {
7.498 - if (Parent::aNode(node)) {
7.499 - Parent::firstFromANode(edge, node);
7.500 - direction = true;
7.501 - } else {
7.502 - Parent::firstFromBNode(edge, node);
7.503 - direction = static_cast<UEdge&>(edge) == INVALID;
7.504 - }
7.505 - }
7.506 - void nextInc(UEdge& edge, bool& direction) const {
7.507 - if (direction) {
7.508 - Parent::nextFromANode(edge);
7.509 - } else {
7.510 - Parent::nextFromBNode(edge);
7.511 - if (edge == INVALID) direction = true;
7.512 - }
7.513 - }
7.514 -
7.515 - class Edge : public UEdge {
7.516 - friend class BpUGraphExtender;
7.517 - protected:
7.518 - bool forward;
7.519 -
7.520 - Edge(const UEdge& edge, bool _forward)
7.521 - : UEdge(edge), forward(_forward) {}
7.522 -
7.523 - public:
7.524 - Edge() {}
7.525 - Edge (Invalid) : UEdge(INVALID), forward(true) {}
7.526 - bool operator==(const Edge& i) const {
7.527 - return UEdge::operator==(i) && forward == i.forward;
7.528 - }
7.529 - bool operator!=(const Edge& i) const {
7.530 - return UEdge::operator!=(i) || forward != i.forward;
7.531 - }
7.532 - bool operator<(const Edge& i) const {
7.533 - return UEdge::operator<(i) ||
7.534 - (!(i.forward<forward) && UEdge(*this)<UEdge(i));
7.535 - }
7.536 - };
7.537 -
7.538 - void first(Edge& edge) const {
7.539 - Parent::first(static_cast<UEdge&>(edge));
7.540 - edge.forward = true;
7.541 - }
7.542 -
7.543 - void next(Edge& edge) const {
7.544 - if (!edge.forward) {
7.545 - Parent::next(static_cast<UEdge&>(edge));
7.546 - }
7.547 - edge.forward = !edge.forward;
7.548 - }
7.549 -
7.550 - void firstOut(Edge& edge, const Node& node) const {
7.551 - if (Parent::aNode(node)) {
7.552 - Parent::firstFromANode(edge, node);
7.553 - edge.forward = true;
7.554 - } else {
7.555 - Parent::firstFromBNode(edge, node);
7.556 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.557 - }
7.558 - }
7.559 - void nextOut(Edge& edge) const {
7.560 - if (edge.forward) {
7.561 - Parent::nextFromANode(edge);
7.562 - } else {
7.563 - Parent::nextFromBNode(edge);
7.564 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.565 - }
7.566 - }
7.567 -
7.568 - void firstIn(Edge& edge, const Node& node) const {
7.569 - if (Parent::bNode(node)) {
7.570 - Parent::firstFromBNode(edge, node);
7.571 - edge.forward = true;
7.572 - } else {
7.573 - Parent::firstFromANode(edge, node);
7.574 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.575 - }
7.576 - }
7.577 - void nextIn(Edge& edge) const {
7.578 - if (edge.forward) {
7.579 - Parent::nextFromBNode(edge);
7.580 - } else {
7.581 - Parent::nextFromANode(edge);
7.582 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.583 - }
7.584 - }
7.585 -
7.586 - Node source(const Edge& edge) const {
7.587 - return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
7.588 - }
7.589 - Node target(const Edge& edge) const {
7.590 - return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
7.591 - }
7.592 -
7.593 - int id(const Edge& edge) const {
7.594 - return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
7.595 - (edge.forward ? 0 : 1);
7.596 - }
7.597 - Edge edgeFromId(int id) const {
7.598 - return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
7.599 - }
7.600 - int maxEdgeId() const {
7.601 - return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
7.602 - }
7.603 -
7.604 - bool direction(const Edge& edge) const {
7.605 - return edge.forward;
7.606 - }
7.607 -
7.608 - Edge direct(const UEdge& edge, bool direction) const {
7.609 - return Edge(edge, direction);
7.610 - }
7.611 -
7.612 - int edgeNum() const {
7.613 - return 2 * Parent::uEdgeNum();
7.614 - }
7.615 -
7.616 - int uEdgeNum() const {
7.617 - return Parent::uEdgeNum();
7.618 - }
7.619 -
7.620 - Node oppositeNode(const UEdge& edge, const Node& node) const {
7.621 - return source(edge) == node ?
7.622 - target(edge) : source(edge);
7.623 - }
7.624 -
7.625 - Edge direct(const UEdge& edge, const Node& node) const {
7.626 - return Edge(edge, node == Parent::source(edge));
7.627 - }
7.628 -
7.629 - Edge oppositeEdge(const Edge& edge) const {
7.630 - return Parent::direct(edge, !Parent::direction(edge));
7.631 - }
7.632 -
7.633 -
7.634 - int maxId(Node) const {
7.635 - return Parent::maxNodeId();
7.636 - }
7.637 - int maxId(BNode) const {
7.638 - return Parent::maxBNodeId();
7.639 - }
7.640 - int maxId(ANode) const {
7.641 - return Parent::maxANodeId();
7.642 - }
7.643 - int maxId(Edge) const {
7.644 - return maxEdgeId();
7.645 - }
7.646 - int maxId(UEdge) const {
7.647 - return Parent::maxUEdgeId();
7.648 - }
7.649 -
7.650 -
7.651 - Node fromId(int id, Node) const {
7.652 - return Parent::nodeFromId(id);
7.653 - }
7.654 - ANode fromId(int id, ANode) const {
7.655 - return Parent::fromANodeId(id);
7.656 - }
7.657 - BNode fromId(int id, BNode) const {
7.658 - return Parent::fromBNodeId(id);
7.659 - }
7.660 - Edge fromId(int id, Edge) const {
7.661 - return Parent::edgeFromId(id);
7.662 - }
7.663 - UEdge fromId(int id, UEdge) const {
7.664 - return Parent::uEdgeFromId(id);
7.665 - }
7.666 -
7.667 - typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
7.668 - typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
7.669 - typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
7.670 - typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
7.671 - typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
7.672 -
7.673 - protected:
7.674 -
7.675 - mutable ANodeNotifier anode_notifier;
7.676 - mutable BNodeNotifier bnode_notifier;
7.677 - mutable NodeNotifier node_notifier;
7.678 - mutable EdgeNotifier edge_notifier;
7.679 - mutable UEdgeNotifier uedge_notifier;
7.680 -
7.681 - public:
7.682 -
7.683 - NodeNotifier& getNotifier(Node) const {
7.684 - return node_notifier;
7.685 - }
7.686 -
7.687 - ANodeNotifier& getNotifier(ANode) const {
7.688 - return anode_notifier;
7.689 - }
7.690 -
7.691 - BNodeNotifier& getNotifier(BNode) const {
7.692 - return bnode_notifier;
7.693 - }
7.694 -
7.695 - EdgeNotifier& getNotifier(Edge) const {
7.696 - return edge_notifier;
7.697 - }
7.698 -
7.699 - UEdgeNotifier& getNotifier(UEdge) const {
7.700 - return uedge_notifier;
7.701 - }
7.702 -
7.703 - class NodeIt : public Node {
7.704 - const Graph* graph;
7.705 - public:
7.706 -
7.707 - NodeIt() { }
7.708 -
7.709 - NodeIt(Invalid i) : Node(INVALID) { }
7.710 -
7.711 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
7.712 - graph->first(static_cast<Node&>(*this));
7.713 - }
7.714 -
7.715 - NodeIt(const Graph& _graph, const Node& node)
7.716 - : Node(node), graph(&_graph) { }
7.717 -
7.718 - NodeIt& operator++() {
7.719 - graph->next(*this);
7.720 - return *this;
7.721 - }
7.722 -
7.723 - };
7.724 -
7.725 - class ANodeIt : public Node {
7.726 - friend class BpUGraphExtender;
7.727 - const Graph* graph;
7.728 - public:
7.729 -
7.730 - ANodeIt() { }
7.731 -
7.732 - ANodeIt(Invalid i) : Node(INVALID) { }
7.733 -
7.734 - explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
7.735 - graph->firstANode(static_cast<Node&>(*this));
7.736 - }
7.737 -
7.738 - ANodeIt(const Graph& _graph, const Node& node)
7.739 - : Node(node), graph(&_graph) {}
7.740 -
7.741 - ANodeIt& operator++() {
7.742 - graph->nextANode(*this);
7.743 - return *this;
7.744 - }
7.745 - };
7.746 -
7.747 - class BNodeIt : public Node {
7.748 - friend class BpUGraphExtender;
7.749 - const Graph* graph;
7.750 - public:
7.751 -
7.752 - BNodeIt() { }
7.753 -
7.754 - BNodeIt(Invalid i) : Node(INVALID) { }
7.755 -
7.756 - explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
7.757 - graph->firstBNode(static_cast<Node&>(*this));
7.758 - }
7.759 -
7.760 - BNodeIt(const Graph& _graph, const Node& node)
7.761 - : Node(node), graph(&_graph) {}
7.762 -
7.763 - BNodeIt& operator++() {
7.764 - graph->nextBNode(*this);
7.765 - return *this;
7.766 - }
7.767 - };
7.768 -
7.769 - class EdgeIt : public Edge {
7.770 - friend class BpUGraphExtender;
7.771 - const Graph* graph;
7.772 - public:
7.773 -
7.774 - EdgeIt() { }
7.775 -
7.776 - EdgeIt(Invalid i) : Edge(INVALID) { }
7.777 -
7.778 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
7.779 - graph->first(static_cast<Edge&>(*this));
7.780 - }
7.781 -
7.782 - EdgeIt(const Graph& _graph, const Edge& edge)
7.783 - : Edge(edge), graph(&_graph) { }
7.784 -
7.785 - EdgeIt& operator++() {
7.786 - graph->next(*this);
7.787 - return *this;
7.788 - }
7.789 -
7.790 - };
7.791 -
7.792 - class UEdgeIt : public UEdge {
7.793 - friend class BpUGraphExtender;
7.794 - const Graph* graph;
7.795 - public:
7.796 -
7.797 - UEdgeIt() { }
7.798 -
7.799 - UEdgeIt(Invalid i) : UEdge(INVALID) { }
7.800 -
7.801 - explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
7.802 - graph->first(static_cast<UEdge&>(*this));
7.803 - }
7.804 -
7.805 - UEdgeIt(const Graph& _graph, const UEdge& edge)
7.806 - : UEdge(edge), graph(&_graph) { }
7.807 -
7.808 - UEdgeIt& operator++() {
7.809 - graph->next(*this);
7.810 - return *this;
7.811 - }
7.812 - };
7.813 -
7.814 - class OutEdgeIt : public Edge {
7.815 - friend class BpUGraphExtender;
7.816 - const Graph* graph;
7.817 - public:
7.818 -
7.819 - OutEdgeIt() { }
7.820 -
7.821 - OutEdgeIt(Invalid i) : Edge(i) { }
7.822 -
7.823 - OutEdgeIt(const Graph& _graph, const Node& node)
7.824 - : graph(&_graph) {
7.825 - graph->firstOut(*this, node);
7.826 - }
7.827 -
7.828 - OutEdgeIt(const Graph& _graph, const Edge& edge)
7.829 - : Edge(edge), graph(&_graph) {}
7.830 -
7.831 - OutEdgeIt& operator++() {
7.832 - graph->nextOut(*this);
7.833 - return *this;
7.834 - }
7.835 -
7.836 - };
7.837 -
7.838 -
7.839 - class InEdgeIt : public Edge {
7.840 - friend class BpUGraphExtender;
7.841 - const Graph* graph;
7.842 - public:
7.843 -
7.844 - InEdgeIt() { }
7.845 -
7.846 - InEdgeIt(Invalid i) : Edge(i) { }
7.847 -
7.848 - InEdgeIt(const Graph& _graph, const Node& node)
7.849 - : graph(&_graph) {
7.850 - graph->firstIn(*this, node);
7.851 - }
7.852 -
7.853 - InEdgeIt(const Graph& _graph, const Edge& edge) :
7.854 - Edge(edge), graph(&_graph) {}
7.855 -
7.856 - InEdgeIt& operator++() {
7.857 - graph->nextIn(*this);
7.858 - return *this;
7.859 - }
7.860 -
7.861 - };
7.862 -
7.863 - /// \brief Base node of the iterator
7.864 - ///
7.865 - /// Returns the base node (ie. the source in this case) of the iterator
7.866 - Node baseNode(const OutEdgeIt &e) const {
7.867 - return Parent::source((Edge&)e);
7.868 - }
7.869 - /// \brief Running node of the iterator
7.870 - ///
7.871 - /// Returns the running node (ie. the target in this case) of the
7.872 - /// iterator
7.873 - Node runningNode(const OutEdgeIt &e) const {
7.874 - return Parent::target((Edge&)e);
7.875 - }
7.876 -
7.877 - /// \brief Base node of the iterator
7.878 - ///
7.879 - /// Returns the base node (ie. the target in this case) of the iterator
7.880 - Node baseNode(const InEdgeIt &e) const {
7.881 - return Parent::target((Edge&)e);
7.882 - }
7.883 - /// \brief Running node of the iterator
7.884 - ///
7.885 - /// Returns the running node (ie. the source in this case) of the
7.886 - /// iterator
7.887 - Node runningNode(const InEdgeIt &e) const {
7.888 - return Parent::source((Edge&)e);
7.889 - }
7.890 -
7.891 - class IncEdgeIt : public Parent::UEdge {
7.892 - friend class BpUGraphExtender;
7.893 - const Graph* graph;
7.894 - bool direction;
7.895 - public:
7.896 -
7.897 - IncEdgeIt() { }
7.898 -
7.899 - IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
7.900 -
7.901 - IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
7.902 - graph->firstInc(*this, direction, n);
7.903 - }
7.904 -
7.905 - IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
7.906 - : graph(&_graph), UEdge(ue) {
7.907 - direction = (graph->source(ue) == n);
7.908 - }
7.909 -
7.910 - IncEdgeIt& operator++() {
7.911 - graph->nextInc(*this, direction);
7.912 - return *this;
7.913 - }
7.914 - };
7.915 -
7.916 -
7.917 - /// Base node of the iterator
7.918 - ///
7.919 - /// Returns the base node of the iterator
7.920 - Node baseNode(const IncEdgeIt &e) const {
7.921 - return e.direction ? source(e) : target(e);
7.922 - }
7.923 -
7.924 - /// Running node of the iterator
7.925 - ///
7.926 - /// Returns the running node of the iterator
7.927 - Node runningNode(const IncEdgeIt &e) const {
7.928 - return e.direction ? target(e) : source(e);
7.929 - }
7.930 -
7.931 - template <typename _Value>
7.932 - class ANodeMap
7.933 - : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
7.934 - public:
7.935 - typedef BpUGraphExtender Graph;
7.936 - typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
7.937 -
7.938 - ANodeMap(const Graph& graph)
7.939 - : Parent(graph) {}
7.940 - ANodeMap(const Graph& graph, const _Value& value)
7.941 - : Parent(graph, value) {}
7.942 -
7.943 - ANodeMap& operator=(const ANodeMap& cmap) {
7.944 - return operator=<ANodeMap>(cmap);
7.945 - }
7.946 -
7.947 - template <typename CMap>
7.948 - ANodeMap& operator=(const CMap& cmap) {
7.949 - Parent::operator=(cmap);
7.950 - return *this;
7.951 - }
7.952 -
7.953 - };
7.954 -
7.955 - template <typename _Value>
7.956 - class BNodeMap
7.957 - : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
7.958 - public:
7.959 - typedef BpUGraphExtender Graph;
7.960 - typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
7.961 -
7.962 - BNodeMap(const Graph& graph)
7.963 - : Parent(graph) {}
7.964 - BNodeMap(const Graph& graph, const _Value& value)
7.965 - : Parent(graph, value) {}
7.966 -
7.967 - BNodeMap& operator=(const BNodeMap& cmap) {
7.968 - return operator=<BNodeMap>(cmap);
7.969 - }
7.970 -
7.971 - template <typename CMap>
7.972 - BNodeMap& operator=(const CMap& cmap) {
7.973 - Parent::operator=(cmap);
7.974 - return *this;
7.975 - }
7.976 -
7.977 - };
7.978 -
7.979 - public:
7.980 -
7.981 - template <typename _Value>
7.982 - class NodeMap {
7.983 - public:
7.984 - typedef BpUGraphExtender Graph;
7.985 -
7.986 - typedef Node Key;
7.987 - typedef _Value Value;
7.988 -
7.989 - /// The reference type of the map;
7.990 - typedef typename ANodeMap<_Value>::Reference Reference;
7.991 - /// The const reference type of the map;
7.992 - typedef typename ANodeMap<_Value>::ConstReference ConstReference;
7.993 -
7.994 - typedef True ReferenceMapTag;
7.995 -
7.996 - NodeMap(const Graph& _graph)
7.997 - : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
7.998 - NodeMap(const Graph& _graph, const _Value& _value)
7.999 - : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
7.1000 -
7.1001 - NodeMap& operator=(const NodeMap& cmap) {
7.1002 - return operator=<NodeMap>(cmap);
7.1003 - }
7.1004 -
7.1005 - template <typename CMap>
7.1006 - NodeMap& operator=(const CMap& cmap) {
7.1007 - checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.1008 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.1009 - Edge it;
7.1010 - for (graph.first(it); it != INVALID; graph.next(it)) {
7.1011 - Parent::set(it, cmap[it]);
7.1012 - }
7.1013 - return *this;
7.1014 - }
7.1015 -
7.1016 - ConstReference operator[](const Key& node) const {
7.1017 - if (Parent::aNode(node)) {
7.1018 - return aNodeMap[node];
7.1019 - } else {
7.1020 - return bNodeMap[node];
7.1021 - }
7.1022 - }
7.1023 -
7.1024 - Reference operator[](const Key& node) {
7.1025 - if (Parent::aNode(node)) {
7.1026 - return aNodeMap[node];
7.1027 - } else {
7.1028 - return bNodeMap[node];
7.1029 - }
7.1030 - }
7.1031 -
7.1032 - void set(const Key& node, const Value& value) {
7.1033 - if (Parent::aNode(node)) {
7.1034 - aNodeMap.set(node, value);
7.1035 - } else {
7.1036 - bNodeMap.set(node, value);
7.1037 - }
7.1038 - }
7.1039 -
7.1040 - class MapIt : public NodeIt {
7.1041 - public:
7.1042 -
7.1043 - typedef NodeIt Parent;
7.1044 -
7.1045 - explicit MapIt(NodeMap& _map)
7.1046 - : Parent(_map.graph), map(_map) {}
7.1047 -
7.1048 - typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
7.1049 - return map[*this];
7.1050 - }
7.1051 -
7.1052 - typename MapTraits<NodeMap>::ReturnValue operator*() {
7.1053 - return map[*this];
7.1054 - }
7.1055 -
7.1056 - void set(const Value& value) {
7.1057 - map.set(*this, value);
7.1058 - }
7.1059 -
7.1060 - private:
7.1061 - NodeMap& map;
7.1062 - };
7.1063 -
7.1064 - class ConstMapIt : public NodeIt {
7.1065 - public:
7.1066 -
7.1067 - typedef NodeIt Parent;
7.1068 -
7.1069 - explicit ConstMapIt(const NodeMap& _map)
7.1070 - : Parent(_map.graph), map(_map) {}
7.1071 -
7.1072 - typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
7.1073 - return map[*this];
7.1074 - }
7.1075 -
7.1076 - private:
7.1077 - const NodeMap& map;
7.1078 - };
7.1079 -
7.1080 - class ItemIt : public NodeIt {
7.1081 - public:
7.1082 -
7.1083 - typedef NodeIt Parent;
7.1084 -
7.1085 - explicit ItemIt(const NodeMap& _map)
7.1086 - : Parent(_map.graph) {}
7.1087 -
7.1088 - };
7.1089 -
7.1090 - private:
7.1091 - const Graph& graph;
7.1092 - ANodeMap<_Value> aNodeMap;
7.1093 - BNodeMap<_Value> bNodeMap;
7.1094 - };
7.1095 -
7.1096 -
7.1097 - template <typename _Value>
7.1098 - class EdgeMap
7.1099 - : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
7.1100 - public:
7.1101 - typedef BpUGraphExtender Graph;
7.1102 - typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.1103 -
7.1104 - EdgeMap(const Graph& graph)
7.1105 - : Parent(graph) {}
7.1106 - EdgeMap(const Graph& graph, const _Value& value)
7.1107 - : Parent(graph, value) {}
7.1108 -
7.1109 - EdgeMap& operator=(const EdgeMap& cmap) {
7.1110 - return operator=<EdgeMap>(cmap);
7.1111 - }
7.1112 -
7.1113 - template <typename CMap>
7.1114 - EdgeMap& operator=(const CMap& cmap) {
7.1115 - Parent::operator=(cmap);
7.1116 - return *this;
7.1117 - }
7.1118 - };
7.1119 -
7.1120 - template <typename _Value>
7.1121 - class UEdgeMap
7.1122 - : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
7.1123 - public:
7.1124 - typedef BpUGraphExtender Graph;
7.1125 - typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
7.1126 -
7.1127 - UEdgeMap(const Graph& graph)
7.1128 - : Parent(graph) {}
7.1129 - UEdgeMap(const Graph& graph, const _Value& value)
7.1130 - : Parent(graph, value) {}
7.1131 -
7.1132 - UEdgeMap& operator=(const UEdgeMap& cmap) {
7.1133 - return operator=<UEdgeMap>(cmap);
7.1134 - }
7.1135 -
7.1136 - template <typename CMap>
7.1137 - UEdgeMap& operator=(const CMap& cmap) {
7.1138 - Parent::operator=(cmap);
7.1139 - return *this;
7.1140 - }
7.1141 - };
7.1142 -
7.1143 -
7.1144 - Node addANode() {
7.1145 - Node node = Parent::addANode();
7.1146 - getNotifier(ANode()).add(node);
7.1147 - getNotifier(Node()).add(node);
7.1148 - return node;
7.1149 - }
7.1150 -
7.1151 - Node addBNode() {
7.1152 - Node node = Parent::addBNode();
7.1153 - getNotifier(BNode()).add(node);
7.1154 - getNotifier(Node()).add(node);
7.1155 - return node;
7.1156 - }
7.1157 -
7.1158 - UEdge addEdge(const Node& source, const Node& target) {
7.1159 - UEdge uedge = Parent::addEdge(source, target);
7.1160 - getNotifier(UEdge()).add(uedge);
7.1161 -
7.1162 - std::vector<Edge> edges;
7.1163 - edges.push_back(direct(uedge, true));
7.1164 - edges.push_back(direct(uedge, false));
7.1165 - getNotifier(Edge()).add(edges);
7.1166 -
7.1167 - return uedge;
7.1168 - }
7.1169 -
7.1170 - void clear() {
7.1171 - getNotifier(Edge()).clear();
7.1172 - getNotifier(UEdge()).clear();
7.1173 - getNotifier(Node()).clear();
7.1174 - getNotifier(BNode()).clear();
7.1175 - getNotifier(ANode()).clear();
7.1176 - Parent::clear();
7.1177 - }
7.1178 -
7.1179 - void erase(const Node& node) {
7.1180 - UEdge uedge;
7.1181 - if (Parent::aNode(node)) {
7.1182 - Parent::firstFromANode(uedge, node);
7.1183 - while (uedge != INVALID) {
7.1184 - erase(uedge);
7.1185 - Parent::firstFromANode(uedge, node);
7.1186 - }
7.1187 - } else {
7.1188 - Parent::firstFromBNode(uedge, node);
7.1189 - while (uedge != INVALID) {
7.1190 - erase(uedge);
7.1191 - Parent::firstFromBNode(uedge, node);
7.1192 - }
7.1193 - }
7.1194 -
7.1195 - getNotifier(Node()).erase(node);
7.1196 - Parent::erase(node);
7.1197 - }
7.1198 -
7.1199 - void erase(const UEdge& uedge) {
7.1200 - std::vector<Edge> edges;
7.1201 - edges.push_back(direct(uedge, true));
7.1202 - edges.push_back(direct(uedge, false));
7.1203 - getNotifier(Edge()).erase(edges);
7.1204 - getNotifier(UEdge()).erase(uedge);
7.1205 - Parent::erase(uedge);
7.1206 - }
7.1207 -
7.1208 -
7.1209 - BpUGraphExtender() {
7.1210 - anode_notifier.setContainer(*this);
7.1211 - bnode_notifier.setContainer(*this);
7.1212 - node_notifier.setContainer(*this);
7.1213 - edge_notifier.setContainer(*this);
7.1214 - uedge_notifier.setContainer(*this);
7.1215 - }
7.1216 -
7.1217 - ~BpUGraphExtender() {
7.1218 - uedge_notifier.clear();
7.1219 - edge_notifier.clear();
7.1220 - node_notifier.clear();
7.1221 - anode_notifier.clear();
7.1222 - bnode_notifier.clear();
7.1223 - }
7.1224 -
7.1225 -
7.1226 - };
7.1227 -
7.1228 }
7.1229
7.1230 #endif
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/lemon/bits/ugraph_extender.h Fri Jun 30 12:14:36 2006 +0000
8.3 @@ -0,0 +1,444 @@
8.4 +/* -*- C++ -*-
8.5 + *
8.6 + * This file is a part of LEMON, a generic C++ optimization library
8.7 + *
8.8 + * Copyright (C) 2003-2006
8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
8.11 + *
8.12 + * Permission to use, modify and distribute this software is granted
8.13 + * provided that this copyright notice appears in all copies. For
8.14 + * precise terms see the accompanying LICENSE file.
8.15 + *
8.16 + * This software is provided "AS IS" with no warranty of any kind,
8.17 + * express or implied, and with no claim as to its suitability for any
8.18 + * purpose.
8.19 + *
8.20 + */
8.21 +
8.22 +#ifndef LEMON_BITS_UGRAPH_EXTENDER_H
8.23 +#define LEMON_BITS_UGRAPH_EXTENDER_H
8.24 +
8.25 +#include <lemon/bits/invalid.h>
8.26 +#include <lemon/error.h>
8.27 +
8.28 +#include <lemon/bits/map_extender.h>
8.29 +#include <lemon/bits/default_map.h>
8.30 +
8.31 +#include <lemon/concept_check.h>
8.32 +#include <lemon/concept/maps.h>
8.33 +
8.34 +///\ingroup graphbits
8.35 +///\file
8.36 +///\brief Extenders for the graph types
8.37 +namespace lemon {
8.38 +
8.39 + /// \ingroup graphbits
8.40 + ///
8.41 + /// \brief Extender for the UGraphs
8.42 + template <typename Base>
8.43 + class UGraphExtender : public Base {
8.44 + public:
8.45 +
8.46 + typedef Base Parent;
8.47 + typedef UGraphExtender Graph;
8.48 +
8.49 + typedef typename Parent::Node Node;
8.50 + typedef typename Parent::Edge Edge;
8.51 + typedef typename Parent::UEdge UEdge;
8.52 +
8.53 + // UGraph extension
8.54 +
8.55 + int maxId(Node) const {
8.56 + return Parent::maxNodeId();
8.57 + }
8.58 +
8.59 + int maxId(Edge) const {
8.60 + return Parent::maxEdgeId();
8.61 + }
8.62 +
8.63 + int maxId(UEdge) const {
8.64 + return Parent::maxUEdgeId();
8.65 + }
8.66 +
8.67 + Node fromId(int id, Node) const {
8.68 + return Parent::nodeFromId(id);
8.69 + }
8.70 +
8.71 + Edge fromId(int id, Edge) const {
8.72 + return Parent::edgeFromId(id);
8.73 + }
8.74 +
8.75 + UEdge fromId(int id, UEdge) const {
8.76 + return Parent::uEdgeFromId(id);
8.77 + }
8.78 +
8.79 + Node oppositeNode(const Node &n, const UEdge &e) const {
8.80 + if( n == Parent::source(e))
8.81 + return Parent::target(e);
8.82 + else if( n == Parent::target(e))
8.83 + return Parent::source(e);
8.84 + else
8.85 + return INVALID;
8.86 + }
8.87 +
8.88 + Edge oppositeEdge(const Edge &e) const {
8.89 + return Parent::direct(e, !Parent::direction(e));
8.90 + }
8.91 +
8.92 + using Parent::direct;
8.93 + Edge direct(const UEdge &ue, const Node &s) const {
8.94 + return Parent::direct(ue, Parent::source(ue) == s);
8.95 + }
8.96 +
8.97 + // Alterable extension
8.98 +
8.99 + typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
8.100 + typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
8.101 + typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
8.102 +
8.103 +
8.104 + protected:
8.105 +
8.106 + mutable NodeNotifier node_notifier;
8.107 + mutable EdgeNotifier edge_notifier;
8.108 + mutable UEdgeNotifier uedge_notifier;
8.109 +
8.110 + public:
8.111 +
8.112 + NodeNotifier& getNotifier(Node) const {
8.113 + return node_notifier;
8.114 + }
8.115 +
8.116 + EdgeNotifier& getNotifier(Edge) const {
8.117 + return edge_notifier;
8.118 + }
8.119 +
8.120 + UEdgeNotifier& getNotifier(UEdge) const {
8.121 + return uedge_notifier;
8.122 + }
8.123 +
8.124 +
8.125 +
8.126 + class NodeIt : public Node {
8.127 + const Graph* graph;
8.128 + public:
8.129 +
8.130 + NodeIt() {}
8.131 +
8.132 + NodeIt(Invalid i) : Node(i) { }
8.133 +
8.134 + explicit NodeIt(const Graph& _graph) : graph(&_graph) {
8.135 + _graph.first(static_cast<Node&>(*this));
8.136 + }
8.137 +
8.138 + NodeIt(const Graph& _graph, const Node& node)
8.139 + : Node(node), graph(&_graph) {}
8.140 +
8.141 + NodeIt& operator++() {
8.142 + graph->next(*this);
8.143 + return *this;
8.144 + }
8.145 +
8.146 + };
8.147 +
8.148 +
8.149 + class EdgeIt : public Edge {
8.150 + const Graph* graph;
8.151 + public:
8.152 +
8.153 + EdgeIt() { }
8.154 +
8.155 + EdgeIt(Invalid i) : Edge(i) { }
8.156 +
8.157 + explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
8.158 + _graph.first(static_cast<Edge&>(*this));
8.159 + }
8.160 +
8.161 + EdgeIt(const Graph& _graph, const Edge& e) :
8.162 + Edge(e), graph(&_graph) { }
8.163 +
8.164 + EdgeIt& operator++() {
8.165 + graph->next(*this);
8.166 + return *this;
8.167 + }
8.168 +
8.169 + };
8.170 +
8.171 +
8.172 + class OutEdgeIt : public Edge {
8.173 + const Graph* graph;
8.174 + public:
8.175 +
8.176 + OutEdgeIt() { }
8.177 +
8.178 + OutEdgeIt(Invalid i) : Edge(i) { }
8.179 +
8.180 + OutEdgeIt(const Graph& _graph, const Node& node)
8.181 + : graph(&_graph) {
8.182 + _graph.firstOut(*this, node);
8.183 + }
8.184 +
8.185 + OutEdgeIt(const Graph& _graph, const Edge& edge)
8.186 + : Edge(edge), graph(&_graph) {}
8.187 +
8.188 + OutEdgeIt& operator++() {
8.189 + graph->nextOut(*this);
8.190 + return *this;
8.191 + }
8.192 +
8.193 + };
8.194 +
8.195 +
8.196 + class InEdgeIt : public Edge {
8.197 + const Graph* graph;
8.198 + public:
8.199 +
8.200 + InEdgeIt() { }
8.201 +
8.202 + InEdgeIt(Invalid i) : Edge(i) { }
8.203 +
8.204 + InEdgeIt(const Graph& _graph, const Node& node)
8.205 + : graph(&_graph) {
8.206 + _graph.firstIn(*this, node);
8.207 + }
8.208 +
8.209 + InEdgeIt(const Graph& _graph, const Edge& edge) :
8.210 + Edge(edge), graph(&_graph) {}
8.211 +
8.212 + InEdgeIt& operator++() {
8.213 + graph->nextIn(*this);
8.214 + return *this;
8.215 + }
8.216 +
8.217 + };
8.218 +
8.219 +
8.220 + class UEdgeIt : public Parent::UEdge {
8.221 + const Graph* graph;
8.222 + public:
8.223 +
8.224 + UEdgeIt() { }
8.225 +
8.226 + UEdgeIt(Invalid i) : UEdge(i) { }
8.227 +
8.228 + explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
8.229 + _graph.first(static_cast<UEdge&>(*this));
8.230 + }
8.231 +
8.232 + UEdgeIt(const Graph& _graph, const UEdge& e) :
8.233 + UEdge(e), graph(&_graph) { }
8.234 +
8.235 + UEdgeIt& operator++() {
8.236 + graph->next(*this);
8.237 + return *this;
8.238 + }
8.239 +
8.240 + };
8.241 +
8.242 + class IncEdgeIt : public Parent::UEdge {
8.243 + friend class UGraphExtender;
8.244 + const Graph* graph;
8.245 + bool direction;
8.246 + public:
8.247 +
8.248 + IncEdgeIt() { }
8.249 +
8.250 + IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
8.251 +
8.252 + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
8.253 + _graph.firstInc(*this, direction, n);
8.254 + }
8.255 +
8.256 + IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
8.257 + : graph(&_graph), UEdge(ue) {
8.258 + direction = (_graph.source(ue) == n);
8.259 + }
8.260 +
8.261 + IncEdgeIt& operator++() {
8.262 + graph->nextInc(*this, direction);
8.263 + return *this;
8.264 + }
8.265 + };
8.266 +
8.267 + /// \brief Base node of the iterator
8.268 + ///
8.269 + /// Returns the base node (ie. the source in this case) of the iterator
8.270 + Node baseNode(const OutEdgeIt &e) const {
8.271 + return Parent::source((Edge)e);
8.272 + }
8.273 + /// \brief Running node of the iterator
8.274 + ///
8.275 + /// Returns the running node (ie. the target in this case) of the
8.276 + /// iterator
8.277 + Node runningNode(const OutEdgeIt &e) const {
8.278 + return Parent::target((Edge)e);
8.279 + }
8.280 +
8.281 + /// \brief Base node of the iterator
8.282 + ///
8.283 + /// Returns the base node (ie. the target in this case) of the iterator
8.284 + Node baseNode(const InEdgeIt &e) const {
8.285 + return Parent::target((Edge)e);
8.286 + }
8.287 + /// \brief Running node of the iterator
8.288 + ///
8.289 + /// Returns the running node (ie. the source in this case) of the
8.290 + /// iterator
8.291 + Node runningNode(const InEdgeIt &e) const {
8.292 + return Parent::source((Edge)e);
8.293 + }
8.294 +
8.295 + /// Base node of the iterator
8.296 + ///
8.297 + /// Returns the base node of the iterator
8.298 + Node baseNode(const IncEdgeIt &e) const {
8.299 + return e.direction ? source(e) : target(e);
8.300 + }
8.301 + /// Running node of the iterator
8.302 + ///
8.303 + /// Returns the running node of the iterator
8.304 + Node runningNode(const IncEdgeIt &e) const {
8.305 + return e.direction ? target(e) : source(e);
8.306 + }
8.307 +
8.308 + // Mappable extension
8.309 +
8.310 + template <typename _Value>
8.311 + class NodeMap
8.312 + : public MapExtender<DefaultMap<Graph, Node, _Value> > {
8.313 + public:
8.314 + typedef UGraphExtender Graph;
8.315 + typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
8.316 +
8.317 + NodeMap(const Graph& graph)
8.318 + : Parent(graph) {}
8.319 + NodeMap(const Graph& graph, const _Value& value)
8.320 + : Parent(graph, value) {}
8.321 +
8.322 + NodeMap& operator=(const NodeMap& cmap) {
8.323 + return operator=<NodeMap>(cmap);
8.324 + }
8.325 +
8.326 + template <typename CMap>
8.327 + NodeMap& operator=(const CMap& cmap) {
8.328 + Parent::operator=(cmap);
8.329 + return *this;
8.330 + }
8.331 +
8.332 + };
8.333 +
8.334 + template <typename _Value>
8.335 + class EdgeMap
8.336 + : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
8.337 + public:
8.338 + typedef UGraphExtender Graph;
8.339 + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
8.340 +
8.341 + EdgeMap(const Graph& graph)
8.342 + : Parent(graph) {}
8.343 + EdgeMap(const Graph& graph, const _Value& value)
8.344 + : Parent(graph, value) {}
8.345 +
8.346 + EdgeMap& operator=(const EdgeMap& cmap) {
8.347 + return operator=<EdgeMap>(cmap);
8.348 + }
8.349 +
8.350 + template <typename CMap>
8.351 + EdgeMap& operator=(const CMap& cmap) {
8.352 + Parent::operator=(cmap);
8.353 + return *this;
8.354 + }
8.355 + };
8.356 +
8.357 +
8.358 + template <typename _Value>
8.359 + class UEdgeMap
8.360 + : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
8.361 + public:
8.362 + typedef UGraphExtender Graph;
8.363 + typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
8.364 +
8.365 + UEdgeMap(const Graph& graph)
8.366 + : Parent(graph) {}
8.367 +
8.368 + UEdgeMap(const Graph& graph, const _Value& value)
8.369 + : Parent(graph, value) {}
8.370 +
8.371 + UEdgeMap& operator=(const UEdgeMap& cmap) {
8.372 + return operator=<UEdgeMap>(cmap);
8.373 + }
8.374 +
8.375 + template <typename CMap>
8.376 + UEdgeMap& operator=(const CMap& cmap) {
8.377 + Parent::operator=(cmap);
8.378 + return *this;
8.379 + }
8.380 +
8.381 + };
8.382 +
8.383 + // Alteration extension
8.384 +
8.385 + Node addNode() {
8.386 + Node node = Parent::addNode();
8.387 + getNotifier(Node()).add(node);
8.388 + return node;
8.389 + }
8.390 +
8.391 + UEdge addEdge(const Node& from, const Node& to) {
8.392 + UEdge uedge = Parent::addEdge(from, to);
8.393 + getNotifier(UEdge()).add(uedge);
8.394 + getNotifier(Edge()).add(Parent::direct(uedge, true));
8.395 + getNotifier(Edge()).add(Parent::direct(uedge, false));
8.396 + return uedge;
8.397 + }
8.398 +
8.399 + void clear() {
8.400 + getNotifier(Edge()).clear();
8.401 + getNotifier(UEdge()).clear();
8.402 + getNotifier(Node()).clear();
8.403 + Parent::clear();
8.404 + }
8.405 +
8.406 + void erase(const Node& node) {
8.407 + Edge edge;
8.408 + Parent::firstOut(edge, node);
8.409 + while (edge != INVALID ) {
8.410 + erase(edge);
8.411 + Parent::firstOut(edge, node);
8.412 + }
8.413 +
8.414 + Parent::firstIn(edge, node);
8.415 + while (edge != INVALID ) {
8.416 + erase(edge);
8.417 + Parent::firstIn(edge, node);
8.418 + }
8.419 +
8.420 + getNotifier(Node()).erase(node);
8.421 + Parent::erase(node);
8.422 + }
8.423 +
8.424 + void erase(const UEdge& uedge) {
8.425 + getNotifier(Edge()).erase(Parent::direct(uedge, true));
8.426 + getNotifier(Edge()).erase(Parent::direct(uedge, false));
8.427 + getNotifier(UEdge()).erase(uedge);
8.428 + Parent::erase(uedge);
8.429 + }
8.430 +
8.431 + UGraphExtender() {
8.432 + node_notifier.setContainer(*this);
8.433 + edge_notifier.setContainer(*this);
8.434 + uedge_notifier.setContainer(*this);
8.435 + }
8.436 +
8.437 + ~UGraphExtender() {
8.438 + uedge_notifier.clear();
8.439 + edge_notifier.clear();
8.440 + node_notifier.clear();
8.441 + }
8.442 +
8.443 + };
8.444 +
8.445 +}
8.446 +
8.447 +#endif
9.1 --- a/lemon/edge_set.h Wed Jun 28 16:27:44 2006 +0000
9.2 +++ b/lemon/edge_set.h Fri Jun 30 12:14:36 2006 +0000
9.3 @@ -22,6 +22,7 @@
9.4
9.5 #include <lemon/bits/default_map.h>
9.6 #include <lemon/bits/edge_set_extender.h>
9.7 +#include <lemon/bits/base_extender.h>
9.8
9.9 /// \ingroup graphs
9.10 /// \file
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/lemon/full_bpugraph.h Fri Jun 30 12:14:36 2006 +0000
10.3 @@ -0,0 +1,266 @@
10.4 +/* -*- C++ -*-
10.5 + *
10.6 + * This file is a part of LEMON, a generic C++ optimization library
10.7 + *
10.8 + * Copyright (C) 2003-2006
10.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
10.11 + *
10.12 + * Permission to use, modify and distribute this software is granted
10.13 + * provided that this copyright notice appears in all copies. For
10.14 + * precise terms see the accompanying LICENSE file.
10.15 + *
10.16 + * This software is provided "AS IS" with no warranty of any kind,
10.17 + * express or implied, and with no claim as to its suitability for any
10.18 + * purpose.
10.19 + *
10.20 + */
10.21 +
10.22 +#ifndef LEMON_FULL_BPUGRAPH_H
10.23 +#define LEMON_FULL_BPUGRAPH_H
10.24 +
10.25 +#include <cmath>
10.26 +
10.27 +#include <lemon/bits/bpugraph_extender.h>
10.28 +
10.29 +#include <lemon/bits/invalid.h>
10.30 +#include <lemon/bits/utility.h>
10.31 +
10.32 +
10.33 +///\ingroup graphs
10.34 +///\file
10.35 +///\brief FullBpUGraph class.
10.36 +
10.37 +
10.38 +namespace lemon {
10.39 +
10.40 + class FullBpUGraphBase {
10.41 + protected:
10.42 +
10.43 + int _aNodeNum;
10.44 + int _bNodeNum;
10.45 +
10.46 + int _edgeNum;
10.47 +
10.48 + public:
10.49 +
10.50 + class NodeSetError : public LogicError {
10.51 + virtual const char* exceptionName() const {
10.52 + return "lemon::FullBpUGraph::NodeSetError";
10.53 + }
10.54 + };
10.55 +
10.56 + class Node {
10.57 + friend class FullBpUGraphBase;
10.58 + protected:
10.59 + int id;
10.60 +
10.61 + Node(int _id) : id(_id) {}
10.62 + public:
10.63 + Node() {}
10.64 + Node(Invalid) { id = -1; }
10.65 + bool operator==(const Node i) const {return id==i.id;}
10.66 + bool operator!=(const Node i) const {return id!=i.id;}
10.67 + bool operator<(const Node i) const {return id<i.id;}
10.68 + };
10.69 +
10.70 + class UEdge {
10.71 + friend class FullBpUGraphBase;
10.72 + protected:
10.73 + int id;
10.74 +
10.75 + UEdge(int _id) { id = _id;}
10.76 + public:
10.77 + UEdge() {}
10.78 + UEdge (Invalid) { id = -1; }
10.79 + bool operator==(const UEdge i) const {return id==i.id;}
10.80 + bool operator!=(const UEdge i) const {return id!=i.id;}
10.81 + bool operator<(const UEdge i) const {return id<i.id;}
10.82 + };
10.83 +
10.84 + void construct(int aNodeNum, int bNodeNum) {
10.85 + _aNodeNum = aNodeNum;
10.86 + _bNodeNum = bNodeNum;
10.87 + _edgeNum = aNodeNum * bNodeNum;
10.88 + }
10.89 +
10.90 + void firstANode(Node& node) const {
10.91 + node.id = 2 * _aNodeNum - 2;
10.92 + if (node.id < 0) node.id = -1;
10.93 + }
10.94 + void nextANode(Node& node) const {
10.95 + node.id -= 2;
10.96 + if (node.id < 0) node.id = -1;
10.97 + }
10.98 +
10.99 + void firstBNode(Node& node) const {
10.100 + node.id = 2 * _bNodeNum - 1;
10.101 + }
10.102 + void nextBNode(Node& node) const {
10.103 + node.id -= 2;
10.104 + }
10.105 +
10.106 + void first(Node& node) const {
10.107 + if (_aNodeNum > 0) {
10.108 + node.id = 2 * _aNodeNum - 2;
10.109 + } else {
10.110 + node.id = 2 * _bNodeNum - 1;
10.111 + }
10.112 + }
10.113 + void next(Node& node) const {
10.114 + node.id -= 2;
10.115 + if (node.id == -2) {
10.116 + node.id = 2 * _bNodeNum - 1;
10.117 + }
10.118 + }
10.119 +
10.120 + void first(UEdge& edge) const {
10.121 + edge.id = _edgeNum - 1;
10.122 + }
10.123 + void next(UEdge& edge) const {
10.124 + --edge.id;
10.125 + }
10.126 +
10.127 + void firstFromANode(UEdge& edge, const Node& node) const {
10.128 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
10.129 + edge.id = (node.id >> 1) * _bNodeNum;
10.130 + }
10.131 + void nextFromANode(UEdge& edge) const {
10.132 + ++(edge.id);
10.133 + if (edge.id % _bNodeNum == 0) edge.id = -1;
10.134 + }
10.135 +
10.136 + void firstFromBNode(UEdge& edge, const Node& node) const {
10.137 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
10.138 + edge.id = (node.id >> 1);
10.139 + }
10.140 + void nextFromBNode(UEdge& edge) const {
10.141 + edge.id += _bNodeNum;
10.142 + if (edge.id >= _edgeNum) edge.id = -1;
10.143 + }
10.144 +
10.145 + static int id(const Node& node) {
10.146 + return node.id;
10.147 + }
10.148 + static Node nodeFromId(int id) {
10.149 + return Node(id);
10.150 + }
10.151 + int maxNodeId() const {
10.152 + return _aNodeNum > _bNodeNum ?
10.153 + _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
10.154 + }
10.155 +
10.156 + static int id(const UEdge& edge) {
10.157 + return edge.id;
10.158 + }
10.159 + static UEdge uEdgeFromId(int id) {
10.160 + return UEdge(id);
10.161 + }
10.162 + int maxUEdgeId() const {
10.163 + return _edgeNum - 1;
10.164 + }
10.165 +
10.166 + static int aNodeId(const Node& node) {
10.167 + return node.id >> 1;
10.168 + }
10.169 + static Node fromANodeId(int id) {
10.170 + return Node(id << 1);
10.171 + }
10.172 + int maxANodeId() const {
10.173 + return _aNodeNum;
10.174 + }
10.175 +
10.176 + static int bNodeId(const Node& node) {
10.177 + return node.id >> 1;
10.178 + }
10.179 + static Node fromBNodeId(int id) {
10.180 + return Node((id << 1) + 1);
10.181 + }
10.182 + int maxBNodeId() const {
10.183 + return _bNodeNum;
10.184 + }
10.185 +
10.186 + Node aNode(const UEdge& edge) const {
10.187 + return Node((edge.id / _bNodeNum) << 1);
10.188 + }
10.189 + Node bNode(const UEdge& edge) const {
10.190 + return Node(((edge.id % _bNodeNum) << 1) + 1);
10.191 + }
10.192 +
10.193 + static bool aNode(const Node& node) {
10.194 + return (node.id & 1) == 0;
10.195 + }
10.196 +
10.197 + static bool bNode(const Node& node) {
10.198 + return (node.id & 1) == 1;
10.199 + }
10.200 +
10.201 + static Node aNode(int index) {
10.202 + return Node(index << 1);
10.203 + }
10.204 +
10.205 + static Node bNode(int index) {
10.206 + return Node((index << 1) + 1);
10.207 + }
10.208 +
10.209 + typedef True NodeNumTag;
10.210 + int nodeNum() const { return _aNodeNum + _bNodeNum; }
10.211 + int aNodeNum() const { return _aNodeNum; }
10.212 + int bNodeNum() const { return _bNodeNum; }
10.213 +
10.214 + typedef True EdgeNumTag;
10.215 + int uEdgeNum() const { return _edgeNum; }
10.216 +
10.217 + };
10.218 +
10.219 +
10.220 + typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
10.221 +
10.222 +
10.223 + /// \ingroup graphs
10.224 + ///
10.225 + /// \brief An undirected full bipartite graph class.
10.226 + ///
10.227 + /// This is a simple and fast bipartite undirected full graph implementation.
10.228 + /// It is completely static, so you can neither add nor delete either
10.229 + /// edges or nodes.
10.230 + ///
10.231 + /// \sa FullUGraphBase
10.232 + /// \sa FullGraph
10.233 + ///
10.234 + /// \author Balazs Dezso
10.235 + class FullBpUGraph :
10.236 + public ExtendedFullBpUGraphBase {
10.237 + public:
10.238 +
10.239 + typedef ExtendedFullBpUGraphBase Parent;
10.240 +
10.241 + FullBpUGraph() {
10.242 + Parent::construct(0, 0);
10.243 + }
10.244 +
10.245 + FullBpUGraph(int aNodeNum, int bNodeNum) {
10.246 + Parent::construct(aNodeNum, bNodeNum);
10.247 + }
10.248 +
10.249 + /// \brief Resize the graph
10.250 + ///
10.251 + void resize(int n, int m) {
10.252 + Parent::getNotifier(Edge()).clear();
10.253 + Parent::getNotifier(UEdge()).clear();
10.254 + Parent::getNotifier(Node()).clear();
10.255 + Parent::getNotifier(ANode()).clear();
10.256 + Parent::getNotifier(BNode()).clear();
10.257 + construct(n, m);
10.258 + Parent::getNotifier(ANode()).build();
10.259 + Parent::getNotifier(BNode()).build();
10.260 + Parent::getNotifier(Node()).build();
10.261 + Parent::getNotifier(UEdge()).build();
10.262 + Parent::getNotifier(Edge()).build();
10.263 + }
10.264 + };
10.265 +
10.266 +} //namespace lemon
10.267 +
10.268 +
10.269 +#endif //LEMON_FULL_GRAPH_H
11.1 --- a/lemon/full_graph.h Wed Jun 28 16:27:44 2006 +0000
11.2 +++ b/lemon/full_graph.h Fri Jun 30 12:14:36 2006 +0000
11.3 @@ -21,7 +21,6 @@
11.4
11.5 #include <cmath>
11.6
11.7 -#include <lemon/bits/base_extender.h>
11.8 #include <lemon/bits/graph_extender.h>
11.9
11.10 #include <lemon/bits/invalid.h>
11.11 @@ -30,7 +29,7 @@
11.12
11.13 ///\ingroup graphs
11.14 ///\file
11.15 -///\brief FullGraph and FullUGraph classes.
11.16 +///\brief FullGraph class.
11.17
11.18
11.19 namespace lemon {
11.20 @@ -247,473 +246,6 @@
11.21 }
11.22 };
11.23
11.24 -
11.25 - /// \brief Base of the FullUGrpah.
11.26 - ///
11.27 - /// Base of the FullUGrpah.
11.28 - class FullUGraphBase {
11.29 - int _nodeNum;
11.30 - int _edgeNum;
11.31 - public:
11.32 -
11.33 - typedef FullUGraphBase Graph;
11.34 -
11.35 - class Node;
11.36 - class Edge;
11.37 -
11.38 - public:
11.39 -
11.40 - FullUGraphBase() {}
11.41 -
11.42 -
11.43 - ///Creates a full graph with \c n nodes.
11.44 - void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
11.45 -
11.46 - /// \brief Returns the node with the given index.
11.47 - ///
11.48 - /// Returns the node with the given index. Because it is a
11.49 - /// static size graph the node's of the graph can be indiced
11.50 - /// by the range from 0 to \e nodeNum()-1 and the index of
11.51 - /// the node can accessed by the \e index() member.
11.52 - Node operator()(int index) const { return Node(index); }
11.53 -
11.54 - /// \brief Returns the index of the node.
11.55 - ///
11.56 - /// Returns the index of the node. Because it is a
11.57 - /// static size graph the node's of the graph can be indiced
11.58 - /// by the range from 0 to \e nodeNum()-1 and the index of
11.59 - /// the node can accessed by the \e index() member.
11.60 - int index(const Node& node) const { return node.id; }
11.61 -
11.62 - typedef True NodeNumTag;
11.63 - typedef True EdgeNumTag;
11.64 -
11.65 - ///Number of nodes.
11.66 - int nodeNum() const { return _nodeNum; }
11.67 - ///Number of edges.
11.68 - int edgeNum() const { return _edgeNum; }
11.69 -
11.70 - /// Maximum node ID.
11.71 -
11.72 - /// Maximum node ID.
11.73 - ///\sa id(Node)
11.74 - int maxNodeId() const { return _nodeNum-1; }
11.75 - /// Maximum edge ID.
11.76 -
11.77 - /// Maximum edge ID.
11.78 - ///\sa id(Edge)
11.79 - int maxEdgeId() const { return _edgeNum-1; }
11.80 -
11.81 - /// \brief Returns the node from its \c id.
11.82 - ///
11.83 - /// Returns the node from its \c id. If there is not node
11.84 - /// with the given id the effect of the function is undefinied.
11.85 - static Node nodeFromId(int id) { return Node(id);}
11.86 -
11.87 - /// \brief Returns the edge from its \c id.
11.88 - ///
11.89 - /// Returns the edge from its \c id. If there is not edge
11.90 - /// with the given id the effect of the function is undefinied.
11.91 - static Edge edgeFromId(int id) { return Edge(id);}
11.92 -
11.93 - Node source(Edge e) const {
11.94 - /// \todo we may do it faster
11.95 - return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
11.96 - }
11.97 -
11.98 - Node target(Edge e) const {
11.99 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
11.100 - return Node(e.id - (source) * (source - 1) / 2);
11.101 - }
11.102 -
11.103 -
11.104 - /// \brief Node ID.
11.105 - ///
11.106 - /// The ID of a valid Node is a nonnegative integer not greater than
11.107 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
11.108 - /// and the greatest node ID can be actually less then \ref maxNodeId().
11.109 - ///
11.110 - /// The ID of the \ref INVALID node is -1.
11.111 - /// \return The ID of the node \c v.
11.112 -
11.113 - static int id(Node v) { return v.id; }
11.114 -
11.115 - /// \brief Edge ID.
11.116 - ///
11.117 - /// The ID of a valid Edge is a nonnegative integer not greater than
11.118 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
11.119 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
11.120 - ///
11.121 - /// The ID of the \ref INVALID edge is -1.
11.122 - ///\return The ID of the edge \c e.
11.123 - static int id(Edge e) { return e.id; }
11.124 -
11.125 - /// \brief Finds an edge between two nodes.
11.126 - ///
11.127 - /// Finds an edge from node \c u to node \c v.
11.128 - ///
11.129 - /// If \c prev is \ref INVALID (this is the default value), then
11.130 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
11.131 - /// the next edge from \c u to \c v after \c prev.
11.132 - /// \return The found edge or INVALID if there is no such an edge.
11.133 - Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
11.134 - if (prev.id != -1 || u.id <= v.id) return Edge(-1);
11.135 - return Edge(u.id * (u.id - 1) / 2 + v.id);
11.136 - }
11.137 -
11.138 - typedef True FindEdgeTag;
11.139 -
11.140 -
11.141 - class Node {
11.142 - friend class FullUGraphBase;
11.143 -
11.144 - protected:
11.145 - int id;
11.146 - Node(int _id) { id = _id;}
11.147 - public:
11.148 - Node() {}
11.149 - Node (Invalid) { id = -1; }
11.150 - bool operator==(const Node node) const {return id == node.id;}
11.151 - bool operator!=(const Node node) const {return id != node.id;}
11.152 - bool operator<(const Node node) const {return id < node.id;}
11.153 - };
11.154 -
11.155 -
11.156 -
11.157 - class Edge {
11.158 - friend class FullUGraphBase;
11.159 -
11.160 - protected:
11.161 - int id; // _nodeNum * target + source;
11.162 -
11.163 - Edge(int _id) : id(_id) {}
11.164 -
11.165 - public:
11.166 - Edge() { }
11.167 - Edge (Invalid) { id = -1; }
11.168 - bool operator==(const Edge edge) const {return id == edge.id;}
11.169 - bool operator!=(const Edge edge) const {return id != edge.id;}
11.170 - bool operator<(const Edge edge) const {return id < edge.id;}
11.171 - };
11.172 -
11.173 - void first(Node& node) const {
11.174 - node.id = _nodeNum - 1;
11.175 - }
11.176 -
11.177 - static void next(Node& node) {
11.178 - --node.id;
11.179 - }
11.180 -
11.181 - void first(Edge& edge) const {
11.182 - edge.id = _edgeNum - 1;
11.183 - }
11.184 -
11.185 - static void next(Edge& edge) {
11.186 - --edge.id;
11.187 - }
11.188 -
11.189 - void firstOut(Edge& edge, const Node& node) const {
11.190 - int src = node.id;
11.191 - int trg = 0;
11.192 - edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
11.193 - }
11.194 -
11.195 - /// \todo with specialized iterators we can make faster iterating
11.196 - void nextOut(Edge& edge) const {
11.197 - int src = source(edge).id;
11.198 - int trg = target(edge).id;
11.199 - ++trg;
11.200 - edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
11.201 - }
11.202 -
11.203 - void firstIn(Edge& edge, const Node& node) const {
11.204 - int src = node.id + 1;
11.205 - int trg = node.id;
11.206 - edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
11.207 - }
11.208 -
11.209 - void nextIn(Edge& edge) const {
11.210 - int src = source(edge).id;
11.211 - int trg = target(edge).id;
11.212 - ++src;
11.213 - edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
11.214 - }
11.215 -
11.216 - };
11.217 -
11.218 - typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
11.219 - ExtendedFullUGraphBase;
11.220 -
11.221 - /// \ingroup graphs
11.222 - ///
11.223 - /// \brief An undirected full graph class.
11.224 - ///
11.225 - /// This is a simple and fast undirected full graph implementation.
11.226 - /// It is completely static, so you can neither add nor delete either
11.227 - /// edges or nodes.
11.228 - ///
11.229 - /// The main difference beetween the \e FullGraph and \e FullUGraph class
11.230 - /// is that this class conforms to the undirected graph concept and
11.231 - /// it does not contain the loop edges.
11.232 - ///
11.233 - /// \sa FullUGraphBase
11.234 - /// \sa FullGraph
11.235 - ///
11.236 - /// \author Balazs Dezso
11.237 - class FullUGraph : public ExtendedFullUGraphBase {
11.238 - public:
11.239 -
11.240 - typedef ExtendedFullUGraphBase Parent;
11.241 -
11.242 - /// \brief Constructor
11.243 - FullUGraph() { construct(0); }
11.244 -
11.245 - /// \brief Constructor
11.246 - FullUGraph(int n) { construct(n); }
11.247 -
11.248 - /// \brief Resize the graph
11.249 - ///
11.250 - /// Resize the graph. The function will fully destroy and build the graph.
11.251 - /// This cause that the maps of the graph will reallocated
11.252 - /// automatically and the previous values will be lost.
11.253 - void resize(int n) {
11.254 - Parent::getNotifier(Edge()).clear();
11.255 - Parent::getNotifier(UEdge()).clear();
11.256 - Parent::getNotifier(Node()).clear();
11.257 - construct(n);
11.258 - Parent::getNotifier(Node()).build();
11.259 - Parent::getNotifier(UEdge()).build();
11.260 - Parent::getNotifier(Edge()).build();
11.261 - }
11.262 - };
11.263 -
11.264 -
11.265 - class FullBpUGraphBase {
11.266 - protected:
11.267 -
11.268 - int _aNodeNum;
11.269 - int _bNodeNum;
11.270 -
11.271 - int _edgeNum;
11.272 -
11.273 - public:
11.274 -
11.275 - class NodeSetError : public LogicError {
11.276 - virtual const char* exceptionName() const {
11.277 - return "lemon::FullBpUGraph::NodeSetError";
11.278 - }
11.279 - };
11.280 -
11.281 - class Node {
11.282 - friend class FullBpUGraphBase;
11.283 - protected:
11.284 - int id;
11.285 -
11.286 - Node(int _id) : id(_id) {}
11.287 - public:
11.288 - Node() {}
11.289 - Node(Invalid) { id = -1; }
11.290 - bool operator==(const Node i) const {return id==i.id;}
11.291 - bool operator!=(const Node i) const {return id!=i.id;}
11.292 - bool operator<(const Node i) const {return id<i.id;}
11.293 - };
11.294 -
11.295 - class UEdge {
11.296 - friend class FullBpUGraphBase;
11.297 - protected:
11.298 - int id;
11.299 -
11.300 - UEdge(int _id) { id = _id;}
11.301 - public:
11.302 - UEdge() {}
11.303 - UEdge (Invalid) { id = -1; }
11.304 - bool operator==(const UEdge i) const {return id==i.id;}
11.305 - bool operator!=(const UEdge i) const {return id!=i.id;}
11.306 - bool operator<(const UEdge i) const {return id<i.id;}
11.307 - };
11.308 -
11.309 - void construct(int aNodeNum, int bNodeNum) {
11.310 - _aNodeNum = aNodeNum;
11.311 - _bNodeNum = bNodeNum;
11.312 - _edgeNum = aNodeNum * bNodeNum;
11.313 - }
11.314 -
11.315 - void firstANode(Node& node) const {
11.316 - node.id = 2 * _aNodeNum - 2;
11.317 - if (node.id < 0) node.id = -1;
11.318 - }
11.319 - void nextANode(Node& node) const {
11.320 - node.id -= 2;
11.321 - if (node.id < 0) node.id = -1;
11.322 - }
11.323 -
11.324 - void firstBNode(Node& node) const {
11.325 - node.id = 2 * _bNodeNum - 1;
11.326 - }
11.327 - void nextBNode(Node& node) const {
11.328 - node.id -= 2;
11.329 - }
11.330 -
11.331 - void first(Node& node) const {
11.332 - if (_aNodeNum > 0) {
11.333 - node.id = 2 * _aNodeNum - 2;
11.334 - } else {
11.335 - node.id = 2 * _bNodeNum - 1;
11.336 - }
11.337 - }
11.338 - void next(Node& node) const {
11.339 - node.id -= 2;
11.340 - if (node.id == -2) {
11.341 - node.id = 2 * _bNodeNum - 1;
11.342 - }
11.343 - }
11.344 -
11.345 - void first(UEdge& edge) const {
11.346 - edge.id = _edgeNum - 1;
11.347 - }
11.348 - void next(UEdge& edge) const {
11.349 - --edge.id;
11.350 - }
11.351 -
11.352 - void firstFromANode(UEdge& edge, const Node& node) const {
11.353 - LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
11.354 - edge.id = (node.id >> 1) * _bNodeNum;
11.355 - }
11.356 - void nextFromANode(UEdge& edge) const {
11.357 - ++(edge.id);
11.358 - if (edge.id % _bNodeNum == 0) edge.id = -1;
11.359 - }
11.360 -
11.361 - void firstFromBNode(UEdge& edge, const Node& node) const {
11.362 - LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
11.363 - edge.id = (node.id >> 1);
11.364 - }
11.365 - void nextFromBNode(UEdge& edge) const {
11.366 - edge.id += _bNodeNum;
11.367 - if (edge.id >= _edgeNum) edge.id = -1;
11.368 - }
11.369 -
11.370 - static int id(const Node& node) {
11.371 - return node.id;
11.372 - }
11.373 - static Node nodeFromId(int id) {
11.374 - return Node(id);
11.375 - }
11.376 - int maxNodeId() const {
11.377 - return _aNodeNum > _bNodeNum ?
11.378 - _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
11.379 - }
11.380 -
11.381 - static int id(const UEdge& edge) {
11.382 - return edge.id;
11.383 - }
11.384 - static UEdge uEdgeFromId(int id) {
11.385 - return UEdge(id);
11.386 - }
11.387 - int maxUEdgeId() const {
11.388 - return _edgeNum - 1;
11.389 - }
11.390 -
11.391 - static int aNodeId(const Node& node) {
11.392 - return node.id >> 1;
11.393 - }
11.394 - static Node fromANodeId(int id) {
11.395 - return Node(id << 1);
11.396 - }
11.397 - int maxANodeId() const {
11.398 - return _aNodeNum;
11.399 - }
11.400 -
11.401 - static int bNodeId(const Node& node) {
11.402 - return node.id >> 1;
11.403 - }
11.404 - static Node fromBNodeId(int id) {
11.405 - return Node((id << 1) + 1);
11.406 - }
11.407 - int maxBNodeId() const {
11.408 - return _bNodeNum;
11.409 - }
11.410 -
11.411 - Node aNode(const UEdge& edge) const {
11.412 - return Node((edge.id / _bNodeNum) << 1);
11.413 - }
11.414 - Node bNode(const UEdge& edge) const {
11.415 - return Node(((edge.id % _bNodeNum) << 1) + 1);
11.416 - }
11.417 -
11.418 - static bool aNode(const Node& node) {
11.419 - return (node.id & 1) == 0;
11.420 - }
11.421 -
11.422 - static bool bNode(const Node& node) {
11.423 - return (node.id & 1) == 1;
11.424 - }
11.425 -
11.426 - static Node aNode(int index) {
11.427 - return Node(index << 1);
11.428 - }
11.429 -
11.430 - static Node bNode(int index) {
11.431 - return Node((index << 1) + 1);
11.432 - }
11.433 -
11.434 - typedef True NodeNumTag;
11.435 - int nodeNum() const { return _aNodeNum + _bNodeNum; }
11.436 - int aNodeNum() const { return _aNodeNum; }
11.437 - int bNodeNum() const { return _bNodeNum; }
11.438 -
11.439 - typedef True EdgeNumTag;
11.440 - int uEdgeNum() const { return _edgeNum; }
11.441 -
11.442 - };
11.443 -
11.444 -
11.445 - typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
11.446 -
11.447 -
11.448 - /// \ingroup graphs
11.449 - ///
11.450 - /// \brief An undirected full bipartite graph class.
11.451 - ///
11.452 - /// This is a simple and fast bipartite undirected full graph implementation.
11.453 - /// It is completely static, so you can neither add nor delete either
11.454 - /// edges or nodes.
11.455 - ///
11.456 - /// \sa FullUGraphBase
11.457 - /// \sa FullGraph
11.458 - ///
11.459 - /// \author Balazs Dezso
11.460 - class FullBpUGraph :
11.461 - public ExtendedFullBpUGraphBase {
11.462 - public:
11.463 -
11.464 - typedef ExtendedFullBpUGraphBase Parent;
11.465 -
11.466 - FullBpUGraph() {
11.467 - Parent::construct(0, 0);
11.468 - }
11.469 -
11.470 - FullBpUGraph(int aNodeNum, int bNodeNum) {
11.471 - Parent::construct(aNodeNum, bNodeNum);
11.472 - }
11.473 -
11.474 - /// \brief Resize the graph
11.475 - ///
11.476 - void resize(int n, int m) {
11.477 - Parent::getNotifier(Edge()).clear();
11.478 - Parent::getNotifier(UEdge()).clear();
11.479 - Parent::getNotifier(Node()).clear();
11.480 - Parent::getNotifier(ANode()).clear();
11.481 - Parent::getNotifier(BNode()).clear();
11.482 - construct(n, m);
11.483 - Parent::getNotifier(ANode()).build();
11.484 - Parent::getNotifier(BNode()).build();
11.485 - Parent::getNotifier(Node()).build();
11.486 - Parent::getNotifier(UEdge()).build();
11.487 - Parent::getNotifier(Edge()).build();
11.488 - }
11.489 - };
11.490 -
11.491 } //namespace lemon
11.492
11.493
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/lemon/full_ugraph.h Fri Jun 30 12:14:36 2006 +0000
12.3 @@ -0,0 +1,280 @@
12.4 +/* -*- C++ -*-
12.5 + *
12.6 + * This file is a part of LEMON, a generic C++ optimization library
12.7 + *
12.8 + * Copyright (C) 2003-2006
12.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
12.11 + *
12.12 + * Permission to use, modify and distribute this software is granted
12.13 + * provided that this copyright notice appears in all copies. For
12.14 + * precise terms see the accompanying LICENSE file.
12.15 + *
12.16 + * This software is provided "AS IS" with no warranty of any kind,
12.17 + * express or implied, and with no claim as to its suitability for any
12.18 + * purpose.
12.19 + *
12.20 + */
12.21 +
12.22 +#ifndef LEMON_FULL_UGRAPH_H
12.23 +#define LEMON_FULL_UGRAPH_H
12.24 +
12.25 +#include <cmath>
12.26 +
12.27 +#include <lemon/bits/base_extender.h>
12.28 +#include <lemon/bits/ugraph_extender.h>
12.29 +
12.30 +#include <lemon/bits/invalid.h>
12.31 +#include <lemon/bits/utility.h>
12.32 +
12.33 +
12.34 +///\ingroup graphs
12.35 +///\file
12.36 +///\brief FullUGraph classes.
12.37 +
12.38 +
12.39 +namespace lemon {
12.40 +
12.41 + /// \brief Base of the FullUGrpah.
12.42 + ///
12.43 + /// Base of the FullUGrpah.
12.44 + class FullUGraphBase {
12.45 + int _nodeNum;
12.46 + int _edgeNum;
12.47 + public:
12.48 +
12.49 + typedef FullUGraphBase Graph;
12.50 +
12.51 + class Node;
12.52 + class Edge;
12.53 +
12.54 + public:
12.55 +
12.56 + FullUGraphBase() {}
12.57 +
12.58 +
12.59 + ///Creates a full graph with \c n nodes.
12.60 + void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
12.61 +
12.62 + /// \brief Returns the node with the given index.
12.63 + ///
12.64 + /// Returns the node with the given index. Because it is a
12.65 + /// static size graph the node's of the graph can be indiced
12.66 + /// by the range from 0 to \e nodeNum()-1 and the index of
12.67 + /// the node can accessed by the \e index() member.
12.68 + Node operator()(int index) const { return Node(index); }
12.69 +
12.70 + /// \brief Returns the index of the node.
12.71 + ///
12.72 + /// Returns the index of the node. Because it is a
12.73 + /// static size graph the node's of the graph can be indiced
12.74 + /// by the range from 0 to \e nodeNum()-1 and the index of
12.75 + /// the node can accessed by the \e index() member.
12.76 + int index(const Node& node) const { return node.id; }
12.77 +
12.78 + typedef True NodeNumTag;
12.79 + typedef True EdgeNumTag;
12.80 +
12.81 + ///Number of nodes.
12.82 + int nodeNum() const { return _nodeNum; }
12.83 + ///Number of edges.
12.84 + int edgeNum() const { return _edgeNum; }
12.85 +
12.86 + /// Maximum node ID.
12.87 +
12.88 + /// Maximum node ID.
12.89 + ///\sa id(Node)
12.90 + int maxNodeId() const { return _nodeNum-1; }
12.91 + /// Maximum edge ID.
12.92 +
12.93 + /// Maximum edge ID.
12.94 + ///\sa id(Edge)
12.95 + int maxEdgeId() const { return _edgeNum-1; }
12.96 +
12.97 + /// \brief Returns the node from its \c id.
12.98 + ///
12.99 + /// Returns the node from its \c id. If there is not node
12.100 + /// with the given id the effect of the function is undefinied.
12.101 + static Node nodeFromId(int id) { return Node(id);}
12.102 +
12.103 + /// \brief Returns the edge from its \c id.
12.104 + ///
12.105 + /// Returns the edge from its \c id. If there is not edge
12.106 + /// with the given id the effect of the function is undefinied.
12.107 + static Edge edgeFromId(int id) { return Edge(id);}
12.108 +
12.109 + Node source(Edge e) const {
12.110 + /// \todo we may do it faster
12.111 + return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
12.112 + }
12.113 +
12.114 + Node target(Edge e) const {
12.115 + int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
12.116 + return Node(e.id - (source) * (source - 1) / 2);
12.117 + }
12.118 +
12.119 +
12.120 + /// \brief Node ID.
12.121 + ///
12.122 + /// The ID of a valid Node is a nonnegative integer not greater than
12.123 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
12.124 + /// and the greatest node ID can be actually less then \ref maxNodeId().
12.125 + ///
12.126 + /// The ID of the \ref INVALID node is -1.
12.127 + /// \return The ID of the node \c v.
12.128 +
12.129 + static int id(Node v) { return v.id; }
12.130 +
12.131 + /// \brief Edge ID.
12.132 + ///
12.133 + /// The ID of a valid Edge is a nonnegative integer not greater than
12.134 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
12.135 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
12.136 + ///
12.137 + /// The ID of the \ref INVALID edge is -1.
12.138 + ///\return The ID of the edge \c e.
12.139 + static int id(Edge e) { return e.id; }
12.140 +
12.141 + /// \brief Finds an edge between two nodes.
12.142 + ///
12.143 + /// Finds an edge from node \c u to node \c v.
12.144 + ///
12.145 + /// If \c prev is \ref INVALID (this is the default value), then
12.146 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
12.147 + /// the next edge from \c u to \c v after \c prev.
12.148 + /// \return The found edge or INVALID if there is no such an edge.
12.149 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
12.150 + if (prev.id != -1 || u.id <= v.id) return Edge(-1);
12.151 + return Edge(u.id * (u.id - 1) / 2 + v.id);
12.152 + }
12.153 +
12.154 + typedef True FindEdgeTag;
12.155 +
12.156 +
12.157 + class Node {
12.158 + friend class FullUGraphBase;
12.159 +
12.160 + protected:
12.161 + int id;
12.162 + Node(int _id) { id = _id;}
12.163 + public:
12.164 + Node() {}
12.165 + Node (Invalid) { id = -1; }
12.166 + bool operator==(const Node node) const {return id == node.id;}
12.167 + bool operator!=(const Node node) const {return id != node.id;}
12.168 + bool operator<(const Node node) const {return id < node.id;}
12.169 + };
12.170 +
12.171 +
12.172 +
12.173 + class Edge {
12.174 + friend class FullUGraphBase;
12.175 +
12.176 + protected:
12.177 + int id; // _nodeNum * target + source;
12.178 +
12.179 + Edge(int _id) : id(_id) {}
12.180 +
12.181 + public:
12.182 + Edge() { }
12.183 + Edge (Invalid) { id = -1; }
12.184 + bool operator==(const Edge edge) const {return id == edge.id;}
12.185 + bool operator!=(const Edge edge) const {return id != edge.id;}
12.186 + bool operator<(const Edge edge) const {return id < edge.id;}
12.187 + };
12.188 +
12.189 + void first(Node& node) const {
12.190 + node.id = _nodeNum - 1;
12.191 + }
12.192 +
12.193 + static void next(Node& node) {
12.194 + --node.id;
12.195 + }
12.196 +
12.197 + void first(Edge& edge) const {
12.198 + edge.id = _edgeNum - 1;
12.199 + }
12.200 +
12.201 + static void next(Edge& edge) {
12.202 + --edge.id;
12.203 + }
12.204 +
12.205 + void firstOut(Edge& edge, const Node& node) const {
12.206 + int src = node.id;
12.207 + int trg = 0;
12.208 + edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
12.209 + }
12.210 +
12.211 + /// \todo with specialized iterators we can make faster iterating
12.212 + void nextOut(Edge& edge) const {
12.213 + int src = source(edge).id;
12.214 + int trg = target(edge).id;
12.215 + ++trg;
12.216 + edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
12.217 + }
12.218 +
12.219 + void firstIn(Edge& edge, const Node& node) const {
12.220 + int src = node.id + 1;
12.221 + int trg = node.id;
12.222 + edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
12.223 + }
12.224 +
12.225 + void nextIn(Edge& edge) const {
12.226 + int src = source(edge).id;
12.227 + int trg = target(edge).id;
12.228 + ++src;
12.229 + edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
12.230 + }
12.231 +
12.232 + };
12.233 +
12.234 + typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
12.235 + ExtendedFullUGraphBase;
12.236 +
12.237 + /// \ingroup graphs
12.238 + ///
12.239 + /// \brief An undirected full graph class.
12.240 + ///
12.241 + /// This is a simple and fast undirected full graph implementation.
12.242 + /// It is completely static, so you can neither add nor delete either
12.243 + /// edges or nodes.
12.244 + ///
12.245 + /// The main difference beetween the \e FullGraph and \e FullUGraph class
12.246 + /// is that this class conforms to the undirected graph concept and
12.247 + /// it does not contain the loop edges.
12.248 + ///
12.249 + /// \sa FullUGraphBase
12.250 + /// \sa FullGraph
12.251 + ///
12.252 + /// \author Balazs Dezso
12.253 + class FullUGraph : public ExtendedFullUGraphBase {
12.254 + public:
12.255 +
12.256 + typedef ExtendedFullUGraphBase Parent;
12.257 +
12.258 + /// \brief Constructor
12.259 + FullUGraph() { construct(0); }
12.260 +
12.261 + /// \brief Constructor
12.262 + FullUGraph(int n) { construct(n); }
12.263 +
12.264 + /// \brief Resize the graph
12.265 + ///
12.266 + /// Resize the graph. The function will fully destroy and build the graph.
12.267 + /// This cause that the maps of the graph will reallocated
12.268 + /// automatically and the previous values will be lost.
12.269 + void resize(int n) {
12.270 + Parent::getNotifier(Edge()).clear();
12.271 + Parent::getNotifier(UEdge()).clear();
12.272 + Parent::getNotifier(Node()).clear();
12.273 + construct(n);
12.274 + Parent::getNotifier(Node()).build();
12.275 + Parent::getNotifier(UEdge()).build();
12.276 + Parent::getNotifier(Edge()).build();
12.277 + }
12.278 + };
12.279 +
12.280 +} //namespace lemon
12.281 +
12.282 +
12.283 +#endif //LEMON_FULL_GRAPH_H
13.1 --- a/lemon/grid_ugraph.h Wed Jun 28 16:27:44 2006 +0000
13.2 +++ b/lemon/grid_ugraph.h Fri Jun 30 12:14:36 2006 +0000
13.3 @@ -24,7 +24,7 @@
13.4 #include <lemon/bits/utility.h>
13.5
13.6 #include <lemon/bits/base_extender.h>
13.7 -#include <lemon/bits/graph_extender.h>
13.8 +#include <lemon/bits/ugraph_extender.h>
13.9
13.10 #include <lemon/xy.h>
13.11
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/lemon/list_bpugraph.h Fri Jun 30 12:14:36 2006 +0000
14.3 @@ -0,0 +1,398 @@
14.4 +/* -*- C++ -*-
14.5 + *
14.6 + * This file is a part of LEMON, a generic C++ optimization library
14.7 + *
14.8 + * Copyright (C) 2003-2006
14.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
14.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
14.11 + *
14.12 + * Permission to use, modify and distribute this software is granted
14.13 + * provided that this copyright notice appears in all copies. For
14.14 + * precise terms see the accompanying LICENSE file.
14.15 + *
14.16 + * This software is provided "AS IS" with no warranty of any kind,
14.17 + * express or implied, and with no claim as to its suitability for any
14.18 + * purpose.
14.19 + *
14.20 + */
14.21 +
14.22 +#ifndef LEMON_LIST_BPUGRAPH_H
14.23 +#define LEMON_LIST_BPUGRAPH_H
14.24 +
14.25 +///\ingroup graphs
14.26 +///\file
14.27 +///\brief ListBpUGraph classes.
14.28 +
14.29 +#include <lemon/bits/bpugraph_extender.h>
14.30 +
14.31 +#include <lemon/error.h>
14.32 +
14.33 +#include <vector>
14.34 +#include <list>
14.35 +
14.36 +namespace lemon {
14.37 +
14.38 + class ListBpUGraphBase {
14.39 + public:
14.40 +
14.41 + class NodeSetError : public LogicError {
14.42 + virtual const char* exceptionName() const {
14.43 + return "lemon::ListBpUGraph::NodeSetError";
14.44 + }
14.45 + };
14.46 +
14.47 + protected:
14.48 +
14.49 + struct NodeT {
14.50 + int first_edge, prev, next;
14.51 + };
14.52 +
14.53 + struct UEdgeT {
14.54 + int aNode, prev_out, next_out;
14.55 + int bNode, prev_in, next_in;
14.56 + };
14.57 +
14.58 + std::vector<NodeT> aNodes;
14.59 + std::vector<NodeT> bNodes;
14.60 +
14.61 + std::vector<UEdgeT> edges;
14.62 +
14.63 + int first_anode;
14.64 + int first_free_anode;
14.65 +
14.66 + int first_bnode;
14.67 + int first_free_bnode;
14.68 +
14.69 + int first_free_edge;
14.70 +
14.71 + public:
14.72 +
14.73 + class Node {
14.74 + friend class ListBpUGraphBase;
14.75 + protected:
14.76 + int id;
14.77 +
14.78 + explicit Node(int _id) : id(_id) {}
14.79 + public:
14.80 + Node() {}
14.81 + Node(Invalid) { id = -1; }
14.82 + bool operator==(const Node i) const {return id==i.id;}
14.83 + bool operator!=(const Node i) const {return id!=i.id;}
14.84 + bool operator<(const Node i) const {return id<i.id;}
14.85 + };
14.86 +
14.87 + class UEdge {
14.88 + friend class ListBpUGraphBase;
14.89 + protected:
14.90 + int id;
14.91 +
14.92 + explicit UEdge(int _id) { id = _id;}
14.93 + public:
14.94 + UEdge() {}
14.95 + UEdge (Invalid) { id = -1; }
14.96 + bool operator==(const UEdge i) const {return id==i.id;}
14.97 + bool operator!=(const UEdge i) const {return id!=i.id;}
14.98 + bool operator<(const UEdge i) const {return id<i.id;}
14.99 + };
14.100 +
14.101 + ListBpUGraphBase()
14.102 + : first_anode(-1), first_free_anode(-1),
14.103 + first_bnode(-1), first_free_bnode(-1),
14.104 + first_free_edge(-1) {}
14.105 +
14.106 + void firstANode(Node& node) const {
14.107 + node.id = first_anode != -1 ? (first_anode << 1) : -1;
14.108 + }
14.109 + void nextANode(Node& node) const {
14.110 + node.id = aNodes[node.id >> 1].next;
14.111 + }
14.112 +
14.113 + void firstBNode(Node& node) const {
14.114 + node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
14.115 + }
14.116 + void nextBNode(Node& node) const {
14.117 + node.id = bNodes[node.id >> 1].next;
14.118 + }
14.119 +
14.120 + void first(Node& node) const {
14.121 + if (first_anode != -1) {
14.122 + node.id = (first_anode << 1);
14.123 + } else if (first_bnode != -1) {
14.124 + node.id = (first_bnode << 1) + 1;
14.125 + } else {
14.126 + node.id = -1;
14.127 + }
14.128 + }
14.129 + void next(Node& node) const {
14.130 + if (aNode(node)) {
14.131 + node.id = aNodes[node.id >> 1].next;
14.132 + if (node.id == -1) {
14.133 + if (first_bnode != -1) {
14.134 + node.id = (first_bnode << 1) + 1;
14.135 + }
14.136 + }
14.137 + } else {
14.138 + node.id = bNodes[node.id >> 1].next;
14.139 + }
14.140 + }
14.141 +
14.142 + void first(UEdge& edge) const {
14.143 + int aNodeId = first_anode;
14.144 + while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
14.145 + aNodeId = aNodes[aNodeId].next != -1 ?
14.146 + aNodes[aNodeId].next >> 1 : -1;
14.147 + }
14.148 + if (aNodeId != -1) {
14.149 + edge.id = aNodes[aNodeId].first_edge;
14.150 + } else {
14.151 + edge.id = -1;
14.152 + }
14.153 + }
14.154 + void next(UEdge& edge) const {
14.155 + int aNodeId = edges[edge.id].aNode >> 1;
14.156 + edge.id = edges[edge.id].next_out;
14.157 + if (edge.id == -1) {
14.158 + aNodeId = aNodes[aNodeId].next != -1 ?
14.159 + aNodes[aNodeId].next >> 1 : -1;
14.160 + while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
14.161 + aNodeId = aNodes[aNodeId].next != -1 ?
14.162 + aNodes[aNodeId].next >> 1 : -1;
14.163 + }
14.164 + if (aNodeId != -1) {
14.165 + edge.id = aNodes[aNodeId].first_edge;
14.166 + } else {
14.167 + edge.id = -1;
14.168 + }
14.169 + }
14.170 + }
14.171 +
14.172 + void firstFromANode(UEdge& edge, const Node& node) const {
14.173 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
14.174 + edge.id = aNodes[node.id >> 1].first_edge;
14.175 + }
14.176 + void nextFromANode(UEdge& edge) const {
14.177 + edge.id = edges[edge.id].next_out;
14.178 + }
14.179 +
14.180 + void firstFromBNode(UEdge& edge, const Node& node) const {
14.181 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
14.182 + edge.id = bNodes[node.id >> 1].first_edge;
14.183 + }
14.184 + void nextFromBNode(UEdge& edge) const {
14.185 + edge.id = edges[edge.id].next_in;
14.186 + }
14.187 +
14.188 + static int id(const Node& node) {
14.189 + return node.id;
14.190 + }
14.191 + static Node nodeFromId(int id) {
14.192 + return Node(id);
14.193 + }
14.194 + int maxNodeId() const {
14.195 + return aNodes.size() > bNodes.size() ?
14.196 + aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
14.197 + }
14.198 +
14.199 + static int id(const UEdge& edge) {
14.200 + return edge.id;
14.201 + }
14.202 + static UEdge uEdgeFromId(int id) {
14.203 + return UEdge(id);
14.204 + }
14.205 + int maxUEdgeId() const {
14.206 + return edges.size();
14.207 + }
14.208 +
14.209 + static int aNodeId(const Node& node) {
14.210 + return node.id >> 1;
14.211 + }
14.212 + static Node fromANodeId(int id) {
14.213 + return Node(id << 1);
14.214 + }
14.215 + int maxANodeId() const {
14.216 + return aNodes.size();
14.217 + }
14.218 +
14.219 + static int bNodeId(const Node& node) {
14.220 + return node.id >> 1;
14.221 + }
14.222 + static Node fromBNodeId(int id) {
14.223 + return Node((id << 1) + 1);
14.224 + }
14.225 + int maxBNodeId() const {
14.226 + return bNodes.size();
14.227 + }
14.228 +
14.229 + Node aNode(const UEdge& edge) const {
14.230 + return Node(edges[edge.id].aNode);
14.231 + }
14.232 + Node bNode(const UEdge& edge) const {
14.233 + return Node(edges[edge.id].bNode);
14.234 + }
14.235 +
14.236 + static bool aNode(const Node& node) {
14.237 + return (node.id & 1) == 0;
14.238 + }
14.239 +
14.240 + static bool bNode(const Node& node) {
14.241 + return (node.id & 1) == 1;
14.242 + }
14.243 +
14.244 + Node addANode() {
14.245 + int aNodeId;
14.246 + if (first_free_anode == -1) {
14.247 + aNodeId = aNodes.size();
14.248 + aNodes.push_back(NodeT());
14.249 + } else {
14.250 + aNodeId = first_free_anode;
14.251 + first_free_anode = aNodes[first_free_anode].next;
14.252 + }
14.253 + if (first_anode != -1) {
14.254 + aNodes[aNodeId].next = first_anode << 1;
14.255 + aNodes[first_anode].prev = aNodeId << 1;
14.256 + } else {
14.257 + aNodes[aNodeId].next = -1;
14.258 + }
14.259 + aNodes[aNodeId].prev = -1;
14.260 + first_anode = aNodeId;
14.261 + aNodes[aNodeId].first_edge = -1;
14.262 + return Node(aNodeId << 1);
14.263 + }
14.264 +
14.265 + Node addBNode() {
14.266 + int bNodeId;
14.267 + if (first_free_bnode == -1) {
14.268 + bNodeId = bNodes.size();
14.269 + bNodes.push_back(NodeT());
14.270 + } else {
14.271 + bNodeId = first_free_bnode;
14.272 + first_free_bnode = bNodes[first_free_bnode].next;
14.273 + }
14.274 + if (first_bnode != -1) {
14.275 + bNodes[bNodeId].next = (first_bnode << 1) + 1;
14.276 + bNodes[first_bnode].prev = (bNodeId << 1) + 1;
14.277 + } else {
14.278 + bNodes[bNodeId].next = -1;
14.279 + }
14.280 + first_bnode = bNodeId;
14.281 + bNodes[bNodeId].first_edge = -1;
14.282 + return Node((bNodeId << 1) + 1);
14.283 + }
14.284 +
14.285 + UEdge addEdge(const Node& source, const Node& target) {
14.286 + LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
14.287 + int edgeId;
14.288 + if (first_free_edge != -1) {
14.289 + edgeId = first_free_edge;
14.290 + first_free_edge = edges[edgeId].next_out;
14.291 + } else {
14.292 + edgeId = edges.size();
14.293 + edges.push_back(UEdgeT());
14.294 + }
14.295 + if ((source.id & 1) == 0) {
14.296 + edges[edgeId].aNode = source.id;
14.297 + edges[edgeId].bNode = target.id;
14.298 + } else {
14.299 + edges[edgeId].aNode = target.id;
14.300 + edges[edgeId].bNode = source.id;
14.301 + }
14.302 + edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
14.303 + edges[edgeId].prev_out = -1;
14.304 + if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
14.305 + edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
14.306 + }
14.307 + aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
14.308 + edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
14.309 + edges[edgeId].prev_in = -1;
14.310 + if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
14.311 + edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
14.312 + }
14.313 + bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
14.314 + return UEdge(edgeId);
14.315 + }
14.316 +
14.317 + void erase(const Node& node) {
14.318 + if (aNode(node)) {
14.319 + int aNodeId = node.id >> 1;
14.320 + if (aNodes[aNodeId].prev != -1) {
14.321 + aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
14.322 + } else {
14.323 + first_anode = aNodes[aNodeId].next >> 1;
14.324 + }
14.325 + if (aNodes[aNodeId].next != -1) {
14.326 + aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
14.327 + }
14.328 + aNodes[aNodeId].next = first_free_anode;
14.329 + first_free_anode = aNodeId;
14.330 + } else {
14.331 + int bNodeId = node.id >> 1;
14.332 + if (bNodes[bNodeId].prev != -1) {
14.333 + bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
14.334 + } else {
14.335 + first_bnode = bNodes[bNodeId].next >> 1;
14.336 + }
14.337 + if (bNodes[bNodeId].next != -1) {
14.338 + bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
14.339 + }
14.340 + bNodes[bNodeId].next = first_free_bnode;
14.341 + first_free_bnode = bNodeId;
14.342 + }
14.343 + }
14.344 +
14.345 + void erase(const UEdge& edge) {
14.346 +
14.347 + if (edges[edge.id].prev_out != -1) {
14.348 + edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
14.349 + } else {
14.350 + aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
14.351 + }
14.352 + if (edges[edge.id].next_out != -1) {
14.353 + edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
14.354 + }
14.355 +
14.356 + if (edges[edge.id].prev_in != -1) {
14.357 + edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
14.358 + } else {
14.359 + bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
14.360 + }
14.361 + if (edges[edge.id].next_in != -1) {
14.362 + edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
14.363 + }
14.364 +
14.365 + edges[edge.id].next_out = first_free_edge;
14.366 + first_free_edge = edge.id;
14.367 + }
14.368 +
14.369 + void clear() {
14.370 + aNodes.clear();
14.371 + bNodes.clear();
14.372 + edges.clear();
14.373 + first_anode = -1;
14.374 + first_free_anode = -1;
14.375 + first_bnode = -1;
14.376 + first_free_bnode = -1;
14.377 + first_free_edge = -1;
14.378 + }
14.379 +
14.380 + };
14.381 +
14.382 +
14.383 + typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
14.384 +
14.385 + /// \ingroup graphs
14.386 + ///
14.387 + /// \brief A smart bipartite undirected graph class.
14.388 + ///
14.389 + /// This is a bipartite undirected graph implementation.
14.390 + /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
14.391 + /// concept.
14.392 + /// \sa concept::BpUGraph.
14.393 + ///
14.394 + class ListBpUGraph : public ExtendedListBpUGraphBase {};
14.395 +
14.396 +
14.397 + /// @}
14.398 +} //namespace lemon
14.399 +
14.400 +
14.401 +#endif
15.1 --- a/lemon/list_graph.h Wed Jun 28 16:27:44 2006 +0000
15.2 +++ b/lemon/list_graph.h Fri Jun 30 12:14:36 2006 +0000
15.3 @@ -21,13 +21,10 @@
15.4
15.5 ///\ingroup graphs
15.6 ///\file
15.7 -///\brief ListGraph, ListUGraph classes.
15.8 +///\brief ListGraph class.
15.9
15.10 -#include <lemon/bits/base_extender.h>
15.11 #include <lemon/bits/graph_extender.h>
15.12
15.13 -#include <lemon/error.h>
15.14 -
15.15 #include <vector>
15.16 #include <list>
15.17
15.18 @@ -309,8 +306,7 @@
15.19
15.20 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
15.21
15.22 - /// \addtogroup graphs
15.23 - /// @{
15.24 + /// \ingroup graphs
15.25
15.26 ///A list graph class.
15.27
15.28 @@ -705,454 +701,6 @@
15.29
15.30 };
15.31
15.32 - ///@}
15.33 -
15.34 - /**************** Undirected List Graph ****************/
15.35 -
15.36 - typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
15.37 - ExtendedListUGraphBase;
15.38 -
15.39 - /// \addtogroup graphs
15.40 - /// @{
15.41 -
15.42 - ///An undirected list graph class.
15.43 -
15.44 - ///This is a simple and fast erasable undirected graph implementation.
15.45 - ///
15.46 - ///It conforms to the
15.47 - ///\ref concept::UGraph "UGraph" concept.
15.48 - ///
15.49 - ///\sa concept::UGraph.
15.50 - ///
15.51 - ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
15.52 - ///haven't been implemented yet.
15.53 - ///
15.54 - class ListUGraph : public ExtendedListUGraphBase {
15.55 - public:
15.56 - typedef ExtendedListUGraphBase Parent;
15.57 - /// \brief Add a new node to the graph.
15.58 - ///
15.59 - /// \return the new node.
15.60 - ///
15.61 - Node addNode() { return Parent::addNode(); }
15.62 -
15.63 - /// \brief Add a new edge to the graph.
15.64 - ///
15.65 - /// Add a new edge to the graph with source node \c s
15.66 - /// and target node \c t.
15.67 - /// \return the new undirected edge.
15.68 - UEdge addEdge(const Node& s, const Node& t) {
15.69 - return Parent::addEdge(s, t);
15.70 - }
15.71 - /// \brief Changes the target of \c e to \c n
15.72 - ///
15.73 - /// Changes the target of \c e to \c n
15.74 - ///
15.75 - /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
15.76 - /// referencing the changed edge remain
15.77 - /// valid. However <tt>InEdge</tt>'s are invalidated.
15.78 - void changeTarget(UEdge e, Node n) {
15.79 - Parent::changeTarget(e,n);
15.80 - }
15.81 - /// Changes the source of \c e to \c n
15.82 - ///
15.83 - /// Changes the source of \c e to \c n
15.84 - ///
15.85 - ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
15.86 - ///referencing the changed edge remain
15.87 - ///valid. However <tt>OutEdge</tt>'s are invalidated.
15.88 - void changeSource(UEdge e, Node n) {
15.89 - Parent::changeSource(e,n);
15.90 - }
15.91 - /// \brief Contract two nodes.
15.92 - ///
15.93 - /// This function contracts two nodes.
15.94 - ///
15.95 - /// Node \p b will be removed but instead of deleting
15.96 - /// its neighboring edges, they will be joined to \p a.
15.97 - /// The last parameter \p r controls whether to remove loops. \c true
15.98 - /// means that loops will be removed.
15.99 - ///
15.100 - /// \note The <tt>Edge</tt>s
15.101 - /// referencing a moved edge remain
15.102 - /// valid.
15.103 - void contract(Node a, Node b, bool r = true) {
15.104 - for(IncEdgeIt e(*this, b); e!=INVALID;) {
15.105 - IncEdgeIt f = e; ++f;
15.106 - if (r && runningNode(e) == a) {
15.107 - erase(e);
15.108 - } else if (source(e) == b) {
15.109 - changeSource(e, a);
15.110 - } else {
15.111 - changeTarget(e, a);
15.112 - }
15.113 - e = f;
15.114 - }
15.115 - erase(b);
15.116 - }
15.117 - };
15.118 -
15.119 -
15.120 - class ListBpUGraphBase {
15.121 - public:
15.122 -
15.123 - class NodeSetError : public LogicError {
15.124 - virtual const char* exceptionName() const {
15.125 - return "lemon::ListBpUGraph::NodeSetError";
15.126 - }
15.127 - };
15.128 -
15.129 - protected:
15.130 -
15.131 - struct NodeT {
15.132 - int first_edge, prev, next;
15.133 - };
15.134 -
15.135 - struct UEdgeT {
15.136 - int aNode, prev_out, next_out;
15.137 - int bNode, prev_in, next_in;
15.138 - };
15.139 -
15.140 - std::vector<NodeT> aNodes;
15.141 - std::vector<NodeT> bNodes;
15.142 -
15.143 - std::vector<UEdgeT> edges;
15.144 -
15.145 - int first_anode;
15.146 - int first_free_anode;
15.147 -
15.148 - int first_bnode;
15.149 - int first_free_bnode;
15.150 -
15.151 - int first_free_edge;
15.152 -
15.153 - public:
15.154 -
15.155 - class Node {
15.156 - friend class ListBpUGraphBase;
15.157 - protected:
15.158 - int id;
15.159 -
15.160 - explicit Node(int _id) : id(_id) {}
15.161 - public:
15.162 - Node() {}
15.163 - Node(Invalid) { id = -1; }
15.164 - bool operator==(const Node i) const {return id==i.id;}
15.165 - bool operator!=(const Node i) const {return id!=i.id;}
15.166 - bool operator<(const Node i) const {return id<i.id;}
15.167 - };
15.168 -
15.169 - class UEdge {
15.170 - friend class ListBpUGraphBase;
15.171 - protected:
15.172 - int id;
15.173 -
15.174 - explicit UEdge(int _id) { id = _id;}
15.175 - public:
15.176 - UEdge() {}
15.177 - UEdge (Invalid) { id = -1; }
15.178 - bool operator==(const UEdge i) const {return id==i.id;}
15.179 - bool operator!=(const UEdge i) const {return id!=i.id;}
15.180 - bool operator<(const UEdge i) const {return id<i.id;}
15.181 - };
15.182 -
15.183 - ListBpUGraphBase()
15.184 - : first_anode(-1), first_free_anode(-1),
15.185 - first_bnode(-1), first_free_bnode(-1),
15.186 - first_free_edge(-1) {}
15.187 -
15.188 - void firstANode(Node& node) const {
15.189 - node.id = first_anode != -1 ? (first_anode << 1) : -1;
15.190 - }
15.191 - void nextANode(Node& node) const {
15.192 - node.id = aNodes[node.id >> 1].next;
15.193 - }
15.194 -
15.195 - void firstBNode(Node& node) const {
15.196 - node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
15.197 - }
15.198 - void nextBNode(Node& node) const {
15.199 - node.id = bNodes[node.id >> 1].next;
15.200 - }
15.201 -
15.202 - void first(Node& node) const {
15.203 - if (first_anode != -1) {
15.204 - node.id = (first_anode << 1);
15.205 - } else if (first_bnode != -1) {
15.206 - node.id = (first_bnode << 1) + 1;
15.207 - } else {
15.208 - node.id = -1;
15.209 - }
15.210 - }
15.211 - void next(Node& node) const {
15.212 - if (aNode(node)) {
15.213 - node.id = aNodes[node.id >> 1].next;
15.214 - if (node.id == -1) {
15.215 - if (first_bnode != -1) {
15.216 - node.id = (first_bnode << 1) + 1;
15.217 - }
15.218 - }
15.219 - } else {
15.220 - node.id = bNodes[node.id >> 1].next;
15.221 - }
15.222 - }
15.223 -
15.224 - void first(UEdge& edge) const {
15.225 - int aNodeId = first_anode;
15.226 - while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
15.227 - aNodeId = aNodes[aNodeId].next != -1 ?
15.228 - aNodes[aNodeId].next >> 1 : -1;
15.229 - }
15.230 - if (aNodeId != -1) {
15.231 - edge.id = aNodes[aNodeId].first_edge;
15.232 - } else {
15.233 - edge.id = -1;
15.234 - }
15.235 - }
15.236 - void next(UEdge& edge) const {
15.237 - int aNodeId = edges[edge.id].aNode >> 1;
15.238 - edge.id = edges[edge.id].next_out;
15.239 - if (edge.id == -1) {
15.240 - aNodeId = aNodes[aNodeId].next != -1 ?
15.241 - aNodes[aNodeId].next >> 1 : -1;
15.242 - while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
15.243 - aNodeId = aNodes[aNodeId].next != -1 ?
15.244 - aNodes[aNodeId].next >> 1 : -1;
15.245 - }
15.246 - if (aNodeId != -1) {
15.247 - edge.id = aNodes[aNodeId].first_edge;
15.248 - } else {
15.249 - edge.id = -1;
15.250 - }
15.251 - }
15.252 - }
15.253 -
15.254 - void firstFromANode(UEdge& edge, const Node& node) const {
15.255 - LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
15.256 - edge.id = aNodes[node.id >> 1].first_edge;
15.257 - }
15.258 - void nextFromANode(UEdge& edge) const {
15.259 - edge.id = edges[edge.id].next_out;
15.260 - }
15.261 -
15.262 - void firstFromBNode(UEdge& edge, const Node& node) const {
15.263 - LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
15.264 - edge.id = bNodes[node.id >> 1].first_edge;
15.265 - }
15.266 - void nextFromBNode(UEdge& edge) const {
15.267 - edge.id = edges[edge.id].next_in;
15.268 - }
15.269 -
15.270 - static int id(const Node& node) {
15.271 - return node.id;
15.272 - }
15.273 - static Node nodeFromId(int id) {
15.274 - return Node(id);
15.275 - }
15.276 - int maxNodeId() const {
15.277 - return aNodes.size() > bNodes.size() ?
15.278 - aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
15.279 - }
15.280 -
15.281 - static int id(const UEdge& edge) {
15.282 - return edge.id;
15.283 - }
15.284 - static UEdge uEdgeFromId(int id) {
15.285 - return UEdge(id);
15.286 - }
15.287 - int maxUEdgeId() const {
15.288 - return edges.size();
15.289 - }
15.290 -
15.291 - static int aNodeId(const Node& node) {
15.292 - return node.id >> 1;
15.293 - }
15.294 - static Node fromANodeId(int id) {
15.295 - return Node(id << 1);
15.296 - }
15.297 - int maxANodeId() const {
15.298 - return aNodes.size();
15.299 - }
15.300 -
15.301 - static int bNodeId(const Node& node) {
15.302 - return node.id >> 1;
15.303 - }
15.304 - static Node fromBNodeId(int id) {
15.305 - return Node((id << 1) + 1);
15.306 - }
15.307 - int maxBNodeId() const {
15.308 - return bNodes.size();
15.309 - }
15.310 -
15.311 - Node aNode(const UEdge& edge) const {
15.312 - return Node(edges[edge.id].aNode);
15.313 - }
15.314 - Node bNode(const UEdge& edge) const {
15.315 - return Node(edges[edge.id].bNode);
15.316 - }
15.317 -
15.318 - static bool aNode(const Node& node) {
15.319 - return (node.id & 1) == 0;
15.320 - }
15.321 -
15.322 - static bool bNode(const Node& node) {
15.323 - return (node.id & 1) == 1;
15.324 - }
15.325 -
15.326 - Node addANode() {
15.327 - int aNodeId;
15.328 - if (first_free_anode == -1) {
15.329 - aNodeId = aNodes.size();
15.330 - aNodes.push_back(NodeT());
15.331 - } else {
15.332 - aNodeId = first_free_anode;
15.333 - first_free_anode = aNodes[first_free_anode].next;
15.334 - }
15.335 - if (first_anode != -1) {
15.336 - aNodes[aNodeId].next = first_anode << 1;
15.337 - aNodes[first_anode].prev = aNodeId << 1;
15.338 - } else {
15.339 - aNodes[aNodeId].next = -1;
15.340 - }
15.341 - aNodes[aNodeId].prev = -1;
15.342 - first_anode = aNodeId;
15.343 - aNodes[aNodeId].first_edge = -1;
15.344 - return Node(aNodeId << 1);
15.345 - }
15.346 -
15.347 - Node addBNode() {
15.348 - int bNodeId;
15.349 - if (first_free_bnode == -1) {
15.350 - bNodeId = bNodes.size();
15.351 - bNodes.push_back(NodeT());
15.352 - } else {
15.353 - bNodeId = first_free_bnode;
15.354 - first_free_bnode = bNodes[first_free_bnode].next;
15.355 - }
15.356 - if (first_bnode != -1) {
15.357 - bNodes[bNodeId].next = (first_bnode << 1) + 1;
15.358 - bNodes[first_bnode].prev = (bNodeId << 1) + 1;
15.359 - } else {
15.360 - bNodes[bNodeId].next = -1;
15.361 - }
15.362 - first_bnode = bNodeId;
15.363 - bNodes[bNodeId].first_edge = -1;
15.364 - return Node((bNodeId << 1) + 1);
15.365 - }
15.366 -
15.367 - UEdge addEdge(const Node& source, const Node& target) {
15.368 - LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
15.369 - int edgeId;
15.370 - if (first_free_edge != -1) {
15.371 - edgeId = first_free_edge;
15.372 - first_free_edge = edges[edgeId].next_out;
15.373 - } else {
15.374 - edgeId = edges.size();
15.375 - edges.push_back(UEdgeT());
15.376 - }
15.377 - if ((source.id & 1) == 0) {
15.378 - edges[edgeId].aNode = source.id;
15.379 - edges[edgeId].bNode = target.id;
15.380 - } else {
15.381 - edges[edgeId].aNode = target.id;
15.382 - edges[edgeId].bNode = source.id;
15.383 - }
15.384 - edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
15.385 - edges[edgeId].prev_out = -1;
15.386 - if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
15.387 - edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
15.388 - }
15.389 - aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
15.390 - edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
15.391 - edges[edgeId].prev_in = -1;
15.392 - if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
15.393 - edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
15.394 - }
15.395 - bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
15.396 - return UEdge(edgeId);
15.397 - }
15.398 -
15.399 - void erase(const Node& node) {
15.400 - if (aNode(node)) {
15.401 - int aNodeId = node.id >> 1;
15.402 - if (aNodes[aNodeId].prev != -1) {
15.403 - aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
15.404 - } else {
15.405 - first_anode = aNodes[aNodeId].next >> 1;
15.406 - }
15.407 - if (aNodes[aNodeId].next != -1) {
15.408 - aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
15.409 - }
15.410 - aNodes[aNodeId].next = first_free_anode;
15.411 - first_free_anode = aNodeId;
15.412 - } else {
15.413 - int bNodeId = node.id >> 1;
15.414 - if (bNodes[bNodeId].prev != -1) {
15.415 - bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
15.416 - } else {
15.417 - first_bnode = bNodes[bNodeId].next >> 1;
15.418 - }
15.419 - if (bNodes[bNodeId].next != -1) {
15.420 - bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
15.421 - }
15.422 - bNodes[bNodeId].next = first_free_bnode;
15.423 - first_free_bnode = bNodeId;
15.424 - }
15.425 - }
15.426 -
15.427 - void erase(const UEdge& edge) {
15.428 -
15.429 - if (edges[edge.id].prev_out != -1) {
15.430 - edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
15.431 - } else {
15.432 - aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
15.433 - }
15.434 - if (edges[edge.id].next_out != -1) {
15.435 - edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
15.436 - }
15.437 -
15.438 - if (edges[edge.id].prev_in != -1) {
15.439 - edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
15.440 - } else {
15.441 - bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
15.442 - }
15.443 - if (edges[edge.id].next_in != -1) {
15.444 - edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
15.445 - }
15.446 -
15.447 - edges[edge.id].next_out = first_free_edge;
15.448 - first_free_edge = edge.id;
15.449 - }
15.450 -
15.451 - void clear() {
15.452 - aNodes.clear();
15.453 - bNodes.clear();
15.454 - edges.clear();
15.455 - first_anode = -1;
15.456 - first_free_anode = -1;
15.457 - first_bnode = -1;
15.458 - first_free_bnode = -1;
15.459 - first_free_edge = -1;
15.460 - }
15.461 -
15.462 - };
15.463 -
15.464 -
15.465 - typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
15.466 -
15.467 - /// \ingroup graphs
15.468 - ///
15.469 - /// \brief A smart bipartite undirected graph class.
15.470 - ///
15.471 - /// This is a bipartite undirected graph implementation.
15.472 - /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
15.473 - /// concept.
15.474 - /// \sa concept::BpUGraph.
15.475 - ///
15.476 - class ListBpUGraph : public ExtendedListBpUGraphBase {};
15.477 -
15.478 -
15.479 - /// @}
15.480 } //namespace lemon
15.481
15.482
16.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
16.2 +++ b/lemon/list_ugraph.h Fri Jun 30 12:14:36 2006 +0000
16.3 @@ -0,0 +1,120 @@
16.4 +/* -*- C++ -*-
16.5 + *
16.6 + * This file is a part of LEMON, a generic C++ optimization library
16.7 + *
16.8 + * Copyright (C) 2003-2006
16.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
16.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
16.11 + *
16.12 + * Permission to use, modify and distribute this software is granted
16.13 + * provided that this copyright notice appears in all copies. For
16.14 + * precise terms see the accompanying LICENSE file.
16.15 + *
16.16 + * This software is provided "AS IS" with no warranty of any kind,
16.17 + * express or implied, and with no claim as to its suitability for any
16.18 + * purpose.
16.19 + *
16.20 + */
16.21 +
16.22 +#ifndef LEMON_LIST_UGRAPH_H
16.23 +#define LEMON_LIST_UGRAPH_H
16.24 +
16.25 +///\ingroup graphs
16.26 +///\file
16.27 +///\brief ListUGraph classes.
16.28 +
16.29 +#include <lemon/list_graph.h>
16.30 +#include <lemon/bits/base_extender.h>
16.31 +#include <lemon/bits/ugraph_extender.h>
16.32 +
16.33 +#include <vector>
16.34 +#include <list>
16.35 +
16.36 +namespace lemon {
16.37 +
16.38 + typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
16.39 + ExtendedListUGraphBase;
16.40 +
16.41 + /// \ingroup graphs
16.42 +
16.43 + ///An undirected list graph class.
16.44 +
16.45 + ///This is a simple and fast erasable undirected graph implementation.
16.46 + ///
16.47 + ///It conforms to the
16.48 + ///\ref concept::UGraph "UGraph" concept.
16.49 + ///
16.50 + ///\sa concept::UGraph.
16.51 + ///
16.52 + ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
16.53 + ///haven't been implemented yet.
16.54 + ///
16.55 + class ListUGraph : public ExtendedListUGraphBase {
16.56 + public:
16.57 + typedef ExtendedListUGraphBase Parent;
16.58 + /// \brief Add a new node to the graph.
16.59 + ///
16.60 + /// \return the new node.
16.61 + ///
16.62 + Node addNode() { return Parent::addNode(); }
16.63 +
16.64 + /// \brief Add a new edge to the graph.
16.65 + ///
16.66 + /// Add a new edge to the graph with source node \c s
16.67 + /// and target node \c t.
16.68 + /// \return the new undirected edge.
16.69 + UEdge addEdge(const Node& s, const Node& t) {
16.70 + return Parent::addEdge(s, t);
16.71 + }
16.72 + /// \brief Changes the target of \c e to \c n
16.73 + ///
16.74 + /// Changes the target of \c e to \c n
16.75 + ///
16.76 + /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
16.77 + /// referencing the changed edge remain
16.78 + /// valid. However <tt>InEdge</tt>'s are invalidated.
16.79 + void changeTarget(UEdge e, Node n) {
16.80 + Parent::changeTarget(e,n);
16.81 + }
16.82 + /// Changes the source of \c e to \c n
16.83 + ///
16.84 + /// Changes the source of \c e to \c n
16.85 + ///
16.86 + ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
16.87 + ///referencing the changed edge remain
16.88 + ///valid. However <tt>OutEdge</tt>'s are invalidated.
16.89 + void changeSource(UEdge e, Node n) {
16.90 + Parent::changeSource(e,n);
16.91 + }
16.92 + /// \brief Contract two nodes.
16.93 + ///
16.94 + /// This function contracts two nodes.
16.95 + ///
16.96 + /// Node \p b will be removed but instead of deleting
16.97 + /// its neighboring edges, they will be joined to \p a.
16.98 + /// The last parameter \p r controls whether to remove loops. \c true
16.99 + /// means that loops will be removed.
16.100 + ///
16.101 + /// \note The <tt>Edge</tt>s
16.102 + /// referencing a moved edge remain
16.103 + /// valid.
16.104 + void contract(Node a, Node b, bool r = true) {
16.105 + for(IncEdgeIt e(*this, b); e!=INVALID;) {
16.106 + IncEdgeIt f = e; ++f;
16.107 + if (r && runningNode(e) == a) {
16.108 + erase(e);
16.109 + } else if (source(e) == b) {
16.110 + changeSource(e, a);
16.111 + } else {
16.112 + changeTarget(e, a);
16.113 + }
16.114 + e = f;
16.115 + }
16.116 + erase(b);
16.117 + }
16.118 + };
16.119 +
16.120 +} //namespace lemon
16.121 +
16.122 +
16.123 +#endif
17.1 --- a/lemon/min_cut.h Wed Jun 28 16:27:44 2006 +0000
17.2 +++ b/lemon/min_cut.h Fri Jun 30 12:14:36 2006 +0000
17.3 @@ -23,6 +23,7 @@
17.4 /// \brief Maximum cardinality search and min cut in undirected graphs.
17.5
17.6 #include <lemon/list_graph.h>
17.7 +#include <lemon/list_ugraph.h>
17.8 #include <lemon/bin_heap.h>
17.9 #include <lemon/bucket_heap.h>
17.10
17.11 @@ -194,7 +195,7 @@
17.12 #ifdef DOXYGEN
17.13 template <typename _Graph, typename _CapacityMap, typename _Traits>
17.14 #else
17.15 - template <typename _Graph = ListUGraph,
17.16 + template <typename _Graph = ListGraph,
17.17 typename _CapacityMap = typename _Graph::template EdgeMap<int>,
17.18 typename _Traits =
17.19 MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
18.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
18.2 +++ b/lemon/smart_bpugraph.h Fri Jun 30 12:14:36 2006 +0000
18.3 @@ -0,0 +1,273 @@
18.4 +/* -*- C++ -*-
18.5 + *
18.6 + * This file is a part of LEMON, a generic C++ optimization library
18.7 + *
18.8 + * Copyright (C) 2003-2006
18.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
18.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
18.11 + *
18.12 + * Permission to use, modify and distribute this software is granted
18.13 + * provided that this copyright notice appears in all copies. For
18.14 + * precise terms see the accompanying LICENSE file.
18.15 + *
18.16 + * This software is provided "AS IS" with no warranty of any kind,
18.17 + * express or implied, and with no claim as to its suitability for any
18.18 + * purpose.
18.19 + *
18.20 + */
18.21 +
18.22 +#ifndef LEMON_SMART_BPUGRAPH_H
18.23 +#define LEMON_SMART_BPUGRAPH_H
18.24 +
18.25 +///\ingroup graphs
18.26 +///\file
18.27 +///\brief SmartBpUGraph class.
18.28 +
18.29 +#include <vector>
18.30 +
18.31 +#include <lemon/bits/invalid.h>
18.32 +
18.33 +#include <lemon/bits/bpugraph_extender.h>
18.34 +
18.35 +#include <lemon/bits/utility.h>
18.36 +#include <lemon/error.h>
18.37 +
18.38 +#include <lemon/bits/graph_extender.h>
18.39 +
18.40 +namespace lemon {
18.41 +
18.42 + class SmartBpUGraphBase {
18.43 + public:
18.44 +
18.45 + class NodeSetError : public LogicError {
18.46 + virtual const char* exceptionName() const {
18.47 + return "lemon::SmartBpUGraph::NodeSetError";
18.48 + }
18.49 + };
18.50 +
18.51 + protected:
18.52 +
18.53 + struct NodeT {
18.54 + int first;
18.55 + NodeT() {}
18.56 + NodeT(int _first) : first(_first) {}
18.57 + };
18.58 +
18.59 + struct UEdgeT {
18.60 + int aNode, next_out;
18.61 + int bNode, next_in;
18.62 + };
18.63 +
18.64 + std::vector<NodeT> aNodes;
18.65 + std::vector<NodeT> bNodes;
18.66 +
18.67 + std::vector<UEdgeT> edges;
18.68 +
18.69 + public:
18.70 +
18.71 + class Node {
18.72 + friend class SmartBpUGraphBase;
18.73 + protected:
18.74 + int id;
18.75 +
18.76 + Node(int _id) : id(_id) {}
18.77 + public:
18.78 + Node() {}
18.79 + Node(Invalid) { id = -1; }
18.80 + bool operator==(const Node i) const {return id==i.id;}
18.81 + bool operator!=(const Node i) const {return id!=i.id;}
18.82 + bool operator<(const Node i) const {return id<i.id;}
18.83 + };
18.84 +
18.85 + class UEdge {
18.86 + friend class SmartBpUGraphBase;
18.87 + protected:
18.88 + int id;
18.89 +
18.90 + UEdge(int _id) { id = _id;}
18.91 + public:
18.92 + UEdge() {}
18.93 + UEdge (Invalid) { id = -1; }
18.94 + bool operator==(const UEdge i) const {return id==i.id;}
18.95 + bool operator!=(const UEdge i) const {return id!=i.id;}
18.96 + bool operator<(const UEdge i) const {return id<i.id;}
18.97 + };
18.98 +
18.99 + void firstANode(Node& node) const {
18.100 + node.id = 2 * aNodes.size() - 2;
18.101 + if (node.id < 0) node.id = -1;
18.102 + }
18.103 + void nextANode(Node& node) const {
18.104 + node.id -= 2;
18.105 + if (node.id < 0) node.id = -1;
18.106 + }
18.107 +
18.108 + void firstBNode(Node& node) const {
18.109 + node.id = 2 * bNodes.size() - 1;
18.110 + }
18.111 + void nextBNode(Node& node) const {
18.112 + node.id -= 2;
18.113 + }
18.114 +
18.115 + void first(Node& node) const {
18.116 + if (aNodes.size() > 0) {
18.117 + node.id = 2 * aNodes.size() - 2;
18.118 + } else {
18.119 + node.id = 2 * bNodes.size() - 1;
18.120 + }
18.121 + }
18.122 + void next(Node& node) const {
18.123 + node.id -= 2;
18.124 + if (node.id == -2) {
18.125 + node.id = 2 * bNodes.size() - 1;
18.126 + }
18.127 + }
18.128 +
18.129 + void first(UEdge& edge) const {
18.130 + edge.id = edges.size() - 1;
18.131 + }
18.132 + void next(UEdge& edge) const {
18.133 + --edge.id;
18.134 + }
18.135 +
18.136 + void firstFromANode(UEdge& edge, const Node& node) const {
18.137 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
18.138 + edge.id = aNodes[node.id >> 1].first;
18.139 + }
18.140 + void nextFromANode(UEdge& edge) const {
18.141 + edge.id = edges[edge.id].next_out;
18.142 + }
18.143 +
18.144 + void firstFromBNode(UEdge& edge, const Node& node) const {
18.145 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
18.146 + edge.id = bNodes[node.id >> 1].first;
18.147 + }
18.148 + void nextFromBNode(UEdge& edge) const {
18.149 + edge.id = edges[edge.id].next_in;
18.150 + }
18.151 +
18.152 + static int id(const Node& node) {
18.153 + return node.id;
18.154 + }
18.155 + static Node nodeFromId(int id) {
18.156 + return Node(id);
18.157 + }
18.158 + int maxNodeId() const {
18.159 + return aNodes.size() > bNodes.size() ?
18.160 + aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
18.161 + }
18.162 +
18.163 + static int id(const UEdge& edge) {
18.164 + return edge.id;
18.165 + }
18.166 + static UEdge uEdgeFromId(int id) {
18.167 + return UEdge(id);
18.168 + }
18.169 + int maxUEdgeId() const {
18.170 + return edges.size();
18.171 + }
18.172 +
18.173 + static int aNodeId(const Node& node) {
18.174 + return node.id >> 1;
18.175 + }
18.176 + static Node fromANodeId(int id) {
18.177 + return Node(id << 1);
18.178 + }
18.179 + int maxANodeId() const {
18.180 + return aNodes.size();
18.181 + }
18.182 +
18.183 + static int bNodeId(const Node& node) {
18.184 + return node.id >> 1;
18.185 + }
18.186 + static Node fromBNodeId(int id) {
18.187 + return Node((id << 1) + 1);
18.188 + }
18.189 + int maxBNodeId() const {
18.190 + return bNodes.size();
18.191 + }
18.192 +
18.193 + Node aNode(const UEdge& edge) const {
18.194 + return Node(edges[edge.id].aNode);
18.195 + }
18.196 + Node bNode(const UEdge& edge) const {
18.197 + return Node(edges[edge.id].bNode);
18.198 + }
18.199 +
18.200 + static bool aNode(const Node& node) {
18.201 + return (node.id & 1) == 0;
18.202 + }
18.203 +
18.204 + static bool bNode(const Node& node) {
18.205 + return (node.id & 1) == 1;
18.206 + }
18.207 +
18.208 + Node addANode() {
18.209 + NodeT nodeT;
18.210 + nodeT.first = -1;
18.211 + aNodes.push_back(nodeT);
18.212 + return Node(aNodes.size() * 2 - 2);
18.213 + }
18.214 +
18.215 + Node addBNode() {
18.216 + NodeT nodeT;
18.217 + nodeT.first = -1;
18.218 + bNodes.push_back(nodeT);
18.219 + return Node(bNodes.size() * 2 - 1);
18.220 + }
18.221 +
18.222 + UEdge addEdge(const Node& source, const Node& target) {
18.223 + LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
18.224 + UEdgeT edgeT;
18.225 + if ((source.id & 1) == 0) {
18.226 + edgeT.aNode = source.id;
18.227 + edgeT.bNode = target.id;
18.228 + } else {
18.229 + edgeT.aNode = target.id;
18.230 + edgeT.bNode = source.id;
18.231 + }
18.232 + edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
18.233 + aNodes[edgeT.aNode >> 1].first = edges.size();
18.234 + edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
18.235 + bNodes[edgeT.bNode >> 1].first = edges.size();
18.236 + edges.push_back(edgeT);
18.237 + return UEdge(edges.size() - 1);
18.238 + }
18.239 +
18.240 + void clear() {
18.241 + aNodes.clear();
18.242 + bNodes.clear();
18.243 + edges.clear();
18.244 + }
18.245 +
18.246 + typedef True NodeNumTag;
18.247 + int nodeNum() const { return aNodes.size() + bNodes.size(); }
18.248 + int aNodeNum() const { return aNodes.size(); }
18.249 + int bNodeNum() const { return bNodes.size(); }
18.250 +
18.251 + typedef True EdgeNumTag;
18.252 + int uEdgeNum() const { return edges.size(); }
18.253 +
18.254 + };
18.255 +
18.256 +
18.257 + typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
18.258 +
18.259 + /// \ingroup graphs
18.260 + ///
18.261 + /// \brief A smart bipartite undirected graph class.
18.262 + ///
18.263 + /// This is a simple and fast bipartite undirected graph implementation.
18.264 + /// It is also quite memory efficient, but at the price
18.265 + /// that <b> it does not support node and edge deletions</b>.
18.266 + /// Except from this it conforms to
18.267 + /// the \ref concept::BpUGraph "BpUGraph" concept.
18.268 + /// \sa concept::BpUGraph.
18.269 + ///
18.270 + class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
18.271 +
18.272 +
18.273 +} //namespace lemon
18.274 +
18.275 +
18.276 +#endif //LEMON_SMART_GRAPH_H
19.1 --- a/lemon/smart_graph.h Wed Jun 28 16:27:44 2006 +0000
19.2 +++ b/lemon/smart_graph.h Fri Jun 30 12:14:36 2006 +0000
19.3 @@ -21,17 +21,15 @@
19.4
19.5 ///\ingroup graphs
19.6 ///\file
19.7 -///\brief SmartGraph and SmartUGraph classes.
19.8 +///\brief SmartGraph class.
19.9
19.10 #include <vector>
19.11
19.12 #include <lemon/bits/invalid.h>
19.13
19.14 -#include <lemon/bits/base_extender.h>
19.15 #include <lemon/bits/graph_extender.h>
19.16
19.17 #include <lemon/bits/utility.h>
19.18 -#include <lemon/error.h>
19.19
19.20 #include <lemon/bits/graph_extender.h>
19.21
19.22 @@ -356,261 +354,6 @@
19.23 };
19.24
19.25
19.26 - /**************** Undirected List Graph ****************/
19.27 -
19.28 - typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
19.29 - ExtendedSmartUGraphBase;
19.30 -
19.31 - /// \ingroup graphs
19.32 - ///
19.33 - /// \brief A smart undirected graph class.
19.34 - ///
19.35 - /// This is a simple and fast undirected graph implementation.
19.36 - /// It is also quite memory efficient, but at the price
19.37 - /// that <b> it does support only limited (only stack-like)
19.38 - /// node and edge deletions</b>.
19.39 - /// Except from this it conforms to
19.40 - /// the \ref concept::UGraph "UGraph" concept.
19.41 - /// \sa concept::UGraph.
19.42 - ///
19.43 - /// \todo Snapshot hasn't been implemented yet.
19.44 - ///
19.45 - class SmartUGraph : public ExtendedSmartUGraphBase {
19.46 - };
19.47 -
19.48 -
19.49 - class SmartBpUGraphBase {
19.50 - public:
19.51 -
19.52 - class NodeSetError : public LogicError {
19.53 - virtual const char* exceptionName() const {
19.54 - return "lemon::SmartBpUGraph::NodeSetError";
19.55 - }
19.56 - };
19.57 -
19.58 - protected:
19.59 -
19.60 - struct NodeT {
19.61 - int first;
19.62 - NodeT() {}
19.63 - NodeT(int _first) : first(_first) {}
19.64 - };
19.65 -
19.66 - struct UEdgeT {
19.67 - int aNode, next_out;
19.68 - int bNode, next_in;
19.69 - };
19.70 -
19.71 - std::vector<NodeT> aNodes;
19.72 - std::vector<NodeT> bNodes;
19.73 -
19.74 - std::vector<UEdgeT> edges;
19.75 -
19.76 - public:
19.77 -
19.78 - class Node {
19.79 - friend class SmartBpUGraphBase;
19.80 - protected:
19.81 - int id;
19.82 -
19.83 - Node(int _id) : id(_id) {}
19.84 - public:
19.85 - Node() {}
19.86 - Node(Invalid) { id = -1; }
19.87 - bool operator==(const Node i) const {return id==i.id;}
19.88 - bool operator!=(const Node i) const {return id!=i.id;}
19.89 - bool operator<(const Node i) const {return id<i.id;}
19.90 - };
19.91 -
19.92 - class UEdge {
19.93 - friend class SmartBpUGraphBase;
19.94 - protected:
19.95 - int id;
19.96 -
19.97 - UEdge(int _id) { id = _id;}
19.98 - public:
19.99 - UEdge() {}
19.100 - UEdge (Invalid) { id = -1; }
19.101 - bool operator==(const UEdge i) const {return id==i.id;}
19.102 - bool operator!=(const UEdge i) const {return id!=i.id;}
19.103 - bool operator<(const UEdge i) const {return id<i.id;}
19.104 - };
19.105 -
19.106 - void firstANode(Node& node) const {
19.107 - node.id = 2 * aNodes.size() - 2;
19.108 - if (node.id < 0) node.id = -1;
19.109 - }
19.110 - void nextANode(Node& node) const {
19.111 - node.id -= 2;
19.112 - if (node.id < 0) node.id = -1;
19.113 - }
19.114 -
19.115 - void firstBNode(Node& node) const {
19.116 - node.id = 2 * bNodes.size() - 1;
19.117 - }
19.118 - void nextBNode(Node& node) const {
19.119 - node.id -= 2;
19.120 - }
19.121 -
19.122 - void first(Node& node) const {
19.123 - if (aNodes.size() > 0) {
19.124 - node.id = 2 * aNodes.size() - 2;
19.125 - } else {
19.126 - node.id = 2 * bNodes.size() - 1;
19.127 - }
19.128 - }
19.129 - void next(Node& node) const {
19.130 - node.id -= 2;
19.131 - if (node.id == -2) {
19.132 - node.id = 2 * bNodes.size() - 1;
19.133 - }
19.134 - }
19.135 -
19.136 - void first(UEdge& edge) const {
19.137 - edge.id = edges.size() - 1;
19.138 - }
19.139 - void next(UEdge& edge) const {
19.140 - --edge.id;
19.141 - }
19.142 -
19.143 - void firstFromANode(UEdge& edge, const Node& node) const {
19.144 - LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
19.145 - edge.id = aNodes[node.id >> 1].first;
19.146 - }
19.147 - void nextFromANode(UEdge& edge) const {
19.148 - edge.id = edges[edge.id].next_out;
19.149 - }
19.150 -
19.151 - void firstFromBNode(UEdge& edge, const Node& node) const {
19.152 - LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
19.153 - edge.id = bNodes[node.id >> 1].first;
19.154 - }
19.155 - void nextFromBNode(UEdge& edge) const {
19.156 - edge.id = edges[edge.id].next_in;
19.157 - }
19.158 -
19.159 - static int id(const Node& node) {
19.160 - return node.id;
19.161 - }
19.162 - static Node nodeFromId(int id) {
19.163 - return Node(id);
19.164 - }
19.165 - int maxNodeId() const {
19.166 - return aNodes.size() > bNodes.size() ?
19.167 - aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
19.168 - }
19.169 -
19.170 - static int id(const UEdge& edge) {
19.171 - return edge.id;
19.172 - }
19.173 - static UEdge uEdgeFromId(int id) {
19.174 - return UEdge(id);
19.175 - }
19.176 - int maxUEdgeId() const {
19.177 - return edges.size();
19.178 - }
19.179 -
19.180 - static int aNodeId(const Node& node) {
19.181 - return node.id >> 1;
19.182 - }
19.183 - static Node fromANodeId(int id) {
19.184 - return Node(id << 1);
19.185 - }
19.186 - int maxANodeId() const {
19.187 - return aNodes.size();
19.188 - }
19.189 -
19.190 - static int bNodeId(const Node& node) {
19.191 - return node.id >> 1;
19.192 - }
19.193 - static Node fromBNodeId(int id) {
19.194 - return Node((id << 1) + 1);
19.195 - }
19.196 - int maxBNodeId() const {
19.197 - return bNodes.size();
19.198 - }
19.199 -
19.200 - Node aNode(const UEdge& edge) const {
19.201 - return Node(edges[edge.id].aNode);
19.202 - }
19.203 - Node bNode(const UEdge& edge) const {
19.204 - return Node(edges[edge.id].bNode);
19.205 - }
19.206 -
19.207 - static bool aNode(const Node& node) {
19.208 - return (node.id & 1) == 0;
19.209 - }
19.210 -
19.211 - static bool bNode(const Node& node) {
19.212 - return (node.id & 1) == 1;
19.213 - }
19.214 -
19.215 - Node addANode() {
19.216 - NodeT nodeT;
19.217 - nodeT.first = -1;
19.218 - aNodes.push_back(nodeT);
19.219 - return Node(aNodes.size() * 2 - 2);
19.220 - }
19.221 -
19.222 - Node addBNode() {
19.223 - NodeT nodeT;
19.224 - nodeT.first = -1;
19.225 - bNodes.push_back(nodeT);
19.226 - return Node(bNodes.size() * 2 - 1);
19.227 - }
19.228 -
19.229 - UEdge addEdge(const Node& source, const Node& target) {
19.230 - LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
19.231 - UEdgeT edgeT;
19.232 - if ((source.id & 1) == 0) {
19.233 - edgeT.aNode = source.id;
19.234 - edgeT.bNode = target.id;
19.235 - } else {
19.236 - edgeT.aNode = target.id;
19.237 - edgeT.bNode = source.id;
19.238 - }
19.239 - edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
19.240 - aNodes[edgeT.aNode >> 1].first = edges.size();
19.241 - edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
19.242 - bNodes[edgeT.bNode >> 1].first = edges.size();
19.243 - edges.push_back(edgeT);
19.244 - return UEdge(edges.size() - 1);
19.245 - }
19.246 -
19.247 - void clear() {
19.248 - aNodes.clear();
19.249 - bNodes.clear();
19.250 - edges.clear();
19.251 - }
19.252 -
19.253 - typedef True NodeNumTag;
19.254 - int nodeNum() const { return aNodes.size() + bNodes.size(); }
19.255 - int aNodeNum() const { return aNodes.size(); }
19.256 - int bNodeNum() const { return bNodes.size(); }
19.257 -
19.258 - typedef True EdgeNumTag;
19.259 - int uEdgeNum() const { return edges.size(); }
19.260 -
19.261 - };
19.262 -
19.263 -
19.264 - typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
19.265 -
19.266 - /// \ingroup graphs
19.267 - ///
19.268 - /// \brief A smart bipartite undirected graph class.
19.269 - ///
19.270 - /// This is a simple and fast bipartite undirected graph implementation.
19.271 - /// It is also quite memory efficient, but at the price
19.272 - /// that <b> it does not support node and edge deletions</b>.
19.273 - /// Except from this it conforms to
19.274 - /// the \ref concept::BpUGraph "BpUGraph" concept.
19.275 - /// \sa concept::BpUGraph.
19.276 - ///
19.277 - class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
19.278 -
19.279 -
19.280 - /// @}
19.281 } //namespace lemon
19.282
19.283
20.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
20.2 +++ b/lemon/smart_ugraph.h Fri Jun 30 12:14:36 2006 +0000
20.3 @@ -0,0 +1,68 @@
20.4 +/* -*- C++ -*-
20.5 + *
20.6 + * This file is a part of LEMON, a generic C++ optimization library
20.7 + *
20.8 + * Copyright (C) 2003-2006
20.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
20.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
20.11 + *
20.12 + * Permission to use, modify and distribute this software is granted
20.13 + * provided that this copyright notice appears in all copies. For
20.14 + * precise terms see the accompanying LICENSE file.
20.15 + *
20.16 + * This software is provided "AS IS" with no warranty of any kind,
20.17 + * express or implied, and with no claim as to its suitability for any
20.18 + * purpose.
20.19 + *
20.20 + */
20.21 +
20.22 +#ifndef LEMON_SMART_UGRAPH_H
20.23 +#define LEMON_SMART_UGRAPH_H
20.24 +
20.25 +///\ingroup graphs
20.26 +///\file
20.27 +///\brief SmartUGraph class.
20.28 +
20.29 +#include <vector>
20.30 +
20.31 +#include <lemon/bits/invalid.h>
20.32 +
20.33 +#include <lemon/smart_graph.h>
20.34 +#include <lemon/bits/base_extender.h>
20.35 +#include <lemon/bits/ugraph_extender.h>
20.36 +
20.37 +#include <lemon/bits/utility.h>
20.38 +#include <lemon/error.h>
20.39 +
20.40 +#include <lemon/bits/graph_extender.h>
20.41 +
20.42 +namespace lemon {
20.43 +
20.44 +
20.45 + typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
20.46 + ExtendedSmartUGraphBase;
20.47 +
20.48 + /// \ingroup graphs
20.49 + ///
20.50 + /// \brief A smart undirected graph class.
20.51 + ///
20.52 + /// This is a simple and fast undirected graph implementation.
20.53 + /// It is also quite memory efficient, but at the price
20.54 + /// that <b> it does support only limited (only stack-like)
20.55 + /// node and edge deletions</b>.
20.56 + /// Except from this it conforms to
20.57 + /// the \ref concept::UGraph "UGraph" concept.
20.58 + /// \sa concept::UGraph.
20.59 + ///
20.60 + /// \todo Snapshot hasn't been implemented yet.
20.61 + ///
20.62 + class SmartUGraph : public ExtendedSmartUGraphBase {
20.63 + };
20.64 +
20.65 +
20.66 +
20.67 + /// @}
20.68 +} //namespace lemon
20.69 +
20.70 +
20.71 +#endif //LEMON_SMART_GRAPH_H
21.1 --- a/test/bipartite_matching_test.cc Wed Jun 28 16:27:44 2006 +0000
21.2 +++ b/test/bipartite_matching_test.cc Fri Jun 30 12:14:36 2006 +0000
21.3 @@ -2,7 +2,7 @@
21.4 #include <iostream>
21.5 #include <sstream>
21.6
21.7 -#include <lemon/list_graph.h>
21.8 +#include <lemon/list_bpugraph.h>
21.9
21.10 #include <lemon/bpugraph_adaptor.h>
21.11 #include <lemon/bipartite_matching.h>
22.1 --- a/test/max_matching_test.cc Wed Jun 28 16:27:44 2006 +0000
22.2 +++ b/test/max_matching_test.cc Fri Jun 30 12:14:36 2006 +0000
22.3 @@ -23,7 +23,7 @@
22.4 #include <cstdlib>
22.5
22.6 #include "test_tools.h"
22.7 -#include <lemon/list_graph.h>
22.8 +#include <lemon/list_ugraph.h>
22.9 #include <lemon/max_matching.h>
22.10
22.11 using namespace std;
23.1 --- a/test/ugraph_test.cc Wed Jun 28 16:27:44 2006 +0000
23.2 +++ b/test/ugraph_test.cc Fri Jun 30 12:14:36 2006 +0000
23.3 @@ -18,9 +18,9 @@
23.4
23.5 #include <lemon/bits/graph_extender.h>
23.6 #include <lemon/concept/ugraph.h>
23.7 -#include <lemon/list_graph.h>
23.8 -#include <lemon/smart_graph.h>
23.9 -#include <lemon/full_graph.h>
23.10 +#include <lemon/list_ugraph.h>
23.11 +#include <lemon/smart_ugraph.h>
23.12 +#include <lemon/full_ugraph.h>
23.13 #include <lemon/grid_ugraph.h>
23.14
23.15 #include <lemon/graph_utils.h>