COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 843:d56fad02dc55

Last change on this file since 843:d56fad02dc55 was 827:6433f69dfc6b, checked in by Alpar Juttner, 20 years ago

Improve docs.

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