372 ///\todo Snapshot hasn't been implemented yet. |
373 ///\todo Snapshot hasn't been implemented yet. |
373 /// |
374 /// |
374 class UndirSmartGraph : public ExtendedUndirSmartGraphBase { |
375 class UndirSmartGraph : public ExtendedUndirSmartGraphBase { |
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 /// @} |
379 } //namespace lemon |
602 } //namespace lemon |
380 |
603 |
381 |
604 |