352 } |
354 } |
353 }; |
355 }; |
354 }; |
356 }; |
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 } //namespace lemon |
614 } //namespace lemon |
358 |
615 |
359 |
616 |
360 #endif //LEMON_SMART_GRAPH_H |
617 #endif //LEMON_SMART_GRAPH_H |