Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/full_graph.h
- Timestamp:
- 06/30/06 14:14:36 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/full_graph.h
r2111 r2115 22 22 #include <cmath> 23 23 24 #include <lemon/bits/base_extender.h>25 24 #include <lemon/bits/graph_extender.h> 26 25 … … 31 30 ///\ingroup graphs 32 31 ///\file 33 ///\brief FullGraph and FullUGraph classes.32 ///\brief FullGraph class. 34 33 35 34 … … 248 247 }; 249 248 250 251 /// \brief Base of the FullUGrpah.252 ///253 /// Base of the FullUGrpah.254 class FullUGraphBase {255 int _nodeNum;256 int _edgeNum;257 public:258 259 typedef FullUGraphBase Graph;260 261 class Node;262 class Edge;263 264 public:265 266 FullUGraphBase() {}267 268 269 ///Creates a full graph with \c n nodes.270 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }271 272 /// \brief Returns the node with the given index.273 ///274 /// Returns the node with the given index. Because it is a275 /// static size graph the node's of the graph can be indiced276 /// by the range from 0 to \e nodeNum()-1 and the index of277 /// the node can accessed by the \e index() member.278 Node operator()(int index) const { return Node(index); }279 280 /// \brief Returns the index of the node.281 ///282 /// Returns the index of the node. Because it is a283 /// static size graph the node's of the graph can be indiced284 /// by the range from 0 to \e nodeNum()-1 and the index of285 /// the node can accessed by the \e index() member.286 int index(const Node& node) const { return node.id; }287 288 typedef True NodeNumTag;289 typedef True EdgeNumTag;290 291 ///Number of nodes.292 int nodeNum() const { return _nodeNum; }293 ///Number of edges.294 int edgeNum() const { return _edgeNum; }295 296 /// Maximum node ID.297 298 /// Maximum node ID.299 ///\sa id(Node)300 int maxNodeId() const { return _nodeNum-1; }301 /// Maximum edge ID.302 303 /// Maximum edge ID.304 ///\sa id(Edge)305 int maxEdgeId() const { return _edgeNum-1; }306 307 /// \brief Returns the node from its \c id.308 ///309 /// Returns the node from its \c id. If there is not node310 /// with the given id the effect of the function is undefinied.311 static Node nodeFromId(int id) { return Node(id);}312 313 /// \brief Returns the edge from its \c id.314 ///315 /// Returns the edge from its \c id. If there is not edge316 /// with the given id the effect of the function is undefinied.317 static Edge edgeFromId(int id) { return Edge(id);}318 319 Node source(Edge e) const {320 /// \todo we may do it faster321 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);322 }323 324 Node target(Edge e) const {325 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;326 return Node(e.id - (source) * (source - 1) / 2);327 }328 329 330 /// \brief Node ID.331 ///332 /// The ID of a valid Node is a nonnegative integer not greater than333 /// \ref maxNodeId(). The range of the ID's is not surely continuous334 /// and the greatest node ID can be actually less then \ref maxNodeId().335 ///336 /// The ID of the \ref INVALID node is -1.337 /// \return The ID of the node \c v.338 339 static int id(Node v) { return v.id; }340 341 /// \brief Edge ID.342 ///343 /// The ID of a valid Edge is a nonnegative integer not greater than344 /// \ref maxEdgeId(). The range of the ID's is not surely continuous345 /// and the greatest edge ID can be actually less then \ref maxEdgeId().346 ///347 /// The ID of the \ref INVALID edge is -1.348 ///\return The ID of the edge \c e.349 static int id(Edge e) { return e.id; }350 351 /// \brief Finds an edge between two nodes.352 ///353 /// Finds an edge from node \c u to node \c v.354 ///355 /// If \c prev is \ref INVALID (this is the default value), then356 /// It finds the first edge from \c u to \c v. Otherwise it looks for357 /// the next edge from \c u to \c v after \c prev.358 /// \return The found edge or INVALID if there is no such an edge.359 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {360 if (prev.id != -1 || u.id <= v.id) return Edge(-1);361 return Edge(u.id * (u.id - 1) / 2 + v.id);362 }363 364 typedef True FindEdgeTag;365 366 367 class Node {368 friend class FullUGraphBase;369 370 protected:371 int id;372 Node(int _id) { id = _id;}373 public:374 Node() {}375 Node (Invalid) { id = -1; }376 bool operator==(const Node node) const {return id == node.id;}377 bool operator!=(const Node node) const {return id != node.id;}378 bool operator<(const Node node) const {return id < node.id;}379 };380 381 382 383 class Edge {384 friend class FullUGraphBase;385 386 protected:387 int id; // _nodeNum * target + source;388 389 Edge(int _id) : id(_id) {}390 391 public:392 Edge() { }393 Edge (Invalid) { id = -1; }394 bool operator==(const Edge edge) const {return id == edge.id;}395 bool operator!=(const Edge edge) const {return id != edge.id;}396 bool operator<(const Edge edge) const {return id < edge.id;}397 };398 399 void first(Node& node) const {400 node.id = _nodeNum - 1;401 }402 403 static void next(Node& node) {404 --node.id;405 }406 407 void first(Edge& edge) const {408 edge.id = _edgeNum - 1;409 }410 411 static void next(Edge& edge) {412 --edge.id;413 }414 415 void firstOut(Edge& edge, const Node& node) const {416 int src = node.id;417 int trg = 0;418 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);419 }420 421 /// \todo with specialized iterators we can make faster iterating422 void nextOut(Edge& edge) const {423 int src = source(edge).id;424 int trg = target(edge).id;425 ++trg;426 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);427 }428 429 void firstIn(Edge& edge, const Node& node) const {430 int src = node.id + 1;431 int trg = node.id;432 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);433 }434 435 void nextIn(Edge& edge) const {436 int src = source(edge).id;437 int trg = target(edge).id;438 ++src;439 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);440 }441 442 };443 444 typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >445 ExtendedFullUGraphBase;446 447 /// \ingroup graphs448 ///449 /// \brief An undirected full graph class.450 ///451 /// This is a simple and fast undirected full graph implementation.452 /// It is completely static, so you can neither add nor delete either453 /// edges or nodes.454 ///455 /// The main difference beetween the \e FullGraph and \e FullUGraph class456 /// is that this class conforms to the undirected graph concept and457 /// it does not contain the loop edges.458 ///459 /// \sa FullUGraphBase460 /// \sa FullGraph461 ///462 /// \author Balazs Dezso463 class FullUGraph : public ExtendedFullUGraphBase {464 public:465 466 typedef ExtendedFullUGraphBase Parent;467 468 /// \brief Constructor469 FullUGraph() { construct(0); }470 471 /// \brief Constructor472 FullUGraph(int n) { construct(n); }473 474 /// \brief Resize the graph475 ///476 /// Resize the graph. The function will fully destroy and build the graph.477 /// This cause that the maps of the graph will reallocated478 /// automatically and the previous values will be lost.479 void resize(int n) {480 Parent::getNotifier(Edge()).clear();481 Parent::getNotifier(UEdge()).clear();482 Parent::getNotifier(Node()).clear();483 construct(n);484 Parent::getNotifier(Node()).build();485 Parent::getNotifier(UEdge()).build();486 Parent::getNotifier(Edge()).build();487 }488 };489 490 491 class FullBpUGraphBase {492 protected:493 494 int _aNodeNum;495 int _bNodeNum;496 497 int _edgeNum;498 499 public:500 501 class NodeSetError : public LogicError {502 virtual const char* exceptionName() const {503 return "lemon::FullBpUGraph::NodeSetError";504 }505 };506 507 class Node {508 friend class FullBpUGraphBase;509 protected:510 int id;511 512 Node(int _id) : id(_id) {}513 public:514 Node() {}515 Node(Invalid) { id = -1; }516 bool operator==(const Node i) const {return id==i.id;}517 bool operator!=(const Node i) const {return id!=i.id;}518 bool operator<(const Node i) const {return id<i.id;}519 };520 521 class UEdge {522 friend class FullBpUGraphBase;523 protected:524 int id;525 526 UEdge(int _id) { id = _id;}527 public:528 UEdge() {}529 UEdge (Invalid) { id = -1; }530 bool operator==(const UEdge i) const {return id==i.id;}531 bool operator!=(const UEdge i) const {return id!=i.id;}532 bool operator<(const UEdge i) const {return id<i.id;}533 };534 535 void construct(int aNodeNum, int bNodeNum) {536 _aNodeNum = aNodeNum;537 _bNodeNum = bNodeNum;538 _edgeNum = aNodeNum * bNodeNum;539 }540 541 void firstANode(Node& node) const {542 node.id = 2 * _aNodeNum - 2;543 if (node.id < 0) node.id = -1;544 }545 void nextANode(Node& node) const {546 node.id -= 2;547 if (node.id < 0) node.id = -1;548 }549 550 void firstBNode(Node& node) const {551 node.id = 2 * _bNodeNum - 1;552 }553 void nextBNode(Node& node) const {554 node.id -= 2;555 }556 557 void first(Node& node) const {558 if (_aNodeNum > 0) {559 node.id = 2 * _aNodeNum - 2;560 } else {561 node.id = 2 * _bNodeNum - 1;562 }563 }564 void next(Node& node) const {565 node.id -= 2;566 if (node.id == -2) {567 node.id = 2 * _bNodeNum - 1;568 }569 }570 571 void first(UEdge& edge) const {572 edge.id = _edgeNum - 1;573 }574 void next(UEdge& edge) const {575 --edge.id;576 }577 578 void firstFromANode(UEdge& edge, const Node& node) const {579 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());580 edge.id = (node.id >> 1) * _bNodeNum;581 }582 void nextFromANode(UEdge& edge) const {583 ++(edge.id);584 if (edge.id % _bNodeNum == 0) edge.id = -1;585 }586 587 void firstFromBNode(UEdge& edge, const Node& node) const {588 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());589 edge.id = (node.id >> 1);590 }591 void nextFromBNode(UEdge& edge) const {592 edge.id += _bNodeNum;593 if (edge.id >= _edgeNum) edge.id = -1;594 }595 596 static int id(const Node& node) {597 return node.id;598 }599 static Node nodeFromId(int id) {600 return Node(id);601 }602 int maxNodeId() const {603 return _aNodeNum > _bNodeNum ?604 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;605 }606 607 static int id(const UEdge& edge) {608 return edge.id;609 }610 static UEdge uEdgeFromId(int id) {611 return UEdge(id);612 }613 int maxUEdgeId() const {614 return _edgeNum - 1;615 }616 617 static int aNodeId(const Node& node) {618 return node.id >> 1;619 }620 static Node fromANodeId(int id) {621 return Node(id << 1);622 }623 int maxANodeId() const {624 return _aNodeNum;625 }626 627 static int bNodeId(const Node& node) {628 return node.id >> 1;629 }630 static Node fromBNodeId(int id) {631 return Node((id << 1) + 1);632 }633 int maxBNodeId() const {634 return _bNodeNum;635 }636 637 Node aNode(const UEdge& edge) const {638 return Node((edge.id / _bNodeNum) << 1);639 }640 Node bNode(const UEdge& edge) const {641 return Node(((edge.id % _bNodeNum) << 1) + 1);642 }643 644 static bool aNode(const Node& node) {645 return (node.id & 1) == 0;646 }647 648 static bool bNode(const Node& node) {649 return (node.id & 1) == 1;650 }651 652 static Node aNode(int index) {653 return Node(index << 1);654 }655 656 static Node bNode(int index) {657 return Node((index << 1) + 1);658 }659 660 typedef True NodeNumTag;661 int nodeNum() const { return _aNodeNum + _bNodeNum; }662 int aNodeNum() const { return _aNodeNum; }663 int bNodeNum() const { return _bNodeNum; }664 665 typedef True EdgeNumTag;666 int uEdgeNum() const { return _edgeNum; }667 668 };669 670 671 typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;672 673 674 /// \ingroup graphs675 ///676 /// \brief An undirected full bipartite graph class.677 ///678 /// This is a simple and fast bipartite undirected full graph implementation.679 /// It is completely static, so you can neither add nor delete either680 /// edges or nodes.681 ///682 /// \sa FullUGraphBase683 /// \sa FullGraph684 ///685 /// \author Balazs Dezso686 class FullBpUGraph :687 public ExtendedFullBpUGraphBase {688 public:689 690 typedef ExtendedFullBpUGraphBase Parent;691 692 FullBpUGraph() {693 Parent::construct(0, 0);694 }695 696 FullBpUGraph(int aNodeNum, int bNodeNum) {697 Parent::construct(aNodeNum, bNodeNum);698 }699 700 /// \brief Resize the graph701 ///702 void resize(int n, int m) {703 Parent::getNotifier(Edge()).clear();704 Parent::getNotifier(UEdge()).clear();705 Parent::getNotifier(Node()).clear();706 Parent::getNotifier(ANode()).clear();707 Parent::getNotifier(BNode()).clear();708 construct(n, m);709 Parent::getNotifier(ANode()).build();710 Parent::getNotifier(BNode()).build();711 Parent::getNotifier(Node()).build();712 Parent::getNotifier(UEdge()).build();713 Parent::getNotifier(Edge()).build();714 }715 };716 717 249 } //namespace lemon 718 250
Note: See TracChangeset
for help on using the changeset viewer.