1.1 --- a/lemon/bits/alteration_notifier.h Mon Nov 21 12:07:05 2005 +0000
1.2 +++ b/lemon/bits/alteration_notifier.h Mon Nov 21 17:48:00 2005 +0000
1.3 @@ -439,6 +439,67 @@
1.4 undir_edge_notifier.clear();
1.5 }
1.6 };
1.7 +
1.8 +
1.9 + template <typename _Base>
1.10 + class AlterableUndirBipartiteGraphExtender : public _Base {
1.11 + public:
1.12 +
1.13 + typedef _Base Parent;
1.14 + typedef AlterableUndirBipartiteGraphExtender Graph;
1.15 +
1.16 + typedef typename Parent::Node Node;
1.17 + typedef typename Parent::LowerNode LowerNode;
1.18 + typedef typename Parent::UpperNode UpperNode;
1.19 + typedef typename Parent::Edge Edge;
1.20 + typedef typename Parent::UndirEdge UndirEdge;
1.21 +
1.22 +
1.23 + typedef AlterationNotifier<Node> NodeNotifier;
1.24 + typedef AlterationNotifier<LowerNode> LowerNodeNotifier;
1.25 + typedef AlterationNotifier<UpperNode> UpperNodeNotifier;
1.26 + typedef AlterationNotifier<Edge> EdgeNotifier;
1.27 + typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
1.28 +
1.29 + protected:
1.30 +
1.31 + mutable NodeNotifier nodeNotifier;
1.32 + mutable LowerNodeNotifier lowerNodeNotifier;
1.33 + mutable UpperNodeNotifier upperNodeNotifier;
1.34 + mutable EdgeNotifier edgeNotifier;
1.35 + mutable UndirEdgeNotifier undirEdgeNotifier;
1.36 +
1.37 + public:
1.38 +
1.39 + NodeNotifier& getNotifier(Node) const {
1.40 + return nodeNotifier;
1.41 + }
1.42 +
1.43 + LowerNodeNotifier& getNotifier(LowerNode) const {
1.44 + return lowerNodeNotifier;
1.45 + }
1.46 +
1.47 + UpperNodeNotifier& getNotifier(UpperNode) const {
1.48 + return upperNodeNotifier;
1.49 + }
1.50 +
1.51 + EdgeNotifier& getNotifier(Edge) const {
1.52 + return edgeNotifier;
1.53 + }
1.54 +
1.55 + UndirEdgeNotifier& getNotifier(UndirEdge) const {
1.56 + return undirEdgeNotifier;
1.57 + }
1.58 +
1.59 + ~AlterableUndirBipartiteGraphExtender() {
1.60 + nodeNotifier.clear();
1.61 + lowerNodeNotifier.clear();
1.62 + upperNodeNotifier.clear();
1.63 + edgeNotifier.clear();
1.64 + undirEdgeNotifier.clear();
1.65 + }
1.66 +
1.67 + };
1.68
1.69 /// @}
1.70
2.1 --- a/lemon/bits/clearable_graph_extender.h Mon Nov 21 12:07:05 2005 +0000
2.2 +++ b/lemon/bits/clearable_graph_extender.h Mon Nov 21 17:48:00 2005 +0000
2.3 @@ -44,6 +44,31 @@
2.4
2.5 };
2.6
2.7 +
2.8 + template <typename _Base>
2.9 + class ClearableUndirBipartiteGraphExtender : public _Base {
2.10 + public:
2.11 +
2.12 + typedef _Base Parent;
2.13 + typedef ClearableUndirBipartiteGraphExtender Graph;
2.14 +
2.15 + typedef typename Parent::Node Node;
2.16 + typedef typename Parent::LowerNode LowerNode;
2.17 + typedef typename Parent::UpperNode UpperNode;
2.18 + typedef typename Parent::Edge Edge;
2.19 + typedef typename Parent::UndirEdge UndirEdge;
2.20 +
2.21 + void clear() {
2.22 + Parent::getNotifier(Edge()).clear();
2.23 + Parent::getNotifier(UndirEdge()).clear();
2.24 + Parent::getNotifier(Node()).clear();
2.25 + Parent::getNotifier(LowerNode()).clear();
2.26 + Parent::getNotifier(UpperNode()).clear();
2.27 + Parent::clear();
2.28 + }
2.29 +
2.30 + };
2.31 +
2.32 }
2.33
2.34 #endif
3.1 --- a/lemon/bits/default_map.h Mon Nov 21 12:07:05 2005 +0000
3.2 +++ b/lemon/bits/default_map.h Mon Nov 21 17:48:00 2005 +0000
3.3 @@ -266,6 +266,272 @@
3.4
3.5 };
3.6
3.7 +
3.8 + template <typename _Base>
3.9 + class MappableUndirBipartiteGraphExtender : public _Base {
3.10 + public:
3.11 +
3.12 + typedef _Base Parent;
3.13 + typedef MappableUndirBipartiteGraphExtender Graph;
3.14 +
3.15 + typedef typename Parent::Node Node;
3.16 + typedef typename Parent::UpperNode UpperNode;
3.17 + typedef typename Parent::LowerNode LowerNode;
3.18 + typedef typename Parent::Edge Edge;
3.19 + typedef typename Parent::UndirEdge UndirEdge;
3.20 +
3.21 + template <typename _Value>
3.22 + class UpperNodeMap
3.23 + : public IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> > {
3.24 + public:
3.25 + typedef MappableUndirBipartiteGraphExtender Graph;
3.26 + typedef IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> >
3.27 + Parent;
3.28 +
3.29 + UpperNodeMap(const Graph& _g)
3.30 + : Parent(_g) {}
3.31 + UpperNodeMap(const Graph& _g, const _Value& _v)
3.32 + : Parent(_g, _v) {}
3.33 +
3.34 + UpperNodeMap& operator=(const UpperNodeMap& cmap) {
3.35 + return operator=<UpperNodeMap>(cmap);
3.36 + }
3.37 +
3.38 +
3.39 + /// \brief Template assign operator.
3.40 + ///
3.41 + /// The given parameter should be conform to the ReadMap
3.42 + /// concept and could be indiced by the current item set of
3.43 + /// the UpperNodeMap. In this case the value for each item
3.44 + /// is assigned by the value of the given ReadMap.
3.45 + template <typename CMap>
3.46 + UpperNodeMap& operator=(const CMap& cmap) {
3.47 + checkConcept<concept::ReadMap<UpperNode, _Value>, CMap>();
3.48 + const typename Parent::Graph* graph = Parent::getGraph();
3.49 + UpperNode it;
3.50 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.51 + Parent::set(it, cmap[it]);
3.52 + }
3.53 + return *this;
3.54 + }
3.55 +
3.56 + };
3.57 +
3.58 + template <typename _Value>
3.59 + class LowerNodeMap
3.60 + : public IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> > {
3.61 + public:
3.62 + typedef MappableUndirBipartiteGraphExtender Graph;
3.63 + typedef IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> >
3.64 + Parent;
3.65 +
3.66 + LowerNodeMap(const Graph& _g)
3.67 + : Parent(_g) {}
3.68 + LowerNodeMap(const Graph& _g, const _Value& _v)
3.69 + : Parent(_g, _v) {}
3.70 +
3.71 + LowerNodeMap& operator=(const LowerNodeMap& cmap) {
3.72 + return operator=<LowerNodeMap>(cmap);
3.73 + }
3.74 +
3.75 +
3.76 + /// \brief Template assign operator.
3.77 + ///
3.78 + /// The given parameter should be conform to the ReadMap
3.79 + /// concept and could be indiced by the current item set of
3.80 + /// the LowerNodeMap. In this case the value for each item
3.81 + /// is assigned by the value of the given ReadMap.
3.82 + template <typename CMap>
3.83 + LowerNodeMap& operator=(const CMap& cmap) {
3.84 + checkConcept<concept::ReadMap<LowerNode, _Value>, CMap>();
3.85 + const typename Parent::Graph* graph = Parent::getGraph();
3.86 + LowerNode it;
3.87 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.88 + Parent::set(it, cmap[it]);
3.89 + }
3.90 + return *this;
3.91 + }
3.92 +
3.93 + };
3.94 +
3.95 + protected:
3.96 +
3.97 + template <typename _Value>
3.98 + class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
3.99 + public:
3.100 + typedef MappableUndirBipartiteGraphExtender Graph;
3.101 +
3.102 + typedef Node Key;
3.103 + typedef _Value Value;
3.104 +
3.105 + /// The reference type of the map;
3.106 + typedef typename LowerNodeMap<_Value>::Reference Reference;
3.107 + /// The pointer type of the map;
3.108 + typedef typename LowerNodeMap<_Value>::Pointer Pointer;
3.109 +
3.110 + /// The const value type of the map.
3.111 + typedef const Value ConstValue;
3.112 + /// The const reference type of the map;
3.113 + typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;
3.114 + /// The pointer type of the map;
3.115 + typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;
3.116 +
3.117 + typedef True ReferenceMapTag;
3.118 +
3.119 + NodeMapBase(const Graph& _g)
3.120 + : graph(&_g), lowerMap(_g), upperMap(_g) {
3.121 + Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
3.122 + }
3.123 + NodeMapBase(const Graph& _g, const _Value& _v)
3.124 + : graph(&_g), lowerMap(_g, _v),
3.125 + upperMap(_g, _v) {
3.126 + Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
3.127 + }
3.128 +
3.129 + virtual ~NodeMapBase() {
3.130 + if (Parent::NodeNotifier::ObserverBase::attached()) {
3.131 + Parent::NodeNotifier::ObserverBase::detach();
3.132 + }
3.133 + }
3.134 +
3.135 + ConstReference operator[](const Key& node) const {
3.136 + if (Parent::upper(node)) {
3.137 + return upperMap[node];
3.138 + } else {
3.139 + return lowerMap[node];
3.140 + }
3.141 + }
3.142 +
3.143 + Reference operator[](const Key& node) {
3.144 + if (Parent::upper(node)) {
3.145 + return upperMap[node];
3.146 + } else {
3.147 + return lowerMap[node];
3.148 + }
3.149 + }
3.150 +
3.151 + void set(const Key& node, const Value& value) {
3.152 + if (Parent::upper(node)) {
3.153 + upperMap.set(node, value);
3.154 + } else {
3.155 + lowerMap.set(node, value);
3.156 + }
3.157 + }
3.158 +
3.159 + protected:
3.160 +
3.161 + virtual void add(const Node&) {}
3.162 + virtual void erase(const Node&) {}
3.163 + virtual void clear() {}
3.164 + virtual void build() {}
3.165 +
3.166 + const Graph* getGraph() const { return graph; }
3.167 +
3.168 + private:
3.169 + const Graph* graph;
3.170 + LowerNodeMap<_Value> lowerMap;
3.171 + UpperNodeMap<_Value> upperMap;
3.172 + };
3.173 +
3.174 + public:
3.175 +
3.176 + template <typename _Value>
3.177 + class NodeMap
3.178 + : public IterableMapExtender<NodeMapBase<_Value> > {
3.179 + public:
3.180 + typedef MappableUndirBipartiteGraphExtender Graph;
3.181 + typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
3.182 +
3.183 + NodeMap(const Graph& _g)
3.184 + : Parent(_g) {}
3.185 + NodeMap(const Graph& _g, const _Value& _v)
3.186 + : Parent(_g, _v) {}
3.187 +
3.188 + NodeMap& operator=(const NodeMap& cmap) {
3.189 + return operator=<NodeMap>(cmap);
3.190 + }
3.191 +
3.192 +
3.193 + /// \brief Template assign operator.
3.194 + ///
3.195 + /// The given parameter should be conform to the ReadMap
3.196 + /// concept and could be indiced by the current item set of
3.197 + /// the NodeMap. In this case the value for each item
3.198 + /// is assigned by the value of the given ReadMap.
3.199 + template <typename CMap>
3.200 + NodeMap& operator=(const CMap& cmap) {
3.201 + checkConcept<concept::ReadMap<Node, _Value>, CMap>();
3.202 + const typename Parent::Graph* graph = Parent::getGraph();
3.203 + Node it;
3.204 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.205 + Parent::set(it, cmap[it]);
3.206 + }
3.207 + return *this;
3.208 + }
3.209 +
3.210 + };
3.211 +
3.212 +
3.213 +
3.214 + template <typename _Value>
3.215 + class EdgeMap
3.216 + : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
3.217 + public:
3.218 + typedef MappableUndirBipartiteGraphExtender Graph;
3.219 + typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
3.220 +
3.221 + EdgeMap(const Graph& _g)
3.222 + : Parent(_g) {}
3.223 + EdgeMap(const Graph& _g, const _Value& _v)
3.224 + : Parent(_g, _v) {}
3.225 +
3.226 + EdgeMap& operator=(const EdgeMap& cmap) {
3.227 + return operator=<EdgeMap>(cmap);
3.228 + }
3.229 +
3.230 + template <typename CMap>
3.231 + EdgeMap& operator=(const CMap& cmap) {
3.232 + checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
3.233 + const typename Parent::Graph* graph = Parent::getGraph();
3.234 + Edge it;
3.235 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.236 + Parent::set(it, cmap[it]);
3.237 + }
3.238 + return *this;
3.239 + }
3.240 + };
3.241 +
3.242 + template <typename _Value>
3.243 + class UndirEdgeMap
3.244 + : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
3.245 + public:
3.246 + typedef MappableUndirBipartiteGraphExtender Graph;
3.247 + typedef IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> >
3.248 + Parent;
3.249 +
3.250 + UndirEdgeMap(const Graph& _g)
3.251 + : Parent(_g) {}
3.252 + UndirEdgeMap(const Graph& _g, const _Value& _v)
3.253 + : Parent(_g, _v) {}
3.254 +
3.255 + UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
3.256 + return operator=<UndirEdgeMap>(cmap);
3.257 + }
3.258 +
3.259 + template <typename CMap>
3.260 + UndirEdgeMap& operator=(const CMap& cmap) {
3.261 + checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
3.262 + const typename Parent::Graph* graph = Parent::getGraph();
3.263 + UndirEdge it;
3.264 + for (graph->first(it); it != INVALID; graph->next(it)) {
3.265 + Parent::set(it, cmap[it]);
3.266 + }
3.267 + return *this;
3.268 + }
3.269 + };
3.270 +
3.271 + };
3.272 +
3.273 }
3.274
3.275 #endif
4.1 --- a/lemon/bits/extendable_graph_extender.h Mon Nov 21 12:07:05 2005 +0000
4.2 +++ b/lemon/bits/extendable_graph_extender.h Mon Nov 21 17:48:00 2005 +0000
4.3 @@ -60,6 +60,48 @@
4.4
4.5 };
4.6
4.7 +
4.8 + template <typename _Base>
4.9 + class ExtendableUndirBipartiteGraphExtender : public _Base {
4.10 + public:
4.11 +
4.12 + typedef _Base Parent;
4.13 + typedef ExtendableUndirBipartiteGraphExtender Graph;
4.14 +
4.15 + typedef typename Parent::Node Node;
4.16 + typedef typename Parent::LowerNode LowerNode;
4.17 + typedef typename Parent::UpperNode UpperNode;
4.18 + typedef typename Parent::Edge Edge;
4.19 + typedef typename Parent::UndirEdge UndirEdge;
4.20 +
4.21 + Node addUpperNode() {
4.22 + Node node = Parent::addUpperNode();
4.23 + Parent::getNotifier(UpperNode()).add(node);
4.24 + Parent::getNotifier(Node()).add(node);
4.25 + return node;
4.26 + }
4.27 +
4.28 + Node addLowerNode() {
4.29 + Node node = Parent::addLowerNode();
4.30 + Parent::getNotifier(LowerNode()).add(node);
4.31 + Parent::getNotifier(Node()).add(node);
4.32 + return node;
4.33 + }
4.34 +
4.35 + UndirEdge addEdge(const Node& source, const Node& target) {
4.36 + UndirEdge undiredge = Parent::addEdge(source, target);
4.37 + Parent::getNotifier(UndirEdge()).add(undiredge);
4.38 +
4.39 + std::vector<Edge> edges;
4.40 + edges.push_back(Parent::direct(undiredge, true));
4.41 + edges.push_back(Parent::direct(undiredge, false));
4.42 + Parent::getNotifier(Edge()).add(edges);
4.43 +
4.44 + return undiredge;
4.45 + }
4.46 +
4.47 + };
4.48 +
4.49 }
4.50
4.51 #endif
5.1 --- a/lemon/bits/graph_extender.h Mon Nov 21 12:07:05 2005 +0000
5.2 +++ b/lemon/bits/graph_extender.h Mon Nov 21 17:48:00 2005 +0000
5.3 @@ -19,6 +19,7 @@
5.4 #define LEMON_GRAPH_EXTENDER_H
5.5
5.6 #include <lemon/invalid.h>
5.7 +#include <lemon/error.h>
5.8
5.9 namespace lemon {
5.10
5.11 @@ -376,6 +377,248 @@
5.12
5.13 };
5.14
5.15 +
5.16 + template <typename _Base>
5.17 + class UndirBipartiteGraphExtender : public _Base {
5.18 + public:
5.19 + typedef _Base Parent;
5.20 + typedef UndirBipartiteGraphExtender Graph;
5.21 +
5.22 + typedef typename Parent::Node Node;
5.23 + typedef typename Parent::Edge UndirEdge;
5.24 +
5.25 + using Parent::first;
5.26 + using Parent::next;
5.27 +
5.28 + using Parent::id;
5.29 +
5.30 + Node source(const UndirEdge& edge) const {
5.31 + return upperNode(edge);
5.32 + }
5.33 + Node target(const UndirEdge& edge) const {
5.34 + return lowerNode(edge);
5.35 + }
5.36 +
5.37 + void firstInc(UndirEdge& edge, bool& direction, const Node& node) const {
5.38 + if (Parent::upper(node)) {
5.39 + Parent::firstDown(edge, node);
5.40 + direction = true;
5.41 + } else {
5.42 + Parent::firstUp(edge, node);
5.43 + direction = static_cast<UndirEdge&>(edge) == INVALID;
5.44 + }
5.45 + }
5.46 + void nextInc(UndirEdge& edge, bool& direction) const {
5.47 + if (direction) {
5.48 + Parent::nextDown(edge);
5.49 + } else {
5.50 + Parent::nextUp(edge);
5.51 + if (edge == INVALID) direction = true;
5.52 + }
5.53 + }
5.54 +
5.55 + int maxUndirEdgeId() const {
5.56 + return Parent::maxEdgeId();
5.57 + }
5.58 +
5.59 + UndirEdge undirEdgeFromId(int id) const {
5.60 + return Parent::edgeFromId(id);
5.61 + }
5.62 +
5.63 + class Edge : public UndirEdge {
5.64 + friend class UndirBipartiteGraphExtender;
5.65 + protected:
5.66 + bool forward;
5.67 +
5.68 + Edge(const UndirEdge& edge, bool _forward)
5.69 + : UndirEdge(edge), forward(_forward) {}
5.70 +
5.71 + public:
5.72 + Edge() {}
5.73 + Edge (Invalid) : UndirEdge(INVALID), forward(true) {}
5.74 + bool operator==(const Edge& i) const {
5.75 + return UndirEdge::operator==(i) && forward == i.forward;
5.76 + }
5.77 + bool operator!=(const Edge& i) const {
5.78 + return UndirEdge::operator!=(i) || forward != i.forward;
5.79 + }
5.80 + bool operator<(const Edge& i) const {
5.81 + return UndirEdge::operator<(i) ||
5.82 + (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i));
5.83 + }
5.84 + };
5.85 +
5.86 + void first(Edge& edge) const {
5.87 + Parent::first(static_cast<UndirEdge&>(edge));
5.88 + edge.forward = true;
5.89 + }
5.90 +
5.91 + void next(Edge& edge) const {
5.92 + if (!edge.forward) {
5.93 + Parent::next(static_cast<UndirEdge&>(edge));
5.94 + }
5.95 + edge.forward = !edge.forward;
5.96 + }
5.97 +
5.98 + void firstOut(Edge& edge, const Node& node) const {
5.99 + if (Parent::upper(node)) {
5.100 + Parent::firstDown(edge, node);
5.101 + edge.forward = true;
5.102 + } else {
5.103 + Parent::firstUp(edge, node);
5.104 + edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
5.105 + }
5.106 + }
5.107 + void nextOut(Edge& edge) const {
5.108 + if (edge.forward) {
5.109 + Parent::nextDown(edge);
5.110 + } else {
5.111 + Parent::nextUp(edge);
5.112 + if (edge == INVALID) {
5.113 + edge.forward = true;
5.114 + }
5.115 + }
5.116 + }
5.117 +
5.118 + void firstIn(Edge& edge, const Node& node) const {
5.119 + if (Parent::lower(node)) {
5.120 + Parent::firstUp(edge, node);
5.121 + edge.forward = true;
5.122 + } else {
5.123 + Parent::firstDown(edge, node);
5.124 + edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
5.125 + }
5.126 + }
5.127 + void nextIn(Edge& edge) const {
5.128 + if (edge.forward) {
5.129 + Parent::nextUp(edge);
5.130 + } else {
5.131 + Parent::nextDown(edge);
5.132 + if (edge == INVALID) {
5.133 + edge.forward = true;
5.134 + }
5.135 + }
5.136 + }
5.137 +
5.138 + Node source(const Edge& edge) const {
5.139 + return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge);
5.140 + }
5.141 + Node target(const Edge& edge) const {
5.142 + return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge);
5.143 + }
5.144 +
5.145 + bool direction(const Edge& edge) const {
5.146 + return edge.forward;
5.147 + }
5.148 +
5.149 + Edge direct(const UndirEdge& edge, const Node& node) const {
5.150 + return Edge(edge, node == Parent::source(edge));
5.151 + }
5.152 +
5.153 + Edge direct(const UndirEdge& edge, bool direction) const {
5.154 + return Edge(edge, direction);
5.155 + }
5.156 +
5.157 + Node oppositeNode(const UndirEdge& edge, const Node& node) const {
5.158 + return source(edge) == node ?
5.159 + target(edge) : source(edge);
5.160 + }
5.161 +
5.162 + Edge oppositeEdge(const Edge& edge) const {
5.163 + return Edge(edge, !edge.forward);
5.164 + }
5.165 +
5.166 + int id(const Edge& edge) const {
5.167 + return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
5.168 + }
5.169 + Edge edgeFromId(int id) const {
5.170 + return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);
5.171 + }
5.172 + int maxEdgeId() const {
5.173 + return (Parent::maxId(UndirEdge()) << 1) + 1;
5.174 + }
5.175 +
5.176 + class UpperNode : public Node {
5.177 + friend class UndirBipartiteGraphExtender;
5.178 + public:
5.179 + UpperNode() {}
5.180 + UpperNode(const Node& node) : Node(node) {
5.181 + LEMON_ASSERT(Parent::upper(node) || node == INVALID,
5.182 + typename Parent::NodeSetError());
5.183 + }
5.184 + UpperNode(Invalid) : Node(INVALID) {}
5.185 + };
5.186 +
5.187 + void first(UpperNode& node) const {
5.188 + Parent::firstUpper(static_cast<Node&>(node));
5.189 + }
5.190 + void next(UpperNode& node) const {
5.191 + Parent::nextUpper(static_cast<Node&>(node));
5.192 + }
5.193 +
5.194 + int id(const UpperNode& node) const {
5.195 + return Parent::upperId(node);
5.196 + }
5.197 +
5.198 + class LowerNode : public Node {
5.199 + friend class UndirBipartiteGraphExtender;
5.200 + public:
5.201 + LowerNode() {}
5.202 + LowerNode(const Node& node) : Node(node) {
5.203 + LEMON_ASSERT(Parent::lower(node) || node == INVALID,
5.204 + typename Parent::NodeSetError());
5.205 + }
5.206 + LowerNode(Invalid) : Node(INVALID) {}
5.207 + };
5.208 +
5.209 + void first(LowerNode& node) const {
5.210 + Parent::firstLower(static_cast<Node&>(node));
5.211 + }
5.212 + void next(LowerNode& node) const {
5.213 + Parent::nextLower(static_cast<Node&>(node));
5.214 + }
5.215 +
5.216 + int id(const LowerNode& node) const {
5.217 + return Parent::upperId(node);
5.218 + }
5.219 +
5.220 +
5.221 +
5.222 + int maxId(Node) const {
5.223 + return Parent::maxNodeId();
5.224 + }
5.225 + int maxId(LowerNode) const {
5.226 + return Parent::maxLowerId();
5.227 + }
5.228 + int maxId(UpperNode) const {
5.229 + return Parent::maxUpperId();
5.230 + }
5.231 + int maxId(Edge) const {
5.232 + return maxEdgeId();
5.233 + }
5.234 + int maxId(UndirEdge) const {
5.235 + return maxUndirEdgeId();
5.236 + }
5.237 +
5.238 +
5.239 + Node fromId(int id, Node) const {
5.240 + return Parent::nodeFromId(id);
5.241 + }
5.242 + UpperNode fromId(int id, UpperNode) const {
5.243 + return Parent::fromUpperId(id);
5.244 + }
5.245 + LowerNode fromId(int id, LowerNode) const {
5.246 + return Parent::fromLowerId(id);
5.247 + }
5.248 + Edge fromId(int id, Edge) const {
5.249 + return edgeFromId(id);
5.250 + }
5.251 + UndirEdge fromId(int id, UndirEdge) const {
5.252 + return undirEdgeFromId(id);
5.253 + }
5.254 +
5.255 + };
5.256 +
5.257 }
5.258
5.259 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H
6.1 --- a/lemon/bits/iterable_graph_extender.h Mon Nov 21 12:07:05 2005 +0000
6.2 +++ b/lemon/bits/iterable_graph_extender.h Mon Nov 21 17:48:00 2005 +0000
6.3 @@ -267,6 +267,250 @@
6.4 }
6.5
6.6 };
6.7 +
6.8 +
6.9 + template <typename _Base>
6.10 + class IterableUndirBipartiteGraphExtender : public _Base {
6.11 + public:
6.12 + typedef _Base Parent;
6.13 + typedef IterableUndirBipartiteGraphExtender Graph;
6.14 +
6.15 + typedef typename Parent::Node Node;
6.16 + typedef typename Parent::UpperNode UpperNode;
6.17 + typedef typename Parent::LowerNode LowerNode;
6.18 + typedef typename Parent::Edge Edge;
6.19 + typedef typename Parent::UndirEdge UndirEdge;
6.20 +
6.21 + class NodeIt : public Node {
6.22 + const Graph* graph;
6.23 + public:
6.24 +
6.25 + NodeIt() { }
6.26 +
6.27 + NodeIt(Invalid i) : Node(INVALID) { }
6.28 +
6.29 + explicit NodeIt(const Graph& _graph) : graph(&_graph) {
6.30 + graph->first(static_cast<Node&>(*this));
6.31 + }
6.32 +
6.33 + NodeIt(const Graph& _graph, const Node& node)
6.34 + : Node(node), graph(&_graph) { }
6.35 +
6.36 + NodeIt& operator++() {
6.37 + graph->next(*this);
6.38 + return *this;
6.39 + }
6.40 +
6.41 + };
6.42 +
6.43 + class UpperNodeIt : public Node {
6.44 + friend class IterableUndirBipartiteGraphExtender;
6.45 + const Graph* graph;
6.46 + public:
6.47 +
6.48 + UpperNodeIt() { }
6.49 +
6.50 + UpperNodeIt(Invalid i) : Node(INVALID) { }
6.51 +
6.52 + explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {
6.53 + graph->firstUpper(static_cast<Node&>(*this));
6.54 + }
6.55 +
6.56 + UpperNodeIt(const Graph& _graph, const Node& node)
6.57 + : Node(node), graph(&_graph) {}
6.58 +
6.59 + UpperNodeIt& operator++() {
6.60 + graph->nextUpper(*this);
6.61 + return *this;
6.62 + }
6.63 + };
6.64 +
6.65 + class LowerNodeIt : public Node {
6.66 + friend class IterableUndirBipartiteGraphExtender;
6.67 + const Graph* graph;
6.68 + public:
6.69 +
6.70 + LowerNodeIt() { }
6.71 +
6.72 + LowerNodeIt(Invalid i) : Node(INVALID) { }
6.73 +
6.74 + explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {
6.75 + graph->firstLower(static_cast<Node&>(*this));
6.76 + }
6.77 +
6.78 + LowerNodeIt(const Graph& _graph, const Node& node)
6.79 + : Node(node), graph(&_graph) {}
6.80 +
6.81 + LowerNodeIt& operator++() {
6.82 + graph->nextLower(*this);
6.83 + return *this;
6.84 + }
6.85 + };
6.86 +
6.87 + class EdgeIt : public Edge {
6.88 + friend class IterableUndirBipartiteGraphExtender;
6.89 + const Graph* graph;
6.90 + public:
6.91 +
6.92 + EdgeIt() { }
6.93 +
6.94 + EdgeIt(Invalid i) : Edge(INVALID) { }
6.95 +
6.96 + explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
6.97 + graph->first(static_cast<Edge&>(*this));
6.98 + }
6.99 +
6.100 + EdgeIt(const Graph& _graph, const Edge& edge)
6.101 + : Edge(edge), graph(&_graph) { }
6.102 +
6.103 + EdgeIt& operator++() {
6.104 + graph->next(*this);
6.105 + return *this;
6.106 + }
6.107 +
6.108 + };
6.109 +
6.110 + class UndirEdgeIt : public UndirEdge {
6.111 + friend class IterableUndirBipartiteGraphExtender;
6.112 + const Graph* graph;
6.113 + public:
6.114 +
6.115 + UndirEdgeIt() { }
6.116 +
6.117 + UndirEdgeIt(Invalid i) : UndirEdge(INVALID) { }
6.118 +
6.119 + explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
6.120 + graph->first(static_cast<UndirEdge&>(*this));
6.121 + }
6.122 +
6.123 + UndirEdgeIt(const Graph& _graph, const UndirEdge& edge)
6.124 + : UndirEdge(edge), graph(&_graph) { }
6.125 +
6.126 + UndirEdgeIt& operator++() {
6.127 + graph->next(*this);
6.128 + return *this;
6.129 + }
6.130 + };
6.131 +
6.132 + class OutEdgeIt : public Edge {
6.133 + friend class IterableUndirBipartiteGraphExtender;
6.134 + const Graph* graph;
6.135 + public:
6.136 +
6.137 + OutEdgeIt() { }
6.138 +
6.139 + OutEdgeIt(Invalid i) : Edge(i) { }
6.140 +
6.141 + OutEdgeIt(const Graph& _graph, const Node& node)
6.142 + : graph(&_graph) {
6.143 + graph->firstOut(*this, node);
6.144 + }
6.145 +
6.146 + OutEdgeIt(const Graph& _graph, const Edge& edge)
6.147 + : Edge(edge), graph(&_graph) {}
6.148 +
6.149 + OutEdgeIt& operator++() {
6.150 + graph->nextOut(*this);
6.151 + return *this;
6.152 + }
6.153 +
6.154 + };
6.155 +
6.156 +
6.157 + class InEdgeIt : public Edge {
6.158 + friend class IterableUndirBipartiteGraphExtender;
6.159 + const Graph* graph;
6.160 + public:
6.161 +
6.162 + InEdgeIt() { }
6.163 +
6.164 + InEdgeIt(Invalid i) : Edge(i) { }
6.165 +
6.166 + InEdgeIt(const Graph& _graph, const Node& node)
6.167 + : graph(&_graph) {
6.168 + graph->firstIn(*this, node);
6.169 + }
6.170 +
6.171 + InEdgeIt(const Graph& _graph, const Edge& edge) :
6.172 + Edge(edge), graph(&_graph) {}
6.173 +
6.174 + InEdgeIt& operator++() {
6.175 + graph->nextIn(*this);
6.176 + return *this;
6.177 + }
6.178 +
6.179 + };
6.180 +
6.181 + /// \brief Base node of the iterator
6.182 + ///
6.183 + /// Returns the base node (ie. the source in this case) of the iterator
6.184 + Node baseNode(const OutEdgeIt &e) const {
6.185 + return Parent::source((Edge&)e);
6.186 + }
6.187 + /// \brief Running node of the iterator
6.188 + ///
6.189 + /// Returns the running node (ie. the target in this case) of the
6.190 + /// iterator
6.191 + Node runningNode(const OutEdgeIt &e) const {
6.192 + return Parent::target((Edge&)e);
6.193 + }
6.194 +
6.195 + /// \brief Base node of the iterator
6.196 + ///
6.197 + /// Returns the base node (ie. the target in this case) of the iterator
6.198 + Node baseNode(const InEdgeIt &e) const {
6.199 + return Parent::target((Edge&)e);
6.200 + }
6.201 + /// \brief Running node of the iterator
6.202 + ///
6.203 + /// Returns the running node (ie. the source in this case) of the
6.204 + /// iterator
6.205 + Node runningNode(const InEdgeIt &e) const {
6.206 + return Parent::source((Edge&)e);
6.207 + }
6.208 +
6.209 + class IncEdgeIt : public Parent::UndirEdge {
6.210 + friend class IterableUndirBipartiteGraphExtender;
6.211 + const Graph* graph;
6.212 + bool direction;
6.213 + public:
6.214 +
6.215 + IncEdgeIt() { }
6.216 +
6.217 + IncEdgeIt(Invalid i) : UndirEdge(i), direction(true) { }
6.218 +
6.219 + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
6.220 + graph->firstInc(*this, direction, n);
6.221 + }
6.222 +
6.223 + IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
6.224 + : graph(&_graph), UndirEdge(ue) {
6.225 + direction = (graph->source(ue) == n);
6.226 + }
6.227 +
6.228 + IncEdgeIt& operator++() {
6.229 + graph->nextInc(*this, direction);
6.230 + return *this;
6.231 + }
6.232 + };
6.233 +
6.234 +
6.235 + /// Base node of the iterator
6.236 + ///
6.237 + /// Returns the base node of the iterator
6.238 + Node baseNode(const IncEdgeIt &e) const {
6.239 + return e.direction ? source(e) : target(e);
6.240 + }
6.241 +
6.242 + /// Running node of the iterator
6.243 + ///
6.244 + /// Returns the running node of the iterator
6.245 + Node runningNode(const IncEdgeIt &e) const {
6.246 + return e.direction ? target(e) : source(e);
6.247 + }
6.248 +
6.249 + };
6.250 +
6.251 }
6.252
6.253 #endif // LEMON_GRAPH_EXTENDER_H
7.1 --- a/lemon/full_graph.h Mon Nov 21 12:07:05 2005 +0000
7.2 +++ b/lemon/full_graph.h Mon Nov 21 17:48:00 2005 +0000
7.3 @@ -402,6 +402,196 @@
7.4 UndirFullGraph(int n) { construct(n); }
7.5 };
7.6
7.7 +
7.8 + class FullUndirBipartiteGraphBase {
7.9 + protected:
7.10 +
7.11 + int _upperNodeNum;
7.12 + int _lowerNodeNum;
7.13 +
7.14 + int _edgeNum;
7.15 +
7.16 + public:
7.17 +
7.18 + class NodeSetError : public LogicError {
7.19 + virtual const char* exceptionName() const {
7.20 + return "lemon::FullUndirBipartiteGraph::NodeSetError";
7.21 + }
7.22 + };
7.23 +
7.24 + class Node {
7.25 + friend class FullUndirBipartiteGraphBase;
7.26 + protected:
7.27 + int id;
7.28 +
7.29 + Node(int _id) : id(_id) {}
7.30 + public:
7.31 + Node() {}
7.32 + Node(Invalid) { id = -1; }
7.33 + bool operator==(const Node i) const {return id==i.id;}
7.34 + bool operator!=(const Node i) const {return id!=i.id;}
7.35 + bool operator<(const Node i) const {return id<i.id;}
7.36 + };
7.37 +
7.38 + class Edge {
7.39 + friend class FullUndirBipartiteGraphBase;
7.40 + protected:
7.41 + int id;
7.42 +
7.43 + Edge(int _id) { id = _id;}
7.44 + public:
7.45 + Edge() {}
7.46 + Edge (Invalid) { id = -1; }
7.47 + bool operator==(const Edge i) const {return id==i.id;}
7.48 + bool operator!=(const Edge i) const {return id!=i.id;}
7.49 + bool operator<(const Edge i) const {return id<i.id;}
7.50 + };
7.51 +
7.52 + void construct(int upperNodeNum, int lowerNodeNum) {
7.53 + _upperNodeNum = upperNodeNum;
7.54 + _lowerNodeNum = lowerNodeNum;
7.55 + _edgeNum = upperNodeNum * lowerNodeNum;
7.56 + }
7.57 +
7.58 + void firstUpper(Node& node) const {
7.59 + node.id = 2 * _upperNodeNum - 2;
7.60 + if (node.id < 0) node.id = -1;
7.61 + }
7.62 + void nextUpper(Node& node) const {
7.63 + node.id -= 2;
7.64 + if (node.id < 0) node.id = -1;
7.65 + }
7.66 +
7.67 + void firstLower(Node& node) const {
7.68 + node.id = 2 * _lowerNodeNum - 1;
7.69 + }
7.70 + void nextLower(Node& node) const {
7.71 + node.id -= 2;
7.72 + }
7.73 +
7.74 + void first(Node& node) const {
7.75 + if (_upperNodeNum > 0) {
7.76 + node.id = 2 * _upperNodeNum - 2;
7.77 + } else {
7.78 + node.id = 2 * _lowerNodeNum - 1;
7.79 + }
7.80 + }
7.81 + void next(Node& node) const {
7.82 + node.id -= 2;
7.83 + if (node.id == -2) {
7.84 + node.id = 2 * _lowerNodeNum - 1;
7.85 + }
7.86 + }
7.87 +
7.88 + void first(Edge& edge) const {
7.89 + edge.id = _edgeNum - 1;
7.90 + }
7.91 + void next(Edge& edge) const {
7.92 + --edge.id;
7.93 + }
7.94 +
7.95 + void firstDown(Edge& edge, const Node& node) const {
7.96 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
7.97 + edge.id = (node.id >> 1) * _lowerNodeNum;
7.98 + }
7.99 + void nextDown(Edge& edge) const {
7.100 + ++(edge.id);
7.101 + if (edge.id % _lowerNodeNum == 0) edge.id = -1;
7.102 + }
7.103 +
7.104 + void firstUp(Edge& edge, const Node& node) const {
7.105 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
7.106 + edge.id = (node.id >> 1);
7.107 + }
7.108 + void nextUp(Edge& edge) const {
7.109 + edge.id += _lowerNodeNum;
7.110 + if (edge.id >= _edgeNum) edge.id = -1;
7.111 + }
7.112 +
7.113 + static int id(const Node& node) {
7.114 + return node.id;
7.115 + }
7.116 + static Node nodeFromId(int id) {
7.117 + return Node(id);
7.118 + }
7.119 + int maxNodeId() const {
7.120 + return _upperNodeNum > _lowerNodeNum ?
7.121 + _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
7.122 + }
7.123 +
7.124 + static int id(const Edge& edge) {
7.125 + return edge.id;
7.126 + }
7.127 + static Edge edgeFromId(int id) {
7.128 + return Edge(id);
7.129 + }
7.130 + int maxEdgeId() const {
7.131 + return _edgeNum - 1;
7.132 + }
7.133 +
7.134 + static int upperId(const Node& node) {
7.135 + return node.id >> 1;
7.136 + }
7.137 + static Node fromUpperId(int id, Node) {
7.138 + return Node(id << 1);
7.139 + }
7.140 + int maxUpperId() const {
7.141 + return _upperNodeNum;
7.142 + }
7.143 +
7.144 + static int lowerId(const Node& node) {
7.145 + return node.id >> 1;
7.146 + }
7.147 + static Node fromLowerId(int id) {
7.148 + return Node((id << 1) + 1);
7.149 + }
7.150 + int maxLowerId() const {
7.151 + return _lowerNodeNum;
7.152 + }
7.153 +
7.154 + Node upperNode(const Edge& edge) const {
7.155 + return Node((edge.id / _lowerNodeNum) << 1);
7.156 + }
7.157 + Node lowerNode(const Edge& edge) const {
7.158 + return Node(((edge.id % _lowerNodeNum) << 1) + 1);
7.159 + }
7.160 +
7.161 + static bool upper(const Node& node) {
7.162 + return (node.id & 1) == 0;
7.163 + }
7.164 +
7.165 + static bool lower(const Node& node) {
7.166 + return (node.id & 1) == 1;
7.167 + }
7.168 +
7.169 + static Node upperNode(int index) {
7.170 + return Node(index << 1);
7.171 + }
7.172 +
7.173 + static Node lowerNode(int index) {
7.174 + return Node((index << 1) + 1);
7.175 + }
7.176 +
7.177 + };
7.178 +
7.179 +
7.180 + typedef MappableUndirBipartiteGraphExtender<
7.181 + IterableUndirBipartiteGraphExtender<
7.182 + AlterableUndirBipartiteGraphExtender<
7.183 + UndirBipartiteGraphExtender <
7.184 + FullUndirBipartiteGraphBase> > > >
7.185 + ExtendedFullUndirBipartiteGraphBase;
7.186 +
7.187 +
7.188 + class FullUndirBipartiteGraph :
7.189 + public ExtendedFullUndirBipartiteGraphBase {
7.190 + public:
7.191 + typedef ExtendedFullUndirBipartiteGraphBase Parent;
7.192 + FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
7.193 + Parent::construct(upperNodeNum, lowerNodeNum);
7.194 + }
7.195 + };
7.196 +
7.197 } //namespace lemon
7.198
7.199
8.1 --- a/lemon/smart_graph.h Mon Nov 21 12:07:05 2005 +0000
8.2 +++ b/lemon/smart_graph.h Mon Nov 21 17:48:00 2005 +0000
8.3 @@ -33,6 +33,7 @@
8.4 #include <lemon/bits/graph_extender.h>
8.5
8.6 #include <lemon/utility.h>
8.7 +#include <lemon/error.h>
8.8
8.9 namespace lemon {
8.10
8.11 @@ -374,6 +375,228 @@
8.12 class UndirSmartGraph : public ExtendedUndirSmartGraphBase {
8.13 };
8.14
8.15 +
8.16 + class SmartUndirBipartiteGraphBase {
8.17 + public:
8.18 +
8.19 + class NodeSetError : public LogicError {
8.20 + virtual const char* exceptionName() const {
8.21 + return "lemon::FullUndirBipartiteGraph::NodeSetError";
8.22 + }
8.23 + };
8.24 +
8.25 + protected:
8.26 +
8.27 + struct NodeT {
8.28 + int first;
8.29 + NodeT() {}
8.30 + NodeT(int _first) : first(_first) {}
8.31 + };
8.32 +
8.33 + struct EdgeT {
8.34 + int upper, next_down;
8.35 + int lower, next_up;
8.36 + };
8.37 +
8.38 + std::vector<NodeT> upperNodes;
8.39 + std::vector<NodeT> lowerNodes;
8.40 +
8.41 + std::vector<EdgeT> edges;
8.42 +
8.43 + public:
8.44 +
8.45 + class Node {
8.46 + friend class SmartUndirBipartiteGraphBase;
8.47 + protected:
8.48 + int id;
8.49 +
8.50 + Node(int _id) : id(_id) {}
8.51 + public:
8.52 + Node() {}
8.53 + Node(Invalid) { id = -1; }
8.54 + bool operator==(const Node i) const {return id==i.id;}
8.55 + bool operator!=(const Node i) const {return id!=i.id;}
8.56 + bool operator<(const Node i) const {return id<i.id;}
8.57 + };
8.58 +
8.59 + class Edge {
8.60 + friend class SmartUndirBipartiteGraphBase;
8.61 + protected:
8.62 + int id;
8.63 +
8.64 + Edge(int _id) { id = _id;}
8.65 + public:
8.66 + Edge() {}
8.67 + Edge (Invalid) { id = -1; }
8.68 + bool operator==(const Edge i) const {return id==i.id;}
8.69 + bool operator!=(const Edge i) const {return id!=i.id;}
8.70 + bool operator<(const Edge i) const {return id<i.id;}
8.71 + };
8.72 +
8.73 + void firstUpper(Node& node) const {
8.74 + node.id = 2 * upperNodes.size() - 2;
8.75 + if (node.id < 0) node.id = -1;
8.76 + }
8.77 + void nextUpper(Node& node) const {
8.78 + node.id -= 2;
8.79 + if (node.id < 0) node.id = -1;
8.80 + }
8.81 +
8.82 + void firstLower(Node& node) const {
8.83 + node.id = 2 * lowerNodes.size() - 1;
8.84 + }
8.85 + void nextLower(Node& node) const {
8.86 + node.id -= 2;
8.87 + }
8.88 +
8.89 + void first(Node& node) const {
8.90 + if (upperNodes.size() > 0) {
8.91 + node.id = 2 * upperNodes.size() - 2;
8.92 + } else {
8.93 + node.id = 2 * lowerNodes.size() - 1;
8.94 + }
8.95 + }
8.96 + void next(Node& node) const {
8.97 + node.id -= 2;
8.98 + if (node.id == -2) {
8.99 + node.id = 2 * lowerNodes.size() - 1;
8.100 + }
8.101 + }
8.102 +
8.103 + void first(Edge& edge) const {
8.104 + edge.id = edges.size() - 1;
8.105 + }
8.106 + void next(Edge& edge) const {
8.107 + --edge.id;
8.108 + }
8.109 +
8.110 + void firstDown(Edge& edge, const Node& node) const {
8.111 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
8.112 + edge.id = upperNodes[node.id >> 1].first;
8.113 + }
8.114 + void nextDown(Edge& edge) const {
8.115 + edge.id = edges[edge.id].next_down;
8.116 + }
8.117 +
8.118 + void firstUp(Edge& edge, const Node& node) const {
8.119 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
8.120 + edge.id = lowerNodes[node.id >> 1].first;
8.121 + }
8.122 + void nextUp(Edge& edge) const {
8.123 + edge.id = edges[edge.id].next_up;
8.124 + }
8.125 +
8.126 + static int id(const Node& node) {
8.127 + return node.id;
8.128 + }
8.129 + static Node nodeFromId(int id) {
8.130 + return Node(id);
8.131 + }
8.132 + int maxNodeId() const {
8.133 + return upperNodes.size() > lowerNodes.size() ?
8.134 + upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
8.135 + }
8.136 +
8.137 + static int id(const Edge& edge) {
8.138 + return edge.id;
8.139 + }
8.140 + static Edge edgeFromId(int id) {
8.141 + return Edge(id);
8.142 + }
8.143 + int maxEdgeId() const {
8.144 + return edges.size();
8.145 + }
8.146 +
8.147 + static int upperId(const Node& node) {
8.148 + return node.id >> 1;
8.149 + }
8.150 + static Node fromUpperId(int id, Node) {
8.151 + return Node(id << 1);
8.152 + }
8.153 + int maxUpperId() const {
8.154 + return upperNodes.size();
8.155 + }
8.156 +
8.157 + static int lowerId(const Node& node) {
8.158 + return node.id >> 1;
8.159 + }
8.160 + static Node fromLowerId(int id) {
8.161 + return Node((id << 1) + 1);
8.162 + }
8.163 + int maxLowerId() const {
8.164 + return lowerNodes.size();
8.165 + }
8.166 +
8.167 + Node upperNode(const Edge& edge) const {
8.168 + return Node(edges[edge.id].upper);
8.169 + }
8.170 + Node lowerNode(const Edge& edge) const {
8.171 + return Node(edges[edge.id].lower);
8.172 + }
8.173 +
8.174 + static bool upper(const Node& node) {
8.175 + return (node.id & 1) == 0;
8.176 + }
8.177 +
8.178 + static bool lower(const Node& node) {
8.179 + return (node.id & 1) == 1;
8.180 + }
8.181 +
8.182 + Node addUpperNode() {
8.183 + NodeT nodeT;
8.184 + nodeT.first = -1;
8.185 + upperNodes.push_back(nodeT);
8.186 + return Node(upperNodes.size() * 2 - 2);
8.187 + }
8.188 +
8.189 + Node addLowerNode() {
8.190 + NodeT nodeT;
8.191 + nodeT.first = -1;
8.192 + lowerNodes.push_back(nodeT);
8.193 + return Node(lowerNodes.size() * 2 - 1);
8.194 + }
8.195 +
8.196 + Edge addEdge(const Node& source, const Node& target) {
8.197 + LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
8.198 + EdgeT edgeT;
8.199 + if ((source.id & 1) == 0) {
8.200 + edgeT.upper = source.id;
8.201 + edgeT.lower = target.id;
8.202 + } else {
8.203 + edgeT.upper = target.id;
8.204 + edgeT.lower = source.id;
8.205 + }
8.206 + edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
8.207 + upperNodes[edgeT.upper >> 1].first = edges.size();
8.208 + edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
8.209 + lowerNodes[edgeT.lower >> 1].first = edges.size();
8.210 + edges.push_back(edgeT);
8.211 + return Edge(edges.size() - 1);
8.212 + }
8.213 +
8.214 + void clear() {
8.215 + upperNodes.clear();
8.216 + lowerNodes.clear();
8.217 + edges.clear();
8.218 + }
8.219 +
8.220 + };
8.221 +
8.222 +
8.223 + typedef ClearableUndirBipartiteGraphExtender<
8.224 + ExtendableUndirBipartiteGraphExtender<
8.225 + MappableUndirBipartiteGraphExtender<
8.226 + IterableUndirBipartiteGraphExtender<
8.227 + AlterableUndirBipartiteGraphExtender<
8.228 + UndirBipartiteGraphExtender <
8.229 + SmartUndirBipartiteGraphBase> > > > > >
8.230 + ExtendedSmartUndirBipartiteGraphBase;
8.231 +
8.232 +
8.233 + class SmartUndirBipartiteGraph :
8.234 + public ExtendedSmartUndirBipartiteGraphBase {
8.235 + };
8.236 +
8.237
8.238 /// @}
8.239 } //namespace lemon