Changeset 1820:22099ef840d7 in lemon0.x for lemon/smart_graph.h
 Timestamp:
 11/21/05 18:48:00 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2370
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/smart_graph.h
r1791 r1820 34 34 35 35 #include <lemon/utility.h> 36 #include <lemon/error.h> 36 37 37 38 namespace lemon { … … 375 376 }; 376 377 378 379 class SmartUndirBipartiteGraphBase { 380 public: 381 382 class NodeSetError : public LogicError { 383 virtual const char* exceptionName() const { 384 return "lemon::FullUndirBipartiteGraph::NodeSetError"; 385 } 386 }; 387 388 protected: 389 390 struct NodeT { 391 int first; 392 NodeT() {} 393 NodeT(int _first) : first(_first) {} 394 }; 395 396 struct EdgeT { 397 int upper, next_down; 398 int lower, next_up; 399 }; 400 401 std::vector<NodeT> upperNodes; 402 std::vector<NodeT> lowerNodes; 403 404 std::vector<EdgeT> edges; 405 406 public: 407 408 class Node { 409 friend class SmartUndirBipartiteGraphBase; 410 protected: 411 int id; 412 413 Node(int _id) : id(_id) {} 414 public: 415 Node() {} 416 Node(Invalid) { id = 1; } 417 bool operator==(const Node i) const {return id==i.id;} 418 bool operator!=(const Node i) const {return id!=i.id;} 419 bool operator<(const Node i) const {return id<i.id;} 420 }; 421 422 class Edge { 423 friend class SmartUndirBipartiteGraphBase; 424 protected: 425 int id; 426 427 Edge(int _id) { id = _id;} 428 public: 429 Edge() {} 430 Edge (Invalid) { id = 1; } 431 bool operator==(const Edge i) const {return id==i.id;} 432 bool operator!=(const Edge i) const {return id!=i.id;} 433 bool operator<(const Edge i) const {return id<i.id;} 434 }; 435 436 void firstUpper(Node& node) const { 437 node.id = 2 * upperNodes.size()  2; 438 if (node.id < 0) node.id = 1; 439 } 440 void nextUpper(Node& node) const { 441 node.id = 2; 442 if (node.id < 0) node.id = 1; 443 } 444 445 void firstLower(Node& node) const { 446 node.id = 2 * lowerNodes.size()  1; 447 } 448 void nextLower(Node& node) const { 449 node.id = 2; 450 } 451 452 void first(Node& node) const { 453 if (upperNodes.size() > 0) { 454 node.id = 2 * upperNodes.size()  2; 455 } else { 456 node.id = 2 * lowerNodes.size()  1; 457 } 458 } 459 void next(Node& node) const { 460 node.id = 2; 461 if (node.id == 2) { 462 node.id = 2 * lowerNodes.size()  1; 463 } 464 } 465 466 void first(Edge& edge) const { 467 edge.id = edges.size()  1; 468 } 469 void next(Edge& edge) const { 470 edge.id; 471 } 472 473 void firstDown(Edge& edge, const Node& node) const { 474 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 475 edge.id = upperNodes[node.id >> 1].first; 476 } 477 void nextDown(Edge& edge) const { 478 edge.id = edges[edge.id].next_down; 479 } 480 481 void firstUp(Edge& edge, const Node& node) const { 482 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 483 edge.id = lowerNodes[node.id >> 1].first; 484 } 485 void nextUp(Edge& edge) const { 486 edge.id = edges[edge.id].next_up; 487 } 488 489 static int id(const Node& node) { 490 return node.id; 491 } 492 static Node nodeFromId(int id) { 493 return Node(id); 494 } 495 int maxNodeId() const { 496 return upperNodes.size() > lowerNodes.size() ? 497 upperNodes.size() * 2  2 : lowerNodes.size() * 2  1; 498 } 499 500 static int id(const Edge& edge) { 501 return edge.id; 502 } 503 static Edge edgeFromId(int id) { 504 return Edge(id); 505 } 506 int maxEdgeId() const { 507 return edges.size(); 508 } 509 510 static int upperId(const Node& node) { 511 return node.id >> 1; 512 } 513 static Node fromUpperId(int id, Node) { 514 return Node(id << 1); 515 } 516 int maxUpperId() const { 517 return upperNodes.size(); 518 } 519 520 static int lowerId(const Node& node) { 521 return node.id >> 1; 522 } 523 static Node fromLowerId(int id) { 524 return Node((id << 1) + 1); 525 } 526 int maxLowerId() const { 527 return lowerNodes.size(); 528 } 529 530 Node upperNode(const Edge& edge) const { 531 return Node(edges[edge.id].upper); 532 } 533 Node lowerNode(const Edge& edge) const { 534 return Node(edges[edge.id].lower); 535 } 536 537 static bool upper(const Node& node) { 538 return (node.id & 1) == 0; 539 } 540 541 static bool lower(const Node& node) { 542 return (node.id & 1) == 1; 543 } 544 545 Node addUpperNode() { 546 NodeT nodeT; 547 nodeT.first = 1; 548 upperNodes.push_back(nodeT); 549 return Node(upperNodes.size() * 2  2); 550 } 551 552 Node addLowerNode() { 553 NodeT nodeT; 554 nodeT.first = 1; 555 lowerNodes.push_back(nodeT); 556 return Node(lowerNodes.size() * 2  1); 557 } 558 559 Edge addEdge(const Node& source, const Node& target) { 560 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); 561 EdgeT edgeT; 562 if ((source.id & 1) == 0) { 563 edgeT.upper = source.id; 564 edgeT.lower = target.id; 565 } else { 566 edgeT.upper = target.id; 567 edgeT.lower = source.id; 568 } 569 edgeT.next_down = upperNodes[edgeT.upper >> 1].first; 570 upperNodes[edgeT.upper >> 1].first = edges.size(); 571 edgeT.next_up = lowerNodes[edgeT.lower >> 1].first; 572 lowerNodes[edgeT.lower >> 1].first = edges.size(); 573 edges.push_back(edgeT); 574 return Edge(edges.size()  1); 575 } 576 577 void clear() { 578 upperNodes.clear(); 579 lowerNodes.clear(); 580 edges.clear(); 581 } 582 583 }; 584 585 586 typedef ClearableUndirBipartiteGraphExtender< 587 ExtendableUndirBipartiteGraphExtender< 588 MappableUndirBipartiteGraphExtender< 589 IterableUndirBipartiteGraphExtender< 590 AlterableUndirBipartiteGraphExtender< 591 UndirBipartiteGraphExtender < 592 SmartUndirBipartiteGraphBase> > > > > > 593 ExtendedSmartUndirBipartiteGraphBase; 594 595 596 class SmartUndirBipartiteGraph : 597 public ExtendedSmartUndirBipartiteGraphBase { 598 }; 599 377 600 378 601 /// @}
Note: See TracChangeset
for help on using the changeset viewer.