Changeset 2115:4cd528a30ec1 in lemon0.x for lemon/smart_graph.h
 Timestamp:
 06/30/06 14:14:36 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2821
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/smart_graph.h
r2111 r2115 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief SmartGraph and SmartUGraph classes.24 ///\brief SmartGraph class. 25 25 26 26 #include <vector> … … 28 28 #include <lemon/bits/invalid.h> 29 29 30 #include <lemon/bits/base_extender.h>31 30 #include <lemon/bits/graph_extender.h> 32 31 33 32 #include <lemon/bits/utility.h> 34 #include <lemon/error.h>35 33 36 34 #include <lemon/bits/graph_extender.h> … … 357 355 358 356 359 /**************** Undirected List Graph ****************/360 361 typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >362 ExtendedSmartUGraphBase;363 364 /// \ingroup graphs365 ///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 price370 /// that <b> it does support only limited (only stacklike)371 /// node and edge deletions</b>.372 /// Except from this it conforms to373 /// 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 graphs600 ///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 price605 /// that <b> it does not support node and edge deletions</b>.606 /// Except from this it conforms to607 /// the \ref concept::BpUGraph "BpUGraph" concept.608 /// \sa concept::BpUGraph.609 ///610 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};611 612 613 /// @}614 357 } //namespace lemon 615 358
Note: See TracChangeset
for help on using the changeset viewer.