COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/full_graph.h @ 780:e06d0d16595f

Last change on this file since 780:e06d0d16595f was 774:4297098d9677, checked in by Alpar Juttner, 20 years ago

Merge back the whole branches/hugo++ to trunk.

File size: 9.0 KB
Line 
1// -*- c++ -*-
2
3#ifndef HUGO_FULL_GRAPH_H
4#define HUGO_FULL_GRAPH_H
5
6///\ingroup graphs
7///\file
8///\brief FullGraph and SymFullGraph classes.
9
10#include <vector>
11#include <limits.h>
12
13#include <hugo/invalid.h>
14
15namespace hugo {
16
17/// \addtogroup graphs
18/// @{
19
20  ///A full graph class.
21
22  ///This is a simple and fast directed full graph implementation.
23  ///It is completely static, so you can neither add nor delete either
24  ///edges or nodes.
25  ///Otherwise it conforms to the graph interface documented under
26  ///the description of \ref GraphSkeleton.
27  ///\sa \ref GraphSkeleton.
28  ///\todo What about loops?
29  ///\todo Don't we need SymEdgeMap?
30  ///
31  ///\author Alpar Juttner
32  class FullGraph {
33    int NodeNum;
34    int EdgeNum;
35  public:
36    template <typename T> class EdgeMap;
37    template <typename T> class NodeMap;
38
39    class Node;
40    class Edge;
41    class NodeIt;
42    class EdgeIt;
43    class OutEdgeIt;
44    class InEdgeIt;
45   
46    template <typename T> class NodeMap;
47    template <typename T> class EdgeMap;
48   
49  public:
50
51    ///Creates a full graph with \c n nodes.
52    FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
53    ///
54    FullGraph(const FullGraph &_g)
55      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
56   
57    int nodeNum() const { return NodeNum; }  //FIXME: What is this?
58    int edgeNum() const { return EdgeNum; }  //FIXME: What is this?
59
60    int maxNodeId() const { return NodeNum; }  //FIXME: What is this?
61    int maxEdgeId() const { return EdgeNum; }  //FIXME: What is this?
62
63    Node tail(Edge e) const { return e.n%NodeNum; }
64    Node head(Edge e) const { return e.n/NodeNum; }
65
66    NodeIt& first(NodeIt& v) const {
67      v=NodeIt(*this); return v; }
68    EdgeIt& first(EdgeIt& e) const {
69      e=EdgeIt(*this); return e; }
70    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
71      e=OutEdgeIt(*this,v); return e; }
72    InEdgeIt& first(InEdgeIt& e, const Node v) const {
73      e=InEdgeIt(*this,v); return e; }
74
75    static int id(Node v) { return v.n; }
76    static int id(Edge e) { return e.n; }
77
78    /// Finds an edge between two nodes.
79   
80    /// Finds an edge from node \c u to node \c v.
81    ///
82    /// If \c prev is \ref INVALID (this is the default value), then
83    /// It finds the first edge from \c u to \c v. Otherwise it looks for
84    /// the next edge from \c u to \c v after \c prev.
85    /// \return The found edge or INVALID if there is no such an edge.
86    Edge findEdge(Node u,Node v, Edge prev = INVALID)
87    {
88      return prev.n==-1?Edge(*this,u.n,v.n):INVALID;
89    }
90   
91     
92    class Node {
93      friend class FullGraph;
94      template <typename T> friend class NodeMap;
95
96      friend class Edge;
97      friend class OutEdgeIt;
98      friend class InEdgeIt;
99      friend class SymEdge;
100
101    protected:
102      int n;
103      friend int FullGraph::id(Node v);
104      Node(int nn) {n=nn;}
105    public:
106      Node() {}
107      Node (Invalid) { n=-1; }
108      bool operator==(const Node i) const {return n==i.n;}
109      bool operator!=(const Node i) const {return n!=i.n;}
110      bool operator<(const Node i) const {return n<i.n;}
111    };
112   
113    class NodeIt : public Node {
114      const FullGraph *G;
115      friend class FullGraph;
116    public:
117      NodeIt() : Node() { }
118      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
119      NodeIt(Invalid i) : Node(i) { }
120      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
121      ///\todo Undocumented conversion Node -\> NodeIt.
122      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
123    };
124
125    class Edge {
126      friend class FullGraph;
127      template <typename T> friend class EdgeMap;
128     
129      friend class Node;
130      friend class NodeIt;
131    protected:
132      int n; //NodeNum*head+tail;
133      friend int FullGraph::id(Edge e);
134
135      Edge(int nn) : n(nn) {}
136      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
137    public:
138      Edge() { }
139      Edge (Invalid) { n=-1; }
140      bool operator==(const Edge i) const {return n==i.n;}
141      bool operator!=(const Edge i) const {return n!=i.n;}
142      bool operator<(const Edge i) const {return n<i.n;}
143      ///\bug This is a workaround until somebody tells me how to
144      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
145      int &idref() {return n;}
146      const int &idref() const {return n;}
147    };
148   
149    class EdgeIt : public Edge {
150      friend class FullGraph;
151    public:
152      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
153      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
154      EdgeIt (Invalid i) : Edge(i) { }
155      EdgeIt() : Edge() { }
156      EdgeIt& operator++() { --n; return *this; }
157
158      ///\bug This is a workaround until somebody tells me how to
159      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
160      int &idref() {return n;}
161    };
162   
163    class OutEdgeIt : public Edge {
164      const FullGraph *G;
165      friend class FullGraph;
166    public:
167      OutEdgeIt() : Edge() { }
168      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
169      OutEdgeIt (Invalid i) : Edge(i) { }
170
171      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
172     
173      OutEdgeIt& operator++()
174      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
175
176    };
177   
178    class InEdgeIt : public Edge {
179      const FullGraph *G;
180      friend class FullGraph;
181    public:
182      InEdgeIt() : Edge() { }
183      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
184      InEdgeIt (Invalid i) : Edge(i) { }
185      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
186      InEdgeIt& operator++()
187      { if(!((++n)%G->NodeNum)) n=-1; return *this; }
188    };
189
190    template <typename T> class NodeMap
191    {
192      std::vector<T> container;
193
194    public:
195      typedef T ValueType;
196      typedef Node KeyType;
197
198      NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
199      NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
200      NodeMap(const NodeMap<T> &m) : container(m.container) { }
201
202      template<typename TT> friend class NodeMap;
203      ///\todo It can copy between different types.
204      template<typename TT> NodeMap(const NodeMap<TT> &m)
205        : container(m.container.size())
206      {
207        typename std::vector<TT>::const_iterator i;
208        for(typename std::vector<TT>::const_iterator i=m.container.begin();
209            i!=m.container.end();
210            i++)
211          container.push_back(*i);
212      }
213      void set(Node n, T a) { container[n.n]=a; }
214      //'T& operator[](Node n)' would be wrong here
215      typename std::vector<T>::reference
216      operator[](Node n) { return container[n.n]; }
217      //'const T& operator[](Node n)' would be wrong here
218      typename std::vector<T>::const_reference
219      operator[](Node n) const { return container[n.n]; }
220
221      ///\warning There is no safety check at all!
222      ///Using operator = between maps attached to different graph may
223      ///cause serious problem.
224      ///\todo Is this really so?
225      ///\todo It can copy between different types.
226      const NodeMap<T>& operator=(const NodeMap<T> &m)
227      {
228        container = m.container;
229        return *this;
230      }
231      template<typename TT>
232      const NodeMap<T>& operator=(const NodeMap<TT> &m)
233      {
234        std::copy(m.container.begin(), m.container.end(), container.begin());
235        return *this;
236      }
237     
238      void update() {}    //Useless for Dynamic Maps
239      void update(T a) {}  //Useless for Dynamic Maps
240    };
241   
242    template <typename T> class EdgeMap
243    {
244      std::vector<T> container;
245
246    public:
247      typedef T ValueType;
248      typedef Edge KeyType;
249
250      EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
251      EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { }
252      EdgeMap(const EdgeMap<T> &m) : container(m.container) { }
253
254      template<typename TT> friend class EdgeMap;
255      ///\todo It can copy between different types.
256      ///\todo We could use 'copy'
257      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
258        container(m.container.size())
259      {
260        typename std::vector<TT>::const_iterator i;
261        for(typename std::vector<TT>::const_iterator i=m.container.begin();
262            i!=m.container.end();
263            i++)
264          container.push_back(*i);
265      }
266      void set(Edge n, T a) { container[n.n]=a; }
267      //T get(Edge n) const { return container[n.n]; }
268      typename std::vector<T>::reference
269      operator[](Edge n) { return container[n.n]; }
270      typename std::vector<T>::const_reference
271      operator[](Edge n) const { return container[n.n]; }
272
273      ///\warning There is no safety check at all!
274      ///Using operator = between maps attached to different graph may
275      ///cause serious problem.
276      ///\todo Is this really so?
277      ///\todo It can copy between different types.
278      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
279      {
280        container = m.container;
281        return *this;
282      }
283      template<typename TT>
284      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
285      {
286        std::copy(m.container.begin(), m.container.end(), container.begin());
287        return *this;
288      }
289
290      void update() {}
291      void update(T a) {}
292    };
293
294  };
295
296  /// @} 
297
298} //namespace hugo
299
300
301
302
303#endif //HUGO_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.