COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 825:738abd9d1262

Last change on this file since 825:738abd9d1262 was 825:738abd9d1262, checked in by Alpar Juttner, 16 years ago

Improved docs.

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