Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/smart_graph.h
- Timestamp:
- 06/30/06 14:15:45 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/smart_graph.h
r2115 r2116 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief SmartGraph class.24 ///\brief SmartGraph and SmartUGraph classes. 25 25 26 26 #include <vector> … … 28 28 #include <lemon/bits/invalid.h> 29 29 30 #include <lemon/bits/base_extender.h> 30 31 #include <lemon/bits/graph_extender.h> 31 32 32 33 #include <lemon/bits/utility.h> 34 #include <lemon/error.h> 33 35 34 36 #include <lemon/bits/graph_extender.h> … … 355 357 356 358 359 /**************** Undirected List Graph ****************/ 360 361 typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> > 362 ExtendedSmartUGraphBase; 363 364 /// \ingroup graphs 365 /// 366 /// \brief A smart undirected graph class. 367 /// 368 /// This is a simple and fast undirected graph implementation. 369 /// It is also quite memory efficient, but at the price 370 /// that <b> it does support only limited (only stack-like) 371 /// node and edge deletions</b>. 372 /// Except from this it conforms to 373 /// the \ref concept::UGraph "UGraph" concept. 374 /// \sa concept::UGraph. 375 /// 376 /// \todo Snapshot hasn't been implemented yet. 377 /// 378 class SmartUGraph : public ExtendedSmartUGraphBase { 379 }; 380 381 382 class SmartBpUGraphBase { 383 public: 384 385 class NodeSetError : public LogicError { 386 virtual const char* exceptionName() const { 387 return "lemon::SmartBpUGraph::NodeSetError"; 388 } 389 }; 390 391 protected: 392 393 struct NodeT { 394 int first; 395 NodeT() {} 396 NodeT(int _first) : first(_first) {} 397 }; 398 399 struct UEdgeT { 400 int aNode, next_out; 401 int bNode, next_in; 402 }; 403 404 std::vector<NodeT> aNodes; 405 std::vector<NodeT> bNodes; 406 407 std::vector<UEdgeT> edges; 408 409 public: 410 411 class Node { 412 friend class SmartBpUGraphBase; 413 protected: 414 int id; 415 416 Node(int _id) : id(_id) {} 417 public: 418 Node() {} 419 Node(Invalid) { id = -1; } 420 bool operator==(const Node i) const {return id==i.id;} 421 bool operator!=(const Node i) const {return id!=i.id;} 422 bool operator<(const Node i) const {return id<i.id;} 423 }; 424 425 class UEdge { 426 friend class SmartBpUGraphBase; 427 protected: 428 int id; 429 430 UEdge(int _id) { id = _id;} 431 public: 432 UEdge() {} 433 UEdge (Invalid) { id = -1; } 434 bool operator==(const UEdge i) const {return id==i.id;} 435 bool operator!=(const UEdge i) const {return id!=i.id;} 436 bool operator<(const UEdge i) const {return id<i.id;} 437 }; 438 439 void firstANode(Node& node) const { 440 node.id = 2 * aNodes.size() - 2; 441 if (node.id < 0) node.id = -1; 442 } 443 void nextANode(Node& node) const { 444 node.id -= 2; 445 if (node.id < 0) node.id = -1; 446 } 447 448 void firstBNode(Node& node) const { 449 node.id = 2 * bNodes.size() - 1; 450 } 451 void nextBNode(Node& node) const { 452 node.id -= 2; 453 } 454 455 void first(Node& node) const { 456 if (aNodes.size() > 0) { 457 node.id = 2 * aNodes.size() - 2; 458 } else { 459 node.id = 2 * bNodes.size() - 1; 460 } 461 } 462 void next(Node& node) const { 463 node.id -= 2; 464 if (node.id == -2) { 465 node.id = 2 * bNodes.size() - 1; 466 } 467 } 468 469 void first(UEdge& edge) const { 470 edge.id = edges.size() - 1; 471 } 472 void next(UEdge& edge) const { 473 --edge.id; 474 } 475 476 void firstFromANode(UEdge& edge, const Node& node) const { 477 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 478 edge.id = aNodes[node.id >> 1].first; 479 } 480 void nextFromANode(UEdge& edge) const { 481 edge.id = edges[edge.id].next_out; 482 } 483 484 void firstFromBNode(UEdge& edge, const Node& node) const { 485 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 486 edge.id = bNodes[node.id >> 1].first; 487 } 488 void nextFromBNode(UEdge& edge) const { 489 edge.id = edges[edge.id].next_in; 490 } 491 492 static int id(const Node& node) { 493 return node.id; 494 } 495 static Node nodeFromId(int id) { 496 return Node(id); 497 } 498 int maxNodeId() const { 499 return aNodes.size() > bNodes.size() ? 500 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; 501 } 502 503 static int id(const UEdge& edge) { 504 return edge.id; 505 } 506 static UEdge uEdgeFromId(int id) { 507 return UEdge(id); 508 } 509 int maxUEdgeId() const { 510 return edges.size(); 511 } 512 513 static int aNodeId(const Node& node) { 514 return node.id >> 1; 515 } 516 static Node fromANodeId(int id) { 517 return Node(id << 1); 518 } 519 int maxANodeId() const { 520 return aNodes.size(); 521 } 522 523 static int bNodeId(const Node& node) { 524 return node.id >> 1; 525 } 526 static Node fromBNodeId(int id) { 527 return Node((id << 1) + 1); 528 } 529 int maxBNodeId() const { 530 return bNodes.size(); 531 } 532 533 Node aNode(const UEdge& edge) const { 534 return Node(edges[edge.id].aNode); 535 } 536 Node bNode(const UEdge& edge) const { 537 return Node(edges[edge.id].bNode); 538 } 539 540 static bool aNode(const Node& node) { 541 return (node.id & 1) == 0; 542 } 543 544 static bool bNode(const Node& node) { 545 return (node.id & 1) == 1; 546 } 547 548 Node addANode() { 549 NodeT nodeT; 550 nodeT.first = -1; 551 aNodes.push_back(nodeT); 552 return Node(aNodes.size() * 2 - 2); 553 } 554 555 Node addBNode() { 556 NodeT nodeT; 557 nodeT.first = -1; 558 bNodes.push_back(nodeT); 559 return Node(bNodes.size() * 2 - 1); 560 } 561 562 UEdge addEdge(const Node& source, const Node& target) { 563 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); 564 UEdgeT edgeT; 565 if ((source.id & 1) == 0) { 566 edgeT.aNode = source.id; 567 edgeT.bNode = target.id; 568 } else { 569 edgeT.aNode = target.id; 570 edgeT.bNode = source.id; 571 } 572 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; 573 aNodes[edgeT.aNode >> 1].first = edges.size(); 574 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; 575 bNodes[edgeT.bNode >> 1].first = edges.size(); 576 edges.push_back(edgeT); 577 return UEdge(edges.size() - 1); 578 } 579 580 void clear() { 581 aNodes.clear(); 582 bNodes.clear(); 583 edges.clear(); 584 } 585 586 typedef True NodeNumTag; 587 int nodeNum() const { return aNodes.size() + bNodes.size(); } 588 int aNodeNum() const { return aNodes.size(); } 589 int bNodeNum() const { return bNodes.size(); } 590 591 typedef True EdgeNumTag; 592 int uEdgeNum() const { return edges.size(); } 593 594 }; 595 596 597 typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase; 598 599 /// \ingroup graphs 600 /// 601 /// \brief A smart bipartite undirected graph class. 602 /// 603 /// This is a simple and fast bipartite undirected graph implementation. 604 /// It is also quite memory efficient, but at the price 605 /// that <b> it does not support node and edge deletions</b>. 606 /// Except from this it conforms to 607 /// the \ref concept::BpUGraph "BpUGraph" concept. 608 /// \sa concept::BpUGraph. 609 /// 610 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; 611 612 613 /// @} 357 614 } //namespace lemon 358 615
Note: See TracChangeset
for help on using the changeset viewer.