COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/list_graph.h @ 57:c1acf0018c0a

Last change on this file since 57:c1acf0018c0a was 57:c1acf0018c0a, checked in by Balazs Dezso <deba@…>, 16 years ago

Port ListDigraph? and ListGraph? from svn -r 3433
Details:

  • port Digraph and Graph concepts
  • port ListDigraph? and ListGraph?
  • port Basic graph constructing tools
  • port Digraph and Graph tests
File size: 38.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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 ListDigraph, ListGraph classes.
25
26#include <lemon/bits/graph_extender.h>
27
28#include <vector>
29#include <list>
30
31namespace lemon {
32
33  class ListDigraphBase {
34
35  protected:
36    struct NodeT {
37      int first_in, first_out;
38      int prev, next;
39    };
40 
41    struct ArcT {
42      int target, source;
43      int prev_in, prev_out;
44      int next_in, next_out;
45    };
46
47    std::vector<NodeT> nodes;
48
49    int first_node;
50
51    int first_free_node;
52
53    std::vector<ArcT> arcs;
54
55    int first_free_arc;
56   
57  public:
58   
59    typedef ListDigraphBase Digraph;
60   
61    class Node {
62      friend class ListDigraphBase;
63    protected:
64
65      int id;
66      explicit Node(int pid) { id = pid;}
67
68    public:
69      Node() {}
70      Node (Invalid) { id = -1; }
71      bool operator==(const Node& node) const {return id == node.id;}
72      bool operator!=(const Node& node) const {return id != node.id;}
73      bool operator<(const Node& node) const {return id < node.id;}
74    };
75
76    class Arc {
77      friend class ListDigraphBase;
78    protected:
79
80      int id;
81      explicit Arc(int pid) { id = pid;}
82
83    public:
84      Arc() {}
85      Arc (Invalid) { id = -1; }
86      bool operator==(const Arc& arc) const {return id == arc.id;}
87      bool operator!=(const Arc& arc) const {return id != arc.id;}
88      bool operator<(const Arc& arc) const {return id < arc.id;}
89    };
90
91
92
93    ListDigraphBase()
94      : nodes(), first_node(-1),
95        first_free_node(-1), arcs(), first_free_arc(-1) {}
96
97   
98    int maxNodeId() const { return nodes.size()-1; }
99    int maxArcId() const { return arcs.size()-1; }
100
101    Node source(Arc e) const { return Node(arcs[e.id].source); }
102    Node target(Arc e) const { return Node(arcs[e.id].target); }
103
104
105    void first(Node& node) const {
106      node.id = first_node;
107    }
108
109    void next(Node& node) const {
110      node.id = nodes[node.id].next;
111    }
112
113
114    void first(Arc& e) const {
115      int n;
116      for(n = first_node;
117          n!=-1 && nodes[n].first_in == -1;
118          n = nodes[n].next);
119      e.id = (n == -1) ? -1 : nodes[n].first_in;
120    }
121
122    void next(Arc& arc) const {
123      if (arcs[arc.id].next_in != -1) {
124        arc.id = arcs[arc.id].next_in;
125      } else {
126        int n;
127        for(n = nodes[arcs[arc.id].target].next;
128          n!=-1 && nodes[n].first_in == -1;
129          n = nodes[n].next);
130        arc.id = (n == -1) ? -1 : nodes[n].first_in;
131      }     
132    }
133
134    void firstOut(Arc &e, const Node& v) const {
135      e.id = nodes[v.id].first_out;
136    }
137    void nextOut(Arc &e) const {
138      e.id=arcs[e.id].next_out;
139    }
140
141    void firstIn(Arc &e, const Node& v) const {
142      e.id = nodes[v.id].first_in;
143    }
144    void nextIn(Arc &e) const {
145      e.id=arcs[e.id].next_in;
146    }
147
148   
149    static int id(Node v) { return v.id; }
150    static int id(Arc e) { return e.id; }
151
152    static Node nodeFromId(int id) { return Node(id);}
153    static Arc arcFromId(int id) { return Arc(id);}
154
155    Node addNode() {     
156      int n;
157     
158      if(first_free_node==-1) {
159        n = nodes.size();
160        nodes.push_back(NodeT());
161      } else {
162        n = first_free_node;
163        first_free_node = nodes[n].next;
164      }
165     
166      nodes[n].next = first_node;
167      if(first_node != -1) nodes[first_node].prev = n;
168      first_node = n;
169      nodes[n].prev = -1;
170     
171      nodes[n].first_in = nodes[n].first_out = -1;
172     
173      return Node(n);
174    }
175   
176    Arc addArc(Node u, Node v) {
177      int n;     
178
179      if (first_free_arc == -1) {
180        n = arcs.size();
181        arcs.push_back(ArcT());
182      } else {
183        n = first_free_arc;
184        first_free_arc = arcs[n].next_in;
185      }
186     
187      arcs[n].source = u.id;
188      arcs[n].target = v.id;
189
190      arcs[n].next_out = nodes[u.id].first_out;
191      if(nodes[u.id].first_out != -1) {
192        arcs[nodes[u.id].first_out].prev_out = n;
193      }
194     
195      arcs[n].next_in = nodes[v.id].first_in;
196      if(nodes[v.id].first_in != -1) {
197        arcs[nodes[v.id].first_in].prev_in = n;
198      }
199     
200      arcs[n].prev_in = arcs[n].prev_out = -1;
201       
202      nodes[u.id].first_out = nodes[v.id].first_in = n;
203
204      return Arc(n);
205    }
206   
207    void erase(const Node& node) {
208      int n = node.id;
209     
210      if(nodes[n].next != -1) {
211        nodes[nodes[n].next].prev = nodes[n].prev;
212      }
213     
214      if(nodes[n].prev != -1) {
215        nodes[nodes[n].prev].next = nodes[n].next;
216      } else {
217        first_node = nodes[n].next;
218      }
219     
220      nodes[n].next = first_free_node;
221      first_free_node = n;
222
223    }
224   
225    void erase(const Arc& arc) {
226      int n = arc.id;
227     
228      if(arcs[n].next_in!=-1) {
229        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
230      }
231
232      if(arcs[n].prev_in!=-1) {
233        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
234      } else {
235        nodes[arcs[n].target].first_in = arcs[n].next_in;
236      }
237
238     
239      if(arcs[n].next_out!=-1) {
240        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
241      }
242
243      if(arcs[n].prev_out!=-1) {
244        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
245      } else {
246        nodes[arcs[n].source].first_out = arcs[n].next_out;
247      }
248     
249      arcs[n].next_in = first_free_arc;
250      first_free_arc = n;     
251
252    }
253
254    void clear() {
255      arcs.clear();
256      nodes.clear();
257      first_node = first_free_node = first_free_arc = -1;
258    }
259
260  protected:
261    void changeTarget(Arc e, Node n)
262    {
263      if(arcs[e.id].next_in != -1)
264        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
265      if(arcs[e.id].prev_in != -1)
266        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
267      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
268      if (nodes[n.id].first_in != -1) {
269        arcs[nodes[n.id].first_in].prev_in = e.id;
270      }
271      arcs[e.id].target = n.id;
272      arcs[e.id].prev_in = -1;
273      arcs[e.id].next_in = nodes[n.id].first_in;
274      nodes[n.id].first_in = e.id;
275    }
276    void changeSource(Arc e, Node n)
277    {
278      if(arcs[e.id].next_out != -1)
279        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
280      if(arcs[e.id].prev_out != -1)
281        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
282      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
283      if (nodes[n.id].first_out != -1) {
284        arcs[nodes[n.id].first_out].prev_out = e.id;
285      }
286      arcs[e.id].source = n.id;
287      arcs[e.id].prev_out = -1;
288      arcs[e.id].next_out = nodes[n.id].first_out;
289      nodes[n.id].first_out = e.id;
290    }
291
292  };
293
294  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
295
296  /// \addtogroup digraphs
297  /// @{
298
299  ///A list digraph class.
300
301  ///This is a simple and fast digraph implementation.
302  ///
303  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
304  ///also provides several additional useful extra functionalities.
305  ///The most of the member functions and nested classes are
306  ///documented only in the concept class.
307  ///
308  ///An important extra feature of this digraph implementation is that
309  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
310  ///
311  ///\sa concepts::Digraph.
312
313  class ListDigraph : public ExtendedListDigraphBase {
314  private:
315    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
316   
317    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
318    ///
319    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
320    ///\brief Assignment of ListDigraph to another one is \e not allowed.
321    ///Use DigraphCopy() instead.
322
323    ///Assignment of ListDigraph to another one is \e not allowed.
324    ///Use DigraphCopy() instead.
325    void operator=(const ListDigraph &) {}
326  public:
327
328    typedef ExtendedListDigraphBase Parent;
329
330    /// Constructor
331   
332    /// Constructor.
333    ///
334    ListDigraph() {}
335
336    ///Add a new node to the digraph.
337   
338    /// \return the new node.
339    ///
340    Node addNode() { return Parent::addNode(); }
341
342    ///Add a new arc to the digraph.
343   
344    ///Add a new arc to the digraph with source node \c s
345    ///and target node \c t.
346    ///\return the new arc.
347    Arc addArc(const Node& s, const Node& t) {
348      return Parent::addArc(s, t);
349    }
350
351    /// Changes the target of \c e to \c n
352
353    /// Changes the target of \c e to \c n
354    ///
355    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
356    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
357    ///invalidated.
358    ///\warning This functionality cannot be used together with the Snapshot
359    ///feature.
360    void changeTarget(Arc e, Node n) {
361      Parent::changeTarget(e,n);
362    }
363    /// Changes the source of \c e to \c n
364
365    /// Changes the source of \c e to \c n
366    ///
367    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
368    ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
369    ///invalidated.
370    ///\warning This functionality cannot be used together with the Snapshot
371    ///feature.
372    void changeSource(Arc e, Node n) {
373      Parent::changeSource(e,n);
374    }
375
376    /// Invert the direction of an arc.
377
378    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
379    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
380    ///invalidated.
381    ///\warning This functionality cannot be used together with the Snapshot
382    ///feature.
383    void reverseArc(Arc e) {
384      Node t=target(e);
385      changeTarget(e,source(e));
386      changeSource(e,t);
387    }
388
389    /// Using this it is possible to avoid the superfluous memory
390    /// allocation: if you know that the digraph you want to build will
391    /// be very large (e.g. it will contain millions of nodes and/or arcs)
392    /// then it is worth reserving space for this amount before starting
393    /// to build the digraph.
394    /// \sa reserveArc
395    void reserveNode(int n) { nodes.reserve(n); };
396
397    /// \brief Using this it is possible to avoid the superfluous memory
398    /// allocation.
399
400    /// Using this it is possible to avoid the superfluous memory
401    /// allocation: if you know that the digraph you want to build will
402    /// be very large (e.g. it will contain millions of nodes and/or arcs)
403    /// then it is worth reserving space for this amount before starting
404    /// to build the digraph.
405    /// \sa reserveNode
406    void reserveArc(int m) { arcs.reserve(m); };
407
408    ///Contract two nodes.
409
410    ///This function contracts two nodes.
411    ///
412    ///Node \p b will be removed but instead of deleting
413    ///incident arcs, they will be joined to \p a.
414    ///The last parameter \p r controls whether to remove loops. \c true
415    ///means that loops will be removed.
416    ///
417    ///\note The <tt>ArcIt</tt>s
418    ///referencing a moved arc remain
419    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
420    ///may be invalidated.
421    ///\warning This functionality cannot be used together with the Snapshot
422    ///feature.
423    void contract(Node a, Node b, bool r = true)
424    {
425      for(OutArcIt e(*this,b);e!=INVALID;) {
426        OutArcIt f=e;
427        ++f;
428        if(r && target(e)==a) erase(e);
429        else changeSource(e,a);
430        e=f;
431      }
432      for(InArcIt e(*this,b);e!=INVALID;) {
433        InArcIt f=e;
434        ++f;
435        if(r && source(e)==a) erase(e);
436        else changeTarget(e,a);
437        e=f;
438      }
439      erase(b);
440    }
441
442    ///Split a node.
443
444    ///This function splits a node. First a new node is added to the digraph,
445    ///then the source of each outgoing arc of \c n is moved to this new node.
446    ///If \c connect is \c true (this is the default value), then a new arc
447    ///from \c n to the newly created node is also added.
448    ///\return The newly created node.
449    ///
450    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
451    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
452    ///be invalidated. 
453    ///
454    ///\warning This functionality cannot be used together with the
455    ///Snapshot feature.  \todo It could be implemented in a bit
456    ///faster way.
457    Node split(Node n, bool connect = true) {
458      Node b = addNode();
459      for(OutArcIt e(*this,n);e!=INVALID;) {
460        OutArcIt f=e;
461        ++f;
462        changeSource(e,b);
463        e=f;
464      }
465      if (connect) addArc(n,b);
466      return b;
467    }
468     
469    ///Split an arc.
470
471    ///This function splits an arc. First a new node \c b is added to
472    ///the digraph, then the original arc is re-targeted to \c
473    ///b. Finally an arc from \c b to the original target is added.
474    ///\return The newly created node. 
475    ///\warning This functionality
476    ///cannot be used together with the Snapshot feature.
477    Node split(Arc e) {
478      Node b = addNode();
479      addArc(b,target(e));
480      changeTarget(e,b);
481      return b;
482    }
483     
484    /// \brief Class to make a snapshot of the digraph and restore
485    /// to it later.
486    ///
487    /// Class to make a snapshot of the digraph and to restore it
488    /// later.
489    ///
490    /// The newly added nodes and arcs can be removed using the
491    /// restore() function.
492    ///
493    /// \warning Arc and node deletions cannot be restored. This
494    /// events invalidate the snapshot.
495    class Snapshot {
496    protected:
497
498      typedef Parent::NodeNotifier NodeNotifier;
499
500      class NodeObserverProxy : public NodeNotifier::ObserverBase {
501      public:
502
503        NodeObserverProxy(Snapshot& _snapshot)
504          : snapshot(_snapshot) {}
505
506        using NodeNotifier::ObserverBase::attach;
507        using NodeNotifier::ObserverBase::detach;
508        using NodeNotifier::ObserverBase::attached;
509       
510      protected:
511       
512        virtual void add(const Node& node) {
513          snapshot.addNode(node);
514        }
515        virtual void add(const std::vector<Node>& nodes) {
516          for (int i = nodes.size() - 1; i >= 0; ++i) {
517            snapshot.addNode(nodes[i]);
518          }
519        }
520        virtual void erase(const Node& node) {
521          snapshot.eraseNode(node);
522        }
523        virtual void erase(const std::vector<Node>& nodes) {
524          for (int i = 0; i < int(nodes.size()); ++i) {
525            snapshot.eraseNode(nodes[i]);
526          }
527        }
528        virtual void build() {
529          Node node;
530          std::vector<Node> nodes;
531          for (notifier()->first(node); node != INVALID;
532               notifier()->next(node)) {
533            nodes.push_back(node);
534          }
535          for (int i = nodes.size() - 1; i >= 0; --i) {
536            snapshot.addNode(nodes[i]);
537          }
538        }
539        virtual void clear() {
540          Node node;
541          for (notifier()->first(node); node != INVALID;
542               notifier()->next(node)) {
543            snapshot.eraseNode(node);
544          }
545        }
546
547        Snapshot& snapshot;
548      };
549
550      class ArcObserverProxy : public ArcNotifier::ObserverBase {
551      public:
552
553        ArcObserverProxy(Snapshot& _snapshot)
554          : snapshot(_snapshot) {}
555
556        using ArcNotifier::ObserverBase::attach;
557        using ArcNotifier::ObserverBase::detach;
558        using ArcNotifier::ObserverBase::attached;
559       
560      protected:
561
562        virtual void add(const Arc& arc) {
563          snapshot.addArc(arc);
564        }
565        virtual void add(const std::vector<Arc>& arcs) {
566          for (int i = arcs.size() - 1; i >= 0; ++i) {
567            snapshot.addArc(arcs[i]);
568          }
569        }
570        virtual void erase(const Arc& arc) {
571          snapshot.eraseArc(arc);
572        }
573        virtual void erase(const std::vector<Arc>& arcs) {
574          for (int i = 0; i < int(arcs.size()); ++i) {
575            snapshot.eraseArc(arcs[i]);
576          }
577        }
578        virtual void build() {
579          Arc arc;
580          std::vector<Arc> arcs;
581          for (notifier()->first(arc); arc != INVALID;
582               notifier()->next(arc)) {
583            arcs.push_back(arc);
584          }
585          for (int i = arcs.size() - 1; i >= 0; --i) {
586            snapshot.addArc(arcs[i]);
587          }
588        }
589        virtual void clear() {
590          Arc arc;
591          for (notifier()->first(arc); arc != INVALID;
592               notifier()->next(arc)) {
593            snapshot.eraseArc(arc);
594          }
595        }
596
597        Snapshot& snapshot;
598      };
599     
600      ListDigraph *digraph;
601
602      NodeObserverProxy node_observer_proxy;
603      ArcObserverProxy arc_observer_proxy;
604
605      std::list<Node> added_nodes;
606      std::list<Arc> added_arcs;
607
608
609      void addNode(const Node& node) {
610        added_nodes.push_front(node);       
611      }
612      void eraseNode(const Node& node) {
613        std::list<Node>::iterator it =
614          std::find(added_nodes.begin(), added_nodes.end(), node);
615        if (it == added_nodes.end()) {
616          clear();
617          arc_observer_proxy.detach();
618          throw NodeNotifier::ImmediateDetach();
619        } else {
620          added_nodes.erase(it);
621        }
622      }
623
624      void addArc(const Arc& arc) {
625        added_arcs.push_front(arc);       
626      }
627      void eraseArc(const Arc& arc) {
628        std::list<Arc>::iterator it =
629          std::find(added_arcs.begin(), added_arcs.end(), arc);
630        if (it == added_arcs.end()) {
631          clear();
632          node_observer_proxy.detach();
633          throw ArcNotifier::ImmediateDetach();
634        } else {
635          added_arcs.erase(it);
636        }       
637      }
638
639      void attach(ListDigraph &_digraph) {
640        digraph = &_digraph;
641        node_observer_proxy.attach(digraph->notifier(Node()));
642        arc_observer_proxy.attach(digraph->notifier(Arc()));
643      }
644           
645      void detach() {
646        node_observer_proxy.detach();
647        arc_observer_proxy.detach();
648      }
649
650      bool attached() const {
651        return node_observer_proxy.attached();
652      }
653
654      void clear() {
655        added_nodes.clear();
656        added_arcs.clear();       
657      }
658
659    public:
660
661      /// \brief Default constructor.
662      ///
663      /// Default constructor.
664      /// To actually make a snapshot you must call save().
665      Snapshot()
666        : digraph(0), node_observer_proxy(*this),
667          arc_observer_proxy(*this) {}
668     
669      /// \brief Constructor that immediately makes a snapshot.
670      ///     
671      /// This constructor immediately makes a snapshot of the digraph.
672      /// \param _digraph The digraph we make a snapshot of.
673      Snapshot(ListDigraph &_digraph)
674        : node_observer_proxy(*this),
675          arc_observer_proxy(*this) {
676        attach(_digraph);
677      }
678     
679      /// \brief Make a snapshot.
680      ///
681      /// Make a snapshot of the digraph.
682      ///
683      /// This function can be called more than once. In case of a repeated
684      /// call, the previous snapshot gets lost.
685      /// \param _digraph The digraph we make the snapshot of.
686      void save(ListDigraph &_digraph) {
687        if (attached()) {
688          detach();
689          clear();
690        }
691        attach(_digraph);
692      }
693     
694      /// \brief Undo the changes until the last snapshot.
695      //
696      /// Undo the changes until the last snapshot created by save().
697      void restore() {
698        detach();
699        for(std::list<Arc>::iterator it = added_arcs.begin();
700            it != added_arcs.end(); ++it) {
701          digraph->erase(*it);
702        }
703        for(std::list<Node>::iterator it = added_nodes.begin();
704            it != added_nodes.end(); ++it) {
705          digraph->erase(*it);
706        }
707        clear();
708      }
709
710      /// \brief Gives back true when the snapshot is valid.
711      ///
712      /// Gives back true when the snapshot is valid.
713      bool valid() const {
714        return attached();
715      }
716    };
717   
718  };
719
720  ///@}
721
722  class ListGraphBase {
723
724  protected:
725
726    struct NodeT {
727      int first_out;
728      int prev, next;
729    };
730 
731    struct ArcT {
732      int target;
733      int prev_out, next_out;
734    };
735
736    std::vector<NodeT> nodes;
737
738    int first_node;
739
740    int first_free_node;
741
742    std::vector<ArcT> arcs;
743
744    int first_free_arc;
745   
746  public:
747   
748    typedef ListGraphBase Digraph;
749
750    class Node;
751    class Arc;
752    class Edge;
753   
754    class Node {
755      friend class ListGraphBase;
756    protected:
757
758      int id;
759      explicit Node(int pid) { id = pid;}
760
761    public:
762      Node() {}
763      Node (Invalid) { id = -1; }
764      bool operator==(const Node& node) const {return id == node.id;}
765      bool operator!=(const Node& node) const {return id != node.id;}
766      bool operator<(const Node& node) const {return id < node.id;}
767    };
768
769    class Edge {
770      friend class ListGraphBase;
771    protected:
772
773      int id;
774      explicit Edge(int pid) { id = pid;}
775
776    public:
777      Edge() {}
778      Edge (Invalid) { id = -1; }
779      bool operator==(const Edge& arc) const {return id == arc.id;}
780      bool operator!=(const Edge& arc) const {return id != arc.id;}
781      bool operator<(const Edge& arc) const {return id < arc.id;}
782    };
783
784    class Arc {
785      friend class ListGraphBase;
786    protected:
787
788      int id;
789      explicit Arc(int pid) { id = pid;}
790
791    public:
792      operator Edge() const { return edgeFromId(id / 2); }
793
794      Arc() {}
795      Arc (Invalid) { id = -1; }
796      bool operator==(const Arc& arc) const {return id == arc.id;}
797      bool operator!=(const Arc& arc) const {return id != arc.id;}
798      bool operator<(const Arc& arc) const {return id < arc.id;}
799    };
800
801
802
803    ListGraphBase()
804      : nodes(), first_node(-1),
805        first_free_node(-1), arcs(), first_free_arc(-1) {}
806
807   
808    int maxNodeId() const { return nodes.size()-1; }
809    int maxEdgeId() const { return arcs.size() / 2 - 1; }
810    int maxArcId() const { return arcs.size()-1; }
811
812    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
813    Node target(Arc e) const { return Node(arcs[e.id].target); }
814
815    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
816    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
817
818    static bool direction(Arc e) {
819      return (e.id & 1) == 1;
820    }
821
822    static Arc direct(Edge e, bool d) {
823      return Arc(e.id * 2 + (d ? 1 : 0));
824    }
825
826    void first(Node& node) const {
827      node.id = first_node;
828    }
829
830    void next(Node& node) const {
831      node.id = nodes[node.id].next;
832    }
833
834    void first(Arc& e) const {
835      int n = first_node;
836      while (n != -1 && nodes[n].first_out == -1) {
837        n = nodes[n].next;
838      }
839      e.id = (n == -1) ? -1 : nodes[n].first_out;
840    }
841
842    void next(Arc& e) const {
843      if (arcs[e.id].next_out != -1) {
844        e.id = arcs[e.id].next_out;
845      } else {
846        int n = nodes[arcs[e.id ^ 1].target].next;
847        while(n != -1 && nodes[n].first_out == -1) {
848          n = nodes[n].next;
849        }
850        e.id = (n == -1) ? -1 : nodes[n].first_out;
851      }     
852    }
853
854    void first(Edge& e) const {
855      int n = first_node;
856      while (n != -1) {
857        e.id = nodes[n].first_out;
858        while ((e.id & 1) != 1) {
859          e.id = arcs[e.id].next_out;
860        }
861        if (e.id != -1) {
862          e.id /= 2;
863          return;
864        }
865        n = nodes[n].next;
866      }
867      e.id = -1;
868    }
869
870    void next(Edge& e) const {
871      int n = arcs[e.id * 2].target;
872      e.id = arcs[(e.id * 2) | 1].next_out;
873      while ((e.id & 1) != 1) {
874        e.id = arcs[e.id].next_out;
875      }
876      if (e.id != -1) {
877        e.id /= 2;
878        return;
879      }
880      n = nodes[n].next;
881      while (n != -1) {
882        e.id = nodes[n].first_out;
883        while ((e.id & 1) != 1) {
884          e.id = arcs[e.id].next_out;
885        }
886        if (e.id != -1) {
887          e.id /= 2;
888          return;
889        }
890        n = nodes[n].next;
891      }
892      e.id = -1;
893    }
894
895    void firstOut(Arc &e, const Node& v) const {
896      e.id = nodes[v.id].first_out;
897    }
898    void nextOut(Arc &e) const {
899      e.id = arcs[e.id].next_out;
900    }
901
902    void firstIn(Arc &e, const Node& v) const {
903      e.id = ((nodes[v.id].first_out) ^ 1);
904      if (e.id == -2) e.id = -1;
905    }
906    void nextIn(Arc &e) const {
907      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
908      if (e.id == -2) e.id = -1;
909    }
910
911    void firstInc(Edge &e, bool& d, const Node& v) const {
912      int de = nodes[v.id].first_out;
913      if (de != -1 ) {
914        e.id = de / 2;
915        d = ((de & 1) == 1);
916      } else {
917        e.id = -1;
918        d = true;
919      }
920    }
921    void nextInc(Edge &e, bool& d) const {
922      int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
923      if (de != -1 ) {
924        e.id = de / 2;
925        d = ((de & 1) == 1);
926      } else {
927        e.id = -1;
928        d = true;
929      }
930    }
931   
932    static int id(Node v) { return v.id; }
933    static int id(Arc e) { return e.id; }
934    static int id(Edge e) { return e.id; }
935
936    static Node nodeFromId(int id) { return Node(id);}
937    static Arc arcFromId(int id) { return Arc(id);}
938    static Edge edgeFromId(int id) { return Edge(id);}
939
940    Node addNode() {     
941      int n;
942     
943      if(first_free_node==-1) {
944        n = nodes.size();
945        nodes.push_back(NodeT());
946      } else {
947        n = first_free_node;
948        first_free_node = nodes[n].next;
949      }
950     
951      nodes[n].next = first_node;
952      if (first_node != -1) nodes[first_node].prev = n;
953      first_node = n;
954      nodes[n].prev = -1;
955     
956      nodes[n].first_out = -1;
957     
958      return Node(n);
959    }
960   
961    Edge addEdge(Node u, Node v) {
962      int n;     
963
964      if (first_free_arc == -1) {
965        n = arcs.size();
966        arcs.push_back(ArcT());
967        arcs.push_back(ArcT());
968      } else {
969        n = first_free_arc;
970        first_free_arc = arcs[n].next_out;
971      }
972     
973      arcs[n].target = u.id;
974      arcs[n | 1].target = v.id;
975
976      arcs[n].next_out = nodes[v.id].first_out;
977      if (nodes[v.id].first_out != -1) {
978        arcs[nodes[v.id].first_out].prev_out = n;
979      }     
980      arcs[n].prev_out = -1;
981      nodes[v.id].first_out = n;
982     
983      arcs[n | 1].next_out = nodes[u.id].first_out;
984      if (nodes[u.id].first_out != -1) {
985        arcs[nodes[u.id].first_out].prev_out = (n | 1);
986      }
987      arcs[n | 1].prev_out = -1;     
988      nodes[u.id].first_out = (n | 1);
989
990      return Edge(n / 2);
991    }
992   
993    void erase(const Node& node) {
994      int n = node.id;
995     
996      if(nodes[n].next != -1) {
997        nodes[nodes[n].next].prev = nodes[n].prev;
998      }
999     
1000      if(nodes[n].prev != -1) {
1001        nodes[nodes[n].prev].next = nodes[n].next;
1002      } else {
1003        first_node = nodes[n].next;
1004      }
1005     
1006      nodes[n].next = first_free_node;
1007      first_free_node = n;
1008
1009    }
1010   
1011    void erase(const Edge& arc) {
1012      int n = arc.id * 2;
1013     
1014      if (arcs[n].next_out != -1) {
1015        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1016      }
1017
1018      if (arcs[n].prev_out != -1) {
1019        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1020      } else {
1021        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1022      }
1023
1024      if (arcs[n | 1].next_out != -1) {
1025        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1026      }
1027
1028      if (arcs[n | 1].prev_out != -1) {
1029        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1030      } else {
1031        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1032      }
1033     
1034      arcs[n].next_out = first_free_arc;
1035      first_free_arc = n;     
1036
1037    }
1038
1039    void clear() {
1040      arcs.clear();
1041      nodes.clear();
1042      first_node = first_free_node = first_free_arc = -1;
1043    }
1044
1045  protected:
1046
1047    void changeTarget(Edge e, Node n) {
1048      if(arcs[2 * e.id].next_out != -1) {
1049        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1050      }
1051      if(arcs[2 * e.id].prev_out != -1) {
1052        arcs[arcs[2 * e.id].prev_out].next_out =
1053          arcs[2 * e.id].next_out;
1054      } else {
1055        nodes[arcs[(2 * e.id) | 1].target].first_out =
1056          arcs[2 * e.id].next_out;
1057      }
1058
1059      if (nodes[n.id].first_out != -1) {
1060        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1061      }
1062      arcs[(2 * e.id) | 1].target = n.id;
1063      arcs[2 * e.id].prev_out = -1;
1064      arcs[2 * e.id].next_out = nodes[n.id].first_out;
1065      nodes[n.id].first_out = 2 * e.id;
1066    }
1067
1068    void changeSource(Edge e, Node n) {
1069      if(arcs[(2 * e.id) | 1].next_out != -1) {
1070        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1071          arcs[(2 * e.id) | 1].prev_out;
1072      }
1073      if(arcs[(2 * e.id) | 1].prev_out != -1) {
1074        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1075          arcs[(2 * e.id) | 1].next_out;
1076      } else {
1077        nodes[arcs[2 * e.id].target].first_out =
1078          arcs[(2 * e.id) | 1].next_out;
1079      }
1080
1081      if (nodes[n.id].first_out != -1) {
1082        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1083      }
1084      arcs[2 * e.id].target = n.id;
1085      arcs[(2 * e.id) | 1].prev_out = -1;
1086      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1087      nodes[n.id].first_out = ((2 * e.id) | 1);
1088    }
1089
1090  };
1091
1092//   typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >
1093//   ExtendedListGraphBase;
1094
1095  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1096
1097
1098
1099  /// \addtogroup digraphs
1100  /// @{
1101
1102  ///An undirected list digraph class.
1103
1104  ///This is a simple and fast undirected digraph implementation.
1105  ///
1106  ///An important extra feature of this digraph implementation is that
1107  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1108  ///
1109  ///It conforms to the
1110  ///\ref concepts::Graph "Graph concept".
1111  ///
1112  ///\sa concepts::Graph.
1113  ///
1114  class ListGraph : public ExtendedListGraphBase {
1115  private:
1116    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
1117
1118    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
1119    ///
1120    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
1121    ///\brief Assignment of ListGraph to another one is \e not allowed.
1122    ///Use GraphCopy() instead.
1123
1124    ///Assignment of ListGraph to another one is \e not allowed.
1125    ///Use GraphCopy() instead.
1126    void operator=(const ListGraph &) {}
1127  public:
1128    /// Constructor
1129   
1130    /// Constructor.
1131    ///
1132    ListGraph() {}
1133
1134    typedef ExtendedListGraphBase Parent;
1135
1136    typedef Parent::OutArcIt IncArcIt;
1137
1138    /// \brief Add a new node to the digraph.
1139    ///
1140    /// \return the new node.
1141    ///
1142    Node addNode() { return Parent::addNode(); }
1143
1144    /// \brief Add a new edge to the digraph.
1145    ///
1146    /// Add a new arc to the digraph with source node \c s
1147    /// and target node \c t.
1148    /// \return the new edge.
1149    Edge addEdge(const Node& s, const Node& t) {
1150      return Parent::addEdge(s, t);
1151    }
1152    /// \brief Changes the source of \c e to \c n
1153    ///
1154    /// Changes the source of \c e to \c n
1155    ///
1156    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1157    ///referencing the changed arc remain
1158    ///valid. However <tt>OutArcIt</tt>s are invalidated.
1159    void changeSource(Edge e, Node n) {
1160      Parent::changeSource(e,n);
1161    }   
1162    /// \brief Changes the target of \c e to \c n
1163    ///
1164    /// Changes the target of \c e to \c n
1165    ///
1166    /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
1167    /// valid. However the other iterators may be invalidated.
1168    void changeTarget(Edge e, Node n) {
1169      Parent::changeTarget(e,n);
1170    }
1171    /// \brief Changes the source of \c e to \c n
1172    ///
1173    /// Changes the source of \c e to \c n. It changes the proper
1174    /// node of the represented edge.
1175    ///
1176    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1177    ///referencing the changed arc remain
1178    ///valid. However <tt>OutArcIt</tt>s are invalidated.
1179    void changeSource(Arc e, Node n) {
1180      if (Parent::direction(e)) {
1181        Parent::changeSource(e,n);
1182      } else {
1183        Parent::changeTarget(e,n);
1184      }
1185    }
1186    /// \brief Changes the target of \c e to \c n
1187    ///
1188    /// Changes the target of \c e to \c n. It changes the proper
1189    /// node of the represented edge.
1190    ///
1191    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
1192    ///referencing the changed arc remain
1193    ///valid. However <tt>InArcIt</tt>s are invalidated.
1194    void changeTarget(Arc e, Node n) {
1195      if (Parent::direction(e)) {
1196        Parent::changeTarget(e,n);
1197      } else {
1198        Parent::changeSource(e,n);
1199      }
1200    }
1201    /// \brief Contract two nodes.
1202    ///
1203    /// This function contracts two nodes.
1204    ///
1205    /// Node \p b will be removed but instead of deleting
1206    /// its neighboring arcs, they will be joined to \p a.
1207    /// The last parameter \p r controls whether to remove loops. \c true
1208    /// means that loops will be removed.
1209    ///
1210    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
1211    /// valid.
1212    void contract(Node a, Node b, bool r = true) {
1213      for(IncArcIt e(*this, b); e!=INVALID;) {
1214        IncArcIt f = e; ++f;
1215        if (r && runningNode(e) == a) {
1216          erase(e);
1217        } else if (source(e) == b) {
1218          changeSource(e, a);
1219        } else {
1220          changeTarget(e, a);
1221        }
1222        e = f;
1223      }
1224      erase(b);
1225    }
1226
1227
1228    /// \brief Class to make a snapshot of the digraph and restore
1229    /// to it later.
1230    ///
1231    /// Class to make a snapshot of the digraph and to restore it
1232    /// later.
1233    ///
1234    /// The newly added nodes and edges can be removed
1235    /// using the restore() function.
1236    ///
1237    /// \warning Arc and node deletions cannot be restored. This
1238    /// events invalidate the snapshot.
1239    class Snapshot {
1240    protected:
1241
1242      typedef Parent::NodeNotifier NodeNotifier;
1243
1244      class NodeObserverProxy : public NodeNotifier::ObserverBase {
1245      public:
1246
1247        NodeObserverProxy(Snapshot& _snapshot)
1248          : snapshot(_snapshot) {}
1249
1250        using NodeNotifier::ObserverBase::attach;
1251        using NodeNotifier::ObserverBase::detach;
1252        using NodeNotifier::ObserverBase::attached;
1253       
1254      protected:
1255       
1256        virtual void add(const Node& node) {
1257          snapshot.addNode(node);
1258        }
1259        virtual void add(const std::vector<Node>& nodes) {
1260          for (int i = nodes.size() - 1; i >= 0; ++i) {
1261            snapshot.addNode(nodes[i]);
1262          }
1263        }
1264        virtual void erase(const Node& node) {
1265          snapshot.eraseNode(node);
1266        }
1267        virtual void erase(const std::vector<Node>& nodes) {
1268          for (int i = 0; i < int(nodes.size()); ++i) {
1269            snapshot.eraseNode(nodes[i]);
1270          }
1271        }
1272        virtual void build() {
1273          Node node;
1274          std::vector<Node> nodes;
1275          for (notifier()->first(node); node != INVALID;
1276               notifier()->next(node)) {
1277            nodes.push_back(node);
1278          }
1279          for (int i = nodes.size() - 1; i >= 0; --i) {
1280            snapshot.addNode(nodes[i]);
1281          }
1282        }
1283        virtual void clear() {
1284          Node node;
1285          for (notifier()->first(node); node != INVALID;
1286               notifier()->next(node)) {
1287            snapshot.eraseNode(node);
1288          }
1289        }
1290
1291        Snapshot& snapshot;
1292      };
1293
1294      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1295      public:
1296
1297        EdgeObserverProxy(Snapshot& _snapshot)
1298          : snapshot(_snapshot) {}
1299
1300        using EdgeNotifier::ObserverBase::attach;
1301        using EdgeNotifier::ObserverBase::detach;
1302        using EdgeNotifier::ObserverBase::attached;
1303       
1304      protected:
1305
1306        virtual void add(const Edge& arc) {
1307          snapshot.addEdge(arc);
1308        }
1309        virtual void add(const std::vector<Edge>& arcs) {
1310          for (int i = arcs.size() - 1; i >= 0; ++i) {
1311            snapshot.addEdge(arcs[i]);
1312          }
1313        }
1314        virtual void erase(const Edge& arc) {
1315          snapshot.eraseEdge(arc);
1316        }
1317        virtual void erase(const std::vector<Edge>& arcs) {
1318          for (int i = 0; i < int(arcs.size()); ++i) {
1319            snapshot.eraseEdge(arcs[i]);
1320          }
1321        }
1322        virtual void build() {
1323          Edge arc;
1324          std::vector<Edge> arcs;
1325          for (notifier()->first(arc); arc != INVALID;
1326               notifier()->next(arc)) {
1327            arcs.push_back(arc);
1328          }
1329          for (int i = arcs.size() - 1; i >= 0; --i) {
1330            snapshot.addEdge(arcs[i]);
1331          }
1332        }
1333        virtual void clear() {
1334          Edge arc;
1335          for (notifier()->first(arc); arc != INVALID;
1336               notifier()->next(arc)) {
1337            snapshot.eraseEdge(arc);
1338          }
1339        }
1340
1341        Snapshot& snapshot;
1342      };
1343     
1344      ListGraph *digraph;
1345
1346      NodeObserverProxy node_observer_proxy;
1347      EdgeObserverProxy arc_observer_proxy;
1348
1349      std::list<Node> added_nodes;
1350      std::list<Edge> added_arcs;
1351
1352
1353      void addNode(const Node& node) {
1354        added_nodes.push_front(node);       
1355      }
1356      void eraseNode(const Node& node) {
1357        std::list<Node>::iterator it =
1358          std::find(added_nodes.begin(), added_nodes.end(), node);
1359        if (it == added_nodes.end()) {
1360          clear();
1361          arc_observer_proxy.detach();
1362          throw NodeNotifier::ImmediateDetach();
1363        } else {
1364          added_nodes.erase(it);
1365        }
1366      }
1367
1368      void addEdge(const Edge& arc) {
1369        added_arcs.push_front(arc);       
1370      }
1371      void eraseEdge(const Edge& arc) {
1372        std::list<Edge>::iterator it =
1373          std::find(added_arcs.begin(), added_arcs.end(), arc);
1374        if (it == added_arcs.end()) {
1375          clear();
1376          node_observer_proxy.detach();
1377          throw EdgeNotifier::ImmediateDetach();
1378        } else {
1379          added_arcs.erase(it);
1380        }       
1381      }
1382
1383      void attach(ListGraph &_digraph) {
1384        digraph = &_digraph;
1385        node_observer_proxy.attach(digraph->notifier(Node()));
1386        arc_observer_proxy.attach(digraph->notifier(Edge()));
1387      }
1388           
1389      void detach() {
1390        node_observer_proxy.detach();
1391        arc_observer_proxy.detach();
1392      }
1393
1394      bool attached() const {
1395        return node_observer_proxy.attached();
1396      }
1397
1398      void clear() {
1399        added_nodes.clear();
1400        added_arcs.clear();       
1401      }
1402
1403    public:
1404
1405      /// \brief Default constructor.
1406      ///
1407      /// Default constructor.
1408      /// To actually make a snapshot you must call save().
1409      Snapshot()
1410        : digraph(0), node_observer_proxy(*this),
1411          arc_observer_proxy(*this) {}
1412     
1413      /// \brief Constructor that immediately makes a snapshot.
1414      ///     
1415      /// This constructor immediately makes a snapshot of the digraph.
1416      /// \param _digraph The digraph we make a snapshot of.
1417      Snapshot(ListGraph &_digraph)
1418        : node_observer_proxy(*this),
1419          arc_observer_proxy(*this) {
1420        attach(_digraph);
1421      }
1422     
1423      /// \brief Make a snapshot.
1424      ///
1425      /// Make a snapshot of the digraph.
1426      ///
1427      /// This function can be called more than once. In case of a repeated
1428      /// call, the previous snapshot gets lost.
1429      /// \param _digraph The digraph we make the snapshot of.
1430      void save(ListGraph &_digraph) {
1431        if (attached()) {
1432          detach();
1433          clear();
1434        }
1435        attach(_digraph);
1436      }
1437     
1438      /// \brief Undo the changes until the last snapshot.
1439      //
1440      /// Undo the changes until the last snapshot created by save().
1441      void restore() {
1442        detach();
1443        for(std::list<Edge>::iterator it = added_arcs.begin();
1444            it != added_arcs.end(); ++it) {
1445          digraph->erase(*it);
1446        }
1447        for(std::list<Node>::iterator it = added_nodes.begin();
1448            it != added_nodes.end(); ++it) {
1449          digraph->erase(*it);
1450        }
1451        clear();
1452      }
1453
1454      /// \brief Gives back true when the snapshot is valid.
1455      ///
1456      /// Gives back true when the snapshot is valid.
1457      bool valid() const {
1458        return attached();
1459      }
1460    };
1461  };
1462 
1463  /// @} 
1464} //namespace lemon
1465 
1466
1467#endif
Note: See TracBrowser for help on using the repository browser.