Changeset 1566:12a3101cf3ab in lemon-0.x
- Timestamp:
- 07/18/05 17:08:18 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2065
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/full_graph.h
r1555 r1566 25 25 #include <lemon/bits/default_map.h> 26 26 27 #include <lemon/bits/undir_graph_extender.h> 28 27 29 #include <lemon/invalid.h> 28 30 #include <lemon/utility.h> … … 37 39 38 40 class FullGraphBase { 39 int NodeNum;40 int EdgeNum;41 int _nodeNum; 42 int _edgeNum; 41 43 public: 42 44 … … 52 54 53 55 ///Creates a full graph with \c n nodes. 54 void construct(int n) { NodeNum = n; EdgeNum = n * n; }56 void construct(int n) { _nodeNum = n; _edgeNum = n * n; } 55 57 /// 56 58 // FullGraphBase(const FullGraphBase &_g) 57 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }59 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { } 58 60 59 61 typedef True NodeNumTag; … … 61 63 62 64 ///Number of nodes. 63 int nodeNum() const { return NodeNum; }65 int nodeNum() const { return _nodeNum; } 64 66 ///Number of edges. 65 int edgeNum() const { return EdgeNum; }67 int edgeNum() const { return _edgeNum; } 66 68 67 69 /// Maximum node ID. … … 69 71 /// Maximum node ID. 70 72 ///\sa id(Node) 71 int maxId(Node = INVALID) const { return NodeNum-1; }73 int maxId(Node = INVALID) const { return _nodeNum-1; } 72 74 /// Maximum edge ID. 73 75 74 76 /// Maximum edge ID. 75 77 ///\sa id(Edge) 76 int maxId(Edge = INVALID) const { return EdgeNum-1; }77 78 Node source(Edge e) const { return e.id % NodeNum; }79 Node target(Edge e) const { return e.id / NodeNum; }78 int maxId(Edge = INVALID) const { return _edgeNum-1; } 79 80 Node source(Edge e) const { return e.id % _nodeNum; } 81 Node target(Edge e) const { return e.id / _nodeNum; } 80 82 81 83 … … 103 105 104 106 static Edge fromId(int id, Edge) { return Edge(id);} 107 108 typedef True FindEdgeTag; 105 109 106 110 /// Finds an edge between two nodes. … … 112 116 /// the next edge from \c u to \c v after \c prev. 113 117 /// \return The found edge or INVALID if there is no such an edge. 114 Edge findEdge(Node u,Node v, Edge prev = INVALID) 115 { 118 Edge findEdge(Node u,Node v, Edge prev = INVALID) const { 116 119 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; 117 120 } … … 138 141 139 142 protected: 140 int id; // NodeNum * target + source;143 int id; // _nodeNum * target + source; 141 144 142 145 Edge(int _id) : id(_id) {} 143 146 144 147 Edge(const FullGraphBase& _graph, int source, int target) 145 : id(_graph. NodeNum * target+source) {}148 : id(_graph._nodeNum * target+source) {} 146 149 public: 147 150 Edge() { } … … 153 156 154 157 void first(Node& node) const { 155 node.id = NodeNum-1;158 node.id = _nodeNum-1; 156 159 } 157 160 … … 161 164 162 165 void first(Edge& edge) const { 163 edge.id = EdgeNum-1;166 edge.id = _edgeNum-1; 164 167 } 165 168 … … 169 172 170 173 void firstOut(Edge& edge, const Node& node) const { 171 edge.id = EdgeNum + node.id - NodeNum;174 edge.id = _edgeNum + node.id - _nodeNum; 172 175 } 173 176 174 177 void nextOut(Edge& edge) const { 175 edge.id -= NodeNum;178 edge.id -= _nodeNum; 176 179 if (edge.id < 0) edge.id = -1; 177 180 } 178 181 179 182 void firstIn(Edge& edge, const Node& node) const { 180 edge.id = node.id * NodeNum;183 edge.id = node.id * _nodeNum; 181 184 } 182 185 183 186 void nextIn(Edge& edge) const { 184 187 ++edge.id; 185 if (edge.id % NodeNum == 0) edge.id = -1;188 if (edge.id % _nodeNum == 0) edge.id = -1; 186 189 } 187 190 … … 189 192 190 193 191 typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase; 192 typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase; 193 typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase; 194 195 /// \addtogroup graphs 196 /// @{ 197 198 ///A full graph class. 199 200 ///This is a simple and fast directed full graph implementation. 201 ///It is completely static, so you can neither add nor delete either 202 ///edges or nodes. 203 ///Thus it conforms to 204 ///the \ref concept::StaticGraph "StaticGraph" concept 205 ///\sa concept::StaticGraph. 206 /// 207 ///\author Alpar Juttner 194 typedef AlterableGraphExtender<FullGraphBase> 195 AlterableFullGraphBase; 196 typedef IterableGraphExtender<AlterableFullGraphBase> 197 IterableFullGraphBase; 198 typedef DefaultMappableGraphExtender<IterableFullGraphBase> 199 MappableFullGraphBase; 200 201 /// \ingroup graphs 202 /// 203 /// \brief A full graph class. 204 /// 205 /// This is a simple and fast directed full graph implementation. 206 /// It is completely static, so you can neither add nor delete either 207 /// edges or nodes. 208 /// Thus it conforms to 209 /// the \ref concept::StaticGraph "StaticGraph" concept 210 /// \sa concept::StaticGraph. 211 /// 212 /// \author Alpar Juttner 208 213 class FullGraph : public MappableFullGraphBase { 209 214 public: … … 214 219 ///@} 215 220 216 // Base graph class for UndirFullGraph.217 221 class UndirFullGraphBase { 218 int NodeNum;219 int EdgeNum;222 int _nodeNum; 223 int _edgeNum; 220 224 public: 221 225 … … 231 235 232 236 ///Creates a full graph with \c n nodes. 233 void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }237 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } 234 238 /// 235 239 // FullGraphBase(const FullGraphBase &_g) 236 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }240 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { } 237 241 238 242 typedef True NodeNumTag; … … 240 244 241 245 ///Number of nodes. 242 int nodeNum() const { return NodeNum; }246 int nodeNum() const { return _nodeNum; } 243 247 ///Number of edges. 244 int edgeNum() const { return EdgeNum; }248 int edgeNum() const { return _edgeNum; } 245 249 246 250 /// Maximum node ID. … … 248 252 /// Maximum node ID. 249 253 ///\sa id(Node) 250 int maxId(Node = INVALID) const { return NodeNum-1; }254 int maxId(Node = INVALID) const { return _nodeNum-1; } 251 255 /// Maximum edge ID. 252 256 253 257 /// Maximum edge ID. 254 258 ///\sa id(Edge) 255 int maxId(Edge = INVALID) const { return EdgeNum-1; }259 int maxId(Edge = INVALID) const { return _edgeNum-1; } 256 260 257 261 Node source(Edge e) const { … … 320 324 321 325 protected: 322 int id; // NodeNum * target + source;326 int id; // _nodeNum * target + source; 323 327 324 328 Edge(int _id) : id(_id) {} 325 329 326 330 Edge(const UndirFullGraphBase& _graph, int source, int target) 327 : id(_graph. NodeNum * target+source) {}331 : id(_graph._nodeNum * target+source) {} 328 332 public: 329 333 Edge() { } … … 335 339 336 340 void first(Node& node) const { 337 node.id = NodeNum-1;341 node.id = _nodeNum-1; 338 342 } 339 343 … … 343 347 344 348 void first(Edge& edge) const { 345 edge.id = EdgeNum-1;349 edge.id = _edgeNum-1; 346 350 } 347 351 … … 370 374 int target = e.id - (source) * (source - 1) / 2; ++target; 371 375 ++source; 372 e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;376 e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1; 373 377 } 374 378 375 379 }; 376 380 377 /// \addtogroup graphs 378 /// @{ 379 380 381 /// \todo UndirFullGraph from the UndirFullGraphBase 382 383 384 /// @} 381 typedef UndirGraphExtender<UndirFullGraphBase> 382 UndirUndirFullGraphBase; 383 typedef AlterableUndirGraphExtender<UndirUndirFullGraphBase> 384 AlterableUndirFullGraphBase; 385 typedef IterableUndirGraphExtender<AlterableUndirFullGraphBase> 386 IterableUndirFullGraphBase; 387 typedef MappableUndirGraphExtender<IterableUndirFullGraphBase> 388 MappableUndirFullGraphBase; 389 390 /// \ingroup graphs 391 /// 392 /// \brief An undirected full graph class. 393 /// 394 /// This is a simple and fast directed full graph implementation. 395 /// It is completely static, so you can neither add nor delete either 396 /// edges or nodes. 397 /// 398 /// The main difference beetween the \e FullGraph and \e UndirFullGraph class 399 /// is that this class conforms to the undirected graph concept and 400 /// it does not contain the hook edges. 401 /// 402 /// \sa FullGraph 403 /// 404 /// \author Balazs Dezso 405 class UndirFullGraph : public MappableUndirFullGraphBase { 406 public: 407 UndirFullGraph(int n) { construct(n); } 408 }; 385 409 386 410 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.