For the sake of icc.
3 #ifndef HUGO_FULL_GRAPH_H
4 #define HUGO_FULL_GRAPH_H
8 ///\brief FullGraph and SymFullGraph classes.
13 #include <hugo/invalid.h>
17 /// \addtogroup graphs
20 ///A full graph class.
22 ///This is a simple and fast directed full graph implementation.
23 ///It is completely static, so you can neither add nor delete either
25 ///Otherwise it conforms to the graph interface documented under
26 ///the description of \ref GraphSkeleton.
27 ///\sa \ref GraphSkeleton.
28 ///\todo Shouldn't we avoid loops?
30 ///\author Alpar Juttner
35 template <typename T> class EdgeMap;
36 template <typename T> class NodeMap;
45 template <typename T> class NodeMap;
46 template <typename T> class EdgeMap;
50 ///Creates a full graph with \c n nodes.
51 FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
53 FullGraph(const FullGraph &_g)
54 : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
56 int nodeNum() const { return NodeNum; } //FIXME: What is this?
57 int edgeNum() const { return EdgeNum; } //FIXME: What is this?
59 int maxNodeId() const { return NodeNum; } //FIXME: What is this?
60 int maxEdgeId() const { return EdgeNum; } //FIXME: What is this?
62 Node tail(Edge e) const { return e.n%NodeNum; }
63 Node head(Edge e) const { return e.n/NodeNum; }
65 Node aNode(OutEdgeIt e) const { return tail(e); }
66 Node aNode(InEdgeIt e) const { return head(e); }
68 Node bNode(OutEdgeIt e) const { return head(e); }
69 Node bNode(InEdgeIt e) const { return tail(e); }
71 NodeIt& first(NodeIt& v) const {
72 v=NodeIt(*this); return v; }
73 EdgeIt& first(EdgeIt& e) const {
74 e=EdgeIt(*this); return e; }
75 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
76 e=OutEdgeIt(*this,v); return e; }
77 InEdgeIt& first(InEdgeIt& e, const Node v) const {
78 e=InEdgeIt(*this,v); return e; }
80 static bool valid(Edge e) { return e.n!=-1; }
81 static bool valid(Node n) { return n.n!=-1; }
83 template <typename It> It getNext(It it) const
84 { It tmp(it); return next(tmp); }
86 NodeIt& next(NodeIt& it) const {
87 it.n=(it.n+2)%(NodeNum+1)-1;
90 OutEdgeIt& next(OutEdgeIt& it) const
91 { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }
92 InEdgeIt& next(InEdgeIt& it) const
93 { if(!((++it.n)%NodeNum)) it.n=-1; return it; }
94 static EdgeIt& next(EdgeIt& it) { --it.n; return it; }
96 static int id(Node v) { return v.n; }
97 static int id(Edge e) { return e.n; }
100 friend class FullGraph;
101 template <typename T> friend class NodeMap;
104 friend class OutEdgeIt;
105 friend class InEdgeIt;
106 friend class SymEdge;
110 friend int FullGraph::id(Node v);
114 Node (Invalid) { n=-1; }
115 bool operator==(const Node i) const {return n==i.n;}
116 bool operator!=(const Node i) const {return n!=i.n;}
117 bool operator<(const Node i) const {return n<i.n;}
120 class NodeIt : public Node {
121 friend class FullGraph;
123 NodeIt() : Node() { }
124 NodeIt(Invalid i) : Node(i) { }
125 NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }
126 ///\todo Undocumented conversion Node -\> NodeIt.
127 NodeIt(const FullGraph& G, const Node &n) : Node(n) { }
131 friend class FullGraph;
132 template <typename T> friend class EdgeMap;
137 int n; //NodeNum*head+tail;
138 friend int FullGraph::id(Edge e);
143 Edge (Invalid) { n=-1; }
144 bool operator==(const Edge i) const {return n==i.n;}
145 bool operator!=(const Edge i) const {return n!=i.n;}
146 bool operator<(const Edge i) const {return n<i.n;}
147 ///\bug This is a workaround until somebody tells me how to
148 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
149 int &idref() {return n;}
150 const int &idref() const {return n;}
153 class EdgeIt : public Edge {
154 friend class FullGraph;
156 EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }
157 EdgeIt (Invalid i) : Edge(i) { }
158 EdgeIt() : Edge() { }
159 ///\bug This is a workaround until somebody tells me how to
160 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
161 int &idref() {return n;}
164 class OutEdgeIt : public Edge {
165 friend class FullGraph;
167 OutEdgeIt() : Edge() { }
168 OutEdgeIt (Invalid i) : Edge(i) { }
170 OutEdgeIt(const FullGraph& G,const Node v)
174 class InEdgeIt : public Edge {
175 friend class FullGraph;
177 InEdgeIt() : Edge() { }
178 InEdgeIt (Invalid i) : Edge(i) { }
179 InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}
182 template <typename T> class NodeMap
184 std::vector<T> container;
188 typedef Node KeyType;
190 NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
191 NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
192 NodeMap(const NodeMap<T> &m) : container(m.container) { }
194 template<typename TT> friend class NodeMap;
195 ///\todo It can copy between different types.
196 template<typename TT> NodeMap(const NodeMap<TT> &m)
197 : container(m.container.size())
199 typename std::vector<TT>::const_iterator i;
200 for(typename std::vector<TT>::const_iterator i=m.container.begin();
201 i!=m.container.end();
203 container.push_back(*i);
205 void set(Node n, T a) { container[n.n]=a; }
206 //'T& operator[](Node n)' would be wrong here
207 typename std::vector<T>::reference
208 operator[](Node n) { return container[n.n]; }
209 //'const T& operator[](Node n)' would be wrong here
210 typename std::vector<T>::const_reference
211 operator[](Node n) const { return container[n.n]; }
213 ///\warning There is no safety check at all!
214 ///Using operator = between maps attached to different graph may
215 ///cause serious problem.
216 ///\todo Is this really so?
217 ///\todo It can copy between different types.
218 const NodeMap<T>& operator=(const NodeMap<T> &m)
220 container = m.container;
223 template<typename TT>
224 const NodeMap<T>& operator=(const NodeMap<TT> &m)
226 std::copy(m.container.begin(), m.container.end(), container.begin());
230 void update() {} //Useless for Dynamic Maps
231 void update(T a) {} //Useless for Dynamic Maps
234 template <typename T> class EdgeMap
236 std::vector<T> container;
240 typedef Edge KeyType;
242 EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
243 EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { }
244 EdgeMap(const EdgeMap<T> &m) : container(m.container) { }
246 template<typename TT> friend class EdgeMap;
247 ///\todo It can copy between different types.
248 ///\todo We could use 'copy'
249 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
250 container(m.container.size())
252 typename std::vector<TT>::const_iterator i;
253 for(typename std::vector<TT>::const_iterator i=m.container.begin();
254 i!=m.container.end();
256 container.push_back(*i);
258 void set(Edge n, T a) { container[n.n]=a; }
259 //T get(Edge n) const { return container[n.n]; }
260 typename std::vector<T>::reference
261 operator[](Edge n) { return container[n.n]; }
262 typename std::vector<T>::const_reference
263 operator[](Edge n) const { return container[n.n]; }
265 ///\warning There is no safety check at all!
266 ///Using operator = between maps attached to different graph may
267 ///cause serious problem.
268 ///\todo Is this really so?
269 ///\todo It can copy between different types.
270 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
272 container = m.container;
275 template<typename TT>
276 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
278 std::copy(m.container.begin(), m.container.end(), container.begin());
295 #endif //HUGO_FULL_GRAPH_H