COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/full_graph.h @ 752:327c2f67a066

Last change on this file since 752:327c2f67a066 was 752:327c2f67a066, checked in by Alpar Juttner, 20 years ago

doc change - one more todo.

File size: 8.6 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    Node aNode(OutEdgeIt e) const { return tail(e); }
67    Node aNode(InEdgeIt e) const { return head(e); }
68
69    Node bNode(OutEdgeIt e) const { return head(e); }
70    Node bNode(InEdgeIt e) const { return tail(e); }
71
72    NodeIt& first(NodeIt& v) const {
73      v=NodeIt(*this); return v; }
74    EdgeIt& first(EdgeIt& e) const {
75      e=EdgeIt(*this); return e; }
76    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
77      e=OutEdgeIt(*this,v); return e; }
78    InEdgeIt& first(InEdgeIt& e, const Node v) const {
79      e=InEdgeIt(*this,v); return e; }
80
81    static bool valid(Edge e) { return e.n!=-1; }
82    static bool valid(Node n) { return n.n!=-1; }
83   
84    template <typename It> It getNext(It it) const
85    { It tmp(it); return next(tmp); }
86
87    NodeIt& next(NodeIt& it) const {
88      it.n=(it.n+2)%(NodeNum+1)-1;
89      return it;
90    }
91    OutEdgeIt& next(OutEdgeIt& it) const
92    { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }
93    InEdgeIt& next(InEdgeIt& it) const
94    { if(!((++it.n)%NodeNum)) it.n=-1; return it; }
95    static EdgeIt& next(EdgeIt& it) { --it.n; return it; }
96
97    static int id(Node v) { return v.n; }
98    static int id(Edge e) { return e.n; }
99
100    class Node {
101      friend class FullGraph;
102      template <typename T> friend class NodeMap;
103
104      friend class Edge;
105      friend class OutEdgeIt;
106      friend class InEdgeIt;
107      friend class SymEdge;
108
109    protected:
110      int n;
111      friend int FullGraph::id(Node v);
112      Node(int nn) {n=nn;}
113    public:
114      Node() {}
115      Node (Invalid) { n=-1; }
116      bool operator==(const Node i) const {return n==i.n;}
117      bool operator!=(const Node i) const {return n!=i.n;}
118      bool operator<(const Node i) const {return n<i.n;}
119    };
120   
121    class NodeIt : public Node {
122      friend class FullGraph;
123    public:
124      NodeIt() : Node() { }
125      NodeIt(Invalid i) : Node(i) { }
126      NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }
127      ///\todo Undocumented conversion Node -\> NodeIt.
128      NodeIt(const FullGraph& G, const Node &n) : Node(n) { }
129    };
130
131    class Edge {
132      friend class FullGraph;
133      template <typename T> friend class EdgeMap;
134     
135      friend class Node;
136      friend class NodeIt;
137    protected:
138      int n; //NodeNum*head+tail;
139      friend int FullGraph::id(Edge e);
140
141      Edge(int nn) {n=nn;}
142    public:
143      Edge() { }
144      Edge (Invalid) { n=-1; }
145      bool operator==(const Edge i) const {return n==i.n;}
146      bool operator!=(const Edge i) const {return n!=i.n;}
147      bool operator<(const Edge i) const {return n<i.n;}
148      ///\bug This is a workaround until somebody tells me how to
149      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
150      int &idref() {return n;}
151      const int &idref() const {return n;}
152    };
153   
154    class EdgeIt : public Edge {
155      friend class FullGraph;
156    public:
157      EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }
158      EdgeIt (Invalid i) : Edge(i) { }
159      EdgeIt() : Edge() { }
160      ///\bug This is a workaround until somebody tells me how to
161      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
162      int &idref() {return n;}
163    };
164   
165    class OutEdgeIt : public Edge {
166      friend class FullGraph;
167    public:
168      OutEdgeIt() : Edge() { }
169      OutEdgeIt (Invalid i) : Edge(i) { }
170
171      OutEdgeIt(const FullGraph& G,const Node v)
172        : Edge(v.n) {}
173    };
174   
175    class InEdgeIt : public Edge {
176      friend class FullGraph;
177    public:
178      InEdgeIt() : Edge() { }
179      InEdgeIt (Invalid i) : Edge(i) { }
180      InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}
181    };
182
183    template <typename T> class NodeMap
184    {
185      std::vector<T> container;
186
187    public:
188      typedef T ValueType;
189      typedef Node KeyType;
190
191      NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
192      NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
193      NodeMap(const NodeMap<T> &m) : container(m.container) { }
194
195      template<typename TT> friend class NodeMap;
196      ///\todo It can copy between different types.
197      template<typename TT> NodeMap(const NodeMap<TT> &m)
198        : container(m.container.size())
199      {
200        typename std::vector<TT>::const_iterator i;
201        for(typename std::vector<TT>::const_iterator i=m.container.begin();
202            i!=m.container.end();
203            i++)
204          container.push_back(*i);
205      }
206      void set(Node n, T a) { container[n.n]=a; }
207      //'T& operator[](Node n)' would be wrong here
208      typename std::vector<T>::reference
209      operator[](Node n) { return container[n.n]; }
210      //'const T& operator[](Node n)' would be wrong here
211      typename std::vector<T>::const_reference
212      operator[](Node n) const { return container[n.n]; }
213
214      ///\warning There is no safety check at all!
215      ///Using operator = between maps attached to different graph may
216      ///cause serious problem.
217      ///\todo Is this really so?
218      ///\todo It can copy between different types.
219      const NodeMap<T>& operator=(const NodeMap<T> &m)
220      {
221        container = m.container;
222        return *this;
223      }
224      template<typename TT>
225      const NodeMap<T>& operator=(const NodeMap<TT> &m)
226      {
227        std::copy(m.container.begin(), m.container.end(), container.begin());
228        return *this;
229      }
230     
231      void update() {}    //Useless for Dynamic Maps
232      void update(T a) {}  //Useless for Dynamic Maps
233    };
234   
235    template <typename T> class EdgeMap
236    {
237      std::vector<T> container;
238
239    public:
240      typedef T ValueType;
241      typedef Edge KeyType;
242
243      EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
244      EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { }
245      EdgeMap(const EdgeMap<T> &m) : container(m.container) { }
246
247      template<typename TT> friend class EdgeMap;
248      ///\todo It can copy between different types.
249      ///\todo We could use 'copy'
250      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
251        container(m.container.size())
252      {
253        typename std::vector<TT>::const_iterator i;
254        for(typename std::vector<TT>::const_iterator i=m.container.begin();
255            i!=m.container.end();
256            i++)
257          container.push_back(*i);
258      }
259      void set(Edge n, T a) { container[n.n]=a; }
260      //T get(Edge n) const { return container[n.n]; }
261      typename std::vector<T>::reference
262      operator[](Edge n) { return container[n.n]; }
263      typename std::vector<T>::const_reference
264      operator[](Edge n) const { return container[n.n]; }
265
266      ///\warning There is no safety check at all!
267      ///Using operator = between maps attached to different graph may
268      ///cause serious problem.
269      ///\todo Is this really so?
270      ///\todo It can copy between different types.
271      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
272      {
273        container = m.container;
274        return *this;
275      }
276      template<typename TT>
277      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
278      {
279        std::copy(m.container.begin(), m.container.end(), container.begin());
280        return *this;
281      }
282     
283      void update() {}
284      void update(T a) {}
285    };
286
287  };
288
289  /// @} 
290
291} //namespace hugo
292
293
294
295
296#endif //HUGO_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.