COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 822:88226d9fe821

Last change on this file since 822:88226d9fe821 was 822:88226d9fe821, checked in by Balazs Dezso, 16 years ago

The MapFactories? have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.

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