COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/list_graph.h @ 2064:2c5f81b35269

Last change on this file since 2064:2c5f81b35269 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 25.0 KB
RevLine 
[948]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[948]8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
[395]18
[921]19#ifndef LEMON_LIST_GRAPH_H
20#define LEMON_LIST_GRAPH_H
[395]21
[948]22///\ingroup graphs
23///\file
[1909]24///\brief ListGraph, ListUGraph classes.
[948]25
[1999]26#include <lemon/bits/base_extender.h>
[1791]27#include <lemon/bits/graph_extender.h>
[782]28
[1774]29#include <lemon/error.h>
30
[1979]31#include <vector>
[1011]32#include <list>
[782]33
[921]34namespace lemon {
[395]35
[946]36  class ListGraphBase {
[406]37
[949]38  protected:
[946]39    struct NodeT {
[1470]40      int first_in, first_out;
[397]41      int prev, next;
[395]42    };
[946]43 
44    struct EdgeT {
[986]45      int target, source;
[397]46      int prev_in, prev_out;
47      int next_in, next_out;
[395]48    };
49
50    std::vector<NodeT> nodes;
[946]51
[397]52    int first_node;
[946]53
[397]54    int first_free_node;
[946]55
[395]56    std::vector<EdgeT> edges;
[946]57
[397]58    int first_free_edge;
[395]59   
[782]60  public:
[395]61   
[946]62    typedef ListGraphBase Graph;
[397]63   
[946]64    class Node {
[975]65      friend class ListGraphBase;
[946]66    protected:
[395]67
[946]68      int id;
[2031]69      explicit Node(int pid) { id = pid;}
[395]70
[946]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    };
[782]78
[946]79    class Edge {
[975]80      friend class ListGraphBase;
[946]81    protected:
[782]82
[946]83      int id;
[2031]84      explicit Edge(int pid) { id = pid;}
[395]85
[946]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()
[782]97      : nodes(), first_node(-1),
98        first_free_node(-1), edges(), first_free_edge(-1) {}
99
[395]100   
[813]101    /// Maximum node ID.
102   
103    /// Maximum node ID.
104    ///\sa id(Node)
[1791]105    int maxNodeId() const { return nodes.size()-1; }
[946]106
[813]107    /// Maximum edge ID.
108   
109    /// Maximum edge ID.
110    ///\sa id(Edge)
[1791]111    int maxEdgeId() const { return edges.size()-1; }
[395]112
[2031]113    Node source(Edge e) const { return Node(edges[e.id].source); }
114    Node target(Edge e) const { return Node(edges[e.id].target); }
[395]115
116
[946]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;
[986]139        for(n = nodes[edges[edge.id].target].next;
[946]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
[813]160   
[946]161    static int id(Node v) { return v.id; }
162    static int id(Edge e) { return e.id; }
[395]163
[1791]164    static Node nodeFromId(int id) { return Node(id);}
165    static Edge edgeFromId(int id) { return Edge(id);}
[1106]166
[397]167    /// Adds a new node to the graph.
168
[813]169    /// \warning It adds the new node to the front of the list.
[397]170    /// (i.e. the lastly added node becomes the first.)
[946]171    Node addNode() {     
[397]172      int n;
173     
[946]174      if(first_free_node==-1) {
175        n = nodes.size();
176        nodes.push_back(NodeT());
177      } else {
[397]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     
[946]189      return Node(n);
[395]190    }
191   
192    Edge addEdge(Node u, Node v) {
[946]193      int n;     
194
195      if (first_free_edge == -1) {
196        n = edges.size();
197        edges.push_back(EdgeT());
198      } else {
[397]199        n = first_free_edge;
200        first_free_edge = edges[n].next_in;
201      }
202     
[986]203      edges[n].source = u.id;
204      edges[n].target = v.id;
[395]205
[946]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     
[397]216      edges[n].prev_in = edges[n].prev_out = -1;
217       
[946]218      nodes[u.id].first_out = nodes[v.id].first_in = n;
[397]219
[946]220      return Edge(n);
[395]221    }
[774]222   
[946]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;
[395]238
[774]239    }
240   
[946]241    void erase(const Edge& edge) {
242      int n = edge.id;
[397]243     
[946]244      if(edges[n].next_in!=-1) {
[397]245        edges[edges[n].next_in].prev_in = edges[n].prev_in;
[946]246      }
247
248      if(edges[n].prev_in!=-1) {
[397]249        edges[edges[n].prev_in].next_in = edges[n].next_in;
[946]250      } else {
[986]251        nodes[edges[n].target].first_in = edges[n].next_in;
[946]252      }
253
[397]254     
[946]255      if(edges[n].next_out!=-1) {
[397]256        edges[edges[n].next_out].prev_out = edges[n].prev_out;
[946]257      }
258
259      if(edges[n].prev_out!=-1) {
[397]260        edges[edges[n].prev_out].next_out = edges[n].next_out;
[946]261      } else {
[986]262        nodes[edges[n].source].first_out = edges[n].next_out;
[946]263      }
[397]264     
265      edges[n].next_in = first_free_edge;
[695]266      first_free_edge = n;     
[397]267
268    }
269
270    void clear() {
[782]271      edges.clear();
272      nodes.clear();
[946]273      first_node = first_free_node = first_free_edge = -1;
[937]274    }
275
[949]276  protected:
[1546]277    void _changeTarget(Edge e, Node n)
[949]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;
[986]283      else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
[1702]284      if (nodes[n.id].first_in != -1) {
285        edges[nodes[n.id].first_in].prev_in = e.id;
286      }
[986]287      edges[e.id].target = n.id;
[949]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    }
[1546]292    void _changeSource(Edge e, Node n)
[949]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;
[986]298      else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
[1702]299      if (nodes[n.id].first_out != -1) {
300        edges[nodes[n.id].first_out].prev_out = e.id;
301      }
[986]302      edges[e.id].source = n.id;
[949]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
[919]308  };
[909]309
[1979]310  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
[400]311
[1718]312  /// \addtogroup graphs
313  /// @{
[400]314
[948]315  ///A list graph class.
[400]316
[948]317  ///This is a simple and fast erasable graph implementation.
318  ///
[1010]319  ///It addition that it conforms to the
320  ///\ref concept::ErasableGraph "ErasableGraph" concept,
321  ///it also provides several additional useful extra functionalities.
[959]322  ///\sa concept::ErasableGraph.
[782]323
[1999]324  class ListGraph : public ExtendedListGraphBase {
[948]325  public:
[1999]326
327    typedef ExtendedListGraphBase Parent;
328
[1546]329    /// Changes the target of \c e to \c n
[948]330
[1546]331    /// Changes the target of \c e to \c n
[948]332    ///
[1010]333    ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
[1546]334    ///referencing the changed edge remain
[1010]335    ///valid. However <tt>InEdge</tt>'s are invalidated.
[1718]336    void changeTarget(Edge e, Node n) {
337      _changeTarget(e,n);
338    }
[1546]339    /// Changes the source of \c e to \c n
[948]340
[1546]341    /// Changes the source of \c e to \c n
[948]342    ///
[1010]343    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
[1546]344    ///referencing the changed edge remain
[1010]345    ///valid. However <tt>OutEdge</tt>'s are invalidated.
[1718]346    void changeSource(Edge e, Node n) {
347      _changeSource(e,n);
348    }
[949]349
[1010]350    /// Invert the direction of an edge.
351
352    ///\note The <tt>Edge</tt>'s
[1546]353    ///referencing the changed edge remain
[1010]354    ///valid. However <tt>OutEdge</tt>'s  and <tt>InEdge</tt>'s are invalidated.
355    void reverseEdge(Edge e) {
356      Node t=target(e);
[1546]357      _changeTarget(e,source(e));
358      _changeSource(e,t);
[1010]359    }
360
361    ///Using this it possible to avoid the superfluous memory allocation.
362
[949]363    ///Using this it possible to avoid the superfluous memory allocation.
364    ///\todo more docs...
365    void reserveEdge(int n) { edges.reserve(n); };
[1010]366
367    ///Contract two nodes.
368
369    ///This function contracts two nodes.
370    ///
371    ///Node \p b will be removed but instead of deleting
372    ///its neighboring edges, they will be joined to \p a.
373    ///The last parameter \p r controls whether to remove loops. \c true
374    ///means that loops will be removed.
375    ///
376    ///\note The <tt>Edge</tt>s
[1281]377    ///referencing a moved edge remain
[1010]378    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
379    ///may be invalidated.
[1718]380    void contract(Node a, Node b, bool r = true)
[1010]381    {
382      for(OutEdgeIt e(*this,b);e!=INVALID;) {
383        OutEdgeIt f=e;
384        ++f;
385        if(r && target(e)==a) erase(e);
[1546]386        else changeSource(e,a);
[1010]387        e=f;
388      }
389      for(InEdgeIt e(*this,b);e!=INVALID;) {
390        InEdgeIt f=e;
391        ++f;
392        if(r && source(e)==a) erase(e);
[1546]393        else changeTarget(e,a);
[1010]394        e=f;
395      }
396      erase(b);
397    }
[1011]398
[1281]399    ///Split a node.
[1011]400
[1284]401    ///This function splits a node. First a new node is added to the graph,
402    ///then the source of each outgoing edge of \c n is moved to this new node.
[1281]403    ///If \c connect is \c true (this is the default value), then a new edge
404    ///from \c n to the newly created node is also added.
405    ///\return The newly created node.
406    ///
407    ///\note The <tt>Edge</tt>s
408    ///referencing a moved edge remain
409    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
410    ///may be invalidated.
[1770]411    ///\warning This functionality cannot be used together with the Snapshot
[1284]412    ///feature.
[1281]413    ///\todo It could be implemented in a bit faster way.
414    Node split(Node n, bool connect = true)
415    {
416      Node b = addNode();
417      for(OutEdgeIt e(*this,n);e!=INVALID;) {
418        OutEdgeIt f=e;
419        ++f;
[1546]420        changeSource(e,b);
[1281]421        e=f;
422      }
423      if(connect) addEdge(n,b);
424      return b;
425    }
426     
[1812]427    ///Split an edge.
428
429    ///This function splits an edge. First a new node \c b is added to the graph,
430    ///then the original edge is re-targetes to \c b. Finally an edge
431    ///from \c b to the original target is added.
432    ///\return The newly created node.
433    ///\warning This functionality cannot be used together with the Snapshot
434    ///feature.
435    Node split(Edge e)
436    {
437      Node b = addNode();
438      addEdge(b,target(e));
439      changeTarget(e,b);
440      return b;
441    }
442     
[1011]443    ///Class to make a snapshot of the graph and to restrore to it later.
444
445    ///Class to make a snapshot of the graph and to restrore to it later.
446    ///
447    ///The newly added nodes and edges can be removed using the
448    ///restore() function.
449    ///
450    ///\warning Edge and node deletions cannot be restored.
[1770]451    ///\warning Snapshots cannot be nested.
[1999]452    class Snapshot : protected Parent::NodeNotifier::ObserverBase,
453                     protected Parent::EdgeNotifier::ObserverBase
[1011]454    {
[1774]455    public:
456     
457      class UnsupportedOperation : public LogicError {
458      public:
459        virtual const char* exceptionName() const {
460          return "lemon::ListGraph::Snapshot::UnsupportedOperation";
461        }
462      };
463           
464
[1999]465    protected:
[1011]466     
467      ListGraph *g;
468      std::list<Node> added_nodes;
469      std::list<Edge> added_edges;
470     
471      bool active;
472      virtual void add(const Node& n) {
473        added_nodes.push_back(n);
474      };
475      virtual void erase(const Node&)
476      {
[1774]477        throw UnsupportedOperation();
[1011]478      }
479      virtual void add(const Edge& n) {
480        added_edges.push_back(n);
481      };
482      virtual void erase(const Edge&)
483      {
[1774]484        throw UnsupportedOperation();
[1011]485      }
486
[1457]487      ///\bug What is this used for?
488      ///
489      virtual void build() {}
490      ///\bug What is this used for?
491      ///
492      virtual void clear() {}
493
[1011]494      void regist(ListGraph &_g) {
495        g=&_g;
[1999]496        Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node()));
497        Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge()));
[1011]498      }
499           
500      void deregist() {
[1999]501        Parent::NodeNotifier::ObserverBase::detach();
502        Parent::EdgeNotifier::ObserverBase::detach();
[1011]503        g=0;
504      }
[1774]505
[1011]506    public:
507      ///Default constructur.
508     
509      ///Default constructur.
510      ///To actually make a snapshot you must call save().
511      ///
[1770]512      Snapshot() : g(0) {}
[1011]513      ///Constructor that immediately makes a snapshot.
514     
515      ///This constructor immediately makes a snapshot of the graph.
516      ///\param _g The graph we make a snapshot of.
[1770]517      Snapshot(ListGraph &_g) {
[1011]518        regist(_g);
519      }
520      ///\bug Is it necessary?
521      ///
[1770]522      ~Snapshot()
[1011]523      {
524        if(g) deregist();
525      }
526     
527      ///Make a snapshot.
528
529      ///Make a snapshot of the graph.
530      ///
531      ///This function can be called more than once. In case of a repeated
532      ///call, the previous snapshot gets lost.
533      ///\param _g The graph we make the snapshot of.
534      void save(ListGraph &_g)
535      {
536        if(g!=&_g) {
537          if(g) deregist();
538          regist(_g);
539        }
540        added_nodes.clear();
541        added_edges.clear();
542      }
543     
544    ///Undo the changes until the last snapshot.
545
546    ///Undo the changes until last snapshot created by save().
547    ///
548    ///\todo This function might be called undo().
549      void restore() {
[1457]550        ListGraph &old_g=*g;
[1011]551        deregist();
552        while(!added_edges.empty()) {
[1457]553          old_g.erase(added_edges.front());
[1011]554          added_edges.pop_front();
555        }
556        while(!added_nodes.empty()) {
[1457]557          old_g.erase(added_nodes.front());
[1011]558          added_nodes.pop_front();
559        }
560      }
561    };
562   
[949]563  };
[1034]564
[1555]565  ///@}
[1034]566
567  /**************** Undirected List Graph ****************/
568
[1979]569  typedef UGraphExtender<UGraphBaseExtender<
570    ListGraphBase> > ExtendedListUGraphBase;
[1034]571
[1718]572  /// \addtogroup graphs
573  /// @{
[1555]574
[1035]575  ///An undirected list graph class.
576
577  ///This is a simple and fast erasable undirected graph implementation.
578  ///
579  ///It conforms to the
[1909]580  ///\ref concept::UGraph "UGraph" concept.
[1035]581  ///
[1909]582  ///\sa concept::UGraph.
[1035]583  ///
[1770]584  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
[1161]585  ///haven't been implemented yet.
[1035]586  ///
[1909]587  class ListUGraph : public ExtendedListUGraphBase {
[1718]588  public:
[1909]589    typedef ExtendedListUGraphBase Parent;
[1718]590    /// \brief Changes the target of \c e to \c n
591    ///
592    /// Changes the target of \c e to \c n
593    ///
594    /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
595    /// referencing the changed edge remain
596    /// valid. However <tt>InEdge</tt>'s are invalidated.
[1909]597    void changeTarget(UEdge e, Node n) {
[1718]598      _changeTarget(e,n);
599    }
600    /// Changes the source of \c e to \c n
601    ///
602    /// Changes the source of \c e to \c n
603    ///
604    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
605    ///referencing the changed edge remain
606    ///valid. However <tt>OutEdge</tt>'s are invalidated.
[1909]607    void changeSource(UEdge e, Node n) {
[1718]608      _changeSource(e,n);
609    }
610    /// \brief Contract two nodes.
611    ///
612    /// This function contracts two nodes.
613    ///
614    /// Node \p b will be removed but instead of deleting
615    /// its neighboring edges, they will be joined to \p a.
616    /// The last parameter \p r controls whether to remove loops. \c true
617    /// means that loops will be removed.
618    ///
619    /// \note The <tt>Edge</tt>s
620    /// referencing a moved edge remain
621    /// valid.
622    void contract(Node a, Node b, bool r = true) {
623      for(IncEdgeIt e(*this, b); e!=INVALID;) {
624        IncEdgeIt f = e; ++f;
625        if (r && runningNode(e) == a) {
626          erase(e);
627        } else if (source(e) == b) {
628          changeSource(e, a);
629        } else {
630          changeTarget(e, a);
631        }
632        e = f;
633      }
634      erase(b);
635    }
[1034]636  };
637
[1982]638
639  class ListBpUGraphBase {
640  public:
641
642    class NodeSetError : public LogicError {
643      virtual const char* exceptionName() const {
644        return "lemon::ListBpUGraph::NodeSetError";
645      }
646    };
647
648  protected:
649
650    struct NodeT {
651      int first_edge, next_node;
652    };
653
654    struct EdgeT {
655      int aNode, prev_out, next_out;
656      int bNode, prev_in, next_in;
657    };
658
659    std::vector<NodeT> aNodes;
660    std::vector<NodeT> bNodes;
661
662    std::vector<EdgeT> edges;
663
664    int first_anode;
665    int first_free_anode;
666
667    int first_bnode;
668    int first_free_bnode;
669
670    int first_free_edge;
671
672  public:
673 
674    class Node {
675      friend class ListBpUGraphBase;
676    protected:
677      int id;
678
[2031]679      explicit Node(int _id) : id(_id) {}
[1982]680    public:
681      Node() {}
682      Node(Invalid) { id = -1; }
683      bool operator==(const Node i) const {return id==i.id;}
684      bool operator!=(const Node i) const {return id!=i.id;}
685      bool operator<(const Node i) const {return id<i.id;}
686    };
687
688    class Edge {
689      friend class ListBpUGraphBase;
690    protected:
691      int id;
692
[2031]693      explicit Edge(int _id) { id = _id;}
[1982]694    public:
695      Edge() {}
696      Edge (Invalid) { id = -1; }
697      bool operator==(const Edge i) const {return id==i.id;}
698      bool operator!=(const Edge i) const {return id!=i.id;}
699      bool operator<(const Edge i) const {return id<i.id;}
700    };
701
702    ListBpUGraphBase()
703      : first_anode(-1), first_free_anode(-1),
704        first_bnode(-1), first_free_bnode(-1),
705        first_free_edge(-1) {}
706
707    void firstANode(Node& node) const {
708      node.id = first_anode != -1 ? (first_anode << 1) : -1;
709    }
710    void nextANode(Node& node) const {
711      node.id = aNodes[node.id >> 1].next_node;
712    }
713
714    void firstBNode(Node& node) const {
715      node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
716    }
717    void nextBNode(Node& node) const {
[1984]718      node.id = bNodes[node.id >> 1].next_node;
[1982]719    }
720
721    void first(Node& node) const {
722      if (first_anode != -1) {
723        node.id = (first_anode << 1);
724      } else if (first_bnode != -1) {
725        node.id = (first_bnode << 1) + 1;
726      } else {
727        node.id = -1;
728      }
729    }
730    void next(Node& node) const {
731      if (aNode(node)) {
732        node.id = aNodes[node.id >> 1].next_node;
733        if (node.id == -1) {
734          if (first_bnode != -1) {
735            node.id = (first_bnode << 1) + 1;
736          }
737        }
738      } else {
739        node.id = bNodes[node.id >> 1].next_node;
740      }
741    }
742 
743    void first(Edge& edge) const {
744      int aNodeId = first_anode;
745      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
746        aNodeId = aNodes[aNodeId].next_node != -1 ?
747          aNodes[aNodeId].next_node >> 1 : -1;
748      }
749      if (aNodeId != -1) {
750        edge.id = aNodes[aNodeId].first_edge;
751      } else {
752        edge.id = -1;
753      }
754    }
755    void next(Edge& edge) const {
756      int aNodeId = edges[edge.id].aNode >> 1;
757      edge.id = edges[edge.id].next_out;
758      if (edge.id == -1) {
759        aNodeId = aNodes[aNodeId].next_node != -1 ?
760          aNodes[aNodeId].next_node >> 1 : -1;
761        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
762          aNodeId = aNodes[aNodeId].next_node != -1 ?
763          aNodes[aNodeId].next_node >> 1 : -1;
764        }
765        if (aNodeId != -1) {
766          edge.id = aNodes[aNodeId].first_edge;
767        } else {
768          edge.id = -1;
769        }
770      }
771    }
772
773    void firstOut(Edge& edge, const Node& node) const {
774      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
775      edge.id = aNodes[node.id >> 1].first_edge;
776    }
777    void nextOut(Edge& edge) const {
778      edge.id = edges[edge.id].next_out;
779    }
780
781    void firstIn(Edge& edge, const Node& node) const {
782      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
783      edge.id = bNodes[node.id >> 1].first_edge;
784    }
785    void nextIn(Edge& edge) const {
786      edge.id = edges[edge.id].next_in;
787    }
788
789    static int id(const Node& node) {
790      return node.id;
791    }
792    static Node nodeFromId(int id) {
793      return Node(id);
794    }
795    int maxNodeId() const {
796      return aNodes.size() > bNodes.size() ?
797        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
798    }
799 
800    static int id(const Edge& edge) {
801      return edge.id;
802    }
803    static Edge edgeFromId(int id) {
804      return Edge(id);
805    }
806    int maxEdgeId() const {
807      return edges.size();
808    }
809 
810    static int aNodeId(const Node& node) {
811      return node.id >> 1;
812    }
[1995]813    static Node fromANodeId(int id) {
[1982]814      return Node(id << 1);
815    }
816    int maxANodeId() const {
817      return aNodes.size();
818    }
819
820    static int bNodeId(const Node& node) {
821      return node.id >> 1;
822    }
823    static Node fromBNodeId(int id) {
824      return Node((id << 1) + 1);
825    }
826    int maxBNodeId() const {
827      return bNodes.size();
828    }
829
830    Node aNode(const Edge& edge) const {
831      return Node(edges[edge.id].aNode);
832    }
833    Node bNode(const Edge& edge) const {
834      return Node(edges[edge.id].bNode);
835    }
836
837    static bool aNode(const Node& node) {
838      return (node.id & 1) == 0;
839    }
840
841    static bool bNode(const Node& node) {
842      return (node.id & 1) == 1;
843    }
844
845    Node addANode() {
846      int aNodeId;
847      if (first_free_anode == -1) {
848        aNodeId = aNodes.size();
849        aNodes.push_back(NodeT());
850      } else {
851        aNodeId = first_free_anode;
852        first_free_anode = aNodes[first_free_anode].next_node;
853      }
854      aNodes[aNodeId].next_node =
855        first_anode != -1 ? (first_anode << 1) : -1;
856      first_anode = aNodeId;
857      aNodes[aNodeId].first_edge = -1;
858      return Node(aNodeId << 1);
859    }
860
861    Node addBNode() {
862      int bNodeId;
[1984]863      if (first_free_bnode == -1) {
[1982]864        bNodeId = bNodes.size();
865        bNodes.push_back(NodeT());
866      } else {
867        bNodeId = first_free_bnode;
868        first_free_bnode = bNodes[first_free_bnode].next_node;
869      }
870      bNodes[bNodeId].next_node =
871        first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
872      first_bnode = bNodeId;
873      bNodes[bNodeId].first_edge = -1;
874      return Node((bNodeId << 1) + 1);
875    }
876
877    Edge addEdge(const Node& source, const Node& target) {
878      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
879      int edgeId;
880      if (first_free_edge != -1) {
881        edgeId = first_free_edge;
882        first_free_edge = edges[edgeId].next_out;
883      } else {
884        edgeId = edges.size();
885        edges.push_back(EdgeT());
886      }
887      if ((source.id & 1) == 0) {
888        edges[edgeId].aNode = source.id;
889        edges[edgeId].bNode = target.id;
890      } else {
891        edges[edgeId].aNode = target.id;
892        edges[edgeId].bNode = source.id;
893      }
894      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
895      edges[edgeId].prev_out = -1;
896      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
897        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
898      }
899      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
900      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
901      edges[edgeId].prev_in = -1;
902      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
903        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
904      }
905      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
906      return Edge(edgeId);
907    }
908
909    void erase(const Node& node) {
910      if (aNode(node)) {
911        int aNodeId = node.id >> 1;
912        aNodes[aNodeId].next_node = first_free_anode;
913        first_free_anode = aNodeId;
914      } else {
915        int bNodeId = node.id >> 1;
916        bNodes[bNodeId].next_node = first_free_bnode;
917        first_free_bnode = bNodeId;
918      }
919    }
920
921    void erase(const Edge& edge) {
922      if (edges[edge.id].prev_out != -1) {
923        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
924      } else {
925        aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
926      }
927      if (edges[edge.id].next_out != -1) {
928        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
929      }
930      if (edges[edge.id].prev_in != -1) {
931        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
932      } else {
933        bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
934      }
935      if (edges[edge.id].next_in != -1) {
936        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
937      }
938      edges[edge.id].next_out = first_free_edge;
939      first_free_edge = edge.id;
940    }
941
942    void clear() {
943      aNodes.clear();
944      bNodes.clear();
945      edges.clear();
946      first_anode = -1;
947      first_free_anode = -1;
948      first_bnode = -1;
949      first_free_bnode = -1;
950      first_free_edge = -1;
951    }
952
953  };
954
955
956  typedef BpUGraphExtender< BpUGraphBaseExtender<
957    ListBpUGraphBase> > ExtendedListBpUGraphBase;
958
959  /// \ingroup graphs
960  ///
961  /// \brief A smart bipartite undirected graph class.
962  ///
963  /// This is a bipartite undirected graph implementation.
[1991]964  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
965  /// concept.
[1982]966  /// \sa concept::BpUGraph.
967  ///
968  class ListBpUGraph : public ExtendedListBpUGraphBase {};
969
[949]970 
[948]971  /// @} 
972} //namespace lemon
[946]973 
[400]974
[946]975#endif
Note: See TracBrowser for help on using the repository browser.