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/array_map.h>
18 #include <hugo/map_defines.h>
22 /// \addtogroup graphs
25 ///A full graph class.
27 ///This is a simple and fast directed full graph implementation.
28 ///It is completely static, so you can neither add nor delete either
30 ///Thus it conforms to
31 ///the \ref skeleton::StaticGraph "StaticGraph" concept
32 ///\sa skeleton::StaticGraph.
33 ///\todo What about loops?
34 ///\todo Don't we need SymEdgeMap?
36 ///\author Alpar Juttner
42 typedef FullGraph Graph;
53 /// Creating map registries.
54 CREATE_MAP_REGISTRIES;
55 /// Creating node and edge maps.
56 CREATE_MAPS(ArrayMap);
60 ///Creates a full graph with \c n nodes.
61 FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
63 FullGraph(const FullGraph &_g)
64 : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
67 int nodeNum() const { return NodeNum; }
69 int edgeNum() const { return EdgeNum; }
75 int maxNodeId() const { return NodeNum-1; }
80 int maxEdgeId() const { return EdgeNum-1; }
82 Node tail(Edge e) const { return e.n%NodeNum; }
83 Node head(Edge e) const { return e.n/NodeNum; }
85 NodeIt& first(NodeIt& v) const {
86 v=NodeIt(*this); return v; }
87 EdgeIt& first(EdgeIt& e) const {
88 e=EdgeIt(*this); return e; }
89 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
90 e=OutEdgeIt(*this,v); return e; }
91 InEdgeIt& first(InEdgeIt& e, const Node v) const {
92 e=InEdgeIt(*this,v); return e; }
96 /// The ID of a valid Node is a nonnegative integer not greater than
97 /// \ref maxNodeId(). The range of the ID's is not surely continuous
98 /// and the greatest node ID can be actually less then \ref maxNodeId().
100 /// The ID of the \ref INVALID node is -1.
101 ///\return The ID of the node \c v.
102 static int id(Node v) { return v.n; }
105 /// The ID of a valid Edge is a nonnegative integer not greater than
106 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
107 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
109 /// The ID of the \ref INVALID edge is -1.
110 ///\return The ID of the edge \c e.
111 static int id(Edge e) { return e.n; }
113 /// Finds an edge between two nodes.
115 /// Finds an edge from node \c u to node \c v.
117 /// If \c prev is \ref INVALID (this is the default value), then
118 /// It finds the first edge from \c u to \c v. Otherwise it looks for
119 /// the next edge from \c u to \c v after \c prev.
120 /// \return The found edge or INVALID if there is no such an edge.
121 Edge findEdge(Node u,Node v, Edge prev = INVALID)
123 return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
128 friend class FullGraph;
129 template <typename T> friend class NodeMap;
132 friend class OutEdgeIt;
133 friend class InEdgeIt;
134 friend class SymEdge;
138 friend int FullGraph::id(Node v);
142 Node (Invalid) { n=-1; }
143 bool operator==(const Node i) const {return n==i.n;}
144 bool operator!=(const Node i) const {return n!=i.n;}
145 bool operator<(const Node i) const {return n<i.n;}
148 class NodeIt : public Node {
150 friend class FullGraph;
152 NodeIt() : Node() { }
153 NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
154 NodeIt(Invalid i) : Node(i) { }
155 NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
156 ///\todo Undocumented conversion Node -\> NodeIt.
157 NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
161 friend class FullGraph;
162 template <typename T> friend class EdgeMap;
167 int n; //NodeNum*head+tail;
168 friend int FullGraph::id(Edge e);
170 Edge(int nn) : n(nn) {}
171 Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
174 Edge (Invalid) { n=-1; }
175 bool operator==(const Edge i) const {return n==i.n;}
176 bool operator!=(const Edge i) const {return n!=i.n;}
177 bool operator<(const Edge i) const {return n<i.n;}
178 ///\bug This is a workaround until somebody tells me how to
179 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
180 int &idref() {return n;}
181 const int &idref() const {return n;}
184 class EdgeIt : public Edge {
185 friend class FullGraph;
187 EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
188 EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
189 EdgeIt (Invalid i) : Edge(i) { }
190 EdgeIt() : Edge() { }
191 EdgeIt& operator++() { --n; return *this; }
193 ///\bug This is a workaround until somebody tells me how to
194 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
195 int &idref() {return n;}
198 class OutEdgeIt : public Edge {
200 friend class FullGraph;
202 OutEdgeIt() : Edge() { }
203 OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
204 OutEdgeIt (Invalid i) : Edge(i) { }
206 OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
208 OutEdgeIt& operator++()
209 { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
213 class InEdgeIt : public Edge {
215 friend class FullGraph;
217 InEdgeIt() : Edge() { }
218 InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
219 InEdgeIt (Invalid i) : Edge(i) { }
220 InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
221 InEdgeIt& operator++()
222 { if(!((++n)%G->NodeNum)) n=-1; return *this; }
234 #endif //HUGO_FULL_GRAPH_H