Some warining fix in maps.
3 #ifndef HUGO_FULL_GRAPH_H
4 #define HUGO_FULL_GRAPH_H
8 ///\brief FullGraph and SymFullGraph classes.
13 #include <hugo/invalid.h>
15 #include <hugo/map_registry.h>
16 #include <hugo/default_map_factory.h>
20 /// \addtogroup graphs
23 ///A full graph class.
25 ///This is a simple and fast directed full graph implementation.
26 ///It is completely static, so you can neither add nor delete either
28 ///Otherwise it conforms to the graph interface documented under
29 ///the description of \ref GraphSkeleton.
30 ///\sa \ref GraphSkeleton.
31 ///\todo What about loops?
32 ///\todo Don't we need SymEdgeMap?
34 ///\author Alpar Juttner
40 typedef FullGraph Graph;
50 CREATE_MAP_REGISTRIES;
51 CREATE_MAPS(DefaultMapFactory);
55 ///Creates a full graph with \c n nodes.
56 FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
58 FullGraph(const FullGraph &_g)
59 : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
62 int nodeNum() const { return NodeNum; }
64 int edgeNum() const { return EdgeNum; }
70 int maxNodeId() const { return NodeNum-1; }
75 int maxEdgeId() const { return EdgeNum-1; }
77 Node tail(Edge e) const { return e.n%NodeNum; }
78 Node head(Edge e) const { return e.n/NodeNum; }
80 NodeIt& first(NodeIt& v) const {
81 v=NodeIt(*this); return v; }
82 EdgeIt& first(EdgeIt& e) const {
83 e=EdgeIt(*this); return e; }
84 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
85 e=OutEdgeIt(*this,v); return e; }
86 InEdgeIt& first(InEdgeIt& e, const Node v) const {
87 e=InEdgeIt(*this,v); return e; }
91 /// The ID of a valid Node is a nonnegative integer not greater than
92 /// \ref maxNodeId(). The range of the ID's is not surely continuous
93 /// and the greatest node ID can be actually less then \ref maxNodeId().
95 /// The ID of the \ref INVALID node is -1.
96 ///\return The ID of the node \c v.
97 static int id(Node v) { return v.n; }
100 /// The ID of a valid Edge is a nonnegative integer not greater than
101 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
102 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
104 /// The ID of the \ref INVALID edge is -1.
105 ///\return The ID of the edge \c e.
106 static int id(Edge e) { return e.n; }
108 /// Finds an edge between two nodes.
110 /// Finds an edge from node \c u to node \c v.
112 /// If \c prev is \ref INVALID (this is the default value), then
113 /// It finds the first edge from \c u to \c v. Otherwise it looks for
114 /// the next edge from \c u to \c v after \c prev.
115 /// \return The found edge or INVALID if there is no such an edge.
116 Edge findEdge(Node u,Node v, Edge prev = INVALID)
118 return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
123 friend class FullGraph;
124 template <typename T> friend class NodeMap;
127 friend class OutEdgeIt;
128 friend class InEdgeIt;
129 friend class SymEdge;
133 friend int FullGraph::id(Node v);
137 Node (Invalid) { n=-1; }
138 bool operator==(const Node i) const {return n==i.n;}
139 bool operator!=(const Node i) const {return n!=i.n;}
140 bool operator<(const Node i) const {return n<i.n;}
143 class NodeIt : public Node {
145 friend class FullGraph;
147 NodeIt() : Node() { }
148 NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
149 NodeIt(Invalid i) : Node(i) { }
150 NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
151 ///\todo Undocumented conversion Node -\> NodeIt.
152 NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
156 friend class FullGraph;
157 template <typename T> friend class EdgeMap;
162 int n; //NodeNum*head+tail;
163 friend int FullGraph::id(Edge e);
165 Edge(int nn) : n(nn) {}
166 Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
169 Edge (Invalid) { n=-1; }
170 bool operator==(const Edge i) const {return n==i.n;}
171 bool operator!=(const Edge i) const {return n!=i.n;}
172 bool operator<(const Edge i) const {return n<i.n;}
173 ///\bug This is a workaround until somebody tells me how to
174 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
175 int &idref() {return n;}
176 const int &idref() const {return n;}
179 class EdgeIt : public Edge {
180 friend class FullGraph;
182 EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
183 EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
184 EdgeIt (Invalid i) : Edge(i) { }
185 EdgeIt() : Edge() { }
186 EdgeIt& operator++() { --n; return *this; }
188 ///\bug This is a workaround until somebody tells me how to
189 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
190 int &idref() {return n;}
193 class OutEdgeIt : public Edge {
195 friend class FullGraph;
197 OutEdgeIt() : Edge() { }
198 OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
199 OutEdgeIt (Invalid i) : Edge(i) { }
201 OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
203 OutEdgeIt& operator++()
204 { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
208 class InEdgeIt : public Edge {
210 friend class FullGraph;
212 InEdgeIt() : Edge() { }
213 InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
214 InEdgeIt (Invalid i) : Edge(i) { }
215 InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
216 InEdgeIt& operator++()
217 { if(!((++n)%G->NodeNum)) n=-1; return *this; }
229 #endif //HUGO_FULL_GRAPH_H