COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 904:b40afcf42a4d

Last change on this file since 904:b40afcf42a4d was 904:b40afcf42a4d, checked in by Alpar Juttner, 16 years ago

Do not document registry and map defines.

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