Changeset 983:3095ff2b5c18 in lemon0.x
 Timestamp:
 11/11/04 12:12:42 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1371
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/full_graph.h
r980 r983 18 18 #define LEMON_FULL_GRAPH_H 19 19 20 #include <cmath> 21 20 22 21 23 #include <lemon/iterable_graph_extender.h> … … 198 200 ///the \ref concept::StaticGraph "StaticGraph" concept 199 201 ///\sa concept::StaticGraph. 200 ///\todo What about loops?201 ///\todo Don't we need SymEdgeMap?202 202 /// 203 203 ///\author Alpar Juttner … … 208 208 }; 209 209 210 211 /// Base graph class for UndirFullGraph. 212 213 class UndirFullGraphBase { 214 int NodeNum; 215 int EdgeNum; 216 public: 217 218 typedef FullGraphBase Graph; 219 220 class Node; 221 class Edge; 222 223 public: 224 225 FullGraphBase() {} 226 227 228 ///Creates a full graph with \c n nodes. 229 void construct(int n) { NodeNum = n; EdgeNum = n * (n  1) / 2; } 230 /// 231 // FullGraphBase(const FullGraphBase &_g) 232 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } 233 234 typedef True NodeNumTag; 235 typedef True EdgeNumTag; 236 237 ///Number of nodes. 238 int nodeNum() const { return NodeNum; } 239 ///Number of edges. 240 int edgeNum() const { return EdgeNum; } 241 242 /// Maximum node ID. 243 244 /// Maximum node ID. 245 ///\sa id(Node) 246 int maxId(Node = INVALID) const { return NodeNum1; } 247 /// Maximum edge ID. 248 249 /// Maximum edge ID. 250 ///\sa id(Edge) 251 int maxId(Edge = INVALID) const { return EdgeNum1; } 252 253 Node tail(Edge e) const { 254 /// \todo we may do it faster 255 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; 256 } 257 258 Node head(Edge e) const { 259 int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; 260 return e.id  (tail) * (tail  1) / 2; 261 } 262 263 264 /// Node ID. 265 266 /// The ID of a valid Node is a nonnegative integer not greater than 267 /// \ref maxNodeId(). The range of the ID's is not surely continuous 268 /// and the greatest node ID can be actually less then \ref maxNodeId(). 269 /// 270 /// The ID of the \ref INVALID node is 1. 271 ///\return The ID of the node \c v. 272 273 static int id(Node v) { return v.id; } 274 /// Edge ID. 275 276 /// The ID of a valid Edge is a nonnegative integer not greater than 277 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 278 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 279 /// 280 /// The ID of the \ref INVALID edge is 1. 281 ///\return The ID of the edge \c e. 282 static int id(Edge e) { return e.id; } 283 284 /// Finds an edge between two nodes. 285 286 /// Finds an edge from node \c u to node \c v. 287 /// 288 /// If \c prev is \ref INVALID (this is the default value), then 289 /// It finds the first edge from \c u to \c v. Otherwise it looks for 290 /// the next edge from \c u to \c v after \c prev. 291 /// \return The found edge or INVALID if there is no such an edge. 292 Edge findEdge(Node u,Node v, Edge prev = INVALID) 293 { 294 return prev.id == 1 ? Edge(*this, u.id, v.id) : INVALID; 295 } 296 297 298 class Node { 299 friend class FullGraphBase; 300 301 protected: 302 int id; 303 Node(int _id) { id = _id;} 304 public: 305 Node() {} 306 Node (Invalid) { id = 1; } 307 bool operator==(const Node node) const {return id == node.id;} 308 bool operator!=(const Node node) const {return id != node.id;} 309 bool operator<(const Node node) const {return id < node.id;} 310 }; 311 312 313 314 class Edge { 315 friend class FullGraphBase; 316 317 protected: 318 int id; // NodeNum * head + tail; 319 320 Edge(int _id) : id(_id) {} 321 322 Edge(const FullGraphBase& _graph, int tail, int head) 323 : id(_graph.NodeNum * head+tail) {} 324 public: 325 Edge() { } 326 Edge (Invalid) { id = 1; } 327 bool operator==(const Edge edge) const {return id == edge.id;} 328 bool operator!=(const Edge edge) const {return id != edge.id;} 329 bool operator<(const Edge edge) const {return id < edge.id;} 330 }; 331 332 void first(Node& node) const { 333 node.id = NodeNum1; 334 } 335 336 static void next(Node& node) { 337 node.id; 338 } 339 340 void first(Edge& edge) const { 341 edge.id = EdgeNum1; 342 } 343 344 static void next(Edge& edge) { 345 edge.id; 346 } 347 348 void firstOut(Edge& edge, const Node& node) const { 349 edge.id = node.id != 0 ? node.id * (node.id  1) / 2 : 1; 350 } 351 352 /// \todo with specialized iterators we can make faster iterating 353 void nextOut(Edge& edge) const { 354 int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; 355 int head = e.id  (tail) * (tail  1) / 2; 356 ++head; 357 return head < tail ? tail * (tail  1) / 2 + head : 1; 358 } 359 360 void firstIn(Edge& edge, const Node& node) const { 361 edge.id = node.id * (node.id + 1) / 2  1; 362 } 363 364 void nextIn(Edge& edge) const { 365 int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; 366 int head = e.id  (tail) * (tail  1) / 2; ++head; 367 ++tail; 368 return tail < nodeNum ? tail * (tail  1) / 2 + head : 1; 369 } 370 371 }; 372 373 /// \todo UndirFullGraph from the UndirFullGraphBase 374 375 376 210 377 /// @} 211 378
Note: See TracChangeset
for help on using the changeset viewer.