NodeSubGraphWrapper, test, and ducumentation modifications.
2 * src/lemon/full_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_FULL_GRAPH_H
18 #define LEMON_FULL_GRAPH_H
22 ///\brief FullGraph and SymFullGraph classes.
27 #include <lemon/invalid.h>
29 #include <lemon/map_registry.h>
30 #include <lemon/array_map.h>
32 #include <lemon/map_defines.h>
36 /// \addtogroup graphs
39 ///A full graph class.
41 ///This is a simple and fast directed full graph implementation.
42 ///It is completely static, so you can neither add nor delete either
44 ///Thus it conforms to
45 ///the \ref skeleton::StaticGraph "StaticGraph" concept
46 ///\sa skeleton::StaticGraph.
47 ///\todo What about loops?
48 ///\todo Don't we need SymEdgeMap?
50 ///\author Alpar Juttner
56 typedef FullGraph Graph;
67 // Create map registries.
68 CREATE_MAP_REGISTRIES;
69 // Create node and edge maps.
70 CREATE_MAPS(ArrayMap);
74 ///Creates a full graph with \c n nodes.
75 FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
77 FullGraph(const FullGraph &_g)
78 : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
81 int nodeNum() const { return NodeNum; }
83 int edgeNum() const { return EdgeNum; }
89 int maxNodeId() const { return NodeNum-1; }
94 int maxEdgeId() const { return EdgeNum-1; }
96 Node tail(Edge e) const { return e.n%NodeNum; }
97 Node head(Edge e) const { return e.n/NodeNum; }
99 NodeIt& first(NodeIt& v) const {
100 v=NodeIt(*this); return v; }
101 EdgeIt& first(EdgeIt& e) const {
102 e=EdgeIt(*this); return e; }
103 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
104 e=OutEdgeIt(*this,v); return e; }
105 InEdgeIt& first(InEdgeIt& e, const Node v) const {
106 e=InEdgeIt(*this,v); return e; }
110 /// The ID of a valid Node is a nonnegative integer not greater than
111 /// \ref maxNodeId(). The range of the ID's is not surely continuous
112 /// and the greatest node ID can be actually less then \ref maxNodeId().
114 /// The ID of the \ref INVALID node is -1.
115 ///\return The ID of the node \c v.
116 static int id(Node v) { return v.n; }
119 /// The ID of a valid Edge is a nonnegative integer not greater than
120 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
121 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
123 /// The ID of the \ref INVALID edge is -1.
124 ///\return The ID of the edge \c e.
125 static int id(Edge e) { return e.n; }
127 /// Finds an edge between two nodes.
129 /// Finds an edge from node \c u to node \c v.
131 /// If \c prev is \ref INVALID (this is the default value), then
132 /// It finds the first edge from \c u to \c v. Otherwise it looks for
133 /// the next edge from \c u to \c v after \c prev.
134 /// \return The found edge or INVALID if there is no such an edge.
135 Edge findEdge(Node u,Node v, Edge prev = INVALID)
137 return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
142 friend class FullGraph;
143 template <typename T> friend class NodeMap;
146 friend class OutEdgeIt;
147 friend class InEdgeIt;
148 friend class SymEdge;
152 friend int FullGraph::id(Node v);
156 Node (Invalid) { n=-1; }
157 bool operator==(const Node i) const {return n==i.n;}
158 bool operator!=(const Node i) const {return n!=i.n;}
159 bool operator<(const Node i) const {return n<i.n;}
162 class NodeIt : public Node {
164 friend class FullGraph;
166 NodeIt() : Node() { }
167 NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
168 NodeIt(Invalid i) : Node(i) { }
169 NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
170 ///\todo Undocumented conversion Node -\> NodeIt.
171 NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
175 friend class FullGraph;
176 template <typename T> friend class EdgeMap;
181 int n; //NodeNum*head+tail;
182 friend int FullGraph::id(Edge e);
184 Edge(int nn) : n(nn) {}
185 Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
188 Edge (Invalid) { n=-1; }
189 bool operator==(const Edge i) const {return n==i.n;}
190 bool operator!=(const Edge i) const {return n!=i.n;}
191 bool operator<(const Edge i) const {return n<i.n;}
192 ///\bug This is a workaround until somebody tells me how to
193 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
194 int &idref() {return n;}
195 const int &idref() const {return n;}
198 class EdgeIt : public Edge {
199 friend class FullGraph;
201 EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
202 EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
203 EdgeIt (Invalid i) : Edge(i) { }
204 EdgeIt() : Edge() { }
205 EdgeIt& operator++() { --n; return *this; }
207 ///\bug This is a workaround until somebody tells me how to
208 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
209 int &idref() {return n;}
212 class OutEdgeIt : public Edge {
214 friend class FullGraph;
216 OutEdgeIt() : Edge() { }
217 OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
218 OutEdgeIt (Invalid i) : Edge(i) { }
220 OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
222 OutEdgeIt& operator++()
223 { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
227 class InEdgeIt : public Edge {
229 friend class FullGraph;
231 InEdgeIt() : Edge() { }
232 InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
233 InEdgeIt (Invalid i) : Edge(i) { }
234 InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
235 InEdgeIt& operator++()
236 { if(!((++n)%G->NodeNum)) n=-1; return *this; }
248 #endif //LEMON_FULL_GRAPH_H