Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/list_ugraph.h
- Timestamp:
- 06/30/06 14:14:36 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
- File:
-
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_ugraph.h
r2114 r2115 17 17 */ 18 18 19 #ifndef LEMON_LIST_ GRAPH_H20 #define LEMON_LIST_ GRAPH_H19 #ifndef LEMON_LIST_UGRAPH_H 20 #define LEMON_LIST_UGRAPH_H 21 21 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief List Graph, ListUGraph classes.24 ///\brief ListUGraph classes. 25 25 26 #include <lemon/list_graph.h> 26 27 #include <lemon/bits/base_extender.h> 27 #include <lemon/bits/graph_extender.h> 28 29 #include <lemon/error.h> 28 #include <lemon/bits/ugraph_extender.h> 30 29 31 30 #include <vector> … … 34 33 namespace lemon { 35 34 36 class ListGraphBase {37 38 protected:39 struct NodeT {40 int first_in, first_out;41 int prev, next;42 };43 44 struct EdgeT {45 int target, source;46 int prev_in, prev_out;47 int next_in, next_out;48 };49 50 std::vector<NodeT> nodes;51 52 int first_node;53 54 int first_free_node;55 56 std::vector<EdgeT> edges;57 58 int first_free_edge;59 60 public:61 62 typedef ListGraphBase Graph;63 64 class Node {65 friend class ListGraphBase;66 protected:67 68 int id;69 explicit Node(int pid) { id = pid;}70 71 public:72 Node() {}73 Node (Invalid) { id = -1; }74 bool operator==(const Node& node) const {return id == node.id;}75 bool operator!=(const Node& node) const {return id != node.id;}76 bool operator<(const Node& node) const {return id < node.id;}77 };78 79 class Edge {80 friend class ListGraphBase;81 protected:82 83 int id;84 explicit Edge(int pid) { id = pid;}85 86 public:87 Edge() {}88 Edge (Invalid) { id = -1; }89 bool operator==(const Edge& edge) const {return id == edge.id;}90 bool operator!=(const Edge& edge) const {return id != edge.id;}91 bool operator<(const Edge& edge) const {return id < edge.id;}92 };93 94 95 96 ListGraphBase()97 : nodes(), first_node(-1),98 first_free_node(-1), edges(), first_free_edge(-1) {}99 100 101 /// Maximum node ID.102 103 /// Maximum node ID.104 ///\sa id(Node)105 int maxNodeId() const { return nodes.size()-1; }106 107 /// Maximum edge ID.108 109 /// Maximum edge ID.110 ///\sa id(Edge)111 int maxEdgeId() const { return edges.size()-1; }112 113 Node source(Edge e) const { return Node(edges[e.id].source); }114 Node target(Edge e) const { return Node(edges[e.id].target); }115 116 117 void first(Node& node) const {118 node.id = first_node;119 }120 121 void next(Node& node) const {122 node.id = nodes[node.id].next;123 }124 125 126 void first(Edge& e) const {127 int n;128 for(n = first_node;129 n!=-1 && nodes[n].first_in == -1;130 n = nodes[n].next);131 e.id = (n == -1) ? -1 : nodes[n].first_in;132 }133 134 void next(Edge& edge) const {135 if (edges[edge.id].next_in != -1) {136 edge.id = edges[edge.id].next_in;137 } else {138 int n;139 for(n = nodes[edges[edge.id].target].next;140 n!=-1 && nodes[n].first_in == -1;141 n = nodes[n].next);142 edge.id = (n == -1) ? -1 : nodes[n].first_in;143 }144 }145 146 void firstOut(Edge &e, const Node& v) const {147 e.id = nodes[v.id].first_out;148 }149 void nextOut(Edge &e) const {150 e.id=edges[e.id].next_out;151 }152 153 void firstIn(Edge &e, const Node& v) const {154 e.id = nodes[v.id].first_in;155 }156 void nextIn(Edge &e) const {157 e.id=edges[e.id].next_in;158 }159 160 161 static int id(Node v) { return v.id; }162 static int id(Edge e) { return e.id; }163 164 static Node nodeFromId(int id) { return Node(id);}165 static Edge edgeFromId(int id) { return Edge(id);}166 167 /// Adds a new node to the graph.168 169 /// \warning It adds the new node to the front of the list.170 /// (i.e. the lastly added node becomes the first.)171 Node addNode() {172 int n;173 174 if(first_free_node==-1) {175 n = nodes.size();176 nodes.push_back(NodeT());177 } else {178 n = first_free_node;179 first_free_node = nodes[n].next;180 }181 182 nodes[n].next = first_node;183 if(first_node != -1) nodes[first_node].prev = n;184 first_node = n;185 nodes[n].prev = -1;186 187 nodes[n].first_in = nodes[n].first_out = -1;188 189 return Node(n);190 }191 192 Edge addEdge(Node u, Node v) {193 int n;194 195 if (first_free_edge == -1) {196 n = edges.size();197 edges.push_back(EdgeT());198 } else {199 n = first_free_edge;200 first_free_edge = edges[n].next_in;201 }202 203 edges[n].source = u.id;204 edges[n].target = v.id;205 206 edges[n].next_out = nodes[u.id].first_out;207 if(nodes[u.id].first_out != -1) {208 edges[nodes[u.id].first_out].prev_out = n;209 }210 211 edges[n].next_in = nodes[v.id].first_in;212 if(nodes[v.id].first_in != -1) {213 edges[nodes[v.id].first_in].prev_in = n;214 }215 216 edges[n].prev_in = edges[n].prev_out = -1;217 218 nodes[u.id].first_out = nodes[v.id].first_in = n;219 220 return Edge(n);221 }222 223 void erase(const Node& node) {224 int n = node.id;225 226 if(nodes[n].next != -1) {227 nodes[nodes[n].next].prev = nodes[n].prev;228 }229 230 if(nodes[n].prev != -1) {231 nodes[nodes[n].prev].next = nodes[n].next;232 } else {233 first_node = nodes[n].next;234 }235 236 nodes[n].next = first_free_node;237 first_free_node = n;238 239 }240 241 void erase(const Edge& edge) {242 int n = edge.id;243 244 if(edges[n].next_in!=-1) {245 edges[edges[n].next_in].prev_in = edges[n].prev_in;246 }247 248 if(edges[n].prev_in!=-1) {249 edges[edges[n].prev_in].next_in = edges[n].next_in;250 } else {251 nodes[edges[n].target].first_in = edges[n].next_in;252 }253 254 255 if(edges[n].next_out!=-1) {256 edges[edges[n].next_out].prev_out = edges[n].prev_out;257 }258 259 if(edges[n].prev_out!=-1) {260 edges[edges[n].prev_out].next_out = edges[n].next_out;261 } else {262 nodes[edges[n].source].first_out = edges[n].next_out;263 }264 265 edges[n].next_in = first_free_edge;266 first_free_edge = n;267 268 }269 270 void clear() {271 edges.clear();272 nodes.clear();273 first_node = first_free_node = first_free_edge = -1;274 }275 276 protected:277 void changeTarget(Edge e, Node n)278 {279 if(edges[e.id].next_in != -1)280 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;281 if(edges[e.id].prev_in != -1)282 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;283 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;284 if (nodes[n.id].first_in != -1) {285 edges[nodes[n.id].first_in].prev_in = e.id;286 }287 edges[e.id].target = n.id;288 edges[e.id].prev_in = -1;289 edges[e.id].next_in = nodes[n.id].first_in;290 nodes[n.id].first_in = e.id;291 }292 void changeSource(Edge e, Node n)293 {294 if(edges[e.id].next_out != -1)295 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;296 if(edges[e.id].prev_out != -1)297 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;298 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;299 if (nodes[n.id].first_out != -1) {300 edges[nodes[n.id].first_out].prev_out = e.id;301 }302 edges[e.id].source = n.id;303 edges[e.id].prev_out = -1;304 edges[e.id].next_out = nodes[n.id].first_out;305 nodes[n.id].first_out = e.id;306 }307 308 };309 310 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;311 312 /// \addtogroup graphs313 /// @{314 315 ///A list graph class.316 317 ///This is a simple and fast erasable graph implementation.318 ///319 ///It conforms to the \ref concept::Graph "Graph" concept and it320 ///also provides several additional useful extra functionalities.321 ///The most of the member functions and nested classes are322 ///documented only in the concept class.323 ///\sa concept::Graph.324 325 class ListGraph : public ExtendedListGraphBase {326 public:327 328 typedef ExtendedListGraphBase Parent;329 330 ///Add a new node to the graph.331 332 /// \return the new node.333 ///334 Node addNode() { return Parent::addNode(); }335 336 ///Add a new edge to the graph.337 338 ///Add a new edge to the graph with source node \c s339 ///and target node \c t.340 ///\return the new edge.341 Edge addEdge(const Node& s, const Node& t) {342 return Parent::addEdge(s, t);343 }344 345 /// Changes the target of \c e to \c n346 347 /// Changes the target of \c e to \c n348 ///349 ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing350 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are351 ///invalidated.352 void changeTarget(Edge e, Node n) {353 Parent::changeTarget(e,n);354 }355 /// Changes the source of \c e to \c n356 357 /// Changes the source of \c e to \c n358 ///359 ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing360 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are361 ///invalidated.362 void changeSource(Edge e, Node n) {363 Parent::changeSource(e,n);364 }365 366 /// Invert the direction of an edge.367 368 ///\note The <tt>Edge</tt>s referencing the changed edge remain369 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are370 ///invalidated.371 void reverseEdge(Edge e) {372 Node t=target(e);373 changeTarget(e,source(e));374 changeSource(e,t);375 }376 377 /// \brief Using this it is possible to avoid the superfluous memory378 /// allocation.379 380 ///Using this it is possible to avoid the superfluous memory381 ///allocation: if you know that the graph you want to build will382 ///contain at least 10 million nodes then it is worth to reserve383 ///space for this amount before starting to build the graph.384 void reserveNode(int n) { nodes.reserve(n); };385 386 /// \brief Using this it is possible to avoid the superfluous memory387 /// allocation.388 389 ///Using this it is possible to avoid the superfluous memory390 ///allocation: see the \ref reserveNode function.391 void reserveEdge(int n) { edges.reserve(n); };392 393 394 ///Contract two nodes.395 396 ///This function contracts two nodes.397 ///398 ///Node \p b will be removed but instead of deleting399 ///incident edges, they will be joined to \p a.400 ///The last parameter \p r controls whether to remove loops. \c true401 ///means that loops will be removed.402 ///403 ///\note The <tt>Edge</tt>s404 ///referencing a moved edge remain405 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s406 ///may be invalidated.407 void contract(Node a, Node b, bool r = true)408 {409 for(OutEdgeIt e(*this,b);e!=INVALID;) {410 OutEdgeIt f=e;411 ++f;412 if(r && target(e)==a) erase(e);413 else changeSource(e,a);414 e=f;415 }416 for(InEdgeIt e(*this,b);e!=INVALID;) {417 InEdgeIt f=e;418 ++f;419 if(r && source(e)==a) erase(e);420 else changeTarget(e,a);421 e=f;422 }423 erase(b);424 }425 426 ///Split a node.427 428 ///This function splits a node. First a new node is added to the graph,429 ///then the source of each outgoing edge of \c n is moved to this new node.430 ///If \c connect is \c true (this is the default value), then a new edge431 ///from \c n to the newly created node is also added.432 ///\return The newly created node.433 ///434 ///\note The <tt>Edge</tt>s435 ///referencing a moved edge remain436 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s437 ///may be invalidated.438 ///\warning This functionality cannot be used together with the Snapshot439 ///feature.440 ///\todo It could be implemented in a bit faster way.441 Node split(Node n, bool connect = true) {442 Node b = addNode();443 for(OutEdgeIt e(*this,n);e!=INVALID;) {444 OutEdgeIt f=e;445 ++f;446 changeSource(e,b);447 e=f;448 }449 if (connect) addEdge(n,b);450 return b;451 }452 453 ///Split an edge.454 455 ///This function splits an edge. First a new node \c b is added to456 ///the graph, then the original edge is re-targeted to \c457 ///b. Finally an edge from \c b to the original target is added.458 ///\return The newly created node.459 ///\warning This functionality460 ///cannot be used together with the Snapshot feature.461 Node split(Edge e) {462 Node b = addNode();463 addEdge(b,target(e));464 changeTarget(e,b);465 return b;466 }467 468 /// \brief Class to make a snapshot of the graph and restore469 /// to it later.470 ///471 /// Class to make a snapshot of the graph and to restore it472 /// later.473 ///474 /// The newly added nodes and edges can be removed using the475 /// restore() function.476 ///477 /// \warning Edge and node deletions cannot be restored.478 class Snapshot {479 public:480 481 class UnsupportedOperation : public LogicError {482 public:483 virtual const char* exceptionName() const {484 return "lemon::ListGraph::Snapshot::UnsupportedOperation";485 }486 };487 488 489 protected:490 491 typedef Parent::NodeNotifier NodeNotifier;492 493 class NodeObserverProxy : public NodeNotifier::ObserverBase {494 public:495 496 NodeObserverProxy(Snapshot& _snapshot)497 : snapshot(_snapshot) {}498 499 using NodeNotifier::ObserverBase::attach;500 using NodeNotifier::ObserverBase::detach;501 using NodeNotifier::ObserverBase::attached;502 503 protected:504 505 virtual void add(const Node& node) {506 snapshot.addNode(node);507 }508 virtual void add(const std::vector<Node>& nodes) {509 for (int i = nodes.size() - 1; i >= 0; ++i) {510 snapshot.addNode(nodes[i]);511 }512 }513 virtual void erase(const Node& node) {514 snapshot.eraseNode(node);515 }516 virtual void erase(const std::vector<Node>& nodes) {517 for (int i = 0; i < (int)nodes.size(); ++i) {518 if (!snapshot.eraseNode(nodes[i])) break;519 }520 }521 virtual void build() {522 NodeNotifier* notifier = getNotifier();523 Node node;524 std::vector<Node> nodes;525 for (notifier->first(node); node != INVALID; notifier->next(node)) {526 nodes.push_back(node);527 }528 for (int i = nodes.size() - 1; i >= 0; --i) {529 snapshot.addNode(nodes[i]);530 }531 }532 virtual void clear() {533 NodeNotifier* notifier = getNotifier();534 Node node;535 for (notifier->first(node); node != INVALID; notifier->next(node)) {536 if (!snapshot.eraseNode(node)) break;537 }538 }539 540 Snapshot& snapshot;541 };542 543 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {544 public:545 546 EdgeObserverProxy(Snapshot& _snapshot)547 : snapshot(_snapshot) {}548 549 using EdgeNotifier::ObserverBase::attach;550 using EdgeNotifier::ObserverBase::detach;551 using EdgeNotifier::ObserverBase::attached;552 553 protected:554 555 virtual void add(const Edge& edge) {556 snapshot.addEdge(edge);557 }558 virtual void add(const std::vector<Edge>& edges) {559 for (int i = edges.size() - 1; i >= 0; ++i) {560 snapshot.addEdge(edges[i]);561 }562 }563 virtual void erase(const Edge& edge) {564 snapshot.eraseEdge(edge);565 }566 virtual void erase(const std::vector<Edge>& edges) {567 for (int i = 0; i < (int)edges.size(); ++i) {568 if (!snapshot.eraseEdge(edges[i])) break;569 }570 }571 virtual void build() {572 EdgeNotifier* notifier = getNotifier();573 Edge edge;574 std::vector<Edge> edges;575 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {576 edges.push_back(edge);577 }578 for (int i = edges.size() - 1; i >= 0; --i) {579 snapshot.addEdge(edges[i]);580 }581 }582 virtual void clear() {583 EdgeNotifier* notifier = getNotifier();584 Edge edge;585 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {586 if (!snapshot.eraseEdge(edge)) break;587 }588 }589 590 Snapshot& snapshot;591 };592 593 ListGraph *graph;594 595 NodeObserverProxy node_observer_proxy;596 EdgeObserverProxy edge_observer_proxy;597 598 std::list<Node> added_nodes;599 std::list<Edge> added_edges;600 601 602 void addNode(const Node& node) {603 added_nodes.push_front(node);604 }605 bool eraseNode(const Node& node) {606 std::list<Node>::iterator it =607 std::find(added_nodes.begin(), added_nodes.end(), node);608 if (it == added_nodes.end()) {609 clear();610 return false;611 } else {612 added_nodes.erase(it);613 return true;614 }615 }616 617 void addEdge(const Edge& edge) {618 added_edges.push_front(edge);619 }620 bool eraseEdge(const Edge& edge) {621 std::list<Edge>::iterator it =622 std::find(added_edges.begin(), added_edges.end(), edge);623 if (it == added_edges.end()) {624 clear();625 return false;626 } else {627 added_edges.erase(it);628 return true;629 }630 }631 632 void attach(ListGraph &_graph) {633 graph = &_graph;634 node_observer_proxy.attach(graph->getNotifier(Node()));635 edge_observer_proxy.attach(graph->getNotifier(Edge()));636 }637 638 void detach() {639 node_observer_proxy.detach();640 edge_observer_proxy.detach();641 }642 643 void clear() {644 detach();645 added_nodes.clear();646 added_edges.clear();647 }648 649 public:650 651 /// \brief Default constructur.652 ///653 /// Default constructor.654 /// To actually make a snapshot you must call save().655 Snapshot()656 : graph(0), node_observer_proxy(*this),657 edge_observer_proxy(*this) {}658 659 /// \brief Constructor that immediately makes a snapshot.660 ///661 /// This constructor immediately makes a snapshot of the graph.662 /// \param _graph The graph we make a snapshot of.663 Snapshot(ListGraph &_graph)664 : node_observer_proxy(*this),665 edge_observer_proxy(*this) {666 attach(_graph);667 }668 669 /// \brief Make a snapshot.670 ///671 /// Make a snapshot of the graph.672 ///673 /// This function can be called more than once. In case of a repeated674 /// call, the previous snapshot gets lost.675 /// \param _graph The graph we make the snapshot of.676 void save(ListGraph &_graph) {677 clear();678 attach(_graph);679 }680 681 /// \brief Undo the changes until the last snapshot.682 //683 /// Undo the changes until last snapshot created by save().684 ///685 /// \todo This function might be called undo().686 void restore() {687 detach();688 while(!added_edges.empty()) {689 graph->erase(added_edges.front());690 added_edges.pop_front();691 }692 while(!added_nodes.empty()) {693 graph->erase(added_nodes.front());694 added_nodes.pop_front();695 }696 }697 698 /// \brief Gives back true when the snapshot is valid.699 ///700 /// Gives back true when the snapshot is valid.701 bool valid() const {702 return node_observer_proxy.attached();703 }704 };705 706 };707 708 ///@}709 710 /**************** Undirected List Graph ****************/711 712 35 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 713 36 ExtendedListUGraphBase; 714 37 715 /// \addtogroup graphs 716 /// @{ 38 /// \ingroup graphs 717 39 718 40 ///An undirected list graph class. … … 793 115 }; 794 116 795 796 class ListBpUGraphBase {797 public:798 799 class NodeSetError : public LogicError {800 virtual const char* exceptionName() const {801 return "lemon::ListBpUGraph::NodeSetError";802 }803 };804 805 protected:806 807 struct NodeT {808 int first_edge, prev, next;809 };810 811 struct UEdgeT {812 int aNode, prev_out, next_out;813 int bNode, prev_in, next_in;814 };815 816 std::vector<NodeT> aNodes;817 std::vector<NodeT> bNodes;818 819 std::vector<UEdgeT> edges;820 821 int first_anode;822 int first_free_anode;823 824 int first_bnode;825 int first_free_bnode;826 827 int first_free_edge;828 829 public:830 831 class Node {832 friend class ListBpUGraphBase;833 protected:834 int id;835 836 explicit Node(int _id) : id(_id) {}837 public:838 Node() {}839 Node(Invalid) { id = -1; }840 bool operator==(const Node i) const {return id==i.id;}841 bool operator!=(const Node i) const {return id!=i.id;}842 bool operator<(const Node i) const {return id<i.id;}843 };844 845 class UEdge {846 friend class ListBpUGraphBase;847 protected:848 int id;849 850 explicit UEdge(int _id) { id = _id;}851 public:852 UEdge() {}853 UEdge (Invalid) { id = -1; }854 bool operator==(const UEdge i) const {return id==i.id;}855 bool operator!=(const UEdge i) const {return id!=i.id;}856 bool operator<(const UEdge i) const {return id<i.id;}857 };858 859 ListBpUGraphBase()860 : first_anode(-1), first_free_anode(-1),861 first_bnode(-1), first_free_bnode(-1),862 first_free_edge(-1) {}863 864 void firstANode(Node& node) const {865 node.id = first_anode != -1 ? (first_anode << 1) : -1;866 }867 void nextANode(Node& node) const {868 node.id = aNodes[node.id >> 1].next;869 }870 871 void firstBNode(Node& node) const {872 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;873 }874 void nextBNode(Node& node) const {875 node.id = bNodes[node.id >> 1].next;876 }877 878 void first(Node& node) const {879 if (first_anode != -1) {880 node.id = (first_anode << 1);881 } else if (first_bnode != -1) {882 node.id = (first_bnode << 1) + 1;883 } else {884 node.id = -1;885 }886 }887 void next(Node& node) const {888 if (aNode(node)) {889 node.id = aNodes[node.id >> 1].next;890 if (node.id == -1) {891 if (first_bnode != -1) {892 node.id = (first_bnode << 1) + 1;893 }894 }895 } else {896 node.id = bNodes[node.id >> 1].next;897 }898 }899 900 void first(UEdge& edge) const {901 int aNodeId = first_anode;902 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {903 aNodeId = aNodes[aNodeId].next != -1 ?904 aNodes[aNodeId].next >> 1 : -1;905 }906 if (aNodeId != -1) {907 edge.id = aNodes[aNodeId].first_edge;908 } else {909 edge.id = -1;910 }911 }912 void next(UEdge& edge) const {913 int aNodeId = edges[edge.id].aNode >> 1;914 edge.id = edges[edge.id].next_out;915 if (edge.id == -1) {916 aNodeId = aNodes[aNodeId].next != -1 ?917 aNodes[aNodeId].next >> 1 : -1;918 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {919 aNodeId = aNodes[aNodeId].next != -1 ?920 aNodes[aNodeId].next >> 1 : -1;921 }922 if (aNodeId != -1) {923 edge.id = aNodes[aNodeId].first_edge;924 } else {925 edge.id = -1;926 }927 }928 }929 930 void firstFromANode(UEdge& edge, const Node& node) const {931 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());932 edge.id = aNodes[node.id >> 1].first_edge;933 }934 void nextFromANode(UEdge& edge) const {935 edge.id = edges[edge.id].next_out;936 }937 938 void firstFromBNode(UEdge& edge, const Node& node) const {939 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());940 edge.id = bNodes[node.id >> 1].first_edge;941 }942 void nextFromBNode(UEdge& edge) const {943 edge.id = edges[edge.id].next_in;944 }945 946 static int id(const Node& node) {947 return node.id;948 }949 static Node nodeFromId(int id) {950 return Node(id);951 }952 int maxNodeId() const {953 return aNodes.size() > bNodes.size() ?954 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;955 }956 957 static int id(const UEdge& edge) {958 return edge.id;959 }960 static UEdge uEdgeFromId(int id) {961 return UEdge(id);962 }963 int maxUEdgeId() const {964 return edges.size();965 }966 967 static int aNodeId(const Node& node) {968 return node.id >> 1;969 }970 static Node fromANodeId(int id) {971 return Node(id << 1);972 }973 int maxANodeId() const {974 return aNodes.size();975 }976 977 static int bNodeId(const Node& node) {978 return node.id >> 1;979 }980 static Node fromBNodeId(int id) {981 return Node((id << 1) + 1);982 }983 int maxBNodeId() const {984 return bNodes.size();985 }986 987 Node aNode(const UEdge& edge) const {988 return Node(edges[edge.id].aNode);989 }990 Node bNode(const UEdge& edge) const {991 return Node(edges[edge.id].bNode);992 }993 994 static bool aNode(const Node& node) {995 return (node.id & 1) == 0;996 }997 998 static bool bNode(const Node& node) {999 return (node.id & 1) == 1;1000 }1001 1002 Node addANode() {1003 int aNodeId;1004 if (first_free_anode == -1) {1005 aNodeId = aNodes.size();1006 aNodes.push_back(NodeT());1007 } else {1008 aNodeId = first_free_anode;1009 first_free_anode = aNodes[first_free_anode].next;1010 }1011 if (first_anode != -1) {1012 aNodes[aNodeId].next = first_anode << 1;1013 aNodes[first_anode].prev = aNodeId << 1;1014 } else {1015 aNodes[aNodeId].next = -1;1016 }1017 aNodes[aNodeId].prev = -1;1018 first_anode = aNodeId;1019 aNodes[aNodeId].first_edge = -1;1020 return Node(aNodeId << 1);1021 }1022 1023 Node addBNode() {1024 int bNodeId;1025 if (first_free_bnode == -1) {1026 bNodeId = bNodes.size();1027 bNodes.push_back(NodeT());1028 } else {1029 bNodeId = first_free_bnode;1030 first_free_bnode = bNodes[first_free_bnode].next;1031 }1032 if (first_bnode != -1) {1033 bNodes[bNodeId].next = (first_bnode << 1) + 1;1034 bNodes[first_bnode].prev = (bNodeId << 1) + 1;1035 } else {1036 bNodes[bNodeId].next = -1;1037 }1038 first_bnode = bNodeId;1039 bNodes[bNodeId].first_edge = -1;1040 return Node((bNodeId << 1) + 1);1041 }1042 1043 UEdge addEdge(const Node& source, const Node& target) {1044 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());1045 int edgeId;1046 if (first_free_edge != -1) {1047 edgeId = first_free_edge;1048 first_free_edge = edges[edgeId].next_out;1049 } else {1050 edgeId = edges.size();1051 edges.push_back(UEdgeT());1052 }1053 if ((source.id & 1) == 0) {1054 edges[edgeId].aNode = source.id;1055 edges[edgeId].bNode = target.id;1056 } else {1057 edges[edgeId].aNode = target.id;1058 edges[edgeId].bNode = source.id;1059 }1060 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;1061 edges[edgeId].prev_out = -1;1062 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {1063 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;1064 }1065 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;1066 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;1067 edges[edgeId].prev_in = -1;1068 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {1069 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;1070 }1071 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;1072 return UEdge(edgeId);1073 }1074 1075 void erase(const Node& node) {1076 if (aNode(node)) {1077 int aNodeId = node.id >> 1;1078 if (aNodes[aNodeId].prev != -1) {1079 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;1080 } else {1081 first_anode = aNodes[aNodeId].next >> 1;1082 }1083 if (aNodes[aNodeId].next != -1) {1084 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;1085 }1086 aNodes[aNodeId].next = first_free_anode;1087 first_free_anode = aNodeId;1088 } else {1089 int bNodeId = node.id >> 1;1090 if (bNodes[bNodeId].prev != -1) {1091 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;1092 } else {1093 first_bnode = bNodes[bNodeId].next >> 1;1094 }1095 if (bNodes[bNodeId].next != -1) {1096 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;1097 }1098 bNodes[bNodeId].next = first_free_bnode;1099 first_free_bnode = bNodeId;1100 }1101 }1102 1103 void erase(const UEdge& edge) {1104 1105 if (edges[edge.id].prev_out != -1) {1106 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;1107 } else {1108 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;1109 }1110 if (edges[edge.id].next_out != -1) {1111 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;1112 }1113 1114 if (edges[edge.id].prev_in != -1) {1115 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;1116 } else {1117 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;1118 }1119 if (edges[edge.id].next_in != -1) {1120 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;1121 }1122 1123 edges[edge.id].next_out = first_free_edge;1124 first_free_edge = edge.id;1125 }1126 1127 void clear() {1128 aNodes.clear();1129 bNodes.clear();1130 edges.clear();1131 first_anode = -1;1132 first_free_anode = -1;1133 first_bnode = -1;1134 first_free_bnode = -1;1135 first_free_edge = -1;1136 }1137 1138 };1139 1140 1141 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;1142 1143 /// \ingroup graphs1144 ///1145 /// \brief A smart bipartite undirected graph class.1146 ///1147 /// This is a bipartite undirected graph implementation.1148 /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"1149 /// concept.1150 /// \sa concept::BpUGraph.1151 ///1152 class ListBpUGraph : public ExtendedListBpUGraphBase {};1153 1154 1155 /// @}1156 117 } //namespace lemon 1157 118
Note: See TracChangeset
for help on using the changeset viewer.