COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/list_ugraph.h


Ignore:
Timestamp:
06/30/06 14:14:36 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
Message:

Splitted graph files

File:
1 copied

Legend:

Unmodified
Added
Removed

  • lemon/list_ugraph.h

    r2114 r2115  
    1717 */
    1818
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
     19#ifndef LEMON_LIST_UGRAPH_H
     20#define LEMON_LIST_UGRAPH_H
    2121
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListGraph, ListUGraph classes.
     24///\brief ListUGraph classes.
    2525
     26#include <lemon/list_graph.h>
    2627#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>
    3029
    3130#include <vector>
    … …  
    3433namespace lemon {
    3534
    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 graphs
    313   /// @{
    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 it
    320   ///also provides several additional useful extra functionalities.
    321   ///The most of the member functions and nested classes are
    322   ///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 s
    339     ///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 n
    346 
    347     /// Changes the target of \c e to \c n
    348     ///
    349     ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
    350     ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
    351     ///invalidated.
    352     void changeTarget(Edge e, Node n) {
    353       Parent::changeTarget(e,n);
    354     }
    355     /// Changes the source of \c e to \c n
    356 
    357     /// Changes the source of \c e to \c n
    358     ///
    359     ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
    360     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
    361     ///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 remain
    369     ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
    370     ///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 memory
    378     /// allocation.
    379 
    380     ///Using this it is possible to avoid the superfluous memory
    381     ///allocation: if you know that the graph you want to build will
    382     ///contain at least 10 million nodes then it is worth to reserve
    383     ///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 memory
    387     /// allocation.
    388 
    389     ///Using this it is possible to avoid the superfluous memory
    390     ///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 deleting
    399     ///incident edges, they will be joined to \p a.
    400     ///The last parameter \p r controls whether to remove loops. \c true
    401     ///means that loops will be removed.
    402     ///
    403     ///\note The <tt>Edge</tt>s
    404     ///referencing a moved edge remain
    405     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
    406     ///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 edge
    431     ///from \c n to the newly created node is also added.
    432     ///\return The newly created node.
    433     ///
    434     ///\note The <tt>Edge</tt>s
    435     ///referencing a moved edge remain
    436     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
    437     ///may be invalidated.
    438     ///\warning This functionality cannot be used together with the Snapshot
    439     ///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 to
    456     ///the graph, then the original edge is re-targeted to \c
    457     ///b. Finally an edge from \c b to the original target is added.
    458     ///\return The newly created node. 
    459     ///\warning This functionality
    460     ///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 restore
    469     /// to it later.
    470     ///
    471     /// Class to make a snapshot of the graph and to restore it
    472     /// later.
    473     ///
    474     /// The newly added nodes and edges can be removed using the
    475     /// 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 repeated
    674       /// 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 
    71235  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
    71336  ExtendedListUGraphBase;
    71437
    715   /// \addtogroup graphs
    716   /// @{
     38  /// \ingroup graphs
    71739
    71840  ///An undirected list graph class.
    … …  
    793115  };
    794116
    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 graphs
    1144   ///
    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   /// @} 
    1156117} //namespace lemon
    1157118 
Note: See TracChangeset for help on using the changeset viewer.