1.1 --- a/lemon/bits/graph_extender.h Sun Nov 14 16:35:31 2010 +0100
1.2 +++ b/lemon/bits/graph_extender.h Sun Nov 14 20:06:23 2010 +0100
1.3 @@ -746,6 +746,610 @@
1.4
1.5 };
1.6
1.7 + // \ingroup _graphbits
1.8 + //
1.9 + // \brief Extender for the BpGraphs
1.10 + template <typename Base>
1.11 + class BpGraphExtender : public Base {
1.12 + typedef Base Parent;
1.13 +
1.14 + public:
1.15 +
1.16 + typedef BpGraphExtender BpGraph;
1.17 +
1.18 + typedef True UndirectedTag;
1.19 +
1.20 + typedef typename Parent::Node Node;
1.21 + typedef typename Parent::Arc Arc;
1.22 + typedef typename Parent::Edge Edge;
1.23 +
1.24 + // BpGraph extension
1.25 +
1.26 + class RedNode : public Node {
1.27 + public:
1.28 + RedNode() {}
1.29 + RedNode(const RedNode& node) : Node(node) {}
1.30 + RedNode(Invalid) : Node(INVALID){}
1.31 + RedNode(const Node& node) : Node(node) {}
1.32 + };
1.33 + class BlueNode : public Node {
1.34 + public:
1.35 + BlueNode() {}
1.36 + BlueNode(const BlueNode& node) : Node(node) {}
1.37 + BlueNode(Invalid) : Node(INVALID){}
1.38 + BlueNode(const Node& node) : Node(node) {}
1.39 + };
1.40 +
1.41 + using Parent::first;
1.42 + using Parent::next;
1.43 +
1.44 + void first(RedNode& node) const {
1.45 + Parent::firstRed(node);
1.46 + }
1.47 +
1.48 + void next(RedNode& node) const {
1.49 + Parent::nextRed(node);
1.50 + }
1.51 +
1.52 + void first(BlueNode& node) const {
1.53 + Parent::firstBlue(node);
1.54 + }
1.55 +
1.56 + void next(BlueNode& node) const {
1.57 + Parent::nextBlue(node);
1.58 + }
1.59 +
1.60 + using Parent::id;
1.61 +
1.62 + int id(const RedNode& node) const {
1.63 + return Parent::redId(node);
1.64 + }
1.65 +
1.66 + int id(const BlueNode& node) const {
1.67 + return Parent::blueId(node);
1.68 + }
1.69 +
1.70 + int maxId(Node) const {
1.71 + return Parent::maxNodeId();
1.72 + }
1.73 +
1.74 + int maxId(RedNode) const {
1.75 + return Parent::maxRedId();
1.76 + }
1.77 +
1.78 + int maxId(BlueNode) const {
1.79 + return Parent::maxBlueId();
1.80 + }
1.81 +
1.82 + int maxId(Arc) const {
1.83 + return Parent::maxArcId();
1.84 + }
1.85 +
1.86 + int maxId(Edge) const {
1.87 + return Parent::maxEdgeId();
1.88 + }
1.89 +
1.90 + static Node fromId(int id, Node) {
1.91 + return Parent::nodeFromId(id);
1.92 + }
1.93 +
1.94 + static Arc fromId(int id, Arc) {
1.95 + return Parent::arcFromId(id);
1.96 + }
1.97 +
1.98 + static Edge fromId(int id, Edge) {
1.99 + return Parent::edgeFromId(id);
1.100 + }
1.101 +
1.102 + Node oppositeNode(const Node &n, const Edge &e) const {
1.103 + if( n == Parent::u(e))
1.104 + return Parent::v(e);
1.105 + else if( n == Parent::v(e))
1.106 + return Parent::u(e);
1.107 + else
1.108 + return INVALID;
1.109 + }
1.110 +
1.111 + Arc oppositeArc(const Arc &arc) const {
1.112 + return Parent::direct(arc, !Parent::direction(arc));
1.113 + }
1.114 +
1.115 + using Parent::direct;
1.116 + Arc direct(const Edge &edge, const Node &node) const {
1.117 + return Parent::direct(edge, Parent::u(edge) == node);
1.118 + }
1.119 +
1.120 + // Alterable extension
1.121 +
1.122 + typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
1.123 + typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
1.124 + typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
1.125 + typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
1.126 + typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
1.127 +
1.128 +
1.129 + protected:
1.130 +
1.131 + mutable NodeNotifier node_notifier;
1.132 + mutable RedNodeNotifier red_node_notifier;
1.133 + mutable BlueNodeNotifier blue_node_notifier;
1.134 + mutable ArcNotifier arc_notifier;
1.135 + mutable EdgeNotifier edge_notifier;
1.136 +
1.137 + public:
1.138 +
1.139 + NodeNotifier& notifier(Node) const {
1.140 + return node_notifier;
1.141 + }
1.142 +
1.143 + RedNodeNotifier& notifier(RedNode) const {
1.144 + return red_node_notifier;
1.145 + }
1.146 +
1.147 + BlueNodeNotifier& notifier(BlueNode) const {
1.148 + return blue_node_notifier;
1.149 + }
1.150 +
1.151 + ArcNotifier& notifier(Arc) const {
1.152 + return arc_notifier;
1.153 + }
1.154 +
1.155 + EdgeNotifier& notifier(Edge) const {
1.156 + return edge_notifier;
1.157 + }
1.158 +
1.159 +
1.160 +
1.161 + class NodeIt : public Node {
1.162 + const BpGraph* _graph;
1.163 + public:
1.164 +
1.165 + NodeIt() {}
1.166 +
1.167 + NodeIt(Invalid i) : Node(i) { }
1.168 +
1.169 + explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
1.170 + _graph->first(static_cast<Node&>(*this));
1.171 + }
1.172 +
1.173 + NodeIt(const BpGraph& graph, const Node& node)
1.174 + : Node(node), _graph(&graph) {}
1.175 +
1.176 + NodeIt& operator++() {
1.177 + _graph->next(*this);
1.178 + return *this;
1.179 + }
1.180 +
1.181 + };
1.182 +
1.183 + class RedIt : public Node {
1.184 + const BpGraph* _graph;
1.185 + public:
1.186 +
1.187 + RedIt() {}
1.188 +
1.189 + RedIt(Invalid i) : Node(i) { }
1.190 +
1.191 + explicit RedIt(const BpGraph& graph) : _graph(&graph) {
1.192 + _graph->firstRed(static_cast<Node&>(*this));
1.193 + }
1.194 +
1.195 + RedIt(const BpGraph& graph, const Node& node)
1.196 + : Node(node), _graph(&graph) {
1.197 + LEMON_DEBUG(_graph->red(node), "Node has to be red.");
1.198 + }
1.199 +
1.200 + RedIt& operator++() {
1.201 + _graph->nextRed(*this);
1.202 + return *this;
1.203 + }
1.204 +
1.205 + };
1.206 +
1.207 + class BlueIt : public Node {
1.208 + const BpGraph* _graph;
1.209 + public:
1.210 +
1.211 + BlueIt() {}
1.212 +
1.213 + BlueIt(Invalid i) : Node(i) { }
1.214 +
1.215 + explicit BlueIt(const BpGraph& graph) : _graph(&graph) {
1.216 + _graph->firstBlue(static_cast<Node&>(*this));
1.217 + }
1.218 +
1.219 + BlueIt(const BpGraph& graph, const Node& node)
1.220 + : Node(node), _graph(&graph) {
1.221 + LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");
1.222 + }
1.223 +
1.224 + BlueIt& operator++() {
1.225 + _graph->nextBlue(*this);
1.226 + return *this;
1.227 + }
1.228 +
1.229 + };
1.230 +
1.231 +
1.232 + class ArcIt : public Arc {
1.233 + const BpGraph* _graph;
1.234 + public:
1.235 +
1.236 + ArcIt() { }
1.237 +
1.238 + ArcIt(Invalid i) : Arc(i) { }
1.239 +
1.240 + explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
1.241 + _graph->first(static_cast<Arc&>(*this));
1.242 + }
1.243 +
1.244 + ArcIt(const BpGraph& graph, const Arc& arc) :
1.245 + Arc(arc), _graph(&graph) { }
1.246 +
1.247 + ArcIt& operator++() {
1.248 + _graph->next(*this);
1.249 + return *this;
1.250 + }
1.251 +
1.252 + };
1.253 +
1.254 +
1.255 + class OutArcIt : public Arc {
1.256 + const BpGraph* _graph;
1.257 + public:
1.258 +
1.259 + OutArcIt() { }
1.260 +
1.261 + OutArcIt(Invalid i) : Arc(i) { }
1.262 +
1.263 + OutArcIt(const BpGraph& graph, const Node& node)
1.264 + : _graph(&graph) {
1.265 + _graph->firstOut(*this, node);
1.266 + }
1.267 +
1.268 + OutArcIt(const BpGraph& graph, const Arc& arc)
1.269 + : Arc(arc), _graph(&graph) {}
1.270 +
1.271 + OutArcIt& operator++() {
1.272 + _graph->nextOut(*this);
1.273 + return *this;
1.274 + }
1.275 +
1.276 + };
1.277 +
1.278 +
1.279 + class InArcIt : public Arc {
1.280 + const BpGraph* _graph;
1.281 + public:
1.282 +
1.283 + InArcIt() { }
1.284 +
1.285 + InArcIt(Invalid i) : Arc(i) { }
1.286 +
1.287 + InArcIt(const BpGraph& graph, const Node& node)
1.288 + : _graph(&graph) {
1.289 + _graph->firstIn(*this, node);
1.290 + }
1.291 +
1.292 + InArcIt(const BpGraph& graph, const Arc& arc) :
1.293 + Arc(arc), _graph(&graph) {}
1.294 +
1.295 + InArcIt& operator++() {
1.296 + _graph->nextIn(*this);
1.297 + return *this;
1.298 + }
1.299 +
1.300 + };
1.301 +
1.302 +
1.303 + class EdgeIt : public Parent::Edge {
1.304 + const BpGraph* _graph;
1.305 + public:
1.306 +
1.307 + EdgeIt() { }
1.308 +
1.309 + EdgeIt(Invalid i) : Edge(i) { }
1.310 +
1.311 + explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
1.312 + _graph->first(static_cast<Edge&>(*this));
1.313 + }
1.314 +
1.315 + EdgeIt(const BpGraph& graph, const Edge& edge) :
1.316 + Edge(edge), _graph(&graph) { }
1.317 +
1.318 + EdgeIt& operator++() {
1.319 + _graph->next(*this);
1.320 + return *this;
1.321 + }
1.322 +
1.323 + };
1.324 +
1.325 + class IncEdgeIt : public Parent::Edge {
1.326 + friend class BpGraphExtender;
1.327 + const BpGraph* _graph;
1.328 + bool _direction;
1.329 + public:
1.330 +
1.331 + IncEdgeIt() { }
1.332 +
1.333 + IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
1.334 +
1.335 + IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
1.336 + _graph->firstInc(*this, _direction, node);
1.337 + }
1.338 +
1.339 + IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
1.340 + : _graph(&graph), Edge(edge) {
1.341 + _direction = (_graph->source(edge) == node);
1.342 + }
1.343 +
1.344 + IncEdgeIt& operator++() {
1.345 + _graph->nextInc(*this, _direction);
1.346 + return *this;
1.347 + }
1.348 + };
1.349 +
1.350 + // \brief Base node of the iterator
1.351 + //
1.352 + // Returns the base node (ie. the source in this case) of the iterator
1.353 + Node baseNode(const OutArcIt &arc) const {
1.354 + return Parent::source(static_cast<const Arc&>(arc));
1.355 + }
1.356 + // \brief Running node of the iterator
1.357 + //
1.358 + // Returns the running node (ie. the target in this case) of the
1.359 + // iterator
1.360 + Node runningNode(const OutArcIt &arc) const {
1.361 + return Parent::target(static_cast<const Arc&>(arc));
1.362 + }
1.363 +
1.364 + // \brief Base node of the iterator
1.365 + //
1.366 + // Returns the base node (ie. the target in this case) of the iterator
1.367 + Node baseNode(const InArcIt &arc) const {
1.368 + return Parent::target(static_cast<const Arc&>(arc));
1.369 + }
1.370 + // \brief Running node of the iterator
1.371 + //
1.372 + // Returns the running node (ie. the source in this case) of the
1.373 + // iterator
1.374 + Node runningNode(const InArcIt &arc) const {
1.375 + return Parent::source(static_cast<const Arc&>(arc));
1.376 + }
1.377 +
1.378 + // Base node of the iterator
1.379 + //
1.380 + // Returns the base node of the iterator
1.381 + Node baseNode(const IncEdgeIt &edge) const {
1.382 + return edge._direction ? this->u(edge) : this->v(edge);
1.383 + }
1.384 + // Running node of the iterator
1.385 + //
1.386 + // Returns the running node of the iterator
1.387 + Node runningNode(const IncEdgeIt &edge) const {
1.388 + return edge._direction ? this->v(edge) : this->u(edge);
1.389 + }
1.390 +
1.391 + // Mappable extension
1.392 +
1.393 + template <typename _Value>
1.394 + class NodeMap
1.395 + : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
1.396 + typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
1.397 +
1.398 + public:
1.399 + explicit NodeMap(const BpGraph& bpgraph)
1.400 + : Parent(bpgraph) {}
1.401 + NodeMap(const BpGraph& bpgraph, const _Value& value)
1.402 + : Parent(bpgraph, value) {}
1.403 +
1.404 + private:
1.405 + NodeMap& operator=(const NodeMap& cmap) {
1.406 + return operator=<NodeMap>(cmap);
1.407 + }
1.408 +
1.409 + template <typename CMap>
1.410 + NodeMap& operator=(const CMap& cmap) {
1.411 + Parent::operator=(cmap);
1.412 + return *this;
1.413 + }
1.414 +
1.415 + };
1.416 +
1.417 + template <typename _Value>
1.418 + class RedMap
1.419 + : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
1.420 + typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
1.421 +
1.422 + public:
1.423 + explicit RedMap(const BpGraph& bpgraph)
1.424 + : Parent(bpgraph) {}
1.425 + RedMap(const BpGraph& bpgraph, const _Value& value)
1.426 + : Parent(bpgraph, value) {}
1.427 +
1.428 + private:
1.429 + RedMap& operator=(const RedMap& cmap) {
1.430 + return operator=<RedMap>(cmap);
1.431 + }
1.432 +
1.433 + template <typename CMap>
1.434 + RedMap& operator=(const CMap& cmap) {
1.435 + Parent::operator=(cmap);
1.436 + return *this;
1.437 + }
1.438 +
1.439 + };
1.440 +
1.441 + template <typename _Value>
1.442 + class BlueMap
1.443 + : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
1.444 + typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
1.445 +
1.446 + public:
1.447 + explicit BlueMap(const BpGraph& bpgraph)
1.448 + : Parent(bpgraph) {}
1.449 + BlueMap(const BpGraph& bpgraph, const _Value& value)
1.450 + : Parent(bpgraph, value) {}
1.451 +
1.452 + private:
1.453 + BlueMap& operator=(const BlueMap& cmap) {
1.454 + return operator=<BlueMap>(cmap);
1.455 + }
1.456 +
1.457 + template <typename CMap>
1.458 + BlueMap& operator=(const CMap& cmap) {
1.459 + Parent::operator=(cmap);
1.460 + return *this;
1.461 + }
1.462 +
1.463 + };
1.464 +
1.465 + template <typename _Value>
1.466 + class ArcMap
1.467 + : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
1.468 + typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
1.469 +
1.470 + public:
1.471 + explicit ArcMap(const BpGraph& graph)
1.472 + : Parent(graph) {}
1.473 + ArcMap(const BpGraph& graph, const _Value& value)
1.474 + : Parent(graph, value) {}
1.475 +
1.476 + private:
1.477 + ArcMap& operator=(const ArcMap& cmap) {
1.478 + return operator=<ArcMap>(cmap);
1.479 + }
1.480 +
1.481 + template <typename CMap>
1.482 + ArcMap& operator=(const CMap& cmap) {
1.483 + Parent::operator=(cmap);
1.484 + return *this;
1.485 + }
1.486 + };
1.487 +
1.488 +
1.489 + template <typename _Value>
1.490 + class EdgeMap
1.491 + : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
1.492 + typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
1.493 +
1.494 + public:
1.495 + explicit EdgeMap(const BpGraph& graph)
1.496 + : Parent(graph) {}
1.497 +
1.498 + EdgeMap(const BpGraph& graph, const _Value& value)
1.499 + : Parent(graph, value) {}
1.500 +
1.501 + private:
1.502 + EdgeMap& operator=(const EdgeMap& cmap) {
1.503 + return operator=<EdgeMap>(cmap);
1.504 + }
1.505 +
1.506 + template <typename CMap>
1.507 + EdgeMap& operator=(const CMap& cmap) {
1.508 + Parent::operator=(cmap);
1.509 + return *this;
1.510 + }
1.511 +
1.512 + };
1.513 +
1.514 + // Alteration extension
1.515 +
1.516 + Node addRedNode() {
1.517 + Node node = Parent::addRedNode();
1.518 + notifier(RedNode()).add(node);
1.519 + notifier(Node()).add(node);
1.520 + return node;
1.521 + }
1.522 +
1.523 + Node addBlueNode() {
1.524 + Node node = Parent::addBlueNode();
1.525 + notifier(BlueNode()).add(node);
1.526 + notifier(Node()).add(node);
1.527 + return node;
1.528 + }
1.529 +
1.530 + Edge addEdge(const Node& from, const Node& to) {
1.531 + Edge edge = Parent::addEdge(from, to);
1.532 + notifier(Edge()).add(edge);
1.533 + std::vector<Arc> av;
1.534 + av.push_back(Parent::direct(edge, true));
1.535 + av.push_back(Parent::direct(edge, false));
1.536 + notifier(Arc()).add(av);
1.537 + return edge;
1.538 + }
1.539 +
1.540 + void clear() {
1.541 + notifier(Arc()).clear();
1.542 + notifier(Edge()).clear();
1.543 + notifier(Node()).clear();
1.544 + notifier(BlueNode()).clear();
1.545 + notifier(RedNode()).clear();
1.546 + Parent::clear();
1.547 + }
1.548 +
1.549 + template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
1.550 + void build(const BpGraph& graph, NodeRefMap& nodeRef,
1.551 + EdgeRefMap& edgeRef) {
1.552 + Parent::build(graph, nodeRef, edgeRef);
1.553 + notifier(RedNode()).build();
1.554 + notifier(BlueNode()).build();
1.555 + notifier(Node()).build();
1.556 + notifier(Edge()).build();
1.557 + notifier(Arc()).build();
1.558 + }
1.559 +
1.560 + void erase(const Node& node) {
1.561 + Arc arc;
1.562 + Parent::firstOut(arc, node);
1.563 + while (arc != INVALID ) {
1.564 + erase(arc);
1.565 + Parent::firstOut(arc, node);
1.566 + }
1.567 +
1.568 + Parent::firstIn(arc, node);
1.569 + while (arc != INVALID ) {
1.570 + erase(arc);
1.571 + Parent::firstIn(arc, node);
1.572 + }
1.573 +
1.574 + if (Parent::red(node)) {
1.575 + notifier(RedNode()).erase(node);
1.576 + } else {
1.577 + notifier(BlueNode()).erase(node);
1.578 + }
1.579 +
1.580 + notifier(Node()).erase(node);
1.581 + Parent::erase(node);
1.582 + }
1.583 +
1.584 + void erase(const Edge& edge) {
1.585 + std::vector<Arc> av;
1.586 + av.push_back(Parent::direct(edge, true));
1.587 + av.push_back(Parent::direct(edge, false));
1.588 + notifier(Arc()).erase(av);
1.589 + notifier(Edge()).erase(edge);
1.590 + Parent::erase(edge);
1.591 + }
1.592 +
1.593 + BpGraphExtender() {
1.594 + red_node_notifier.setContainer(*this);
1.595 + blue_node_notifier.setContainer(*this);
1.596 + node_notifier.setContainer(*this);
1.597 + arc_notifier.setContainer(*this);
1.598 + edge_notifier.setContainer(*this);
1.599 + }
1.600 +
1.601 + ~BpGraphExtender() {
1.602 + edge_notifier.clear();
1.603 + arc_notifier.clear();
1.604 + node_notifier.clear();
1.605 + blue_node_notifier.clear();
1.606 + red_node_notifier.clear();
1.607 + }
1.608 +
1.609 + };
1.610 +
1.611 }
1.612
1.613 #endif
2.1 --- a/lemon/bits/traits.h Sun Nov 14 16:35:31 2010 +0100
2.2 +++ b/lemon/bits/traits.h Sun Nov 14 20:06:23 2010 +0100
2.3 @@ -151,6 +151,88 @@
2.4
2.5 };
2.6
2.7 + template <typename GR, typename Enable = void>
2.8 + struct RedNodeNotifierIndicator {
2.9 + typedef InvalidType Type;
2.10 + };
2.11 + template <typename GR>
2.12 + struct RedNodeNotifierIndicator<
2.13 + GR,
2.14 + typename enable_if<typename GR::RedNodeNotifier::Notifier, void>::type
2.15 + > {
2.16 + typedef typename GR::RedNodeNotifier Type;
2.17 + };
2.18 +
2.19 + template <typename GR>
2.20 + class ItemSetTraits<GR, typename GR::RedNode> {
2.21 + public:
2.22 +
2.23 + typedef GR BpGraph;
2.24 + typedef GR Graph;
2.25 + typedef GR Digraph;
2.26 +
2.27 + typedef typename GR::RedNode Item;
2.28 + typedef typename GR::RedIt ItemIt;
2.29 +
2.30 + typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier;
2.31 +
2.32 + template <typename V>
2.33 + class Map : public GR::template RedMap<V> {
2.34 + typedef typename GR::template RedMap<V> Parent;
2.35 +
2.36 + public:
2.37 + typedef typename GR::template RedMap<V> Type;
2.38 + typedef typename Parent::Value Value;
2.39 +
2.40 + Map(const GR& _bpgraph) : Parent(_bpgraph) {}
2.41 + Map(const GR& _bpgraph, const Value& _value)
2.42 + : Parent(_bpgraph, _value) {}
2.43 +
2.44 + };
2.45 +
2.46 + };
2.47 +
2.48 + template <typename GR, typename Enable = void>
2.49 + struct BlueNodeNotifierIndicator {
2.50 + typedef InvalidType Type;
2.51 + };
2.52 + template <typename GR>
2.53 + struct BlueNodeNotifierIndicator<
2.54 + GR,
2.55 + typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type
2.56 + > {
2.57 + typedef typename GR::BlueNodeNotifier Type;
2.58 + };
2.59 +
2.60 + template <typename GR>
2.61 + class ItemSetTraits<GR, typename GR::BlueNode> {
2.62 + public:
2.63 +
2.64 + typedef GR BpGraph;
2.65 + typedef GR Graph;
2.66 + typedef GR Digraph;
2.67 +
2.68 + typedef typename GR::BlueNode Item;
2.69 + typedef typename GR::BlueIt ItemIt;
2.70 +
2.71 + typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier;
2.72 +
2.73 + template <typename V>
2.74 + class Map : public GR::template BlueMap<V> {
2.75 + typedef typename GR::template BlueMap<V> Parent;
2.76 +
2.77 + public:
2.78 + typedef typename GR::template BlueMap<V> Type;
2.79 + typedef typename Parent::Value Value;
2.80 +
2.81 + Map(const GR& _bpgraph) : Parent(_bpgraph) {}
2.82 + Map(const GR& _bpgraph, const Value& _value)
2.83 + : Parent(_bpgraph, _value) {}
2.84 +
2.85 + };
2.86 +
2.87 + };
2.88 +
2.89 template <typename Map, typename Enable = void>
2.90 struct MapTraits {
2.91 typedef False ReferenceMapTag;
3.1 --- a/lemon/core.h Sun Nov 14 16:35:31 2010 +0100
3.2 +++ b/lemon/core.h Sun Nov 14 20:06:23 2010 +0100
3.3 @@ -148,6 +148,48 @@
3.4 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
3.5 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
3.6
3.7 + ///Create convenience typedefs for the bipartite graph types and iterators
3.8 +
3.9 + ///This \c \#define creates the same convenient type definitions as defined
3.10 + ///by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it creates
3.11 + ///\c RedNode, \c RedIt, \c BoolRedMap, \c IntRedMap, \c DoubleRedMap,
3.12 + ///\c BlueNode, \c BlueIt, \c BoolBlueMap, \c IntBlueMap, \c DoubleBlueMap.
3.13 + ///
3.14 + ///\note If the graph type is a dependent type, ie. the graph type depend
3.15 + ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
3.16 + ///macro.
3.17 +#define BPGRAPH_TYPEDEFS(BpGraph) \
3.18 + GRAPH_TYPEDEFS(BpGraph); \
3.19 + typedef BpGraph::RedNode RedNode; \
3.20 + typedef BpGraph::RedIt RedIt; \
3.21 + typedef BpGraph::RedMap<bool> BoolRedMap; \
3.22 + typedef BpGraph::RedMap<int> IntRedMap; \
3.23 + typedef BpGraph::RedMap<double> DoubleRedMap \
3.24 + typedef BpGraph::BlueNode BlueNode; \
3.25 + typedef BpGraph::BlueIt BlueIt; \
3.26 + typedef BpGraph::BlueMap<bool> BoolBlueMap; \
3.27 + typedef BpGraph::BlueMap<int> IntBlueMap; \
3.28 + typedef BpGraph::BlueMap<double> DoubleBlueMap
3.29 +
3.30 + ///Create convenience typedefs for the bipartite graph types and iterators
3.31 +
3.32 + ///\see BPGRAPH_TYPEDEFS
3.33 + ///
3.34 + ///\note Use this macro, if the graph type is a dependent type,
3.35 + ///ie. the graph type depend on a template parameter.
3.36 +#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \
3.37 + TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \
3.38 + typedef typename BpGraph::RedNode RedNode; \
3.39 + typedef typename BpGraph::RedIt RedIt; \
3.40 + typedef typename BpGraph::template RedMap<bool> BoolRedMap; \
3.41 + typedef typename BpGraph::template RedMap<int> IntRedMap; \
3.42 + typedef typename BpGraph::template RedMap<double> DoubleRedMap; \
3.43 + typedef typename BpGraph::BlueNode BlueNode; \
3.44 + typedef typename BpGraph::BlueIt BlueIt; \
3.45 + typedef typename BpGraph::template BlueMap<bool> BoolBlueMap; \
3.46 + typedef typename BpGraph::template BlueMap<int> IntBlueMap; \
3.47 + typedef typename BpGraph::template BlueMap<double> DoubleBlueMap
3.48 +
3.49 /// \brief Function to count the items in a graph.
3.50 ///
3.51 /// This function counts the items (nodes, arcs etc.) in a graph.
3.52 @@ -199,6 +241,74 @@
3.53 return _core_bits::CountNodesSelector<Graph>::count(g);
3.54 }
3.55
3.56 + namespace _graph_utils_bits {
3.57 +
3.58 + template <typename Graph, typename Enable = void>
3.59 + struct CountRedNodesSelector {
3.60 + static int count(const Graph &g) {
3.61 + return countItems<Graph, typename Graph::RedNode>(g);
3.62 + }
3.63 + };
3.64 +
3.65 + template <typename Graph>
3.66 + struct CountRedNodesSelector<
3.67 + Graph, typename
3.68 + enable_if<typename Graph::NodeNumTag, void>::type>
3.69 + {
3.70 + static int count(const Graph &g) {
3.71 + return g.redNum();
3.72 + }
3.73 + };
3.74 + }
3.75 +
3.76 + /// \brief Function to count the red nodes in the graph.
3.77 + ///
3.78 + /// This function counts the red nodes in the graph.
3.79 + /// The complexity of the function is O(n) but for some
3.80 + /// graph structures it is specialized to run in O(1).
3.81 + ///
3.82 + /// If the graph contains a \e redNum() member function and a
3.83 + /// \e NodeNumTag tag then this function calls directly the member
3.84 + /// function to query the cardinality of the node set.
3.85 + template <typename Graph>
3.86 + inline int countRedNodes(const Graph& g) {
3.87 + return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
3.88 + }
3.89 +
3.90 + namespace _graph_utils_bits {
3.91 +
3.92 + template <typename Graph, typename Enable = void>
3.93 + struct CountBlueNodesSelector {
3.94 + static int count(const Graph &g) {
3.95 + return countItems<Graph, typename Graph::BlueNode>(g);
3.96 + }
3.97 + };
3.98 +
3.99 + template <typename Graph>
3.100 + struct CountBlueNodesSelector<
3.101 + Graph, typename
3.102 + enable_if<typename Graph::NodeNumTag, void>::type>
3.103 + {
3.104 + static int count(const Graph &g) {
3.105 + return g.blueNum();
3.106 + }
3.107 + };
3.108 + }
3.109 +
3.110 + /// \brief Function to count the blue nodes in the graph.
3.111 + ///
3.112 + /// This function counts the blue nodes in the graph.
3.113 + /// The complexity of the function is O(n) but for some
3.114 + /// graph structures it is specialized to run in O(1).
3.115 + ///
3.116 + /// If the graph contains a \e blueNum() member function and a
3.117 + /// \e NodeNumTag tag then this function calls directly the member
3.118 + /// function to query the cardinality of the node set.
3.119 + template <typename Graph>
3.120 + inline int countBlueNodes(const Graph& g) {
3.121 + return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
3.122 + }
3.123 +
3.124 // Arc counting:
3.125
3.126 namespace _core_bits {
3.127 @@ -1257,7 +1367,7 @@
3.128
3.129 /// The Digraph type
3.130 typedef GR Digraph;
3.131 -
3.132 +
3.133 protected:
3.134
3.135 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
4.1 --- a/lemon/smart_graph.h Sun Nov 14 16:35:31 2010 +0100
4.2 +++ b/lemon/smart_graph.h Sun Nov 14 20:06:23 2010 +0100
4.3 @@ -405,8 +405,6 @@
4.4 std::vector<NodeT> nodes;
4.5 std::vector<ArcT> arcs;
4.6
4.7 - int first_free_arc;
4.8 -
4.9 public:
4.10
4.11 typedef SmartGraphBase Graph;
4.12 @@ -811,6 +809,514 @@
4.13 };
4.14 };
4.15
4.16 + class SmartBpGraphBase {
4.17 +
4.18 + protected:
4.19 +
4.20 + struct NodeT {
4.21 + int first_out;
4.22 + int partition_next;
4.23 + int partition_index;
4.24 + bool red;
4.25 + };
4.26 +
4.27 + struct ArcT {
4.28 + int target;
4.29 + int next_out;
4.30 + };
4.31 +
4.32 + std::vector<NodeT> nodes;
4.33 + std::vector<ArcT> arcs;
4.34 +
4.35 + int first_red, first_blue;
4.36 +
4.37 + public:
4.38 +
4.39 + typedef SmartBpGraphBase Graph;
4.40 +
4.41 + class Node;
4.42 + class Arc;
4.43 + class Edge;
4.44 +
4.45 + class Node {
4.46 + friend class SmartBpGraphBase;
4.47 + protected:
4.48 +
4.49 + int _id;
4.50 + explicit Node(int id) { _id = id;}
4.51 +
4.52 + public:
4.53 + Node() {}
4.54 + Node (Invalid) { _id = -1; }
4.55 + bool operator==(const Node& node) const {return _id == node._id;}
4.56 + bool operator!=(const Node& node) const {return _id != node._id;}
4.57 + bool operator<(const Node& node) const {return _id < node._id;}
4.58 + };
4.59 +
4.60 + class Edge {
4.61 + friend class SmartBpGraphBase;
4.62 + protected:
4.63 +
4.64 + int _id;
4.65 + explicit Edge(int id) { _id = id;}
4.66 +
4.67 + public:
4.68 + Edge() {}
4.69 + Edge (Invalid) { _id = -1; }
4.70 + bool operator==(const Edge& arc) const {return _id == arc._id;}
4.71 + bool operator!=(const Edge& arc) const {return _id != arc._id;}
4.72 + bool operator<(const Edge& arc) const {return _id < arc._id;}
4.73 + };
4.74 +
4.75 + class Arc {
4.76 + friend class SmartBpGraphBase;
4.77 + protected:
4.78 +
4.79 + int _id;
4.80 + explicit Arc(int id) { _id = id;}
4.81 +
4.82 + public:
4.83 + operator Edge() const {
4.84 + return _id != -1 ? edgeFromId(_id / 2) : INVALID;
4.85 + }
4.86 +
4.87 + Arc() {}
4.88 + Arc (Invalid) { _id = -1; }
4.89 + bool operator==(const Arc& arc) const {return _id == arc._id;}
4.90 + bool operator!=(const Arc& arc) const {return _id != arc._id;}
4.91 + bool operator<(const Arc& arc) const {return _id < arc._id;}
4.92 + };
4.93 +
4.94 +
4.95 +
4.96 + SmartBpGraphBase()
4.97 + : nodes(), arcs(), first_red(-1), first_blue(-1) {}
4.98 +
4.99 + typedef True NodeNumTag;
4.100 + typedef True EdgeNumTag;
4.101 + typedef True ArcNumTag;
4.102 +
4.103 + int nodeNum() const { return nodes.size(); }
4.104 + int redNum() const {
4.105 + return first_red == -1 ? 0 : nodes[first_red].partition_index + 1;
4.106 + }
4.107 + int blueNum() const {
4.108 + return first_blue == -1 ? 0 : nodes[first_blue].partition_index + 1;
4.109 + }
4.110 + int edgeNum() const { return arcs.size() / 2; }
4.111 + int arcNum() const { return arcs.size(); }
4.112 +
4.113 + int maxNodeId() const { return nodes.size()-1; }
4.114 + int maxRedId() const {
4.115 + return first_red == -1 ? -1 : nodes[first_red].partition_index;
4.116 + }
4.117 + int maxBlueId() const {
4.118 + return first_blue == -1 ? -1 : nodes[first_blue].partition_index;
4.119 + }
4.120 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
4.121 + int maxArcId() const { return arcs.size()-1; }
4.122 +
4.123 + bool red(Node n) const { return nodes[n._id].red; }
4.124 + bool blue(Node n) const { return !nodes[n._id].red; }
4.125 +
4.126 + Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
4.127 + Node target(Arc a) const { return Node(arcs[a._id].target); }
4.128 +
4.129 + Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
4.130 + Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
4.131 +
4.132 + Node u(Edge e) const { return redNode(e); }
4.133 + Node v(Edge e) const { return blueNode(e); }
4.134 +
4.135 + static bool direction(Arc a) {
4.136 + return (a._id & 1) == 1;
4.137 + }
4.138 +
4.139 + static Arc direct(Edge e, bool d) {
4.140 + return Arc(e._id * 2 + (d ? 1 : 0));
4.141 + }
4.142 +
4.143 + void first(Node& node) const {
4.144 + node._id = nodes.size() - 1;
4.145 + }
4.146 +
4.147 + static void next(Node& node) {
4.148 + --node._id;
4.149 + }
4.150 +
4.151 + void firstRed(Node& node) const {
4.152 + node._id = first_red;
4.153 + }
4.154 +
4.155 + void nextRed(Node& node) const {
4.156 + node._id = nodes[node._id].partition_next;
4.157 + }
4.158 +
4.159 + void firstBlue(Node& node) const {
4.160 + node._id = first_blue;
4.161 + }
4.162 +
4.163 + void nextBlue(Node& node) const {
4.164 + node._id = nodes[node._id].partition_next;
4.165 + }
4.166 +
4.167 + void first(Arc& arc) const {
4.168 + arc._id = arcs.size() - 1;
4.169 + }
4.170 +
4.171 + static void next(Arc& arc) {
4.172 + --arc._id;
4.173 + }
4.174 +
4.175 + void first(Edge& arc) const {
4.176 + arc._id = arcs.size() / 2 - 1;
4.177 + }
4.178 +
4.179 + static void next(Edge& arc) {
4.180 + --arc._id;
4.181 + }
4.182 +
4.183 + void firstOut(Arc &arc, const Node& v) const {
4.184 + arc._id = nodes[v._id].first_out;
4.185 + }
4.186 + void nextOut(Arc &arc) const {
4.187 + arc._id = arcs[arc._id].next_out;
4.188 + }
4.189 +
4.190 + void firstIn(Arc &arc, const Node& v) const {
4.191 + arc._id = ((nodes[v._id].first_out) ^ 1);
4.192 + if (arc._id == -2) arc._id = -1;
4.193 + }
4.194 + void nextIn(Arc &arc) const {
4.195 + arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
4.196 + if (arc._id == -2) arc._id = -1;
4.197 + }
4.198 +
4.199 + void firstInc(Edge &arc, bool& d, const Node& v) const {
4.200 + int de = nodes[v._id].first_out;
4.201 + if (de != -1) {
4.202 + arc._id = de / 2;
4.203 + d = ((de & 1) == 1);
4.204 + } else {
4.205 + arc._id = -1;
4.206 + d = true;
4.207 + }
4.208 + }
4.209 + void nextInc(Edge &arc, bool& d) const {
4.210 + int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
4.211 + if (de != -1) {
4.212 + arc._id = de / 2;
4.213 + d = ((de & 1) == 1);
4.214 + } else {
4.215 + arc._id = -1;
4.216 + d = true;
4.217 + }
4.218 + }
4.219 +
4.220 + static int id(Node v) { return v._id; }
4.221 + int redId(Node v) const {
4.222 + LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
4.223 + return nodes[v._id].partition_index;
4.224 + }
4.225 + int blueId(Node v) const {
4.226 + LEMON_DEBUG(nodes[v._id].red, "Node has to be blue");
4.227 + return nodes[v._id].partition_index;
4.228 + }
4.229 + static int id(Arc e) { return e._id; }
4.230 + static int id(Edge e) { return e._id; }
4.231 +
4.232 + static Node nodeFromId(int id) { return Node(id);}
4.233 + static Arc arcFromId(int id) { return Arc(id);}
4.234 + static Edge edgeFromId(int id) { return Edge(id);}
4.235 +
4.236 + bool valid(Node n) const {
4.237 + return n._id >= 0 && n._id < static_cast<int>(nodes.size());
4.238 + }
4.239 + bool valid(Arc a) const {
4.240 + return a._id >= 0 && a._id < static_cast<int>(arcs.size());
4.241 + }
4.242 + bool valid(Edge e) const {
4.243 + return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
4.244 + }
4.245 +
4.246 + Node addRedNode() {
4.247 + int n = nodes.size();
4.248 + nodes.push_back(NodeT());
4.249 + nodes[n].first_out = -1;
4.250 + nodes[n].red = true;
4.251 + if (first_red == -1) {
4.252 + nodes[n].partition_index = 0;
4.253 + } else {
4.254 + nodes[n].partition_index = nodes[first_red].partition_index + 1;
4.255 + }
4.256 + nodes[n].partition_next = first_red;
4.257 + first_red = n;
4.258 +
4.259 + return Node(n);
4.260 + }
4.261 +
4.262 + Node addBlueNode() {
4.263 + int n = nodes.size();
4.264 + nodes.push_back(NodeT());
4.265 + nodes[n].first_out = -1;
4.266 + nodes[n].red = false;
4.267 + if (first_blue == -1) {
4.268 + nodes[n].partition_index = 0;
4.269 + } else {
4.270 + nodes[n].partition_index = nodes[first_blue].partition_index + 1;
4.271 + }
4.272 + nodes[n].partition_next = first_blue;
4.273 + first_blue = n;
4.274 +
4.275 + return Node(n);
4.276 + }
4.277 +
4.278 + Edge addEdge(Node u, Node v) {
4.279 + int n = arcs.size();
4.280 + arcs.push_back(ArcT());
4.281 + arcs.push_back(ArcT());
4.282 +
4.283 + arcs[n].target = u._id;
4.284 + arcs[n | 1].target = v._id;
4.285 +
4.286 + arcs[n].next_out = nodes[v._id].first_out;
4.287 + nodes[v._id].first_out = n;
4.288 +
4.289 + arcs[n | 1].next_out = nodes[u._id].first_out;
4.290 + nodes[u._id].first_out = (n | 1);
4.291 +
4.292 + return Edge(n / 2);
4.293 + }
4.294 +
4.295 + void clear() {
4.296 + arcs.clear();
4.297 + nodes.clear();
4.298 + first_red = -1;
4.299 + first_blue = -1;
4.300 + }
4.301 +
4.302 + };
4.303 +
4.304 + typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase;
4.305 +
4.306 + /// \ingroup graphs
4.307 + ///
4.308 + /// \brief A smart undirected graph class.
4.309 + ///
4.310 + /// \ref SmartBpGraph is a simple and fast graph implementation.
4.311 + /// It is also quite memory efficient but at the price
4.312 + /// that it does not support node and edge deletion
4.313 + /// (except for the Snapshot feature).
4.314 + ///
4.315 + /// This type fully conforms to the \ref concepts::Graph "Graph concept"
4.316 + /// and it also provides some additional functionalities.
4.317 + /// Most of its member functions and nested classes are documented
4.318 + /// only in the concept class.
4.319 + ///
4.320 + /// This class provides constant time counting for nodes, edges and arcs.
4.321 + ///
4.322 + /// \sa concepts::Graph
4.323 + /// \sa SmartDigraph
4.324 + class SmartBpGraph : public ExtendedSmartBpGraphBase {
4.325 + typedef ExtendedSmartBpGraphBase Parent;
4.326 +
4.327 + private:
4.328 + /// Graphs are \e not copy constructible. Use GraphCopy instead.
4.329 + SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {};
4.330 + /// \brief Assignment of a graph to another one is \e not allowed.
4.331 + /// Use GraphCopy instead.
4.332 + void operator=(const SmartBpGraph &) {}
4.333 +
4.334 + public:
4.335 +
4.336 + /// Constructor
4.337 +
4.338 + /// Constructor.
4.339 + ///
4.340 + SmartBpGraph() {}
4.341 +
4.342 + /// \brief Add a new red node to the graph.
4.343 + ///
4.344 + /// This function adds a red new node to the graph.
4.345 + /// \return The new node.
4.346 + Node addRedNode() { return Parent::addRedNode(); }
4.347 +
4.348 + /// \brief Add a new blue node to the graph.
4.349 + ///
4.350 + /// This function adds a blue new node to the graph.
4.351 + /// \return The new node.
4.352 + Node addBlueNode() { return Parent::addBlueNode(); }
4.353 +
4.354 + /// \brief Add a new edge to the graph.
4.355 + ///
4.356 + /// This function adds a new edge to the graph between nodes
4.357 + /// \c u and \c v with inherent orientation from node \c u to
4.358 + /// node \c v.
4.359 + /// \return The new edge.
4.360 + Edge addEdge(Node red, Node blue) {
4.361 + LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
4.362 + "Edge has to be formed by a red and a blue nodes");
4.363 + return Parent::addEdge(red, blue);
4.364 + }
4.365 +
4.366 + /// \brief Node validity check
4.367 + ///
4.368 + /// This function gives back \c true if the given node is valid,
4.369 + /// i.e. it is a real node of the graph.
4.370 + ///
4.371 + /// \warning A removed node (using Snapshot) could become valid again
4.372 + /// if new nodes are added to the graph.
4.373 + bool valid(Node n) const { return Parent::valid(n); }
4.374 +
4.375 + /// \brief Edge validity check
4.376 + ///
4.377 + /// This function gives back \c true if the given edge is valid,
4.378 + /// i.e. it is a real edge of the graph.
4.379 + ///
4.380 + /// \warning A removed edge (using Snapshot) could become valid again
4.381 + /// if new edges are added to the graph.
4.382 + bool valid(Edge e) const { return Parent::valid(e); }
4.383 +
4.384 + /// \brief Arc validity check
4.385 + ///
4.386 + /// This function gives back \c true if the given arc is valid,
4.387 + /// i.e. it is a real arc of the graph.
4.388 + ///
4.389 + /// \warning A removed arc (using Snapshot) could become valid again
4.390 + /// if new edges are added to the graph.
4.391 + bool valid(Arc a) const { return Parent::valid(a); }
4.392 +
4.393 + ///Clear the graph.
4.394 +
4.395 + ///This function erases all nodes and arcs from the graph.
4.396 + ///
4.397 + void clear() {
4.398 + Parent::clear();
4.399 + }
4.400 +
4.401 + /// Reserve memory for nodes.
4.402 +
4.403 + /// Using this function, it is possible to avoid superfluous memory
4.404 + /// allocation: if you know that the graph you want to build will
4.405 + /// be large (e.g. it will contain millions of nodes and/or edges),
4.406 + /// then it is worth reserving space for this amount before starting
4.407 + /// to build the graph.
4.408 + /// \sa reserveEdge()
4.409 + void reserveNode(int n) { nodes.reserve(n); };
4.410 +
4.411 + /// Reserve memory for edges.
4.412 +
4.413 + /// Using this function, it is possible to avoid superfluous memory
4.414 + /// allocation: if you know that the graph you want to build will
4.415 + /// be large (e.g. it will contain millions of nodes and/or edges),
4.416 + /// then it is worth reserving space for this amount before starting
4.417 + /// to build the graph.
4.418 + /// \sa reserveNode()
4.419 + void reserveEdge(int m) { arcs.reserve(2 * m); };
4.420 +
4.421 + public:
4.422 +
4.423 + class Snapshot;
4.424 +
4.425 + protected:
4.426 +
4.427 + void saveSnapshot(Snapshot &s)
4.428 + {
4.429 + s._graph = this;
4.430 + s.node_num = nodes.size();
4.431 + s.arc_num = arcs.size();
4.432 + }
4.433 +
4.434 + void restoreSnapshot(const Snapshot &s)
4.435 + {
4.436 + while(s.arc_num<arcs.size()) {
4.437 + int n=arcs.size()-1;
4.438 + Edge arc=edgeFromId(n/2);
4.439 + Parent::notifier(Edge()).erase(arc);
4.440 + std::vector<Arc> dir;
4.441 + dir.push_back(arcFromId(n));
4.442 + dir.push_back(arcFromId(n-1));
4.443 + Parent::notifier(Arc()).erase(dir);
4.444 + nodes[arcs[n-1].target].first_out=arcs[n].next_out;
4.445 + nodes[arcs[n].target].first_out=arcs[n-1].next_out;
4.446 + arcs.pop_back();
4.447 + arcs.pop_back();
4.448 + }
4.449 + while(s.node_num<nodes.size()) {
4.450 + int n=nodes.size()-1;
4.451 + Node node = nodeFromId(n);
4.452 + if (Parent::red(node)) {
4.453 + first_red = nodes[n].partition_next;
4.454 + Parent::notifier(RedNode()).erase(node);
4.455 + } else {
4.456 + first_blue = nodes[n].partition_next;
4.457 + Parent::notifier(BlueNode()).erase(node);
4.458 + }
4.459 + Parent::notifier(Node()).erase(node);
4.460 + nodes.pop_back();
4.461 + }
4.462 + }
4.463 +
4.464 + public:
4.465 +
4.466 + ///Class to make a snapshot of the graph and to restore it later.
4.467 +
4.468 + ///Class to make a snapshot of the graph and to restore it later.
4.469 + ///
4.470 + ///The newly added nodes and edges can be removed using the
4.471 + ///restore() function. This is the only way for deleting nodes and/or
4.472 + ///edges from a SmartBpGraph structure.
4.473 + ///
4.474 + ///\note After a state is restored, you cannot restore a later state,
4.475 + ///i.e. you cannot add the removed nodes and edges again using
4.476 + ///another Snapshot instance.
4.477 + ///
4.478 + ///\warning The validity of the snapshot is not stored due to
4.479 + ///performance reasons. If you do not use the snapshot correctly,
4.480 + ///it can cause broken program, invalid or not restored state of
4.481 + ///the graph or no change.
4.482 + class Snapshot
4.483 + {
4.484 + SmartBpGraph *_graph;
4.485 + protected:
4.486 + friend class SmartBpGraph;
4.487 + unsigned int node_num;
4.488 + unsigned int arc_num;
4.489 + public:
4.490 + ///Default constructor.
4.491 +
4.492 + ///Default constructor.
4.493 + ///You have to call save() to actually make a snapshot.
4.494 + Snapshot() : _graph(0) {}
4.495 + ///Constructor that immediately makes a snapshot
4.496 +
4.497 + /// This constructor immediately makes a snapshot of the given graph.
4.498 + ///
4.499 + Snapshot(SmartBpGraph &gr) {
4.500 + gr.saveSnapshot(*this);
4.501 + }
4.502 +
4.503 + ///Make a snapshot.
4.504 +
4.505 + ///This function makes a snapshot of the given graph.
4.506 + ///It can be called more than once. In case of a repeated
4.507 + ///call, the previous snapshot gets lost.
4.508 + void save(SmartBpGraph &gr)
4.509 + {
4.510 + gr.saveSnapshot(*this);
4.511 + }
4.512 +
4.513 + ///Undo the changes until the last snapshot.
4.514 +
4.515 + ///This function undos the changes until the last snapshot
4.516 + ///created by save() or Snapshot(SmartBpGraph&).
4.517 + void restore()
4.518 + {
4.519 + _graph->restoreSnapshot(*this);
4.520 + }
4.521 + };
4.522 + };
4.523 +
4.524 } //namespace lemon
4.525
4.526
5.1 --- a/test/bpgraph_test.cc Sun Nov 14 16:35:31 2010 +0100
5.2 +++ b/test/bpgraph_test.cc Sun Nov 14 20:06:23 2010 +0100
5.3 @@ -18,10 +18,8 @@
5.4
5.5 #include <lemon/concepts/bpgraph.h>
5.6 //#include <lemon/list_graph.h>
5.7 -//#include <lemon/smart_graph.h>
5.8 +#include <lemon/smart_graph.h>
5.9 //#include <lemon/full_graph.h>
5.10 -//#include <lemon/grid_graph.h>
5.11 -//#include <lemon/hypercube_graph.h>
5.12
5.13 #include "test_tools.h"
5.14 #include "graph_test.h"
5.15 @@ -29,6 +27,192 @@
5.16 using namespace lemon;
5.17 using namespace lemon::concepts;
5.18
5.19 +template <class BpGraph>
5.20 +void checkBpGraphBuild() {
5.21 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
5.22 +
5.23 + BpGraph G;
5.24 + checkGraphNodeList(G, 0);
5.25 + checkGraphRedNodeList(G, 0);
5.26 + checkGraphBlueNodeList(G, 0);
5.27 + checkGraphEdgeList(G, 0);
5.28 + checkGraphArcList(G, 0);
5.29 +
5.30 + G.reserveNode(3);
5.31 + G.reserveEdge(3);
5.32 +
5.33 + Node
5.34 + rn1 = G.addRedNode();
5.35 + checkGraphNodeList(G, 1);
5.36 + checkGraphRedNodeList(G, 1);
5.37 + checkGraphBlueNodeList(G, 0);
5.38 + checkGraphEdgeList(G, 0);
5.39 + checkGraphArcList(G, 0);
5.40 +
5.41 + Node
5.42 + bn1 = G.addBlueNode(),
5.43 + bn2 = G.addBlueNode();
5.44 + checkGraphNodeList(G, 3);
5.45 + checkGraphRedNodeList(G, 1);
5.46 + checkGraphBlueNodeList(G, 2);
5.47 + checkGraphEdgeList(G, 0);
5.48 + checkGraphArcList(G, 0);
5.49 +
5.50 + Edge e1 = G.addEdge(rn1, bn2);
5.51 + check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge");
5.52 + check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge");
5.53 +
5.54 + checkGraphNodeList(G, 3);
5.55 + checkGraphRedNodeList(G, 1);
5.56 + checkGraphBlueNodeList(G, 2);
5.57 + checkGraphEdgeList(G, 1);
5.58 + checkGraphArcList(G, 2);
5.59 +
5.60 + checkGraphIncEdgeArcLists(G, rn1, 1);
5.61 + checkGraphIncEdgeArcLists(G, bn1, 0);
5.62 + checkGraphIncEdgeArcLists(G, bn2, 1);
5.63 +
5.64 + checkGraphConEdgeList(G, 1);
5.65 + checkGraphConArcList(G, 2);
5.66 +
5.67 + Edge
5.68 + e2 = G.addEdge(rn1, bn1),
5.69 + e3 = G.addEdge(rn1, bn2);
5.70 +
5.71 + checkGraphNodeList(G, 3);
5.72 + checkGraphRedNodeList(G, 1);
5.73 + checkGraphBlueNodeList(G, 2);
5.74 + checkGraphEdgeList(G, 3);
5.75 + checkGraphArcList(G, 6);
5.76 +
5.77 + checkGraphIncEdgeArcLists(G, rn1, 3);
5.78 + checkGraphIncEdgeArcLists(G, bn1, 1);
5.79 + checkGraphIncEdgeArcLists(G, bn2, 2);
5.80 +
5.81 + checkGraphConEdgeList(G, 3);
5.82 + checkGraphConArcList(G, 6);
5.83 +
5.84 + checkArcDirections(G);
5.85 +
5.86 + checkNodeIds(G);
5.87 + checkRedNodeIds(G);
5.88 + checkBlueNodeIds(G);
5.89 + checkArcIds(G);
5.90 + checkEdgeIds(G);
5.91 +
5.92 + checkGraphNodeMap(G);
5.93 + checkGraphRedMap(G);
5.94 + checkGraphBlueMap(G);
5.95 + checkGraphArcMap(G);
5.96 + checkGraphEdgeMap(G);
5.97 +}
5.98 +
5.99 +template <class Graph>
5.100 +void checkBpGraphSnapshot() {
5.101 + TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
5.102 +
5.103 + Graph G;
5.104 + Node
5.105 + n1 = G.addRedNode(),
5.106 + n2 = G.addBlueNode(),
5.107 + n3 = G.addBlueNode();
5.108 + Edge
5.109 + e1 = G.addEdge(n1, n2),
5.110 + e2 = G.addEdge(n1, n3);
5.111 +
5.112 + checkGraphNodeList(G, 3);
5.113 + checkGraphRedNodeList(G, 1);
5.114 + checkGraphBlueNodeList(G, 2);
5.115 + checkGraphEdgeList(G, 2);
5.116 + checkGraphArcList(G, 4);
5.117 +
5.118 + typename Graph::Snapshot snapshot(G);
5.119 +
5.120 + Node n4 = G.addRedNode();
5.121 + G.addEdge(n4, n2);
5.122 + G.addEdge(n4, n3);
5.123 +
5.124 + checkGraphNodeList(G, 4);
5.125 + checkGraphRedNodeList(G, 2);
5.126 + checkGraphBlueNodeList(G, 2);
5.127 + checkGraphEdgeList(G, 4);
5.128 + checkGraphArcList(G, 8);
5.129 +
5.130 + snapshot.restore();
5.131 +
5.132 + checkGraphNodeList(G, 3);
5.133 + checkGraphRedNodeList(G, 1);
5.134 + checkGraphBlueNodeList(G, 2);
5.135 + checkGraphEdgeList(G, 2);
5.136 + checkGraphArcList(G, 4);
5.137 +
5.138 + checkGraphIncEdgeArcLists(G, n1, 2);
5.139 + checkGraphIncEdgeArcLists(G, n2, 1);
5.140 + checkGraphIncEdgeArcLists(G, n3, 1);
5.141 +
5.142 + checkGraphConEdgeList(G, 2);
5.143 + checkGraphConArcList(G, 4);
5.144 +
5.145 + checkNodeIds(G);
5.146 + checkRedNodeIds(G);
5.147 + checkBlueNodeIds(G);
5.148 + checkArcIds(G);
5.149 + checkEdgeIds(G);
5.150 +
5.151 + checkGraphNodeMap(G);
5.152 + checkGraphRedMap(G);
5.153 + checkGraphBlueMap(G);
5.154 + checkGraphArcMap(G);
5.155 + checkGraphEdgeMap(G);
5.156 +
5.157 + G.addRedNode();
5.158 + snapshot.save(G);
5.159 +
5.160 + G.addEdge(G.addRedNode(), G.addBlueNode());
5.161 +
5.162 + snapshot.restore();
5.163 + snapshot.save(G);
5.164 +
5.165 + checkGraphNodeList(G, 4);
5.166 + checkGraphRedNodeList(G, 2);
5.167 + checkGraphBlueNodeList(G, 2);
5.168 + checkGraphEdgeList(G, 2);
5.169 + checkGraphArcList(G, 4);
5.170 +
5.171 + G.addEdge(G.addRedNode(), G.addBlueNode());
5.172 +
5.173 + snapshot.restore();
5.174 +
5.175 + checkGraphNodeList(G, 4);
5.176 + checkGraphRedNodeList(G, 2);
5.177 + checkGraphBlueNodeList(G, 2);
5.178 + checkGraphEdgeList(G, 2);
5.179 + checkGraphArcList(G, 4);
5.180 +}
5.181 +
5.182 +template <typename Graph>
5.183 +void checkBpGraphValidity() {
5.184 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
5.185 + Graph g;
5.186 +
5.187 + Node
5.188 + n1 = g.addRedNode(),
5.189 + n2 = g.addBlueNode(),
5.190 + n3 = g.addBlueNode();
5.191 +
5.192 + Edge
5.193 + e1 = g.addEdge(n1, n2),
5.194 + e2 = g.addEdge(n1, n3);
5.195 +
5.196 + check(g.valid(n1), "Wrong validity check");
5.197 + check(g.valid(e1), "Wrong validity check");
5.198 + check(g.valid(g.direct(e1, true)), "Wrong validity check");
5.199 +
5.200 + check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
5.201 + check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
5.202 + check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
5.203 +}
5.204 +
5.205 void checkConcepts() {
5.206 { // Checking graph components
5.207 checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
5.208 @@ -51,16 +235,27 @@
5.209 checkConcept<ErasableBpGraphComponent<>,
5.210 ErasableBpGraphComponent<> >();
5.211
5.212 - checkConcept<ClearableGraphComponent<>,
5.213 - ClearableGraphComponent<> >();
5.214 + checkConcept<ClearableBpGraphComponent<>,
5.215 + ClearableBpGraphComponent<> >();
5.216
5.217 }
5.218 { // Checking skeleton graph
5.219 checkConcept<BpGraph, BpGraph>();
5.220 }
5.221 + { // Checking SmartBpGraph
5.222 + checkConcept<BpGraph, SmartBpGraph>();
5.223 + checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
5.224 + checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
5.225 + checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
5.226 + }
5.227 }
5.228
5.229 void checkGraphs() {
5.230 + { // Checking SmartGraph
5.231 + checkBpGraphBuild<SmartBpGraph>();
5.232 + checkBpGraphSnapshot<SmartBpGraph>();
5.233 + checkBpGraphValidity<SmartBpGraph>();
5.234 + }
5.235 }
5.236
5.237 int main() {
6.1 --- a/test/graph_test.h Sun Nov 14 16:35:31 2010 +0100
6.2 +++ b/test/graph_test.h Sun Nov 14 20:06:23 2010 +0100
6.3 @@ -41,6 +41,30 @@
6.4 }
6.5
6.6 template<class Graph>
6.7 + void checkGraphRedNodeList(const Graph &G, int cnt)
6.8 + {
6.9 + typename Graph::RedIt n(G);
6.10 + for(int i=0;i<cnt;i++) {
6.11 + check(n!=INVALID,"Wrong red Node list linking.");
6.12 + ++n;
6.13 + }
6.14 + check(n==INVALID,"Wrong red Node list linking.");
6.15 + check(countRedNodes(G)==cnt,"Wrong red Node number.");
6.16 + }
6.17 +
6.18 + template<class Graph>
6.19 + void checkGraphBlueNodeList(const Graph &G, int cnt)
6.20 + {
6.21 + typename Graph::BlueIt n(G);
6.22 + for(int i=0;i<cnt;i++) {
6.23 + check(n!=INVALID,"Wrong blue Node list linking.");
6.24 + ++n;
6.25 + }
6.26 + check(n==INVALID,"Wrong blue Node list linking.");
6.27 + check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
6.28 + }
6.29 +
6.30 + template<class Graph>
6.31 void checkGraphArcList(const Graph &G, int cnt)
6.32 {
6.33 typename Graph::ArcIt e(G);
6.34 @@ -166,6 +190,7 @@
6.35
6.36 template <typename Graph>
6.37 void checkNodeIds(const Graph& G) {
6.38 + typedef typename Graph::Node Node;
6.39 std::set<int> values;
6.40 for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
6.41 check(G.nodeFromId(G.id(n)) == n, "Wrong id");
6.42 @@ -173,10 +198,40 @@
6.43 check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
6.44 values.insert(G.id(n));
6.45 }
6.46 + check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id");
6.47 + }
6.48 +
6.49 + template <typename Graph>
6.50 + void checkRedNodeIds(const Graph& G) {
6.51 + typedef typename Graph::RedNode RedNode;
6.52 + std::set<int> values;
6.53 + for (typename Graph::RedIt n(G); n != INVALID; ++n) {
6.54 + check(G.red(n), "Wrong partition");
6.55 + check(G.redId(n) == G.id(RedNode(n)), "Wrong id");
6.56 + check(values.find(G.redId(n)) == values.end(), "Wrong id");
6.57 + check(G.redId(n) <= G.maxRedId(), "Wrong maximum id");
6.58 + values.insert(G.id(n));
6.59 + }
6.60 + check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
6.61 + }
6.62 +
6.63 + template <typename Graph>
6.64 + void checkBlueNodeIds(const Graph& G) {
6.65 + typedef typename Graph::BlueNode BlueNode;
6.66 + std::set<int> values;
6.67 + for (typename Graph::BlueIt n(G); n != INVALID; ++n) {
6.68 + check(G.blue(n), "Wrong partition");
6.69 + check(G.blueId(n) == G.id(BlueNode(n)), "Wrong id");
6.70 + check(values.find(G.blueId(n)) == values.end(), "Wrong id");
6.71 + check(G.blueId(n) <= G.maxBlueId(), "Wrong maximum id");
6.72 + values.insert(G.id(n));
6.73 + }
6.74 + check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");
6.75 }
6.76
6.77 template <typename Graph>
6.78 void checkArcIds(const Graph& G) {
6.79 + typedef typename Graph::Arc Arc;
6.80 std::set<int> values;
6.81 for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
6.82 check(G.arcFromId(G.id(a)) == a, "Wrong id");
6.83 @@ -184,10 +239,12 @@
6.84 check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
6.85 values.insert(G.id(a));
6.86 }
6.87 + check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
6.88 }
6.89
6.90 template <typename Graph>
6.91 void checkEdgeIds(const Graph& G) {
6.92 + typedef typename Graph::Edge Edge;
6.93 std::set<int> values;
6.94 for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
6.95 check(G.edgeFromId(G.id(e)) == e, "Wrong id");
6.96 @@ -195,6 +252,7 @@
6.97 check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
6.98 values.insert(G.id(e));
6.99 }
6.100 + check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
6.101 }
6.102
6.103 template <typename Graph>
6.104 @@ -228,6 +286,66 @@
6.105 }
6.106
6.107 template <typename Graph>
6.108 + void checkGraphRedMap(const Graph& G) {
6.109 + typedef typename Graph::Node Node;
6.110 + typedef typename Graph::RedIt RedIt;
6.111 +
6.112 + typedef typename Graph::template RedMap<int> IntRedMap;
6.113 + IntRedMap map(G, 42);
6.114 + for (RedIt it(G); it != INVALID; ++it) {
6.115 + check(map[it] == 42, "Wrong map constructor.");
6.116 + }
6.117 + int s = 0;
6.118 + for (RedIt it(G); it != INVALID; ++it) {
6.119 + map[it] = 0;
6.120 + check(map[it] == 0, "Wrong operator[].");
6.121 + map.set(it, s);
6.122 + check(map[it] == s, "Wrong set.");
6.123 + ++s;
6.124 + }
6.125 + s = s * (s - 1) / 2;
6.126 + for (RedIt it(G); it != INVALID; ++it) {
6.127 + s -= map[it];
6.128 + }
6.129 + check(s == 0, "Wrong sum.");
6.130 +
6.131 + // map = constMap<Node>(12);
6.132 + // for (NodeIt it(G); it != INVALID; ++it) {
6.133 + // check(map[it] == 12, "Wrong operator[].");
6.134 + // }
6.135 + }
6.136 +
6.137 + template <typename Graph>
6.138 + void checkGraphBlueMap(const Graph& G) {
6.139 + typedef typename Graph::Node Node;
6.140 + typedef typename Graph::BlueIt BlueIt;
6.141 +
6.142 + typedef typename Graph::template BlueMap<int> IntBlueMap;
6.143 + IntBlueMap map(G, 42);
6.144 + for (BlueIt it(G); it != INVALID; ++it) {
6.145 + check(map[it] == 42, "Wrong map constructor.");
6.146 + }
6.147 + int s = 0;
6.148 + for (BlueIt it(G); it != INVALID; ++it) {
6.149 + map[it] = 0;
6.150 + check(map[it] == 0, "Wrong operator[].");
6.151 + map.set(it, s);
6.152 + check(map[it] == s, "Wrong set.");
6.153 + ++s;
6.154 + }
6.155 + s = s * (s - 1) / 2;
6.156 + for (BlueIt it(G); it != INVALID; ++it) {
6.157 + s -= map[it];
6.158 + }
6.159 + check(s == 0, "Wrong sum.");
6.160 +
6.161 + // map = constMap<Node>(12);
6.162 + // for (NodeIt it(G); it != INVALID; ++it) {
6.163 + // check(map[it] == 12, "Wrong operator[].");
6.164 + // }
6.165 + }
6.166 +
6.167 + template <typename Graph>
6.168 void checkGraphArcMap(const Graph& G) {
6.169 typedef typename Graph::Arc Arc;
6.170 typedef typename Graph::ArcIt ArcIt;