COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 880:9d0bfd35b97c

Last change on this file since 880:9d0bfd35b97c was 880:9d0bfd35b97c, checked in by Alpar Juttner, 16 years ago
  • Name changing: XYZGraphSkeleton -> XYZGraph
  • Fix some bad \ref's in the doc.
File size: 31.0 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/default_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(DefaultMap);
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    /// Importing maps from the base class ListGraph.
446    KEEP_MAPS(ListGraph, SymListGraph);
447
448    /// Creating symmetric map registry.
449    CREATE_SYM_EDGE_MAP_REGISTRY;
450    /// Creating symmetric edge map.
451    CREATE_SYM_EDGE_MAP(DefaultMap);
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.idref() = e.idref() - 2*(e.idref()%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    /// Creating node map registry.
534    CREATE_NODE_MAP_REGISTRY;
535    /// Creating node maps.
536    CREATE_NODE_MAP(DefaultMap);
537
538    /// Creating empty map structure for edges.
539    template <typename Value>
540    class EdgeMap {
541    public:
542      EdgeMap() {}
543      EdgeMap(const Graph&) {}
544      EdgeMap(const Graph&, const Value&) {}
545
546      EdgeMap(const EdgeMap&) {}
547      template <typename CMap> EdgeMap(const CMap&) {}
548
549      EdgeMap& operator=(const EdgeMap&) {}
550      template <typename CMap> EdgeMap& operator=(const CMap&) {}
551     
552      class ConstIterator {
553      public:
554        bool operator==(const ConstIterator&) {return true;}
555        bool operator!=(const ConstIterator&) {return false;}
556      };
557
558      typedef ConstIterator Iterator;
559     
560      Iterator begin() { return Iterator();}
561      Iterator end() { return Iterator();}
562
563      ConstIterator begin() const { return ConstIterator();}
564      ConstIterator end() const { return ConstIterator();}
565
566    };
567   
568  public:
569
570    ///Default constructor
571    NodeSet()
572      : nodes(), first_node(-1), first_free_node(-1) {}
573    ///Copy constructor
574    NodeSet(const NodeSet &_g)
575      : nodes(_g.nodes), first_node(_g.first_node),
576        first_free_node(_g.first_free_node) {}
577   
578    ///Number of nodes.
579    int nodeNum() const { return nodes.size(); }
580    ///Number of edges.
581    int edgeNum() const { return 0; }
582
583    /// Maximum node ID.
584   
585    /// Maximum node ID.
586    ///\sa id(Node)
587    int maxNodeId() const { return nodes.size()-1; }
588    /// Maximum edge ID.
589   
590    /// Maximum edge ID.
591    ///\sa id(Edge)
592    int maxEdgeId() const { return 0; }
593
594    Node tail(Edge e) const { return INVALID; }
595    Node head(Edge e) const { return INVALID; }
596
597    NodeIt& first(NodeIt& v) const {
598      v=NodeIt(*this); return v; }
599    EdgeIt& first(EdgeIt& e) const {
600      e=EdgeIt(*this); return e; }
601    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
602      e=OutEdgeIt(*this,v); return e; }
603    InEdgeIt& first(InEdgeIt& e, const Node v) const {
604      e=InEdgeIt(*this,v); return e; }
605
606    /// Node ID.
607   
608    /// The ID of a valid Node is a nonnegative integer not greater than
609    /// \ref maxNodeId(). The range of the ID's is not surely continuous
610    /// and the greatest node ID can be actually less then \ref maxNodeId().
611    ///
612    /// The ID of the \ref INVALID node is -1.
613    ///\return The ID of the node \c v.
614    int id(Node v) const { return v.n; }
615    /// Edge ID.
616   
617    /// The ID of a valid Edge is a nonnegative integer not greater than
618    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
619    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
620    ///
621    /// The ID of the \ref INVALID edge is -1.
622    ///\return The ID of the edge \c e.
623    int id(Edge e) const { return -1; }
624
625    /// Adds a new node to the graph.
626
627    /// \warning It adds the new node to the front of the list.
628    /// (i.e. the lastly added node becomes the first.)
629    Node addNode() {
630      int n;
631     
632      if(first_free_node==-1)
633        {
634          n = nodes.size();
635          nodes.push_back(NodeT());
636        }
637      else {
638        n = first_free_node;
639        first_free_node = nodes[n].next;
640      }
641     
642      nodes[n].next = first_node;
643      if(first_node != -1) nodes[first_node].prev = n;
644      first_node = n;
645      nodes[n].prev = -1;
646     
647      nodes[n].first_in = nodes[n].first_out = -1;
648     
649      Node nn; nn.n=n;
650
651      //Update dynamic maps
652      node_maps.add(nn);
653
654      return nn;
655    }
656   
657    void erase(Node nn) {
658      int n=nn.n;
659     
660      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
661      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
662      else first_node = nodes[n].next;
663     
664      nodes[n].next = first_free_node;
665      first_free_node = n;
666
667      //Update dynamic maps
668      node_maps.erase(nn);
669    }
670   
671       
672    Edge findEdge(Node u,Node v, Edge prev = INVALID)
673    {
674      return INVALID;
675    }
676   
677    void clear() {
678      node_maps.clear();
679      nodes.clear();
680      first_node = first_free_node = -1;
681    }
682
683    class Node {
684      friend class NodeSet;
685      template <typename T> friend class NodeMap;
686     
687      friend class Edge;
688      friend class OutEdgeIt;
689      friend class InEdgeIt;
690
691    protected:
692      int n;
693      friend int NodeSet::id(Node v) const;
694      Node(int nn) {n=nn;}
695    public:
696      Node() {}
697      Node (Invalid i) { n=-1; }
698      bool operator==(const Node i) const {return n==i.n;}
699      bool operator!=(const Node i) const {return n!=i.n;}
700      bool operator<(const Node i) const {return n<i.n;}
701    };
702   
703    class NodeIt : public Node {
704      const NodeSet *G;
705      friend class NodeSet;
706    public:
707      NodeIt() : Node() { }
708      NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
709      NodeIt(Invalid i) : Node(i) { }
710      NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
711      NodeIt &operator++() {
712        n=G->nodes[n].next;
713        return *this;
714      }
715    };
716
717    class Edge {
718      //friend class NodeSet;
719      //template <typename T> friend class EdgeMap;
720
721      //template <typename T> friend class SymNodeSet::SymEdgeMap;     
722      //friend Edge SymNodeSet::opposite(Edge) const;
723     
724      //      friend class Node;
725      //      friend class NodeIt;
726    protected:
727      //friend int NodeSet::id(Edge e) const;
728      //      Edge(int nn) {}
729    public:
730      Edge() { }
731      Edge (Invalid) { }
732      bool operator==(const Edge i) const {return true;}
733      bool operator!=(const Edge i) const {return false;}
734      bool operator<(const Edge i) const {return false;}
735      ///\bug This is a workaround until somebody tells me how to
736      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
737      //      int idref() {return -1;}
738      //      int idref() const {return -1;}
739    };
740   
741    class EdgeIt : public Edge {
742      //friend class NodeSet;
743    public:
744      EdgeIt(const NodeSet& G) : Edge() { }
745      EdgeIt(const NodeSet&, Edge) : Edge() { }
746      EdgeIt (Invalid i) : Edge(i) { }
747      EdgeIt() : Edge() { }
748      ///\bug This is a workaround until somebody tells me how to
749      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
750      //      int idref() {return -1;}
751      EdgeIt operator++() { return INVALID; }
752    };
753   
754    class OutEdgeIt : public Edge {
755      friend class NodeSet;
756    public:
757      OutEdgeIt() : Edge() { }
758      OutEdgeIt(const NodeSet&, Edge) : Edge() { }
759      OutEdgeIt (Invalid i) : Edge(i) { }
760      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
761      OutEdgeIt operator++() { return INVALID; }
762    };
763   
764    class InEdgeIt : public Edge {
765      friend class NodeSet;
766    public:
767      InEdgeIt() : Edge() { }
768      InEdgeIt(const NodeSet&, Edge) : Edge() { }
769      InEdgeIt (Invalid i) : Edge(i) { }
770      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
771      InEdgeIt operator++() { return INVALID; }
772    };
773
774  };
775
776
777
778  ///Graph structure using a node set of another graph.
779
780  ///This structure can be used to establish another graph over a node set
781  /// of an existing one. The node iterator will go through the nodes of the
782  /// original graph, and the NodeMap's of both graphs will convert to
783  /// each other.
784  ///
785  ///\warning Adding or deleting nodes from the graph is not safe if an
786  ///\ref EdgeSet is currently attached to it!
787  ///
788  ///\todo Make it possible to add/delete edges from the base graph
789  ///(and from \ref EdgeSet, as well)
790  ///
791  ///\param GG The type of the graph which shares its node set with this class.
792  ///Its interface must conform to the
793  ///\ref skeleton::StaticGraph "StaticGraph" concept.
794  ///
795  ///It conforms to the
796  ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept.
797  ///\sa skeleton::ExtendableGraph.
798  ///\sa NodeSet.
799  template<typename GG>
800  class EdgeSet {
801
802    typedef GG NodeGraphType;
803
804    NodeGraphType &G;
805
806  public:
807
808    class Node;
809    class Edge;
810    class OutEdgeIt;
811    class InEdgeIt;
812    class SymEdge;
813
814    typedef EdgeSet Graph;
815
816    int id(Node v) const;
817
818    class Node : public NodeGraphType::Node {
819      friend class EdgeSet;
820      //      template <typename T> friend class NodeMap;
821     
822      friend class Edge;
823      friend class OutEdgeIt;
824      friend class InEdgeIt;
825      friend class SymEdge;
826
827    public:
828      friend int EdgeSet::id(Node v) const;
829      //      Node(int nn) {n=nn;}
830    public:
831      Node() : NodeGraphType::Node() {}
832      Node (Invalid i) : NodeGraphType::Node(i) {}
833      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
834    };
835   
836    class NodeIt : public NodeGraphType::NodeIt {
837      friend class EdgeSet;
838    public:
839      NodeIt() : NodeGraphType::NodeIt() { }
840      NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
841      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
842      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
843      NodeIt(const typename NodeGraphType::NodeIt &n)
844        : NodeGraphType::NodeIt(n) {}
845
846      operator Node() { return Node(*this);}
847      NodeIt &operator++()
848      { this->NodeGraphType::NodeIt::operator++(); return *this;}
849    };
850
851  private:
852    //Edges are double linked.
853    //The free edges are only single linked using the "next_in" field.
854    struct NodeT
855    {
856      int first_in,first_out;
857      NodeT() : first_in(-1), first_out(-1) { }
858    };
859
860    struct EdgeT
861    {
862      Node head, tail;
863      int prev_in, prev_out;
864      int next_in, next_out;
865    };
866
867   
868    typename NodeGraphType::template NodeMap<NodeT> nodes;
869   
870    std::vector<EdgeT> edges;
871    //The first free edge
872    int first_free_edge;
873   
874  public:
875   
876    class Node;
877    class Edge;
878
879    class NodeIt;
880    class EdgeIt;
881    class OutEdgeIt;
882    class InEdgeIt;
883
884
885    /// Creates edge map registry.
886    CREATE_EDGE_MAP_REGISTRY;
887    /// Creates edge maps.
888    CREATE_EDGE_MAP(DefaultMap);
889
890    /// Imports node maps from the NodeGraphType.
891    IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
892   
893   
894  public:
895
896    ///Constructor
897   
898    ///Construates a new graph based on the nodeset of an existing one.
899    ///\param _G the base graph.
900    explicit EdgeSet(NodeGraphType &_G)
901      : G(_G), nodes(_G), edges(),
902        first_free_edge(-1) {}
903    ///Copy constructor
904
905    ///Makes a copy of an EdgeSet.
906    ///It will be based on the same graph.
907    explicit EdgeSet(const EdgeSet &_g)
908      : G(_g.G), nodes(_g.G), edges(_g.edges),
909        first_free_edge(_g.first_free_edge) {}
910   
911    ///Number of nodes.
912    int nodeNum() const { return G.nodeNum(); }
913    ///Number of edges.
914    int edgeNum() const { return edges.size(); }
915
916    /// Maximum node ID.
917   
918    /// Maximum node ID.
919    ///\sa id(Node)
920    int maxNodeId() const { return G.maxNodeId(); }
921    /// Maximum edge ID.
922   
923    /// Maximum edge ID.
924    ///\sa id(Edge)
925    int maxEdgeId() const { return edges.size()-1; }
926
927    Node tail(Edge e) const { return edges[e.n].tail; }
928    Node head(Edge e) const { return edges[e.n].head; }
929
930    NodeIt& first(NodeIt& v) const {
931      v=NodeIt(*this); return v; }
932    EdgeIt& first(EdgeIt& e) const {
933      e=EdgeIt(*this); return e; }
934    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
935      e=OutEdgeIt(*this,v); return e; }
936    InEdgeIt& first(InEdgeIt& e, const Node v) const {
937      e=InEdgeIt(*this,v); return e; }
938
939    /// Node ID.
940   
941    /// The ID of a valid Node is a nonnegative integer not greater than
942    /// \ref maxNodeId(). The range of the ID's is not surely continuous
943    /// and the greatest node ID can be actually less then \ref maxNodeId().
944    ///
945    /// The ID of the \ref INVALID node is -1.
946    ///\return The ID of the node \c v.
947    int id(Node v) { return G.id(v); }
948    /// Edge ID.
949   
950    /// The ID of a valid Edge is a nonnegative integer not greater than
951    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
952    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
953    ///
954    /// The ID of the \ref INVALID edge is -1.
955    ///\return The ID of the edge \c e.
956    int id(Edge e) const { return e.n; }
957
958    /// Adds a new node to the graph.
959    Node addNode() { return G.addNode(); }
960   
961    Edge addEdge(Node u, Node v) {
962      int n;
963     
964      if(first_free_edge==-1)
965        {
966          n = edges.size();
967          edges.push_back(EdgeT());
968        }
969      else {
970        n = first_free_edge;
971        first_free_edge = edges[n].next_in;
972      }
973     
974      edges[n].tail = u; edges[n].head = v;
975
976      edges[n].next_out = nodes[u].first_out;
977      if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
978      edges[n].next_in = nodes[v].first_in;
979      if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
980      edges[n].prev_in = edges[n].prev_out = -1;
981       
982      nodes[u].first_out = nodes[v].first_in = n;
983
984      Edge e; e.n=n;
985
986      //Update dynamic maps
987      edge_maps.add(e);
988
989      return e;
990    }
991
992    /// Finds an edge between two nodes.
993
994    /// Finds an edge from node \c u to node \c v.
995    ///
996    /// If \c prev is \ref INVALID (this is the default value), then
997    /// It finds the first edge from \c u to \c v. Otherwise it looks for
998    /// the next edge from \c u to \c v after \c prev.
999    /// \return The found edge or INVALID if there is no such an edge.
1000    Edge findEdge(Node u,Node v, Edge prev = INVALID)
1001    {
1002      int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
1003      while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
1004      prev.n=e;
1005      return prev;
1006    }
1007   
1008  private:
1009    void eraseEdge(int n) {
1010     
1011      if(edges[n].next_in!=-1)
1012        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1013      if(edges[n].prev_in!=-1)
1014        edges[edges[n].prev_in].next_in = edges[n].next_in;
1015      else nodes[edges[n].head].first_in = edges[n].next_in;
1016     
1017      if(edges[n].next_out!=-1)
1018        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1019      if(edges[n].prev_out!=-1)
1020        edges[edges[n].prev_out].next_out = edges[n].next_out;
1021      else nodes[edges[n].tail].first_out = edges[n].next_out;
1022     
1023      edges[n].next_in = first_free_edge;
1024      first_free_edge = -1;     
1025
1026      //Update dynamic maps
1027      Edge e; e.n = n;
1028      edge_maps.erase(e);
1029    }
1030     
1031  public:
1032
1033//     void erase(Node nn) {
1034//       int n=nn.n;
1035//       int m;
1036//       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1037//       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1038//     }
1039   
1040    void erase(Edge e) { eraseEdge(e.n); }
1041
1042    ///Clear all edges. (Doesn't clear the nodes!)
1043    void clear() {
1044      edge_maps.clear();
1045      edges.clear();
1046      first_free_edge=-1;
1047    }
1048
1049
1050    class Edge {
1051    public:
1052      friend class EdgeSet;
1053      template <typename T> friend class EdgeMap;
1054
1055      friend class Node;
1056      friend class NodeIt;
1057    public:
1058      ///\bug It should be at least protected
1059      ///
1060      int n;
1061    protected:
1062      friend int EdgeSet::id(Edge e) const;
1063
1064      Edge(int nn) {n=nn;}
1065    public:
1066      Edge() { }
1067      Edge (Invalid) { n=-1; }
1068      bool operator==(const Edge i) const {return n==i.n;}
1069      bool operator!=(const Edge i) const {return n!=i.n;}
1070      bool operator<(const Edge i) const {return n<i.n;}
1071      ///\bug This is a workaround until somebody tells me how to
1072      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1073      int &idref() {return n;}
1074      const int &idref() const {return n;}
1075    };
1076   
1077    class EdgeIt : public Edge {
1078      friend class EdgeSet;
1079      template <typename T> friend class EdgeMap;
1080   
1081      const EdgeSet *G;
1082    public:
1083      EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
1084        //              typename NodeGraphType::Node m;
1085        NodeIt m;
1086        for(G->first(m);
1087            m!=INVALID && G->nodes[m].first_in == -1;  ++m);
1088        ///\bug AJJAJ! This is a non sense!!!!!!!
1089        this->n = m!=INVALID?-1:G->nodes[m].first_in;
1090      }
1091      EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1092      EdgeIt (Invalid i) : Edge(i) { }
1093      EdgeIt() : Edge() { }
1094      ///.
1095     
1096      ///\bug UNIMPLEMENTED!!!!!
1097      //
1098      EdgeIt &operator++() {
1099        return *this;
1100      }
1101       ///\bug This is a workaround until somebody tells me how to
1102      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1103      int &idref() {return this->n;}
1104    };
1105   
1106    class OutEdgeIt : public Edge {
1107      const EdgeSet *G;
1108      friend class EdgeSet;
1109    public:
1110      OutEdgeIt() : Edge() { }
1111      OutEdgeIt (Invalid i) : Edge(i) { }
1112      OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1113
1114      OutEdgeIt(const EdgeSet& _G,const Node v) :
1115        Edge(_G.nodes[v].first_out), G(&_G) { }
1116      OutEdgeIt &operator++() {
1117        Edge::n = G->edges[Edge::n].next_out;
1118        return *this;
1119      }
1120    };
1121   
1122    class InEdgeIt : public Edge {
1123      const EdgeSet *G;
1124      friend class EdgeSet;
1125    public:
1126      InEdgeIt() : Edge() { }
1127      InEdgeIt (Invalid i) : Edge(i) { }
1128      InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
1129      InEdgeIt(const EdgeSet& _G,Node v)
1130        : Edge(_G.nodes[v].first_in), G(&_G) { }
1131      InEdgeIt &operator++() {
1132        Edge::n = G->edges[Edge::n].next_in;
1133        return *this;
1134      }
1135    };
1136   
1137  };
1138
1139  template<typename GG>
1140  inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1141
1142/// @} 
1143
1144} //namespace hugo
1145
1146#endif //HUGO_LIST_GRAPH_H
Note: See TracBrowser for help on using the repository browser.