COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 798:6d1abeb62dd3

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