1.1 --- a/lemon/full_graph.h Fri Sep 29 11:23:54 2006 +0000
1.2 +++ b/lemon/full_graph.h Fri Sep 29 11:25:27 2006 +0000
1.3 @@ -35,9 +35,6 @@
1.4
1.5 namespace lemon {
1.6
1.7 - /// \brief Base of the FullGrpah.
1.8 - ///
1.9 - /// Base of the FullGrpah.
1.10 class FullGraphBase {
1.11 int _nodeNum;
1.12 int _edgeNum;
1.13 @@ -48,71 +45,35 @@
1.14 class Node;
1.15 class Edge;
1.16
1.17 - public:
1.18 + protected:
1.19
1.20 FullGraphBase() {}
1.21
1.22 + void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
1.23
1.24 - ///Creates a full graph with \c n nodes.
1.25 - void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
1.26 + public:
1.27
1.28 typedef True NodeNumTag;
1.29 typedef True EdgeNumTag;
1.30
1.31 - /// \brief Returns the node with the given index.
1.32 - ///
1.33 - /// Returns the node with the given index. Because it is a
1.34 - /// static size graph the node's of the graph can be indiced
1.35 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.36 - /// the node can accessed by the \e index() member.
1.37 Node operator()(int index) const { return Node(index); }
1.38 -
1.39 - /// \brief Returns the index of the node.
1.40 - ///
1.41 - /// Returns the index of the node. Because it is a
1.42 - /// static size graph the node's of the graph can be indiced
1.43 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.44 - /// the node can accessed by the \e index() member.
1.45 int index(const Node& node) const { return node.id; }
1.46
1.47 - ///Number of nodes.
1.48 + Edge edge(const Node& u, const Node& v) const {
1.49 + return Edge(*this, u.id, v.id);
1.50 + }
1.51 +
1.52 int nodeNum() const { return _nodeNum; }
1.53 - ///Number of edges.
1.54 int edgeNum() const { return _edgeNum; }
1.55
1.56 - /// Maximum node ID.
1.57 -
1.58 - /// Maximum node ID.
1.59 - ///\sa id(Node)
1.60 int maxNodeId() const { return _nodeNum-1; }
1.61 - /// Maximum edge ID.
1.62 -
1.63 - /// Maximum edge ID.
1.64 - ///\sa id(Edge)
1.65 int maxEdgeId() const { return _edgeNum-1; }
1.66
1.67 Node source(Edge e) const { return e.id % _nodeNum; }
1.68 Node target(Edge e) const { return e.id / _nodeNum; }
1.69
1.70
1.71 - /// Node ID.
1.72 -
1.73 - /// The ID of a valid Node is a nonnegative integer not greater than
1.74 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.75 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.76 - ///
1.77 - /// The ID of the \ref INVALID node is -1.
1.78 - ///\return The ID of the node \c v.
1.79 -
1.80 static int id(Node v) { return v.id; }
1.81 - /// Edge ID.
1.82 -
1.83 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.84 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.85 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.86 - ///
1.87 - /// The ID of the \ref INVALID edge is -1.
1.88 - ///\return The ID of the edge \c e.
1.89 static int id(Edge e) { return e.id; }
1.90
1.91 static Node nodeFromId(int id) { return Node(id);}
1.92 @@ -121,14 +82,6 @@
1.93
1.94 typedef True FindEdgeTag;
1.95
1.96 - /// Finds an edge between two nodes.
1.97 -
1.98 - /// Finds an edge from node \c u to node \c v.
1.99 - ///
1.100 - /// If \c prev is \ref INVALID (this is the default value), then
1.101 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.102 - /// the next edge from \c u to \c v after \c prev.
1.103 - /// \return The found edge or INVALID if there is no such an edge.
1.104 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
1.105 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
1.106 }
1.107 @@ -217,7 +170,6 @@
1.108 /// the \ref concept::Graph "Graph" concept
1.109 /// \sa concept::Graph.
1.110 ///
1.111 - /// \sa FullGraphBase
1.112 /// \sa FullUGraph
1.113 ///
1.114 /// \author Alpar Juttner
1.115 @@ -245,12 +197,37 @@
1.116 Parent::getNotifier(Node()).build();
1.117 Parent::getNotifier(Edge()).build();
1.118 }
1.119 +
1.120 + /// \brief Returns the node with the given index.
1.121 + ///
1.122 + /// Returns the node with the given index. Because it is a
1.123 + /// static size graph the node's of the graph can be indiced
1.124 + /// by the range from 0 to \e nodeNum()-1 and the index of
1.125 + /// the node can accessed by the \e index() member.
1.126 + Node operator()(int index) const { return Parent::operator()(index); }
1.127 +
1.128 + /// \brief Returns the index of the node.
1.129 + ///
1.130 + /// Returns the index of the node. Because it is a
1.131 + /// static size graph the node's of the graph can be indiced
1.132 + /// by the range from 0 to \e nodeNum()-1 and the index of
1.133 + /// the node can accessed by the \e index() member.
1.134 + int index(const Node& node) const { return Parent::index(node); }
1.135 +
1.136 + /// \brief Returns the edge connects the given nodes.
1.137 + ///
1.138 + /// Returns the edge connects the given nodes.
1.139 + Edge edge(const Node& u, const Node& v) const {
1.140 + return Parent::edge(u, v);
1.141 + }
1.142 +
1.143 + /// \brief Number of nodes.
1.144 + int nodeNum() const { return Parent::nodeNum(); }
1.145 + /// \brief Number of edges.
1.146 + int edgeNum() const { return Parent::edgeNum(); }
1.147 };
1.148
1.149
1.150 - /// \brief Base of the FullUGrpah.
1.151 - ///
1.152 - /// Base of the FullUGrpah.
1.153 class FullUGraphBase {
1.154 int _nodeNum;
1.155 int _edgeNum;
1.156 @@ -261,59 +238,32 @@
1.157 class Node;
1.158 class Edge;
1.159
1.160 - public:
1.161 + protected:
1.162
1.163 FullUGraphBase() {}
1.164
1.165 -
1.166 - ///Creates a full graph with \c n nodes.
1.167 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
1.168
1.169 - /// \brief Returns the node with the given index.
1.170 - ///
1.171 - /// Returns the node with the given index. Because it is a
1.172 - /// static size graph the node's of the graph can be indiced
1.173 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.174 - /// the node can accessed by the \e index() member.
1.175 + public:
1.176 +
1.177 +
1.178 Node operator()(int index) const { return Node(index); }
1.179 + int index(const Node& node) const { return node.id; }
1.180
1.181 - /// \brief Returns the index of the node.
1.182 - ///
1.183 - /// Returns the index of the node. Because it is a
1.184 - /// static size graph the node's of the graph can be indiced
1.185 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.186 - /// the node can accessed by the \e index() member.
1.187 - int index(const Node& node) const { return node.id; }
1.188 + Edge edge(const Node& u, const Node& v) const {
1.189 + return Edge(u.id * (u.id - 1) / 2 + v.id);
1.190 + }
1.191
1.192 typedef True NodeNumTag;
1.193 typedef True EdgeNumTag;
1.194
1.195 - ///Number of nodes.
1.196 int nodeNum() const { return _nodeNum; }
1.197 - ///Number of edges.
1.198 int edgeNum() const { return _edgeNum; }
1.199
1.200 - /// Maximum node ID.
1.201 -
1.202 - /// Maximum node ID.
1.203 - ///\sa id(Node)
1.204 int maxNodeId() const { return _nodeNum-1; }
1.205 - /// Maximum edge ID.
1.206 -
1.207 - /// Maximum edge ID.
1.208 - ///\sa id(Edge)
1.209 int maxEdgeId() const { return _edgeNum-1; }
1.210
1.211 - /// \brief Returns the node from its \c id.
1.212 - ///
1.213 - /// Returns the node from its \c id. If there is not node
1.214 - /// with the given id the effect of the function is undefinied.
1.215 static Node nodeFromId(int id) { return Node(id);}
1.216 -
1.217 - /// \brief Returns the edge from its \c id.
1.218 - ///
1.219 - /// Returns the edge from its \c id. If there is not edge
1.220 - /// with the given id the effect of the function is undefinied.
1.221 static Edge edgeFromId(int id) { return Edge(id);}
1.222
1.223 Node source(Edge e) const {
1.224 @@ -326,36 +276,9 @@
1.225 return Node(e.id - (source) * (source - 1) / 2);
1.226 }
1.227
1.228 -
1.229 - /// \brief Node ID.
1.230 - ///
1.231 - /// The ID of a valid Node is a nonnegative integer not greater than
1.232 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.233 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.234 - ///
1.235 - /// The ID of the \ref INVALID node is -1.
1.236 - /// \return The ID of the node \c v.
1.237 -
1.238 static int id(Node v) { return v.id; }
1.239 -
1.240 - /// \brief Edge ID.
1.241 - ///
1.242 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.243 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.244 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.245 - ///
1.246 - /// The ID of the \ref INVALID edge is -1.
1.247 - ///\return The ID of the edge \c e.
1.248 static int id(Edge e) { return e.id; }
1.249
1.250 - /// \brief Finds an edge between two nodes.
1.251 - ///
1.252 - /// Finds an edge from node \c u to node \c v.
1.253 - ///
1.254 - /// If \c prev is \ref INVALID (this is the default value), then
1.255 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.256 - /// the next edge from \c u to \c v after \c prev.
1.257 - /// \return The found edge or INVALID if there is no such an edge.
1.258 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.259 if (prev.id != -1 || u.id <= v.id) return Edge(-1);
1.260 return Edge(u.id * (u.id - 1) / 2 + v.id);
1.261 @@ -456,7 +379,6 @@
1.262 /// is that this class conforms to the undirected graph concept and
1.263 /// it does not contain the loop edges.
1.264 ///
1.265 - /// \sa FullUGraphBase
1.266 /// \sa FullGraph
1.267 ///
1.268 /// \author Balazs Dezso
1.269 @@ -485,6 +407,55 @@
1.270 Parent::getNotifier(UEdge()).build();
1.271 Parent::getNotifier(Edge()).build();
1.272 }
1.273 +
1.274 + /// \brief Returns the node with the given index.
1.275 + ///
1.276 + /// Returns the node with the given index. Because it is a
1.277 + /// static size graph the node's of the graph can be indiced
1.278 + /// by the range from 0 to \e nodeNum()-1 and the index of
1.279 + /// the node can accessed by the \e index() member.
1.280 + Node operator()(int index) const { return Parent::operator()(index); }
1.281 +
1.282 + /// \brief Returns the index of the node.
1.283 + ///
1.284 + /// Returns the index of the node. Because it is a
1.285 + /// static size graph the node's of the graph can be indiced
1.286 + /// by the range from 0 to \e nodeNum()-1 and the index of
1.287 + /// the node can accessed by the \e index() member.
1.288 + int index(const Node& node) const { return Parent::index(node); }
1.289 +
1.290 + /// \brief Number of nodes.
1.291 + int nodeNum() const { return Parent::nodeNum(); }
1.292 + /// \brief Number of edges.
1.293 + int edgeNum() const { return Parent::edgeNum(); }
1.294 + /// \brief Number of undirected edges.
1.295 + int uEdgeNum() const { return Parent::uEdgeNum(); }
1.296 +
1.297 + /// \brief Returns the edge connects the given nodes.
1.298 + ///
1.299 + /// Returns the edge connects the given nodes.
1.300 + Edge edge(const Node& u, const Node& v) const {
1.301 + if (Parent::index(u) > Parent::index(v)) {
1.302 + return Parent::direct(Parent::edge(u, v), true);
1.303 + } else if (Parent::index(u) == Parent::index(v)) {
1.304 + return INVALID;
1.305 + } else {
1.306 + return Parent::direct(Parent::edge(v, u), false);
1.307 + }
1.308 + }
1.309 +
1.310 + /// \brief Returns the undirected edge connects the given nodes.
1.311 + ///
1.312 + /// Returns the undirected edge connects the given nodes.
1.313 + UEdge uEdge(const Node& u, const Node& v) const {
1.314 + if (Parent::index(u) > Parent::index(v)) {
1.315 + return Parent::edge(u, v);
1.316 + } else if (Parent::index(u) == Parent::index(v)) {
1.317 + return INVALID;
1.318 + } else {
1.319 + return Parent::edge(v, u);
1.320 + }
1.321 + }
1.322 };
1.323
1.324
1.325 @@ -496,6 +467,16 @@
1.326
1.327 int _edgeNum;
1.328
1.329 + protected:
1.330 +
1.331 + FullBpUGraphBase() {}
1.332 +
1.333 + void construct(int aNodeNum, int bNodeNum) {
1.334 + _aNodeNum = aNodeNum;
1.335 + _bNodeNum = bNodeNum;
1.336 + _edgeNum = aNodeNum * bNodeNum;
1.337 + }
1.338 +
1.339 public:
1.340
1.341 class NodeSetError : public LogicError {
1.342 @@ -533,10 +514,20 @@
1.343 bool operator<(const UEdge i) const {return id<i.id;}
1.344 };
1.345
1.346 - void construct(int aNodeNum, int bNodeNum) {
1.347 - _aNodeNum = aNodeNum;
1.348 - _bNodeNum = bNodeNum;
1.349 - _edgeNum = aNodeNum * bNodeNum;
1.350 + Node aNode(int index) const { return Node(index << 1); }
1.351 + Node bNode(int index) const { return Node((index << 1) + 1); }
1.352 +
1.353 + int aNodeIndex(const Node& node) const { return node.id >> 1; }
1.354 + int bNodeIndex(const Node& node) const { return node.id >> 1; }
1.355 +
1.356 + UEdge uEdge(const Node& u, const Node& v) const {
1.357 + if (((u.id ^ v.id) & 1) != 1) {
1.358 + return UEdge(-1);
1.359 + } else if ((u.id & 1) == 0) {
1.360 + return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
1.361 + } else {
1.362 + return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
1.363 + }
1.364 }
1.365
1.366 void firstANode(Node& node) const {
1.367 @@ -650,13 +641,6 @@
1.368 return (node.id & 1) == 1;
1.369 }
1.370
1.371 - static Node aNode(int index) {
1.372 - return Node(index << 1);
1.373 - }
1.374 -
1.375 - static Node bNode(int index) {
1.376 - return Node((index << 1) + 1);
1.377 - }
1.378
1.379 typedef True NodeNumTag;
1.380 int nodeNum() const { return _aNodeNum + _bNodeNum; }
1.381 @@ -666,6 +650,18 @@
1.382 typedef True EdgeNumTag;
1.383 int uEdgeNum() const { return _edgeNum; }
1.384
1.385 +
1.386 + typedef True FindEdgeTag;
1.387 + UEdge findUEdge(Node u, Node v, UEdge prev = INVALID) const {
1.388 + if (prev.id != -1 || ((u.id ^ v.id) & 1) != 1) {
1.389 + return UEdge(-1);
1.390 + } else if ((u.id & 1) == 0) {
1.391 + return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
1.392 + } else {
1.393 + return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
1.394 + }
1.395 + }
1.396 +
1.397 };
1.398
1.399
1.400 @@ -680,9 +676,6 @@
1.401 /// It is completely static, so you can neither add nor delete either
1.402 /// edges or nodes.
1.403 ///
1.404 - /// \sa FullUGraphBase
1.405 - /// \sa FullGraph
1.406 - ///
1.407 /// \author Balazs Dezso
1.408 class FullBpUGraph :
1.409 public ExtendedFullBpUGraphBase {
1.410 @@ -700,6 +693,7 @@
1.411
1.412 /// \brief Resize the graph
1.413 ///
1.414 + /// Resize the graph
1.415 void resize(int n, int m) {
1.416 Parent::getNotifier(Edge()).clear();
1.417 Parent::getNotifier(UEdge()).clear();
1.418 @@ -713,6 +707,72 @@
1.419 Parent::getNotifier(UEdge()).build();
1.420 Parent::getNotifier(Edge()).build();
1.421 }
1.422 +
1.423 + /// \brief Number of nodes.
1.424 + int nodeNum() const { return Parent::nodeNum(); }
1.425 + /// \brief Number of A-nodes.
1.426 + int aNodeNum() const { return Parent::aNodeNum(); }
1.427 + /// \brief Number of B-nodes.
1.428 + int bNodeNum() const { return Parent::bNodeNum(); }
1.429 + /// \brief Number of edges.
1.430 + int edgeNum() const { return Parent::edgeNum(); }
1.431 + /// \brief Number of undirected edges.
1.432 + int uEdgeNum() const { return Parent::uEdgeNum(); }
1.433 +
1.434 +
1.435 + using Parent::aNode;
1.436 + using Parent::bNode;
1.437 +
1.438 + /// \brief Returns the A-node with the given index.
1.439 + ///
1.440 + /// Returns the A-node with the given index. Because it is a
1.441 + /// static size graph the node's of the graph can be indiced
1.442 + /// by the range from 0 to \e aNodeNum()-1 and the index of
1.443 + /// the node can accessed by the \e aNodeIndex() member.
1.444 + Node aNode(int index) const { return Parent::aNode(index); }
1.445 +
1.446 + /// \brief Returns the B-node with the given index.
1.447 + ///
1.448 + /// Returns the B-node with the given index. Because it is a
1.449 + /// static size graph the node's of the graph can be indiced
1.450 + /// by the range from 0 to \e bNodeNum()-1 and the index of
1.451 + /// the node can accessed by the \e bNodeIndex() member.
1.452 + Node bNode(int index) const { return Parent::bNode(index); }
1.453 +
1.454 + /// \brief Returns the index of the A-node.
1.455 + ///
1.456 + /// Returns the index of the A-node. Because it is a
1.457 + /// static size graph the node's of the graph can be indiced
1.458 + /// by the range from 0 to \e aNodeNum()-1 and the index of
1.459 + /// the node can accessed by the \e aNodeIndex() member.
1.460 + int aNodeIndex(const Node& node) const { return Parent::aNodeIndex(node); }
1.461 +
1.462 + /// \brief Returns the index of the B-node.
1.463 + ///
1.464 + /// Returns the index of the B-node. Because it is a
1.465 + /// static size graph the node's of the graph can be indiced
1.466 + /// by the range from 0 to \e bNodeNum()-1 and the index of
1.467 + /// the node can accessed by the \e bNodeIndex() member.
1.468 + int bNodeIndex(const Node& node) const { return Parent::bNodeIndex(node); }
1.469 +
1.470 + /// \brief Returns the edge connects the given nodes.
1.471 + ///
1.472 + /// Returns the edge connects the given nodes.
1.473 + Edge edge(const Node& u, const Node& v) const {
1.474 + UEdge uedge = Parent::uEdge(u, v);
1.475 + if (uedge != INVALID) {
1.476 + return Parent::direct(uedge, Parent::aNode(u));
1.477 + } else {
1.478 + return INVALID;
1.479 + }
1.480 + }
1.481 +
1.482 + /// \brief Returns the undirected edge connects the given nodes.
1.483 + ///
1.484 + /// Returns the undirected edge connects the given nodes.
1.485 + UEdge uEdge(const Node& u, const Node& v) const {
1.486 + return Parent::uEdge(u, v);
1.487 + }
1.488 };
1.489
1.490 } //namespace lemon