1.1 --- a/lemon/full_bpugraph.h Fri Jun 30 12:14:36 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,266 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2006
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_FULL_BPUGRAPH_H
1.23 -#define LEMON_FULL_BPUGRAPH_H
1.24 -
1.25 -#include <cmath>
1.26 -
1.27 -#include <lemon/bits/bpugraph_extender.h>
1.28 -
1.29 -#include <lemon/bits/invalid.h>
1.30 -#include <lemon/bits/utility.h>
1.31 -
1.32 -
1.33 -///\ingroup graphs
1.34 -///\file
1.35 -///\brief FullBpUGraph class.
1.36 -
1.37 -
1.38 -namespace lemon {
1.39 -
1.40 - class FullBpUGraphBase {
1.41 - protected:
1.42 -
1.43 - int _aNodeNum;
1.44 - int _bNodeNum;
1.45 -
1.46 - int _edgeNum;
1.47 -
1.48 - public:
1.49 -
1.50 - class NodeSetError : public LogicError {
1.51 - virtual const char* exceptionName() const {
1.52 - return "lemon::FullBpUGraph::NodeSetError";
1.53 - }
1.54 - };
1.55 -
1.56 - class Node {
1.57 - friend class FullBpUGraphBase;
1.58 - protected:
1.59 - int id;
1.60 -
1.61 - Node(int _id) : id(_id) {}
1.62 - public:
1.63 - Node() {}
1.64 - Node(Invalid) { id = -1; }
1.65 - bool operator==(const Node i) const {return id==i.id;}
1.66 - bool operator!=(const Node i) const {return id!=i.id;}
1.67 - bool operator<(const Node i) const {return id<i.id;}
1.68 - };
1.69 -
1.70 - class UEdge {
1.71 - friend class FullBpUGraphBase;
1.72 - protected:
1.73 - int id;
1.74 -
1.75 - UEdge(int _id) { id = _id;}
1.76 - public:
1.77 - UEdge() {}
1.78 - UEdge (Invalid) { id = -1; }
1.79 - bool operator==(const UEdge i) const {return id==i.id;}
1.80 - bool operator!=(const UEdge i) const {return id!=i.id;}
1.81 - bool operator<(const UEdge i) const {return id<i.id;}
1.82 - };
1.83 -
1.84 - void construct(int aNodeNum, int bNodeNum) {
1.85 - _aNodeNum = aNodeNum;
1.86 - _bNodeNum = bNodeNum;
1.87 - _edgeNum = aNodeNum * bNodeNum;
1.88 - }
1.89 -
1.90 - void firstANode(Node& node) const {
1.91 - node.id = 2 * _aNodeNum - 2;
1.92 - if (node.id < 0) node.id = -1;
1.93 - }
1.94 - void nextANode(Node& node) const {
1.95 - node.id -= 2;
1.96 - if (node.id < 0) node.id = -1;
1.97 - }
1.98 -
1.99 - void firstBNode(Node& node) const {
1.100 - node.id = 2 * _bNodeNum - 1;
1.101 - }
1.102 - void nextBNode(Node& node) const {
1.103 - node.id -= 2;
1.104 - }
1.105 -
1.106 - void first(Node& node) const {
1.107 - if (_aNodeNum > 0) {
1.108 - node.id = 2 * _aNodeNum - 2;
1.109 - } else {
1.110 - node.id = 2 * _bNodeNum - 1;
1.111 - }
1.112 - }
1.113 - void next(Node& node) const {
1.114 - node.id -= 2;
1.115 - if (node.id == -2) {
1.116 - node.id = 2 * _bNodeNum - 1;
1.117 - }
1.118 - }
1.119 -
1.120 - void first(UEdge& edge) const {
1.121 - edge.id = _edgeNum - 1;
1.122 - }
1.123 - void next(UEdge& edge) const {
1.124 - --edge.id;
1.125 - }
1.126 -
1.127 - void firstFromANode(UEdge& edge, const Node& node) const {
1.128 - LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1.129 - edge.id = (node.id >> 1) * _bNodeNum;
1.130 - }
1.131 - void nextFromANode(UEdge& edge) const {
1.132 - ++(edge.id);
1.133 - if (edge.id % _bNodeNum == 0) edge.id = -1;
1.134 - }
1.135 -
1.136 - void firstFromBNode(UEdge& edge, const Node& node) const {
1.137 - LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1.138 - edge.id = (node.id >> 1);
1.139 - }
1.140 - void nextFromBNode(UEdge& edge) const {
1.141 - edge.id += _bNodeNum;
1.142 - if (edge.id >= _edgeNum) edge.id = -1;
1.143 - }
1.144 -
1.145 - static int id(const Node& node) {
1.146 - return node.id;
1.147 - }
1.148 - static Node nodeFromId(int id) {
1.149 - return Node(id);
1.150 - }
1.151 - int maxNodeId() const {
1.152 - return _aNodeNum > _bNodeNum ?
1.153 - _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
1.154 - }
1.155 -
1.156 - static int id(const UEdge& edge) {
1.157 - return edge.id;
1.158 - }
1.159 - static UEdge uEdgeFromId(int id) {
1.160 - return UEdge(id);
1.161 - }
1.162 - int maxUEdgeId() const {
1.163 - return _edgeNum - 1;
1.164 - }
1.165 -
1.166 - static int aNodeId(const Node& node) {
1.167 - return node.id >> 1;
1.168 - }
1.169 - static Node fromANodeId(int id) {
1.170 - return Node(id << 1);
1.171 - }
1.172 - int maxANodeId() const {
1.173 - return _aNodeNum;
1.174 - }
1.175 -
1.176 - static int bNodeId(const Node& node) {
1.177 - return node.id >> 1;
1.178 - }
1.179 - static Node fromBNodeId(int id) {
1.180 - return Node((id << 1) + 1);
1.181 - }
1.182 - int maxBNodeId() const {
1.183 - return _bNodeNum;
1.184 - }
1.185 -
1.186 - Node aNode(const UEdge& edge) const {
1.187 - return Node((edge.id / _bNodeNum) << 1);
1.188 - }
1.189 - Node bNode(const UEdge& edge) const {
1.190 - return Node(((edge.id % _bNodeNum) << 1) + 1);
1.191 - }
1.192 -
1.193 - static bool aNode(const Node& node) {
1.194 - return (node.id & 1) == 0;
1.195 - }
1.196 -
1.197 - static bool bNode(const Node& node) {
1.198 - return (node.id & 1) == 1;
1.199 - }
1.200 -
1.201 - static Node aNode(int index) {
1.202 - return Node(index << 1);
1.203 - }
1.204 -
1.205 - static Node bNode(int index) {
1.206 - return Node((index << 1) + 1);
1.207 - }
1.208 -
1.209 - typedef True NodeNumTag;
1.210 - int nodeNum() const { return _aNodeNum + _bNodeNum; }
1.211 - int aNodeNum() const { return _aNodeNum; }
1.212 - int bNodeNum() const { return _bNodeNum; }
1.213 -
1.214 - typedef True EdgeNumTag;
1.215 - int uEdgeNum() const { return _edgeNum; }
1.216 -
1.217 - };
1.218 -
1.219 -
1.220 - typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
1.221 -
1.222 -
1.223 - /// \ingroup graphs
1.224 - ///
1.225 - /// \brief An undirected full bipartite graph class.
1.226 - ///
1.227 - /// This is a simple and fast bipartite undirected full graph implementation.
1.228 - /// It is completely static, so you can neither add nor delete either
1.229 - /// edges or nodes.
1.230 - ///
1.231 - /// \sa FullUGraphBase
1.232 - /// \sa FullGraph
1.233 - ///
1.234 - /// \author Balazs Dezso
1.235 - class FullBpUGraph :
1.236 - public ExtendedFullBpUGraphBase {
1.237 - public:
1.238 -
1.239 - typedef ExtendedFullBpUGraphBase Parent;
1.240 -
1.241 - FullBpUGraph() {
1.242 - Parent::construct(0, 0);
1.243 - }
1.244 -
1.245 - FullBpUGraph(int aNodeNum, int bNodeNum) {
1.246 - Parent::construct(aNodeNum, bNodeNum);
1.247 - }
1.248 -
1.249 - /// \brief Resize the graph
1.250 - ///
1.251 - void resize(int n, int m) {
1.252 - Parent::getNotifier(Edge()).clear();
1.253 - Parent::getNotifier(UEdge()).clear();
1.254 - Parent::getNotifier(Node()).clear();
1.255 - Parent::getNotifier(ANode()).clear();
1.256 - Parent::getNotifier(BNode()).clear();
1.257 - construct(n, m);
1.258 - Parent::getNotifier(ANode()).build();
1.259 - Parent::getNotifier(BNode()).build();
1.260 - Parent::getNotifier(Node()).build();
1.261 - Parent::getNotifier(UEdge()).build();
1.262 - Parent::getNotifier(Edge()).build();
1.263 - }
1.264 - };
1.265 -
1.266 -} //namespace lemon
1.267 -
1.268 -
1.269 -#endif //LEMON_FULL_GRAPH_H