COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/list_graph.h @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 13 years ago

Splitted graph files

File size: 18.7 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 class.
25
26#include <lemon/bits/graph_extender.h>
27
28#include <vector>
29#include <list>
30
31namespace lemon {
32
33  class ListGraphBase {
34
35  protected:
36    struct NodeT {
37      int first_in, first_out;
38      int prev, next;
39    };
40 
41    struct EdgeT {
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<EdgeT> edges;
54
55    int first_free_edge;
56   
57  public:
58   
59    typedef ListGraphBase Graph;
60   
61    class Node {
62      friend class ListGraphBase;
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 Edge {
77      friend class ListGraphBase;
78    protected:
79
80      int id;
81      explicit Edge(int pid) { id = pid;}
82
83    public:
84      Edge() {}
85      Edge (Invalid) { id = -1; }
86      bool operator==(const Edge& edge) const {return id == edge.id;}
87      bool operator!=(const Edge& edge) const {return id != edge.id;}
88      bool operator<(const Edge& edge) const {return id < edge.id;}
89    };
90
91
92
93    ListGraphBase()
94      : nodes(), first_node(-1),
95        first_free_node(-1), edges(), first_free_edge(-1) {}
96
97   
98    /// Maximum node ID.
99   
100    /// Maximum node ID.
101    ///\sa id(Node)
102    int maxNodeId() const { return nodes.size()-1; }
103
104    /// Maximum edge ID.
105   
106    /// Maximum edge ID.
107    ///\sa id(Edge)
108    int maxEdgeId() const { return edges.size()-1; }
109
110    Node source(Edge e) const { return Node(edges[e.id].source); }
111    Node target(Edge e) const { return Node(edges[e.id].target); }
112
113
114    void first(Node& node) const {
115      node.id = first_node;
116    }
117
118    void next(Node& node) const {
119      node.id = nodes[node.id].next;
120    }
121
122
123    void first(Edge& e) const {
124      int n;
125      for(n = first_node;
126          n!=-1 && nodes[n].first_in == -1;
127          n = nodes[n].next);
128      e.id = (n == -1) ? -1 : nodes[n].first_in;
129    }
130
131    void next(Edge& edge) const {
132      if (edges[edge.id].next_in != -1) {
133        edge.id = edges[edge.id].next_in;
134      } else {
135        int n;
136        for(n = nodes[edges[edge.id].target].next;
137          n!=-1 && nodes[n].first_in == -1;
138          n = nodes[n].next);
139        edge.id = (n == -1) ? -1 : nodes[n].first_in;
140      }     
141    }
142
143    void firstOut(Edge &e, const Node& v) const {
144      e.id = nodes[v.id].first_out;
145    }
146    void nextOut(Edge &e) const {
147      e.id=edges[e.id].next_out;
148    }
149
150    void firstIn(Edge &e, const Node& v) const {
151      e.id = nodes[v.id].first_in;
152    }
153    void nextIn(Edge &e) const {
154      e.id=edges[e.id].next_in;
155    }
156
157   
158    static int id(Node v) { return v.id; }
159    static int id(Edge e) { return e.id; }
160
161    static Node nodeFromId(int id) { return Node(id);}
162    static Edge edgeFromId(int id) { return Edge(id);}
163
164    /// Adds a new node to the graph.
165
166    /// \warning It adds the new node to the front of the list.
167    /// (i.e. the lastly added node becomes the first.)
168    Node addNode() {     
169      int n;
170     
171      if(first_free_node==-1) {
172        n = nodes.size();
173        nodes.push_back(NodeT());
174      } else {
175        n = first_free_node;
176        first_free_node = nodes[n].next;
177      }
178     
179      nodes[n].next = first_node;
180      if(first_node != -1) nodes[first_node].prev = n;
181      first_node = n;
182      nodes[n].prev = -1;
183     
184      nodes[n].first_in = nodes[n].first_out = -1;
185     
186      return Node(n);
187    }
188   
189    Edge addEdge(Node u, Node v) {
190      int n;     
191
192      if (first_free_edge == -1) {
193        n = edges.size();
194        edges.push_back(EdgeT());
195      } else {
196        n = first_free_edge;
197        first_free_edge = edges[n].next_in;
198      }
199     
200      edges[n].source = u.id;
201      edges[n].target = v.id;
202
203      edges[n].next_out = nodes[u.id].first_out;
204      if(nodes[u.id].first_out != -1) {
205        edges[nodes[u.id].first_out].prev_out = n;
206      }
207     
208      edges[n].next_in = nodes[v.id].first_in;
209      if(nodes[v.id].first_in != -1) {
210        edges[nodes[v.id].first_in].prev_in = n;
211      }
212     
213      edges[n].prev_in = edges[n].prev_out = -1;
214       
215      nodes[u.id].first_out = nodes[v.id].first_in = n;
216
217      return Edge(n);
218    }
219   
220    void erase(const Node& node) {
221      int n = node.id;
222     
223      if(nodes[n].next != -1) {
224        nodes[nodes[n].next].prev = nodes[n].prev;
225      }
226     
227      if(nodes[n].prev != -1) {
228        nodes[nodes[n].prev].next = nodes[n].next;
229      } else {
230        first_node = nodes[n].next;
231      }
232     
233      nodes[n].next = first_free_node;
234      first_free_node = n;
235
236    }
237   
238    void erase(const Edge& edge) {
239      int n = edge.id;
240     
241      if(edges[n].next_in!=-1) {
242        edges[edges[n].next_in].prev_in = edges[n].prev_in;
243      }
244
245      if(edges[n].prev_in!=-1) {
246        edges[edges[n].prev_in].next_in = edges[n].next_in;
247      } else {
248        nodes[edges[n].target].first_in = edges[n].next_in;
249      }
250
251     
252      if(edges[n].next_out!=-1) {
253        edges[edges[n].next_out].prev_out = edges[n].prev_out;
254      }
255
256      if(edges[n].prev_out!=-1) {
257        edges[edges[n].prev_out].next_out = edges[n].next_out;
258      } else {
259        nodes[edges[n].source].first_out = edges[n].next_out;
260      }
261     
262      edges[n].next_in = first_free_edge;
263      first_free_edge = n;     
264
265    }
266
267    void clear() {
268      edges.clear();
269      nodes.clear();
270      first_node = first_free_node = first_free_edge = -1;
271    }
272
273  protected:
274    void changeTarget(Edge e, Node n)
275    {
276      if(edges[e.id].next_in != -1)
277        edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
278      if(edges[e.id].prev_in != -1)
279        edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
280      else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
281      if (nodes[n.id].first_in != -1) {
282        edges[nodes[n.id].first_in].prev_in = e.id;
283      }
284      edges[e.id].target = n.id;
285      edges[e.id].prev_in = -1;
286      edges[e.id].next_in = nodes[n.id].first_in;
287      nodes[n.id].first_in = e.id;
288    }
289    void changeSource(Edge e, Node n)
290    {
291      if(edges[e.id].next_out != -1)
292        edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
293      if(edges[e.id].prev_out != -1)
294        edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
295      else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
296      if (nodes[n.id].first_out != -1) {
297        edges[nodes[n.id].first_out].prev_out = e.id;
298      }
299      edges[e.id].source = n.id;
300      edges[e.id].prev_out = -1;
301      edges[e.id].next_out = nodes[n.id].first_out;
302      nodes[n.id].first_out = e.id;
303    }
304
305  };
306
307  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
308
309  /// \ingroup graphs
310
311  ///A list graph class.
312
313  ///This is a simple and fast erasable graph implementation.
314  ///
315  ///It conforms to the \ref concept::Graph "Graph" concept and it
316  ///also provides several additional useful extra functionalities.
317  ///The most of the member functions and nested classes are
318  ///documented only in the concept class.
319  ///\sa concept::Graph.
320
321  class ListGraph : public ExtendedListGraphBase {
322  public:
323
324    typedef ExtendedListGraphBase Parent;
325
326    ///Add a new node to the graph.
327   
328    /// \return the new node.
329    ///
330    Node addNode() { return Parent::addNode(); }
331
332    ///Add a new edge to the graph.
333   
334    ///Add a new edge to the graph with source node \c s
335    ///and target node \c t.
336    ///\return the new edge.
337    Edge addEdge(const Node& s, const Node& t) {
338      return Parent::addEdge(s, t);
339    }
340
341    /// Changes the target of \c e to \c n
342
343    /// Changes the target of \c e to \c n
344    ///
345    ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
346    ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
347    ///invalidated.
348    void changeTarget(Edge e, Node n) {
349      Parent::changeTarget(e,n);
350    }
351    /// Changes the source of \c e to \c n
352
353    /// Changes the source of \c e to \c n
354    ///
355    ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
356    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
357    ///invalidated.
358    void changeSource(Edge e, Node n) {
359      Parent::changeSource(e,n);
360    }
361
362    /// Invert the direction of an edge.
363
364    ///\note The <tt>Edge</tt>s referencing the changed edge remain
365    ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
366    ///invalidated.
367    void reverseEdge(Edge e) {
368      Node t=target(e);
369      changeTarget(e,source(e));
370      changeSource(e,t);
371    }
372
373    /// \brief Using this it is possible to avoid the superfluous memory
374    /// allocation.
375
376    ///Using this it is possible to avoid the superfluous memory
377    ///allocation: if you know that the graph you want to build will
378    ///contain at least 10 million nodes then it is worth to reserve
379    ///space for this amount before starting to build the graph.
380    void reserveNode(int n) { nodes.reserve(n); };
381
382    /// \brief Using this it is possible to avoid the superfluous memory
383    /// allocation.
384
385    ///Using this it is possible to avoid the superfluous memory
386    ///allocation: see the \ref reserveNode function.
387    void reserveEdge(int n) { edges.reserve(n); };
388
389
390    ///Contract two nodes.
391
392    ///This function contracts two nodes.
393    ///
394    ///Node \p b will be removed but instead of deleting
395    ///incident edges, they will be joined to \p a.
396    ///The last parameter \p r controls whether to remove loops. \c true
397    ///means that loops will be removed.
398    ///
399    ///\note The <tt>Edge</tt>s
400    ///referencing a moved edge remain
401    ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
402    ///may be invalidated.
403    void contract(Node a, Node b, bool r = true)
404    {
405      for(OutEdgeIt e(*this,b);e!=INVALID;) {
406        OutEdgeIt f=e;
407        ++f;
408        if(r && target(e)==a) erase(e);
409        else changeSource(e,a);
410        e=f;
411      }
412      for(InEdgeIt e(*this,b);e!=INVALID;) {
413        InEdgeIt f=e;
414        ++f;
415        if(r && source(e)==a) erase(e);
416        else changeTarget(e,a);
417        e=f;
418      }
419      erase(b);
420    }
421
422    ///Split a node.
423
424    ///This function splits a node. First a new node is added to the graph,
425    ///then the source of each outgoing edge of \c n is moved to this new node.
426    ///If \c connect is \c true (this is the default value), then a new edge
427    ///from \c n to the newly created node is also added.
428    ///\return The newly created node.
429    ///
430    ///\note The <tt>Edge</tt>s
431    ///referencing a moved edge remain
432    ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
433    ///may be invalidated.
434    ///\warning This functionality cannot be used together with the Snapshot
435    ///feature.
436    ///\todo It could be implemented in a bit faster way.
437    Node split(Node n, bool connect = true) {
438      Node b = addNode();
439      for(OutEdgeIt e(*this,n);e!=INVALID;) {
440        OutEdgeIt f=e;
441        ++f;
442        changeSource(e,b);
443        e=f;
444      }
445      if (connect) addEdge(n,b);
446      return b;
447    }
448     
449    ///Split an edge.
450
451    ///This function splits an edge. First a new node \c b is added to
452    ///the graph, then the original edge is re-targeted to \c
453    ///b. Finally an edge from \c b to the original target is added.
454    ///\return The newly created node. 
455    ///\warning This functionality
456    ///cannot be used together with the Snapshot feature.
457    Node split(Edge e) {
458      Node b = addNode();
459      addEdge(b,target(e));
460      changeTarget(e,b);
461      return b;
462    }
463     
464    /// \brief Class to make a snapshot of the graph and restore
465    /// to it later.
466    ///
467    /// Class to make a snapshot of the graph and to restore it
468    /// later.
469    ///
470    /// The newly added nodes and edges can be removed using the
471    /// restore() function.
472    ///
473    /// \warning Edge and node deletions cannot be restored.
474    class Snapshot {
475    public:
476     
477      class UnsupportedOperation : public LogicError {
478      public:
479        virtual const char* exceptionName() const {
480          return "lemon::ListGraph::Snapshot::UnsupportedOperation";
481        }
482      };
483           
484
485    protected:
486
487      typedef Parent::NodeNotifier NodeNotifier;
488
489      class NodeObserverProxy : public NodeNotifier::ObserverBase {
490      public:
491
492        NodeObserverProxy(Snapshot& _snapshot)
493          : snapshot(_snapshot) {}
494
495        using NodeNotifier::ObserverBase::attach;
496        using NodeNotifier::ObserverBase::detach;
497        using NodeNotifier::ObserverBase::attached;
498       
499      protected:
500       
501        virtual void add(const Node& node) {
502          snapshot.addNode(node);
503        }
504        virtual void add(const std::vector<Node>& nodes) {
505          for (int i = nodes.size() - 1; i >= 0; ++i) {
506            snapshot.addNode(nodes[i]);
507          }
508        }
509        virtual void erase(const Node& node) {
510          snapshot.eraseNode(node);
511        }
512        virtual void erase(const std::vector<Node>& nodes) {
513          for (int i = 0; i < (int)nodes.size(); ++i) {
514            if (!snapshot.eraseNode(nodes[i])) break;
515          }
516        }
517        virtual void build() {
518          NodeNotifier* notifier = getNotifier();
519          Node node;
520          std::vector<Node> nodes;
521          for (notifier->first(node); node != INVALID; notifier->next(node)) {
522            nodes.push_back(node);
523          }
524          for (int i = nodes.size() - 1; i >= 0; --i) {
525            snapshot.addNode(nodes[i]);
526          }
527        }
528        virtual void clear() {
529          NodeNotifier* notifier = getNotifier();
530          Node node;
531          for (notifier->first(node); node != INVALID; notifier->next(node)) {
532            if (!snapshot.eraseNode(node)) break;
533          }
534        }
535
536        Snapshot& snapshot;
537      };
538
539      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
540      public:
541
542        EdgeObserverProxy(Snapshot& _snapshot)
543          : snapshot(_snapshot) {}
544
545        using EdgeNotifier::ObserverBase::attach;
546        using EdgeNotifier::ObserverBase::detach;
547        using EdgeNotifier::ObserverBase::attached;
548       
549      protected:
550
551        virtual void add(const Edge& edge) {
552          snapshot.addEdge(edge);
553        }
554        virtual void add(const std::vector<Edge>& edges) {
555          for (int i = edges.size() - 1; i >= 0; ++i) {
556            snapshot.addEdge(edges[i]);
557          }
558        }
559        virtual void erase(const Edge& edge) {
560          snapshot.eraseEdge(edge);
561        }
562        virtual void erase(const std::vector<Edge>& edges) {
563          for (int i = 0; i < (int)edges.size(); ++i) {
564            if (!snapshot.eraseEdge(edges[i])) break;
565          }
566        }
567        virtual void build() {
568          EdgeNotifier* notifier = getNotifier();
569          Edge edge;
570          std::vector<Edge> edges;
571          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
572            edges.push_back(edge);
573          }
574          for (int i = edges.size() - 1; i >= 0; --i) {
575            snapshot.addEdge(edges[i]);
576          }
577        }
578        virtual void clear() {
579          EdgeNotifier* notifier = getNotifier();
580          Edge edge;
581          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
582            if (!snapshot.eraseEdge(edge)) break;
583          }
584        }
585
586        Snapshot& snapshot;
587      };
588     
589      ListGraph *graph;
590
591      NodeObserverProxy node_observer_proxy;
592      EdgeObserverProxy edge_observer_proxy;
593
594      std::list<Node> added_nodes;
595      std::list<Edge> added_edges;
596
597
598      void addNode(const Node& node) {
599        added_nodes.push_front(node);       
600      }
601      bool eraseNode(const Node& node) {
602        std::list<Node>::iterator it =
603          std::find(added_nodes.begin(), added_nodes.end(), node);
604        if (it == added_nodes.end()) {
605          clear();
606          return false;
607        } else {
608          added_nodes.erase(it);
609          return true;
610        }
611      }
612
613      void addEdge(const Edge& edge) {
614        added_edges.push_front(edge);       
615      }
616      bool eraseEdge(const Edge& edge) {
617        std::list<Edge>::iterator it =
618          std::find(added_edges.begin(), added_edges.end(), edge);
619        if (it == added_edges.end()) {
620          clear();
621          return false;
622        } else {
623          added_edges.erase(it);
624          return true;
625        }       
626      }
627
628      void attach(ListGraph &_graph) {
629        graph = &_graph;
630        node_observer_proxy.attach(graph->getNotifier(Node()));
631        edge_observer_proxy.attach(graph->getNotifier(Edge()));
632      }
633           
634      void detach() {
635        node_observer_proxy.detach();
636        edge_observer_proxy.detach();
637      }
638
639      void clear() {
640        detach();
641        added_nodes.clear();
642        added_edges.clear();       
643      }
644
645    public:
646
647      /// \brief Default constructur.
648      ///
649      /// Default constructor.
650      /// To actually make a snapshot you must call save().
651      Snapshot()
652        : graph(0), node_observer_proxy(*this),
653          edge_observer_proxy(*this) {}
654     
655      /// \brief Constructor that immediately makes a snapshot.
656      ///     
657      /// This constructor immediately makes a snapshot of the graph.
658      /// \param _graph The graph we make a snapshot of.
659      Snapshot(ListGraph &_graph)
660        : node_observer_proxy(*this),
661          edge_observer_proxy(*this) {
662        attach(_graph);
663      }
664     
665      /// \brief Make a snapshot.
666      ///
667      /// Make a snapshot of the graph.
668      ///
669      /// This function can be called more than once. In case of a repeated
670      /// call, the previous snapshot gets lost.
671      /// \param _graph The graph we make the snapshot of.
672      void save(ListGraph &_graph) {
673        clear();
674        attach(_graph);
675      }
676     
677      /// \brief Undo the changes until the last snapshot.
678      //
679      /// Undo the changes until last snapshot created by save().
680      ///
681      /// \todo This function might be called undo().
682      void restore() {
683        detach();
684        while(!added_edges.empty()) {
685          graph->erase(added_edges.front());
686          added_edges.pop_front();
687        }
688        while(!added_nodes.empty()) {
689          graph->erase(added_nodes.front());
690          added_nodes.pop_front();
691        }
692      }
693
694      /// \brief Gives back true when the snapshot is valid.
695      ///
696      /// Gives back true when the snapshot is valid.
697      bool valid() const {
698        return node_observer_proxy.attached();
699      }
700    };
701   
702  };
703
704} //namespace lemon
705 
706
707#endif
Note: See TracBrowser for help on using the repository browser.