1.1 --- a/lemon/full_graph.h Mon Nov 21 12:07:05 2005 +0000
1.2 +++ b/lemon/full_graph.h Mon Nov 21 17:48:00 2005 +0000
1.3 @@ -402,6 +402,196 @@
1.4 UndirFullGraph(int n) { construct(n); }
1.5 };
1.6
1.7 +
1.8 + class FullUndirBipartiteGraphBase {
1.9 + protected:
1.10 +
1.11 + int _upperNodeNum;
1.12 + int _lowerNodeNum;
1.13 +
1.14 + int _edgeNum;
1.15 +
1.16 + public:
1.17 +
1.18 + class NodeSetError : public LogicError {
1.19 + virtual const char* exceptionName() const {
1.20 + return "lemon::FullUndirBipartiteGraph::NodeSetError";
1.21 + }
1.22 + };
1.23 +
1.24 + class Node {
1.25 + friend class FullUndirBipartiteGraphBase;
1.26 + protected:
1.27 + int id;
1.28 +
1.29 + Node(int _id) : id(_id) {}
1.30 + public:
1.31 + Node() {}
1.32 + Node(Invalid) { id = -1; }
1.33 + bool operator==(const Node i) const {return id==i.id;}
1.34 + bool operator!=(const Node i) const {return id!=i.id;}
1.35 + bool operator<(const Node i) const {return id<i.id;}
1.36 + };
1.37 +
1.38 + class Edge {
1.39 + friend class FullUndirBipartiteGraphBase;
1.40 + protected:
1.41 + int id;
1.42 +
1.43 + Edge(int _id) { id = _id;}
1.44 + public:
1.45 + Edge() {}
1.46 + Edge (Invalid) { id = -1; }
1.47 + bool operator==(const Edge i) const {return id==i.id;}
1.48 + bool operator!=(const Edge i) const {return id!=i.id;}
1.49 + bool operator<(const Edge i) const {return id<i.id;}
1.50 + };
1.51 +
1.52 + void construct(int upperNodeNum, int lowerNodeNum) {
1.53 + _upperNodeNum = upperNodeNum;
1.54 + _lowerNodeNum = lowerNodeNum;
1.55 + _edgeNum = upperNodeNum * lowerNodeNum;
1.56 + }
1.57 +
1.58 + void firstUpper(Node& node) const {
1.59 + node.id = 2 * _upperNodeNum - 2;
1.60 + if (node.id < 0) node.id = -1;
1.61 + }
1.62 + void nextUpper(Node& node) const {
1.63 + node.id -= 2;
1.64 + if (node.id < 0) node.id = -1;
1.65 + }
1.66 +
1.67 + void firstLower(Node& node) const {
1.68 + node.id = 2 * _lowerNodeNum - 1;
1.69 + }
1.70 + void nextLower(Node& node) const {
1.71 + node.id -= 2;
1.72 + }
1.73 +
1.74 + void first(Node& node) const {
1.75 + if (_upperNodeNum > 0) {
1.76 + node.id = 2 * _upperNodeNum - 2;
1.77 + } else {
1.78 + node.id = 2 * _lowerNodeNum - 1;
1.79 + }
1.80 + }
1.81 + void next(Node& node) const {
1.82 + node.id -= 2;
1.83 + if (node.id == -2) {
1.84 + node.id = 2 * _lowerNodeNum - 1;
1.85 + }
1.86 + }
1.87 +
1.88 + void first(Edge& edge) const {
1.89 + edge.id = _edgeNum - 1;
1.90 + }
1.91 + void next(Edge& edge) const {
1.92 + --edge.id;
1.93 + }
1.94 +
1.95 + void firstDown(Edge& edge, const Node& node) const {
1.96 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1.97 + edge.id = (node.id >> 1) * _lowerNodeNum;
1.98 + }
1.99 + void nextDown(Edge& edge) const {
1.100 + ++(edge.id);
1.101 + if (edge.id % _lowerNodeNum == 0) edge.id = -1;
1.102 + }
1.103 +
1.104 + void firstUp(Edge& edge, const Node& node) const {
1.105 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1.106 + edge.id = (node.id >> 1);
1.107 + }
1.108 + void nextUp(Edge& edge) const {
1.109 + edge.id += _lowerNodeNum;
1.110 + if (edge.id >= _edgeNum) edge.id = -1;
1.111 + }
1.112 +
1.113 + static int id(const Node& node) {
1.114 + return node.id;
1.115 + }
1.116 + static Node nodeFromId(int id) {
1.117 + return Node(id);
1.118 + }
1.119 + int maxNodeId() const {
1.120 + return _upperNodeNum > _lowerNodeNum ?
1.121 + _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
1.122 + }
1.123 +
1.124 + static int id(const Edge& edge) {
1.125 + return edge.id;
1.126 + }
1.127 + static Edge edgeFromId(int id) {
1.128 + return Edge(id);
1.129 + }
1.130 + int maxEdgeId() const {
1.131 + return _edgeNum - 1;
1.132 + }
1.133 +
1.134 + static int upperId(const Node& node) {
1.135 + return node.id >> 1;
1.136 + }
1.137 + static Node fromUpperId(int id, Node) {
1.138 + return Node(id << 1);
1.139 + }
1.140 + int maxUpperId() const {
1.141 + return _upperNodeNum;
1.142 + }
1.143 +
1.144 + static int lowerId(const Node& node) {
1.145 + return node.id >> 1;
1.146 + }
1.147 + static Node fromLowerId(int id) {
1.148 + return Node((id << 1) + 1);
1.149 + }
1.150 + int maxLowerId() const {
1.151 + return _lowerNodeNum;
1.152 + }
1.153 +
1.154 + Node upperNode(const Edge& edge) const {
1.155 + return Node((edge.id / _lowerNodeNum) << 1);
1.156 + }
1.157 + Node lowerNode(const Edge& edge) const {
1.158 + return Node(((edge.id % _lowerNodeNum) << 1) + 1);
1.159 + }
1.160 +
1.161 + static bool upper(const Node& node) {
1.162 + return (node.id & 1) == 0;
1.163 + }
1.164 +
1.165 + static bool lower(const Node& node) {
1.166 + return (node.id & 1) == 1;
1.167 + }
1.168 +
1.169 + static Node upperNode(int index) {
1.170 + return Node(index << 1);
1.171 + }
1.172 +
1.173 + static Node lowerNode(int index) {
1.174 + return Node((index << 1) + 1);
1.175 + }
1.176 +
1.177 + };
1.178 +
1.179 +
1.180 + typedef MappableUndirBipartiteGraphExtender<
1.181 + IterableUndirBipartiteGraphExtender<
1.182 + AlterableUndirBipartiteGraphExtender<
1.183 + UndirBipartiteGraphExtender <
1.184 + FullUndirBipartiteGraphBase> > > >
1.185 + ExtendedFullUndirBipartiteGraphBase;
1.186 +
1.187 +
1.188 + class FullUndirBipartiteGraph :
1.189 + public ExtendedFullUndirBipartiteGraphBase {
1.190 + public:
1.191 + typedef ExtendedFullUndirBipartiteGraphBase Parent;
1.192 + FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
1.193 + Parent::construct(upperNodeNum, lowerNodeNum);
1.194 + }
1.195 + };
1.196 +
1.197 } //namespace lemon
1.198
1.199