COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_bpugraph.h @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 13 years ago

Splitted graph files

File size: 6.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_FULL_BPUGRAPH_H
20#define LEMON_FULL_BPUGRAPH_H
21
22#include <cmath>
23
24#include <lemon/bits/bpugraph_extender.h>
25
26#include <lemon/bits/invalid.h>
27#include <lemon/bits/utility.h>
28
29
30///\ingroup graphs
31///\file
32///\brief FullBpUGraph class.
33
34
35namespace lemon {
36
37  class FullBpUGraphBase {
38  protected:
39
40    int _aNodeNum;
41    int _bNodeNum;
42
43    int _edgeNum;
44
45  public:
46
47    class NodeSetError : public LogicError {
48      virtual const char* exceptionName() const {
49        return "lemon::FullBpUGraph::NodeSetError";
50      }
51    };
52 
53    class Node {
54      friend class FullBpUGraphBase;
55    protected:
56      int id;
57
58      Node(int _id) : id(_id) {}
59    public:
60      Node() {}
61      Node(Invalid) { id = -1; }
62      bool operator==(const Node i) const {return id==i.id;}
63      bool operator!=(const Node i) const {return id!=i.id;}
64      bool operator<(const Node i) const {return id<i.id;}
65    };
66
67    class UEdge {
68      friend class FullBpUGraphBase;
69    protected:
70      int id;
71
72      UEdge(int _id) { id = _id;}
73    public:
74      UEdge() {}
75      UEdge (Invalid) { id = -1; }
76      bool operator==(const UEdge i) const {return id==i.id;}
77      bool operator!=(const UEdge i) const {return id!=i.id;}
78      bool operator<(const UEdge i) const {return id<i.id;}
79    };
80
81    void construct(int aNodeNum, int bNodeNum) {
82      _aNodeNum = aNodeNum;
83      _bNodeNum = bNodeNum;
84      _edgeNum = aNodeNum * bNodeNum;
85    }
86
87    void firstANode(Node& node) const {
88      node.id = 2 * _aNodeNum - 2;
89      if (node.id < 0) node.id = -1;
90    }
91    void nextANode(Node& node) const {
92      node.id -= 2;
93      if (node.id < 0) node.id = -1;
94    }
95
96    void firstBNode(Node& node) const {
97      node.id = 2 * _bNodeNum - 1;
98    }
99    void nextBNode(Node& node) const {
100      node.id -= 2;
101    }
102
103    void first(Node& node) const {
104      if (_aNodeNum > 0) {
105        node.id = 2 * _aNodeNum - 2;
106      } else {
107        node.id = 2 * _bNodeNum - 1;
108      }
109    }
110    void next(Node& node) const {
111      node.id -= 2;
112      if (node.id == -2) {
113        node.id = 2 * _bNodeNum - 1;
114      }
115    }
116 
117    void first(UEdge& edge) const {
118      edge.id = _edgeNum - 1;
119    }
120    void next(UEdge& edge) const {
121      --edge.id;
122    }
123
124    void firstFromANode(UEdge& edge, const Node& node) const {
125      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
126      edge.id = (node.id >> 1) * _bNodeNum;
127    }
128    void nextFromANode(UEdge& edge) const {
129      ++(edge.id);
130      if (edge.id % _bNodeNum == 0) edge.id = -1;
131    }
132
133    void firstFromBNode(UEdge& edge, const Node& node) const {
134      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
135      edge.id = (node.id >> 1);
136    }
137    void nextFromBNode(UEdge& edge) const {
138      edge.id += _bNodeNum;
139      if (edge.id >= _edgeNum) edge.id = -1;
140    }
141
142    static int id(const Node& node) {
143      return node.id;
144    }
145    static Node nodeFromId(int id) {
146      return Node(id);
147    }
148    int maxNodeId() const {
149      return _aNodeNum > _bNodeNum ?
150        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
151    }
152 
153    static int id(const UEdge& edge) {
154      return edge.id;
155    }
156    static UEdge uEdgeFromId(int id) {
157      return UEdge(id);
158    }
159    int maxUEdgeId() const {
160      return _edgeNum - 1;
161    }
162 
163    static int aNodeId(const Node& node) {
164      return node.id >> 1;
165    }
166    static Node fromANodeId(int id) {
167      return Node(id << 1);
168    }
169    int maxANodeId() const {
170      return _aNodeNum;
171    }
172
173    static int bNodeId(const Node& node) {
174      return node.id >> 1;
175    }
176    static Node fromBNodeId(int id) {
177      return Node((id << 1) + 1);
178    }
179    int maxBNodeId() const {
180      return _bNodeNum;
181    }
182
183    Node aNode(const UEdge& edge) const {
184      return Node((edge.id / _bNodeNum) << 1);
185    }
186    Node bNode(const UEdge& edge) const {
187      return Node(((edge.id % _bNodeNum) << 1) + 1);
188    }
189
190    static bool aNode(const Node& node) {
191      return (node.id & 1) == 0;
192    }
193
194    static bool bNode(const Node& node) {
195      return (node.id & 1) == 1;
196    }
197
198    static Node aNode(int index) {
199      return Node(index << 1);
200    }
201
202    static Node bNode(int index) {
203      return Node((index << 1) + 1);
204    }
205
206    typedef True NodeNumTag;
207    int nodeNum() const { return _aNodeNum + _bNodeNum; }
208    int aNodeNum() const { return _aNodeNum; }
209    int bNodeNum() const { return _bNodeNum; }
210
211    typedef True EdgeNumTag;
212    int uEdgeNum() const { return _edgeNum; }
213
214  };
215
216
217  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
218
219
220  /// \ingroup graphs
221  ///
222  /// \brief An undirected full bipartite graph class.
223  ///
224  /// This is a simple and fast bipartite undirected full graph implementation.
225  /// It is completely static, so you can neither add nor delete either
226  /// edges or nodes.
227  ///
228  /// \sa FullUGraphBase
229  /// \sa FullGraph
230  ///
231  /// \author Balazs Dezso
232  class FullBpUGraph :
233    public ExtendedFullBpUGraphBase {
234  public:
235
236    typedef ExtendedFullBpUGraphBase Parent;
237
238    FullBpUGraph() {
239      Parent::construct(0, 0);
240    }
241
242    FullBpUGraph(int aNodeNum, int bNodeNum) {
243      Parent::construct(aNodeNum, bNodeNum);
244    }
245
246    /// \brief Resize the graph
247    ///
248    void resize(int n, int m) {
249      Parent::getNotifier(Edge()).clear();
250      Parent::getNotifier(UEdge()).clear();
251      Parent::getNotifier(Node()).clear();
252      Parent::getNotifier(ANode()).clear();
253      Parent::getNotifier(BNode()).clear();
254      construct(n, m);
255      Parent::getNotifier(ANode()).build();
256      Parent::getNotifier(BNode()).build();
257      Parent::getNotifier(Node()).build();
258      Parent::getNotifier(UEdge()).build();
259      Parent::getNotifier(Edge()).build();
260    }
261  };
262
263} //namespace lemon
264
265
266#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.