364 } |
364 } |
365 }; |
365 }; |
366 }; |
366 }; |
367 |
367 |
368 |
368 |
369 /**************** Undirected List Graph ****************/ |
369 class SmartUGraphBase { |
370 |
370 |
371 typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> > |
371 protected: |
372 ExtendedSmartUGraphBase; |
372 |
|
373 struct NodeT { |
|
374 int first_out; |
|
375 }; |
|
376 |
|
377 struct EdgeT { |
|
378 int target; |
|
379 int next_out; |
|
380 }; |
|
381 |
|
382 std::vector<NodeT> nodes; |
|
383 std::vector<EdgeT> edges; |
|
384 |
|
385 int first_free_edge; |
|
386 |
|
387 public: |
|
388 |
|
389 typedef SmartUGraphBase Graph; |
|
390 |
|
391 class Node { |
|
392 friend class SmartUGraphBase; |
|
393 protected: |
|
394 |
|
395 int id; |
|
396 explicit Node(int pid) { id = pid;} |
|
397 |
|
398 public: |
|
399 Node() {} |
|
400 Node (Invalid) { id = -1; } |
|
401 bool operator==(const Node& node) const {return id == node.id;} |
|
402 bool operator!=(const Node& node) const {return id != node.id;} |
|
403 bool operator<(const Node& node) const {return id < node.id;} |
|
404 }; |
|
405 |
|
406 class UEdge { |
|
407 friend class SmartUGraphBase; |
|
408 protected: |
|
409 |
|
410 int id; |
|
411 explicit UEdge(int pid) { id = pid;} |
|
412 |
|
413 public: |
|
414 UEdge() {} |
|
415 UEdge (Invalid) { id = -1; } |
|
416 bool operator==(const UEdge& edge) const {return id == edge.id;} |
|
417 bool operator!=(const UEdge& edge) const {return id != edge.id;} |
|
418 bool operator<(const UEdge& edge) const {return id < edge.id;} |
|
419 }; |
|
420 |
|
421 class Edge { |
|
422 friend class SmartUGraphBase; |
|
423 protected: |
|
424 |
|
425 int id; |
|
426 explicit Edge(int pid) { id = pid;} |
|
427 |
|
428 public: |
|
429 operator UEdge() const { return UEdge(id / 2); } |
|
430 |
|
431 Edge() {} |
|
432 Edge (Invalid) { id = -1; } |
|
433 bool operator==(const Edge& edge) const {return id == edge.id;} |
|
434 bool operator!=(const Edge& edge) const {return id != edge.id;} |
|
435 bool operator<(const Edge& edge) const {return id < edge.id;} |
|
436 }; |
|
437 |
|
438 |
|
439 |
|
440 SmartUGraphBase() |
|
441 : nodes(), edges() {} |
|
442 |
|
443 |
|
444 int maxNodeId() const { return nodes.size()-1; } |
|
445 int maxUEdgeId() const { return edges.size() / 2 - 1; } |
|
446 int maxEdgeId() const { return edges.size()-1; } |
|
447 |
|
448 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); } |
|
449 Node target(Edge e) const { return Node(edges[e.id].target); } |
|
450 |
|
451 Node source(UEdge e) const { return Node(edges[2 * e.id].target); } |
|
452 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); } |
|
453 |
|
454 static bool direction(Edge e) { |
|
455 return (e.id & 1) == 1; |
|
456 } |
|
457 |
|
458 static Edge direct(UEdge e, bool d) { |
|
459 return Edge(e.id * 2 + (d ? 1 : 0)); |
|
460 } |
|
461 |
|
462 void first(Node& node) const { |
|
463 node.id = nodes.size() - 1; |
|
464 } |
|
465 |
|
466 void next(Node& node) const { |
|
467 --node.id; |
|
468 } |
|
469 |
|
470 void first(Edge& edge) const { |
|
471 edge.id = edges.size() - 1; |
|
472 } |
|
473 |
|
474 void next(Edge& edge) const { |
|
475 --edge.id; |
|
476 } |
|
477 |
|
478 void first(UEdge& edge) const { |
|
479 edge.id = edges.size() / 2 - 1; |
|
480 } |
|
481 |
|
482 void next(UEdge& edge) const { |
|
483 --edge.id; |
|
484 } |
|
485 |
|
486 void firstOut(Edge &edge, const Node& v) const { |
|
487 edge.id = nodes[v.id].first_out; |
|
488 } |
|
489 void nextOut(Edge &edge) const { |
|
490 edge.id = edges[edge.id].next_out; |
|
491 } |
|
492 |
|
493 void firstIn(Edge &edge, const Node& v) const { |
|
494 edge.id = ((nodes[v.id].first_out) ^ 1); |
|
495 if (e.id == -2) e.id = -1; |
|
496 } |
|
497 void nextIn(Edge &edge) const { |
|
498 edge.id = ((edges[edge.id ^ 1].next_out) ^ 1); |
|
499 if (e.id == -2) e.id = -1; |
|
500 } |
|
501 |
|
502 void firstInc(UEdge &edge, bool& d, const Node& v) const { |
|
503 int de = nodes[v.id].first_out; |
|
504 edge.id = de / 2; |
|
505 d = ((de & 1) == 1); |
|
506 } |
|
507 void nextInc(UEdge &edge, bool& d) const { |
|
508 int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out); |
|
509 edge.id = de / 2; |
|
510 d = ((de & 1) == 1); |
|
511 } |
|
512 |
|
513 static int id(Node v) { return v.id; } |
|
514 static int id(Edge e) { return e.id; } |
|
515 static int id(UEdge e) { return e.id; } |
|
516 |
|
517 static Node nodeFromId(int id) { return Node(id);} |
|
518 static Edge edgeFromId(int id) { return Edge(id);} |
|
519 static UEdge uEdgeFromId(int id) { return UEdge(id);} |
|
520 |
|
521 Node addNode() { |
|
522 int n = nodes.size(); |
|
523 nodes.push_back(NodeT()); |
|
524 nodes[n].first_out = -1; |
|
525 |
|
526 return Node(n); |
|
527 } |
|
528 |
|
529 UEdge addEdge(Node u, Node v) { |
|
530 int n = edges.size(); |
|
531 edges.push_back(EdgeT()); |
|
532 edges.push_back(EdgeT()); |
|
533 |
|
534 edges[n].target = u.id; |
|
535 edges[n | 1].target = v.id; |
|
536 |
|
537 edges[n].next_out = nodes[v.id].first_out; |
|
538 edges[n | 1].next_out = nodes[u.id].first_out; |
|
539 |
|
540 nodes[v.id].first_out = n; |
|
541 nodes[u.id].first_out = (n | 1); |
|
542 |
|
543 return UEdge(n / 2); |
|
544 } |
|
545 |
|
546 void clear() { |
|
547 edges.clear(); |
|
548 nodes.clear(); |
|
549 } |
|
550 |
|
551 }; |
|
552 |
|
553 typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase; |
373 |
554 |
374 /// \ingroup graphs |
555 /// \ingroup graphs |
375 /// |
556 /// |
376 /// \brief A smart undirected graph class. |
557 /// \brief A smart undirected graph class. |
377 /// |
558 /// |
441 |
623 |
442 class Snapshot; |
624 class Snapshot; |
443 |
625 |
444 protected: |
626 protected: |
445 |
627 |
|
628 void saveSnapshot(Snapshot &s) |
|
629 { |
|
630 s.g = this; |
|
631 s.node_num = nodes.size(); |
|
632 s.edge_num = edges.size(); |
|
633 } |
446 |
634 |
447 void restoreSnapshot(const Snapshot &s) |
635 void restoreSnapshot(const Snapshot &s) |
448 { |
636 { |
449 while(s.edge_num<edges.size()) { |
637 while(s.edge_num<edges.size()) { |
450 UEdge edge = uEdgeFromId(edges.size()-1); |
638 int n=edges.size()-1; |
|
639 UEdge edge=uEdgeFromId(n/2); |
451 Parent::getNotifier(UEdge()).erase(edge); |
640 Parent::getNotifier(UEdge()).erase(edge); |
452 std::vector<Edge> dir; |
641 std::vector<Edge> dir; |
453 dir.push_back(Parent::direct(edge, true)); |
642 dir.push_back(edgeFromId(n)); |
454 dir.push_back(Parent::direct(edge, false)); |
643 dir.push_back(edgeFromId(n-1)); |
455 Parent::getNotifier(Edge()).erase(dir); |
644 Parent::getNotifier(Edge()).erase(dir); |
456 nodes[edges.back().source].first_out=edges.back().next_out; |
645 nodes[edges[n].target].first_out=edges[n].next_out; |
457 nodes[edges.back().target].first_in=edges.back().next_in; |
646 nodes[edges[n-1].target].first_out=edges[n-1].next_out; |
458 edges.pop_back(); |
647 edges.pop_back(); |
|
648 edges.pop_back(); |
459 } |
649 } |
460 while(s.node_num<nodes.size()) { |
650 while(s.node_num<nodes.size()) { |
461 Node node = nodeFromId(nodes.size()-1); |
651 int n=nodes.size()-1; |
|
652 Node node = nodeFromId(n); |
462 Parent::getNotifier(Node()).erase(node); |
653 Parent::getNotifier(Node()).erase(node); |
463 nodes.pop_back(); |
654 nodes.pop_back(); |
464 } |
655 } |
465 } |
656 } |
466 |
657 |
497 Snapshot() : g(0) {} |
688 Snapshot() : g(0) {} |
498 ///Constructor that immediately makes a snapshot |
689 ///Constructor that immediately makes a snapshot |
499 |
690 |
500 ///This constructor immediately makes a snapshot of the graph. |
691 ///This constructor immediately makes a snapshot of the graph. |
501 ///\param _g The graph we make a snapshot of. |
692 ///\param _g The graph we make a snapshot of. |
502 Snapshot(SmartUGraph &_g) :g(&_g) { |
693 Snapshot(SmartUGraph &g) { |
503 node_num=g->nodes.size(); |
694 g.saveSnapshot(*this); |
504 edge_num=g->edges.size(); |
|
505 } |
695 } |
506 |
696 |
507 ///Make a snapshot. |
697 ///Make a snapshot. |
508 |
698 |
509 ///Make a snapshot of the graph. |
699 ///Make a snapshot of the graph. |
510 /// |
700 /// |
511 ///This function can be called more than once. In case of a repeated |
701 ///This function can be called more than once. In case of a repeated |
512 ///call, the previous snapshot gets lost. |
702 ///call, the previous snapshot gets lost. |
513 ///\param _g The graph we make the snapshot of. |
703 ///\param _g The graph we make the snapshot of. |
514 void save(SmartUGraph &_g) |
704 void save(SmartUGraph &g) |
515 { |
705 { |
516 g=&_g; |
706 g.saveSnapshot(*this); |
517 node_num=g->nodes.size(); |
|
518 edge_num=g->edges.size(); |
|
519 } |
707 } |
520 |
708 |
521 ///Undo the changes until a snapshot. |
709 ///Undo the changes until a snapshot. |
522 |
710 |
523 ///Undo the changes until a snapshot created by save(). |
711 ///Undo the changes until a snapshot created by save(). |