COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 903:2e664d4969d7

Last change on this file since 903:2e664d4969d7 was 897:ef09eee53b09, checked in by Balazs Dezso, 20 years ago

The default constructors are removed from the maps.
The ArrayMap? is the map structure of the graphs.

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