COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/list_graph.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1991:d7442141d9ef, checked in by Balazs Dezso, 14 years ago

The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor?, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor? is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor?<UndirGraphAdaptor?<Graph>>.

The ResGraphAdaptor? is based on this composition.

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