1.1 --- a/demo/coloring.cc Fri Jun 30 12:14:36 2006 +0000
1.2 +++ b/demo/coloring.cc Fri Jun 30 12:15:45 2006 +0000
1.3 @@ -29,7 +29,7 @@
1.4
1.5 #include <iostream>
1.6
1.7 -#include <lemon/smart_ugraph.h>
1.8 +#include <lemon/smart_graph.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 Fri Jun 30 12:14:36 2006 +0000
2.2 +++ b/demo/strongly_connected_orientation.cc Fri Jun 30 12:15:45 2006 +0000
2.3 @@ -18,7 +18,7 @@
2.4
2.5 #include <iostream>
2.6
2.7 -#include <lemon/smart_ugraph.h>
2.8 +#include <lemon/smart_graph.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 Fri Jun 30 12:14:36 2006 +0000
3.2 +++ b/demo/topology_demo.cc Fri Jun 30 12:15:45 2006 +0000
3.3 @@ -17,7 +17,6 @@
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 Fri Jun 30 12:14:36 2006 +0000
4.2 +++ b/doc/graphs.dox Fri Jun 30 12:15:45 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. This functionalities
4.8 -are defined in the \ref lemon::concept::Graph "Graph" concept.
4.9 +as incoming and outgoing edges of a given node.
4.10
4.11 -The next important graph type concept is the undirected graph concept
4.12 -what is defined in the \ref lemon::concept::UGraph "UGraph" concept class.
4.13 -Each undirected graphs provide node - undirected edge list interfaces.
4.14 -In addition the undirected graphs can be used as directed graphs so
4.15 -they are also conform to the \ref lemon::concept::Graph "Graph" concept.
4.16 +Each graph should meet the \ref lemon::concept::Graph "Graph" concept.
4.17 +This concept does not make it possible to change the graph (i.e. it is
4.18 +not possible to add or delete edges or nodes). Most of the graph
4.19 +algorithms will run on these graphs.
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 Fri Jun 30 12:14:36 2006 +0000
5.2 +++ b/lemon/Makefile.am Fri Jun 30 12:15:45 2006 +0000
5.3 @@ -43,9 +43,7 @@
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 @@ -58,9 +56,7 @@
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 @@ -81,9 +77,7 @@
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 @@ -98,7 +92,6 @@
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 @@ -110,7 +103,6 @@
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 --- a/lemon/bits/bpugraph_extender.h Fri Jun 30 12:14:36 2006 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,838 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
7.2 +++ b/lemon/bits/graph_extender.h Fri Jun 30 12:15:45 2006 +0000
7.3 @@ -20,10 +20,14 @@
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 @@ -314,6 +318,1212 @@
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 --- a/lemon/bits/ugraph_extender.h Fri Jun 30 12:14:36 2006 +0000
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,444 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
9.2 +++ b/lemon/edge_set.h Fri Jun 30 12:15:45 2006 +0000
9.3 @@ -22,7 +22,6 @@
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 --- a/lemon/full_bpugraph.h Fri Jun 30 12:14:36 2006 +0000
10.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
10.3 @@ -1,266 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
11.2 +++ b/lemon/full_graph.h Fri Jun 30 12:15:45 2006 +0000
11.3 @@ -21,6 +21,7 @@
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 @@ -29,7 +30,7 @@
11.12
11.13 ///\ingroup graphs
11.14 ///\file
11.15 -///\brief FullGraph class.
11.16 +///\brief FullGraph and FullUGraph classes.
11.17
11.18
11.19 namespace lemon {
11.20 @@ -246,6 +247,473 @@
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 --- a/lemon/full_ugraph.h Fri Jun 30 12:14:36 2006 +0000
12.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
12.3 @@ -1,280 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
13.2 +++ b/lemon/grid_ugraph.h Fri Jun 30 12:15:45 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/ugraph_extender.h>
13.8 +#include <lemon/bits/graph_extender.h>
13.9
13.10 #include <lemon/xy.h>
13.11
14.1 --- a/lemon/list_bpugraph.h Fri Jun 30 12:14:36 2006 +0000
14.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
14.3 @@ -1,398 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
15.2 +++ b/lemon/list_graph.h Fri Jun 30 12:15:45 2006 +0000
15.3 @@ -21,10 +21,13 @@
15.4
15.5 ///\ingroup graphs
15.6 ///\file
15.7 -///\brief ListGraph class.
15.8 +///\brief ListGraph, ListUGraph classes.
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 @@ -306,7 +309,8 @@
15.19
15.20 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
15.21
15.22 - /// \ingroup graphs
15.23 + /// \addtogroup graphs
15.24 + /// @{
15.25
15.26 ///A list graph class.
15.27
15.28 @@ -701,6 +705,454 @@
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 --- a/lemon/list_ugraph.h Fri Jun 30 12:14:36 2006 +0000
16.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
16.3 @@ -1,120 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
17.2 +++ b/lemon/min_cut.h Fri Jun 30 12:15:45 2006 +0000
17.3 @@ -23,7 +23,6 @@
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 @@ -195,7 +194,7 @@
17.12 #ifdef DOXYGEN
17.13 template <typename _Graph, typename _CapacityMap, typename _Traits>
17.14 #else
17.15 - template <typename _Graph = ListGraph,
17.16 + template <typename _Graph = ListUGraph,
17.17 typename _CapacityMap = typename _Graph::template EdgeMap<int>,
17.18 typename _Traits =
17.19 MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
18.1 --- a/lemon/smart_bpugraph.h Fri Jun 30 12:14:36 2006 +0000
18.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
18.3 @@ -1,273 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
19.2 +++ b/lemon/smart_graph.h Fri Jun 30 12:15:45 2006 +0000
19.3 @@ -21,15 +21,17 @@
19.4
19.5 ///\ingroup graphs
19.6 ///\file
19.7 -///\brief SmartGraph class.
19.8 +///\brief SmartGraph and SmartUGraph classes.
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 @@ -354,6 +356,261 @@
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 --- a/lemon/smart_ugraph.h Fri Jun 30 12:14:36 2006 +0000
20.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
20.3 @@ -1,68 +0,0 @@
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 Fri Jun 30 12:14:36 2006 +0000
21.2 +++ b/test/bipartite_matching_test.cc Fri Jun 30 12:15:45 2006 +0000
21.3 @@ -2,7 +2,7 @@
21.4 #include <iostream>
21.5 #include <sstream>
21.6
21.7 -#include <lemon/list_bpugraph.h>
21.8 +#include <lemon/list_graph.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 Fri Jun 30 12:14:36 2006 +0000
22.2 +++ b/test/max_matching_test.cc Fri Jun 30 12:15:45 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_ugraph.h>
22.8 +#include <lemon/list_graph.h>
22.9 #include <lemon/max_matching.h>
22.10
22.11 using namespace std;
23.1 --- a/test/ugraph_test.cc Fri Jun 30 12:14:36 2006 +0000
23.2 +++ b/test/ugraph_test.cc Fri Jun 30 12:15:45 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_ugraph.h>
23.8 -#include <lemon/smart_ugraph.h>
23.9 -#include <lemon/full_ugraph.h>
23.10 +#include <lemon/list_graph.h>
23.11 +#include <lemon/smart_graph.h>
23.12 +#include <lemon/full_graph.h>
23.13 #include <lemon/grid_ugraph.h>
23.14
23.15 #include <lemon/graph_utils.h>