COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/list_graph.h @ 929:882790531532

Last change on this file since 929:882790531532 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

File size: 29.4 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_LIST_GRAPH_H
18#define LEMON_LIST_GRAPH_H
19
20///\ingroup graphs
21///\file
22///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
23
24#include <vector>
25#include <climits>
26
27#include <lemon/invalid.h>
28
29#include <lemon/map_registry.h>
30#include <lemon/array_map.h>
31
32#include <lemon/sym_map.h>
33
34#include <lemon/map_defines.h>
35
36
37namespace lemon {
38
39/// \addtogroup graphs
40/// @{
41
42  ///A list graph class.
43
44  ///This is a simple and fast erasable graph implementation.
45  ///
46  ///It conforms to the
47  ///\ref skeleton::ErasableGraph "ErasableGraph" concept.
48  ///\sa skeleton::ErasableGraph.
49  class ListGraph {
50
51    //Nodes are double linked.
52    //The free nodes are only single linked using the "next" field.
53    struct NodeT
54    {
55      int first_in,first_out;
56      int prev, next;
57    };
58    //Edges are double linked.
59    //The free edges are only single linked using the "next_in" field.
60    struct EdgeT
61    {
62      int head, tail;
63      int prev_in, prev_out;
64      int next_in, next_out;
65    };
66
67    std::vector<NodeT> nodes;
68    //The first node
69    int first_node;
70    //The first free node
71    int first_free_node;
72    std::vector<EdgeT> edges;
73    //The first free edge
74    int first_free_edge;
75   
76  public:
77   
78    typedef ListGraph Graph;
79   
80    class Node;
81    class Edge;
82
83   
84  public:
85
86    class NodeIt;
87    class EdgeIt;
88    class OutEdgeIt;
89    class InEdgeIt;
90
91    // Create map registries.
92    CREATE_MAP_REGISTRIES;
93    // Create node and edge maps.
94    CREATE_MAPS(ArrayMap);
95
96  public:
97
98    ListGraph()
99      : nodes(), first_node(-1),
100        first_free_node(-1), edges(), first_free_edge(-1) {}
101
102    ListGraph(const ListGraph &_g)
103      : nodes(_g.nodes), first_node(_g.first_node),
104        first_free_node(_g.first_free_node), edges(_g.edges),
105        first_free_edge(_g.first_free_edge) {}
106   
107    ///Number of nodes.
108    int nodeNum() const { return nodes.size(); }
109    ///Number of edges.
110    int edgeNum() const { return edges.size(); }
111
112    ///Set the expected maximum number of edges.
113
114    ///With this function, it is possible to set the expected number of edges.
115    ///The use of this fasten the building of the graph and makes
116    ///it possible to avoid the superfluous memory allocation.
117    void reserveEdge(int n) { edges.reserve(n); };
118   
119    /// Maximum node ID.
120   
121    /// Maximum node ID.
122    ///\sa id(Node)
123    int maxNodeId() const { return nodes.size()-1; }
124    /// Maximum edge ID.
125   
126    /// Maximum edge ID.
127    ///\sa id(Edge)
128    int maxEdgeId() const { return edges.size()-1; }
129
130    Node tail(Edge e) const { return edges[e.n].tail; }
131    Node head(Edge e) const { return edges[e.n].head; }
132
133    NodeIt& first(NodeIt& v) const {
134      v=NodeIt(*this); return v; }
135    EdgeIt& first(EdgeIt& e) const {
136      e=EdgeIt(*this); return e; }
137    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
138      e=OutEdgeIt(*this,v); return e; }
139    InEdgeIt& first(InEdgeIt& e, const Node v) const {
140      e=InEdgeIt(*this,v); return e; }
141
142    /// Node ID.
143   
144    /// The ID of a valid Node is a nonnegative integer not greater than
145    /// \ref maxNodeId(). The range of the ID's is not surely continuous
146    /// and the greatest node ID can be actually less then \ref maxNodeId().
147    ///
148    /// The ID of the \ref INVALID node is -1.
149    ///\return The ID of the node \c v.
150    static int id(Node v) { return v.n; }
151    /// Edge ID.
152   
153    /// The ID of a valid Edge is a nonnegative integer not greater than
154    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
155    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
156    ///
157    /// The ID of the \ref INVALID edge is -1.
158    ///\return The ID of the edge \c e.
159    static int id(Edge e) { return e.n; }
160
161    /// Adds a new node to the graph.
162
163    /// \warning It adds the new node to the front of the list.
164    /// (i.e. the lastly added node becomes the first.)
165    Node addNode() {
166      int n;
167     
168      if(first_free_node==-1)
169        {
170          n = nodes.size();
171          nodes.push_back(NodeT());
172        }
173      else {
174        n = first_free_node;
175        first_free_node = nodes[n].next;
176      }
177     
178      nodes[n].next = first_node;
179      if(first_node != -1) nodes[first_node].prev = n;
180      first_node = n;
181      nodes[n].prev = -1;
182     
183      nodes[n].first_in = nodes[n].first_out = -1;
184     
185      Node nn; nn.n=n;
186
187      //Update dynamic maps
188      node_maps.add(nn);
189
190      return nn;
191    }
192   
193    Edge addEdge(Node u, Node v) {
194      int n;
195     
196      if(first_free_edge==-1)
197        {
198          n = edges.size();
199          edges.push_back(EdgeT());
200        }
201      else {
202        n = first_free_edge;
203        first_free_edge = edges[n].next_in;
204      }
205     
206      edges[n].tail = u.n; edges[n].head = v.n;
207
208      edges[n].next_out = nodes[u.n].first_out;
209      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
210      edges[n].next_in = nodes[v.n].first_in;
211      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
212      edges[n].prev_in = edges[n].prev_out = -1;
213       
214      nodes[u.n].first_out = nodes[v.n].first_in = n;
215
216      Edge e; e.n=n;
217
218      //Update dynamic maps
219      edge_maps.add(e);
220
221      return e;
222    }
223   
224    /// Finds an edge between two nodes.
225
226    /// Finds an edge from node \c u to node \c v.
227    ///
228    /// If \c prev is \ref INVALID (this is the default value), then
229    /// It finds the first edge from \c u to \c v. Otherwise it looks for
230    /// the next edge from \c u to \c v after \c prev.
231    /// \return The found edge or INVALID if there is no such an edge.
232    Edge findEdge(Node u,Node v, Edge prev = INVALID)
233    {
234      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
235      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
236      prev.n=e;
237      return prev;
238    }
239   
240  private:
241    void eraseEdge(int n) {
242     
243      if(edges[n].next_in!=-1)
244        edges[edges[n].next_in].prev_in = edges[n].prev_in;
245      if(edges[n].prev_in!=-1)
246        edges[edges[n].prev_in].next_in = edges[n].next_in;
247      else nodes[edges[n].head].first_in = edges[n].next_in;
248     
249      if(edges[n].next_out!=-1)
250        edges[edges[n].next_out].prev_out = edges[n].prev_out;
251      if(edges[n].prev_out!=-1)
252        edges[edges[n].prev_out].next_out = edges[n].next_out;
253      else nodes[edges[n].tail].first_out = edges[n].next_out;
254     
255      edges[n].next_in = first_free_edge;
256      first_free_edge = n;     
257
258      //Update dynamic maps
259      Edge e; e.n=n;
260      edge_maps.erase(e);
261
262    }
263     
264  public:
265
266    void erase(Node nn) {
267      int n=nn.n;
268     
269      int m;
270      while((m=nodes[n].first_in)!=-1) eraseEdge(m);
271      while((m=nodes[n].first_out)!=-1) eraseEdge(m);
272
273      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
274      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
275      else first_node = nodes[n].next;
276     
277      nodes[n].next = first_free_node;
278      first_free_node = n;
279
280      //Update dynamic maps
281      node_maps.erase(nn);
282
283    }
284   
285    void erase(Edge e) { eraseEdge(e.n); }
286
287    void clear() {
288      edge_maps.clear();
289      edges.clear();
290      node_maps.clear();
291      nodes.clear();
292      first_node=first_free_node=first_free_edge=-1;
293    }
294
295    class Node {
296      friend class ListGraph;
297      template <typename T> friend class NodeMap;
298       
299      friend class Edge;
300      friend class OutEdgeIt;
301      friend class InEdgeIt;
302      friend class SymEdge;
303
304    protected:
305      int n;
306      friend int ListGraph::id(Node v);
307      Node(int nn) {n=nn;}
308    public:
309      Node() {}
310      Node (Invalid) { n=-1; }
311      bool operator==(const Node i) const {return n==i.n;}
312      bool operator!=(const Node i) const {return n!=i.n;}
313      bool operator<(const Node i) const {return n<i.n;}
314      //      ///Validity check
315      //      operator bool() { return n!=-1; }
316    };
317   
318    class NodeIt : public Node {
319      const ListGraph *G;
320      friend class ListGraph;
321    public:
322      NodeIt() : Node() { }
323      NodeIt(Invalid i) : Node(i) { }
324      NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
325      NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
326      NodeIt &operator++() {
327        n=G->nodes[n].next;
328        return *this;
329      }
330      //      ///Validity check
331      //      operator bool() { return Node::operator bool(); }     
332    };
333
334    class Edge {
335      friend class ListGraph;
336      template <typename T> friend class EdgeMap;
337
338      friend class SymListGraph;
339     
340      friend class Node;
341      friend class NodeIt;
342    protected:
343      int n;
344      friend int ListGraph::id(Edge e);
345
346    public:
347      /// An Edge with id \c n.
348
349      /// \bug It should be
350      /// obtained by a member function of the Graph.
351      Edge(int nn) {n=nn;}
352
353      Edge() { }
354      Edge (Invalid) { n=-1; }
355      bool operator==(const Edge i) const {return n==i.n;}
356      bool operator!=(const Edge i) const {return n!=i.n;}
357      bool operator<(const Edge i) const {return n<i.n;}
358      //      ///Validity check
359      //      operator bool() { return n!=-1; }
360   };
361   
362    class EdgeIt : public Edge {
363      const ListGraph *G;
364      friend class ListGraph;
365    public:
366      EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
367        int m;
368        for(m=_G.first_node;
369            m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
370        n = (m==-1)?-1:_G.nodes[m].first_in;
371      }
372      EdgeIt (Invalid i) : Edge(i) { }
373      EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
374      EdgeIt() : Edge() { }
375      EdgeIt &operator++() {
376        if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
377        else {
378          int nn;
379          for(nn=G->nodes[G->edges[n].head].next;
380              nn!=-1 && G->nodes[nn].first_in == -1;
381              nn = G->nodes[nn].next) ;
382          n = (nn==-1)?-1:G->nodes[nn].first_in;
383        }
384        return *this;
385      }
386      //      ///Validity check
387      //      operator bool() { return Edge::operator bool(); }     
388    };
389   
390    class OutEdgeIt : public Edge {
391      const ListGraph *G;
392      friend class ListGraph;
393    public:
394      OutEdgeIt() : Edge() { }
395      OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
396      OutEdgeIt (Invalid i) : Edge(i) { }
397
398      OutEdgeIt(const ListGraph& _G,const Node v)
399        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
400      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
401      //      ///Validity check
402      //      operator bool() { return Edge::operator bool(); }     
403    };
404   
405    class InEdgeIt : public Edge {
406      const ListGraph *G;
407      friend class ListGraph;
408    public:
409      InEdgeIt() : Edge() { }
410      InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
411      InEdgeIt (Invalid i) : Edge(i) { }
412      InEdgeIt(const ListGraph& _G,Node v)
413        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
414      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
415      //      ///Validity check
416      //      operator bool() { return Edge::operator bool(); }     
417    };
418  };
419
420  ///Graph for bidirectional edges.
421
422  ///The purpose of this graph structure is to handle graphs
423  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
424  ///of oppositely directed edges.
425  ///There is a new edge map type called
426  ///\ref lemon::SymListGraph::SymEdgeMap "SymEdgeMap"
427  ///that complements this
428  ///feature by
429  ///storing shared values for the edge pairs. The usual
430  ///\ref lemon::skeleton::StaticGraph::EdgeMap "EdgeMap"
431  ///can be used
432  ///as well.
433  ///
434  ///The oppositely directed edge can also be obtained easily
435  ///using \ref lemon::SymListGraph::opposite() "opposite()" member function.
436  ///
437  ///Here erase(Edge) deletes a pair of edges.
438  ///
439  ///\todo this date structure need some reconsiderations. Maybe it
440  ///should be implemented independently from ListGraph.
441 
442  class SymListGraph : public ListGraph
443  {
444  public:
445
446    typedef SymListGraph Graph;
447
448    // Create symmetric map registry.
449    CREATE_SYM_EDGE_MAP_REGISTRY;
450    // Create symmetric edge map.
451    CREATE_SYM_EDGE_MAP(ArrayMap);
452
453    SymListGraph() : ListGraph() { }
454    SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
455    ///Adds a pair of oppositely directed edges to the graph.
456    Edge addEdge(Node u, Node v)
457    {
458      Edge e = ListGraph::addEdge(u,v);
459      Edge f = ListGraph::addEdge(v,u);
460      sym_edge_maps.add(e);
461      sym_edge_maps.add(f);
462     
463      return e;
464    }
465
466    void erase(Node n) { ListGraph::erase(n);}
467    ///The oppositely directed edge.
468
469    ///Returns the oppositely directed
470    ///pair of the edge \c e.
471    static Edge opposite(Edge e)
472    {
473      Edge f;
474      f.n = e.n - 2*(e.n%2) + 1;
475      return f;
476    }
477   
478    ///Removes a pair of oppositely directed edges to the graph.
479    void erase(Edge e) {
480      Edge f = opposite(e);
481      sym_edge_maps.erase(e);
482      sym_edge_maps.erase(f);
483      ListGraph::erase(f);
484      ListGraph::erase(e);
485    }   
486  };
487
488
489  ///A graph class containing only nodes.
490
491  ///This class implements a graph structure without edges.
492  ///The most useful application of this class is to be the node set of an
493  ///\ref EdgeSet class.
494  ///
495  ///It conforms to
496  ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept
497  ///with the exception that you cannot
498  ///add (or delete) edges. The usual edge iterators are exists, but they are
499  ///always \ref INVALID.
500  ///\sa skeleton::ExtendableGraph
501  ///\sa EdgeSet
502  class NodeSet {
503
504    //Nodes are double linked.
505    //The free nodes are only single linked using the "next" field.
506    struct NodeT
507    {
508      int first_in,first_out;
509      int prev, next;
510      //      NodeT() {}
511    };
512
513    std::vector<NodeT> nodes;
514    //The first node
515    int first_node;
516    //The first free node
517    int first_free_node;
518   
519  public:
520
521    typedef NodeSet Graph;
522   
523    class Node;
524    class Edge;
525
526  public:
527
528    class NodeIt;
529    class EdgeIt;
530    class OutEdgeIt;
531    class InEdgeIt;
532   
533    // Create node map registry.
534    CREATE_NODE_MAP_REGISTRY;
535    // Create node maps.
536    CREATE_NODE_MAP(ArrayMap);
537
538    /// Creating empty map structure for edges.
539    template <typename Value>
540    class EdgeMap {
541    public:
542      EdgeMap(const Graph&) {}
543      EdgeMap(const Graph&, const Value&) {}
544
545      EdgeMap(const EdgeMap&) {}
546      template <typename CMap> EdgeMap(const CMap&) {}
547
548      EdgeMap& operator=(const EdgeMap&) {}
549      template <typename CMap> EdgeMap& operator=(const CMap&) {}
550     
551      class ConstIterator {
552      public:
553        bool operator==(const ConstIterator&) {return true;}
554        bool operator!=(const ConstIterator&) {return false;}
555      };
556
557      typedef ConstIterator Iterator;
558     
559      Iterator begin() { return Iterator();}
560      Iterator end() { return Iterator();}
561
562      ConstIterator begin() const { return ConstIterator();}
563      ConstIterator end() const { return ConstIterator();}
564
565    };
566   
567  public:
568
569    ///Default constructor
570    NodeSet()
571      : nodes(), first_node(-1), first_free_node(-1) {}
572    ///Copy constructor
573    NodeSet(const NodeSet &_g)
574      : nodes(_g.nodes), first_node(_g.first_node),
575        first_free_node(_g.first_free_node) {}
576   
577    ///Number of nodes.
578    int nodeNum() const { return nodes.size(); }
579    ///Number of edges.
580    int edgeNum() const { return 0; }
581
582    /// Maximum node ID.
583   
584    /// Maximum node ID.
585    ///\sa id(Node)
586    int maxNodeId() const { return nodes.size()-1; }
587    /// Maximum edge ID.
588   
589    /// Maximum edge ID.
590    ///\sa id(Edge)
591    int maxEdgeId() const { return 0; }
592
593    Node tail(Edge e) const { return INVALID; }
594    Node head(Edge e) const { return INVALID; }
595
596    NodeIt& first(NodeIt& v) const {
597      v=NodeIt(*this); return v; }
598    EdgeIt& first(EdgeIt& e) const {
599      e=EdgeIt(*this); return e; }
600    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
601      e=OutEdgeIt(*this,v); return e; }
602    InEdgeIt& first(InEdgeIt& e, const Node v) const {
603      e=InEdgeIt(*this,v); return e; }
604
605    /// Node ID.
606   
607    /// The ID of a valid Node is a nonnegative integer not greater than
608    /// \ref maxNodeId(). The range of the ID's is not surely continuous
609    /// and the greatest node ID can be actually less then \ref maxNodeId().
610    ///
611    /// The ID of the \ref INVALID node is -1.
612    ///\return The ID of the node \c v.
613    static int id(Node v) { return v.n; }
614    /// Edge ID.
615   
616    /// The ID of a valid Edge is a nonnegative integer not greater than
617    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
618    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
619    ///
620    /// The ID of the \ref INVALID edge is -1.
621    ///\return The ID of the edge \c e.
622    static int id(Edge e) { return -1; }
623
624    /// Adds a new node to the graph.
625
626    /// \warning It adds the new node to the front of the list.
627    /// (i.e. the lastly added node becomes the first.)
628    Node addNode() {
629      int n;
630     
631      if(first_free_node==-1)
632        {
633          n = nodes.size();
634          nodes.push_back(NodeT());
635        }
636      else {
637        n = first_free_node;
638        first_free_node = nodes[n].next;
639      }
640     
641      nodes[n].next = first_node;
642      if(first_node != -1) nodes[first_node].prev = n;
643      first_node = n;
644      nodes[n].prev = -1;
645     
646      nodes[n].first_in = nodes[n].first_out = -1;
647     
648      Node nn; nn.n=n;
649
650      //Update dynamic maps
651      node_maps.add(nn);
652
653      return nn;
654    }
655   
656    void erase(Node nn) {
657      int n=nn.n;
658     
659      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
660      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
661      else first_node = nodes[n].next;
662     
663      nodes[n].next = first_free_node;
664      first_free_node = n;
665
666      //Update dynamic maps
667      node_maps.erase(nn);
668    }
669   
670       
671    Edge findEdge(Node u,Node v, Edge prev = INVALID)
672    {
673      return INVALID;
674    }
675   
676    void clear() {
677      node_maps.clear();
678      nodes.clear();
679      first_node = first_free_node = -1;
680    }
681
682    class Node {
683      friend class NodeSet;
684      template <typename T> friend class NodeMap;
685     
686      friend class Edge;
687      friend class OutEdgeIt;
688      friend class InEdgeIt;
689
690    protected:
691      int n;
692      friend int NodeSet::id(Node v);
693      Node(int nn) {n=nn;}
694    public:
695      Node() {}
696      Node (Invalid i) { n=-1; }
697      bool operator==(const Node i) const {return n==i.n;}
698      bool operator!=(const Node i) const {return n!=i.n;}
699      bool operator<(const Node i) const {return n<i.n;}
700    };
701   
702    class NodeIt : public Node {
703      const NodeSet *G;
704      friend class NodeSet;
705    public:
706      NodeIt() : Node() { }
707      NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
708      NodeIt(Invalid i) : Node(i) { }
709      NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
710      NodeIt &operator++() {
711        n=G->nodes[n].next;
712        return *this;
713      }
714    };
715
716    class Edge {
717    public:
718      Edge() { }
719      Edge (Invalid) { }
720      bool operator==(const Edge i) const {return true;}
721      bool operator!=(const Edge i) const {return false;}
722      bool operator<(const Edge i) const {return false;}
723    };
724   
725    class EdgeIt : public Edge {
726    public:
727      EdgeIt(const NodeSet& G) : Edge() { }
728      EdgeIt(const NodeSet&, Edge) : Edge() { }
729      EdgeIt (Invalid i) : Edge(i) { }
730      EdgeIt() : Edge() { }
731      EdgeIt operator++() { return INVALID; }
732    };
733   
734    class OutEdgeIt : public Edge {
735      friend class NodeSet;
736    public:
737      OutEdgeIt() : Edge() { }
738      OutEdgeIt(const NodeSet&, Edge) : Edge() { }
739      OutEdgeIt (Invalid i) : Edge(i) { }
740      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
741      OutEdgeIt operator++() { return INVALID; }
742    };
743   
744    class InEdgeIt : public Edge {
745      friend class NodeSet;
746    public:
747      InEdgeIt() : Edge() { }
748      InEdgeIt(const NodeSet&, Edge) : Edge() { }
749      InEdgeIt (Invalid i) : Edge(i) { }
750      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
751      InEdgeIt operator++() { return INVALID; }
752    };
753
754  };
755
756
757
758  ///Graph structure using a node set of another graph.
759
760  ///This structure can be used to establish another graph over a node set
761  /// of an existing one. The node iterator will go through the nodes of the
762  /// original graph, and the NodeMap's of both graphs will convert to
763  /// each other.
764  ///
765  ///\warning Adding or deleting nodes from the graph is not safe if an
766  ///\ref EdgeSet is currently attached to it!
767  ///
768  ///\todo Make it possible to add/delete edges from the base graph
769  ///(and from \ref EdgeSet, as well)
770  ///
771  ///\param GG The type of the graph which shares its node set with this class.
772  ///Its interface must conform to the
773  ///\ref skeleton::StaticGraph "StaticGraph" concept.
774  ///
775  ///It conforms to the
776  ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept.
777  ///\sa skeleton::ExtendableGraph.
778  ///\sa NodeSet.
779  template<typename GG>
780  class EdgeSet {
781
782    typedef GG NodeGraphType;
783
784    NodeGraphType &G;
785
786  public:
787
788    class Node;
789    class Edge;
790    class OutEdgeIt;
791    class InEdgeIt;
792    class SymEdge;
793
794    typedef EdgeSet Graph;
795
796    int id(Node v) const;
797
798    class Node : public NodeGraphType::Node {
799      friend class EdgeSet;
800     
801      friend class Edge;
802      friend class OutEdgeIt;
803      friend class InEdgeIt;
804      friend class SymEdge;
805
806    public:
807      friend int EdgeSet::id(Node v) const;
808    public:
809      Node() : NodeGraphType::Node() {}
810      Node (Invalid i) : NodeGraphType::Node(i) {}
811      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
812    };
813   
814    class NodeIt : public NodeGraphType::NodeIt {
815      friend class EdgeSet;
816    public:
817      NodeIt() : NodeGraphType::NodeIt() { }
818      NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
819      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
820      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
821      NodeIt(const typename NodeGraphType::NodeIt &n)
822        : NodeGraphType::NodeIt(n) {}
823
824      operator Node() { return Node(*this);}
825      NodeIt &operator++()
826      { this->NodeGraphType::NodeIt::operator++(); return *this;}
827    };
828
829  private:
830    //Edges are double linked.
831    //The free edges are only single linked using the "next_in" field.
832    struct NodeT
833    {
834      int first_in,first_out;
835      NodeT() : first_in(-1), first_out(-1) { }
836    };
837
838    struct EdgeT
839    {
840      Node head, tail;
841      int prev_in, prev_out;
842      int next_in, next_out;
843    };
844
845   
846    typename NodeGraphType::template NodeMap<NodeT> nodes;
847   
848    std::vector<EdgeT> edges;
849    //The first free edge
850    int first_free_edge;
851   
852  public:
853   
854    class Node;
855    class Edge;
856
857    class NodeIt;
858    class EdgeIt;
859    class OutEdgeIt;
860    class InEdgeIt;
861
862
863    // Create edge map registry.
864    CREATE_EDGE_MAP_REGISTRY;
865    // Create edge maps.
866    CREATE_EDGE_MAP(ArrayMap);
867
868    // Import node maps from the NodeGraphType.
869    IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
870   
871   
872  public:
873
874    ///Constructor
875   
876    ///Construates a new graph based on the nodeset of an existing one.
877    ///\param _G the base graph.
878    explicit EdgeSet(NodeGraphType &_G)
879      : G(_G), nodes(_G), edges(),
880        first_free_edge(-1) {}
881    ///Copy constructor
882
883    ///Makes a copy of an EdgeSet.
884    ///It will be based on the same graph.
885    explicit EdgeSet(const EdgeSet &_g)
886      : G(_g.G), nodes(_g.G), edges(_g.edges),
887        first_free_edge(_g.first_free_edge) {}
888   
889    ///Number of nodes.
890    int nodeNum() const { return G.nodeNum(); }
891    ///Number of edges.
892    int edgeNum() const { return edges.size(); }
893
894    /// Maximum node ID.
895   
896    /// Maximum node ID.
897    ///\sa id(Node)
898    int maxNodeId() const { return G.maxNodeId(); }
899    /// Maximum edge ID.
900   
901    /// Maximum edge ID.
902    ///\sa id(Edge)
903    int maxEdgeId() const { return edges.size()-1; }
904
905    Node tail(Edge e) const { return edges[e.n].tail; }
906    Node head(Edge e) const { return edges[e.n].head; }
907
908    NodeIt& first(NodeIt& v) const {
909      v=NodeIt(*this); return v; }
910    EdgeIt& first(EdgeIt& e) const {
911      e=EdgeIt(*this); return e; }
912    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
913      e=OutEdgeIt(*this,v); return e; }
914    InEdgeIt& first(InEdgeIt& e, const Node v) const {
915      e=InEdgeIt(*this,v); return e; }
916
917    /// Node ID.
918   
919    /// The ID of a valid Node is a nonnegative integer not greater than
920    /// \ref maxNodeId(). The range of the ID's is not surely continuous
921    /// and the greatest node ID can be actually less then \ref maxNodeId().
922    ///
923    /// The ID of the \ref INVALID node is -1.
924    ///\return The ID of the node \c v.
925    int id(Node v) { return G.id(v); }
926    /// Edge ID.
927   
928    /// The ID of a valid Edge is a nonnegative integer not greater than
929    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
930    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
931    ///
932    /// The ID of the \ref INVALID edge is -1.
933    ///\return The ID of the edge \c e.
934    static int id(Edge e) { return e.n; }
935
936    /// Adds a new node to the graph.
937    Node addNode() { return G.addNode(); }
938   
939    Edge addEdge(Node u, Node v) {
940      int n;
941     
942      if(first_free_edge==-1)
943        {
944          n = edges.size();
945          edges.push_back(EdgeT());
946        }
947      else {
948        n = first_free_edge;
949        first_free_edge = edges[n].next_in;
950      }
951     
952      edges[n].tail = u; edges[n].head = v;
953
954      edges[n].next_out = nodes[u].first_out;
955      if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
956      edges[n].next_in = nodes[v].first_in;
957      if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
958      edges[n].prev_in = edges[n].prev_out = -1;
959       
960      nodes[u].first_out = nodes[v].first_in = n;
961
962      Edge e; e.n=n;
963
964      //Update dynamic maps
965      edge_maps.add(e);
966
967      return e;
968    }
969
970    /// Finds an edge between two nodes.
971
972    /// Finds an edge from node \c u to node \c v.
973    ///
974    /// If \c prev is \ref INVALID (this is the default value), then
975    /// It finds the first edge from \c u to \c v. Otherwise it looks for
976    /// the next edge from \c u to \c v after \c prev.
977    /// \return The found edge or INVALID if there is no such an edge.
978    Edge findEdge(Node u,Node v, Edge prev = INVALID)
979    {
980      int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
981      while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
982      prev.n=e;
983      return prev;
984    }
985   
986  private:
987    void eraseEdge(int n) {
988     
989      if(edges[n].next_in!=-1)
990        edges[edges[n].next_in].prev_in = edges[n].prev_in;
991      if(edges[n].prev_in!=-1)
992        edges[edges[n].prev_in].next_in = edges[n].next_in;
993      else nodes[edges[n].head].first_in = edges[n].next_in;
994     
995      if(edges[n].next_out!=-1)
996        edges[edges[n].next_out].prev_out = edges[n].prev_out;
997      if(edges[n].prev_out!=-1)
998        edges[edges[n].prev_out].next_out = edges[n].next_out;
999      else nodes[edges[n].tail].first_out = edges[n].next_out;
1000     
1001      edges[n].next_in = first_free_edge;
1002      first_free_edge = -1;     
1003
1004      //Update dynamic maps
1005      Edge e; e.n = n;
1006      edge_maps.erase(e);
1007    }
1008     
1009  public:
1010
1011    void erase(Edge e) { eraseEdge(e.n); }
1012
1013    ///Clear all edges. (Doesn't clear the nodes!)
1014    void clear() {
1015      edge_maps.clear();
1016      edges.clear();
1017      first_free_edge=-1;
1018    }
1019
1020
1021    class Edge {
1022    public:
1023      friend class EdgeSet;
1024      template <typename T> friend class EdgeMap;
1025
1026      friend class Node;
1027      friend class NodeIt;
1028    protected:
1029      int n;
1030      friend int EdgeSet::id(Edge e) const;
1031
1032      Edge(int nn) {n=nn;}
1033    public:
1034      Edge() { }
1035      Edge (Invalid) { n=-1; }
1036      bool operator==(const Edge i) const {return n==i.n;}
1037      bool operator!=(const Edge i) const {return n!=i.n;}
1038      bool operator<(const Edge i) const {return n<i.n;}
1039    };
1040   
1041    class EdgeIt : public Edge {
1042      friend class EdgeSet;
1043      template <typename T> friend class EdgeMap;
1044   
1045      const EdgeSet *G;
1046    public:
1047      EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
1048        NodeIt m;
1049        for(G->first(m);
1050            m!=INVALID && G->nodes[m].first_in == -1;  ++m);
1051        ///\bug AJJAJ! This is a non sense!!!!!!!
1052        this->n = m!=INVALID?-1:G->nodes[m].first_in;
1053      }
1054      EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1055      EdgeIt (Invalid i) : Edge(i) { }
1056      EdgeIt() : Edge() { }
1057      ///.
1058     
1059      ///\bug UNIMPLEMENTED!!!!!
1060      //
1061      EdgeIt &operator++() {
1062        return *this;
1063      }
1064    };
1065   
1066    class OutEdgeIt : public Edge {
1067      const EdgeSet *G;
1068      friend class EdgeSet;
1069    public:
1070      OutEdgeIt() : Edge() { }
1071      OutEdgeIt (Invalid i) : Edge(i) { }
1072      OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1073
1074      OutEdgeIt(const EdgeSet& _G,const Node v) :
1075        Edge(_G.nodes[v].first_out), G(&_G) { }
1076      OutEdgeIt &operator++() {
1077        Edge::n = G->edges[Edge::n].next_out;
1078        return *this;
1079      }
1080    };
1081   
1082    class InEdgeIt : public Edge {
1083      const EdgeSet *G;
1084      friend class EdgeSet;
1085    public:
1086      InEdgeIt() : Edge() { }
1087      InEdgeIt (Invalid i) : Edge(i) { }
1088      InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1089      InEdgeIt(const EdgeSet& _G,Node v)
1090        : Edge(_G.nodes[v].first_in), G(&_G) { }
1091      InEdgeIt &operator++() {
1092        Edge::n = G->edges[Edge::n].next_in;
1093        return *this;
1094      }
1095    };
1096   
1097  };
1098
1099  template<typename GG>
1100  inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1101
1102/// @} 
1103
1104} //namespace lemon
1105
1106#endif //LEMON_LIST_GRAPH_H
Note: See TracBrowser for help on using the repository browser.