COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 905:5be029d19c98

Last change on this file since 905:5be029d19c98 was 905:5be029d19c98, checked in by Alpar Juttner, 18 years ago

Some code cleaning in id related stuffs

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