More "doxygenish" syntax.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_FULL_GRAPH_H
20 #define LEMON_FULL_GRAPH_H
24 #include <lemon/bits/base_extender.h>
25 #include <lemon/bits/graph_extender.h>
27 #include <lemon/bits/invalid.h>
28 #include <lemon/bits/utility.h>
33 ///\brief FullGraph and FullUGraph classes.
38 /// \brief Base of the FullGrpah.
40 /// Base of the FullGrpah.
46 typedef FullGraphBase Graph;
56 ///Creates a full graph with \c n nodes.
57 void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
59 typedef True NodeNumTag;
60 typedef True EdgeNumTag;
62 /// \brief Returns the node with the given index.
64 /// Returns the node with the given index. Because it is a
65 /// static size graph the node's of the graph can be indiced
66 /// by the range from 0 to \e nodeNum()-1 and the index of
67 /// the node can accessed by the \e index() member.
68 Node operator()(int index) const { return Node(index); }
70 /// \brief Returns the index of the node.
72 /// Returns the index of the node. Because it is a
73 /// static size graph the node's of the graph can be indiced
74 /// by the range from 0 to \e nodeNum()-1 and the index of
75 /// the node can accessed by the \e index() member.
76 int index(const Node& node) const { return node.id; }
79 int nodeNum() const { return _nodeNum; }
81 int edgeNum() const { return _edgeNum; }
87 int maxNodeId() const { return _nodeNum-1; }
92 int maxEdgeId() const { return _edgeNum-1; }
94 Node source(Edge e) const { return e.id % _nodeNum; }
95 Node target(Edge e) const { return e.id / _nodeNum; }
100 /// The ID of a valid Node is a nonnegative integer not greater than
101 /// \ref maxNodeId(). The range of the ID's is not surely continuous
102 /// and the greatest node ID can be actually less then \ref maxNodeId().
104 /// The ID of the \ref INVALID node is -1.
105 ///\return The ID of the node \c v.
107 static int id(Node v) { return v.id; }
110 /// The ID of a valid Edge is a nonnegative integer not greater than
111 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
112 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
114 /// The ID of the \ref INVALID edge is -1.
115 ///\return The ID of the edge \c e.
116 static int id(Edge e) { return e.id; }
118 static Node nodeFromId(int id) { return Node(id);}
120 static Edge edgeFromId(int id) { return Edge(id);}
122 typedef True FindEdgeTag;
124 /// Finds an edge between two nodes.
126 /// Finds an edge from node \c u to node \c v.
128 /// If \c prev is \ref INVALID (this is the default value), then
129 /// It finds the first edge from \c u to \c v. Otherwise it looks for
130 /// the next edge from \c u to \c v after \c prev.
131 /// \return The found edge or INVALID if there is no such an edge.
132 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
133 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
138 friend class FullGraphBase;
142 Node(int _id) : id(_id) {}
145 Node (Invalid) : id(-1) {}
146 bool operator==(const Node node) const {return id == node.id;}
147 bool operator!=(const Node node) const {return id != node.id;}
148 bool operator<(const Node node) const {return id < node.id;}
154 friend class FullGraphBase;
157 int id; // _nodeNum * target + source;
159 Edge(int _id) : id(_id) {}
161 Edge(const FullGraphBase& _graph, int source, int target)
162 : id(_graph._nodeNum * target+source) {}
165 Edge (Invalid) { id = -1; }
166 bool operator==(const Edge edge) const {return id == edge.id;}
167 bool operator!=(const Edge edge) const {return id != edge.id;}
168 bool operator<(const Edge edge) const {return id < edge.id;}
171 void first(Node& node) const {
172 node.id = _nodeNum-1;
175 static void next(Node& node) {
179 void first(Edge& edge) const {
180 edge.id = _edgeNum-1;
183 static void next(Edge& edge) {
187 void firstOut(Edge& edge, const Node& node) const {
188 edge.id = _edgeNum + node.id - _nodeNum;
191 void nextOut(Edge& edge) const {
193 if (edge.id < 0) edge.id = -1;
196 void firstIn(Edge& edge, const Node& node) const {
197 edge.id = node.id * _nodeNum;
200 void nextIn(Edge& edge) const {
202 if (edge.id % _nodeNum == 0) edge.id = -1;
207 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
211 /// \brief A full graph class.
213 /// This is a simple and fast directed full graph implementation.
214 /// It is completely static, so you can neither add nor delete either
216 /// Thus it conforms to
217 /// the \ref concept::Graph "Graph" concept
218 /// \sa concept::Graph.
220 /// \sa FullGraphBase
223 /// \author Alpar Juttner
224 class FullGraph : public ExtendedFullGraphBase {
227 typedef ExtendedFullGraphBase Parent;
229 /// \brief Constructor
230 FullGraph() { construct(0); }
232 /// \brief Constructor
234 FullGraph(int n) { construct(n); }
236 /// \brief Resize the graph
238 /// Resize the graph. The function will fully destroy and build the graph.
239 /// This cause that the maps of the graph will reallocated
240 /// automatically and the previous values will be lost.
242 Parent::getNotifier(Edge()).clear();
243 Parent::getNotifier(Node()).clear();
245 Parent::getNotifier(Node()).build();
246 Parent::getNotifier(Edge()).build();
251 /// \brief Base of the FullUGrpah.
253 /// Base of the FullUGrpah.
254 class FullUGraphBase {
259 typedef FullUGraphBase Graph;
269 ///Creates a full graph with \c n nodes.
270 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
272 /// \brief Returns the node with the given index.
274 /// Returns the node with the given index. Because it is a
275 /// static size graph the node's of the graph can be indiced
276 /// by the range from 0 to \e nodeNum()-1 and the index of
277 /// the node can accessed by the \e index() member.
278 Node operator()(int index) const { return Node(index); }
280 /// \brief Returns the index of the node.
282 /// Returns the index of the node. Because it is a
283 /// static size graph the node's of the graph can be indiced
284 /// by the range from 0 to \e nodeNum()-1 and the index of
285 /// the node can accessed by the \e index() member.
286 int index(const Node& node) const { return node.id; }
288 typedef True NodeNumTag;
289 typedef True EdgeNumTag;
292 int nodeNum() const { return _nodeNum; }
294 int edgeNum() const { return _edgeNum; }
300 int maxNodeId() const { return _nodeNum-1; }
305 int maxEdgeId() const { return _edgeNum-1; }
307 /// \brief Returns the node from its \c id.
309 /// Returns the node from its \c id. If there is not node
310 /// with the given id the effect of the function is undefinied.
311 static Node nodeFromId(int id) { return Node(id);}
313 /// \brief Returns the edge from its \c id.
315 /// Returns the edge from its \c id. If there is not edge
316 /// with the given id the effect of the function is undefinied.
317 static Edge edgeFromId(int id) { return Edge(id);}
319 Node source(Edge e) const {
320 /// \todo we may do it faster
321 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
324 Node target(Edge e) const {
325 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
326 return Node(e.id - (source) * (source - 1) / 2);
332 /// The ID of a valid Node is a nonnegative integer not greater than
333 /// \ref maxNodeId(). The range of the ID's is not surely continuous
334 /// and the greatest node ID can be actually less then \ref maxNodeId().
336 /// The ID of the \ref INVALID node is -1.
337 /// \return The ID of the node \c v.
339 static int id(Node v) { return v.id; }
343 /// The ID of a valid Edge is a nonnegative integer not greater than
344 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
345 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
347 /// The ID of the \ref INVALID edge is -1.
348 ///\return The ID of the edge \c e.
349 static int id(Edge e) { return e.id; }
351 /// \brief Finds an edge between two nodes.
353 /// Finds an edge from node \c u to node \c v.
355 /// If \c prev is \ref INVALID (this is the default value), then
356 /// It finds the first edge from \c u to \c v. Otherwise it looks for
357 /// the next edge from \c u to \c v after \c prev.
358 /// \return The found edge or INVALID if there is no such an edge.
359 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
360 if (prev.id != -1 || u.id <= v.id) return Edge(-1);
361 return Edge(u.id * (u.id - 1) / 2 + v.id);
364 typedef True FindEdgeTag;
368 friend class FullUGraphBase;
372 Node(int _id) { id = _id;}
375 Node (Invalid) { id = -1; }
376 bool operator==(const Node node) const {return id == node.id;}
377 bool operator!=(const Node node) const {return id != node.id;}
378 bool operator<(const Node node) const {return id < node.id;}
384 friend class FullUGraphBase;
387 int id; // _nodeNum * target + source;
389 Edge(int _id) : id(_id) {}
393 Edge (Invalid) { id = -1; }
394 bool operator==(const Edge edge) const {return id == edge.id;}
395 bool operator!=(const Edge edge) const {return id != edge.id;}
396 bool operator<(const Edge edge) const {return id < edge.id;}
399 void first(Node& node) const {
400 node.id = _nodeNum - 1;
403 static void next(Node& node) {
407 void first(Edge& edge) const {
408 edge.id = _edgeNum - 1;
411 static void next(Edge& edge) {
415 void firstOut(Edge& edge, const Node& node) const {
418 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
421 /// \todo with specialized iterators we can make faster iterating
422 void nextOut(Edge& edge) const {
423 int src = source(edge).id;
424 int trg = target(edge).id;
426 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
429 void firstIn(Edge& edge, const Node& node) const {
430 int src = node.id + 1;
432 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
435 void nextIn(Edge& edge) const {
436 int src = source(edge).id;
437 int trg = target(edge).id;
439 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
444 typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
445 ExtendedFullUGraphBase;
449 /// \brief An undirected full graph class.
451 /// This is a simple and fast undirected full graph implementation.
452 /// It is completely static, so you can neither add nor delete either
455 /// The main difference beetween the \e FullGraph and \e FullUGraph class
456 /// is that this class conforms to the undirected graph concept and
457 /// it does not contain the loop edges.
459 /// \sa FullUGraphBase
462 /// \author Balazs Dezso
463 class FullUGraph : public ExtendedFullUGraphBase {
466 typedef ExtendedFullUGraphBase Parent;
468 /// \brief Constructor
469 FullUGraph() { construct(0); }
471 /// \brief Constructor
472 FullUGraph(int n) { construct(n); }
474 /// \brief Resize the graph
476 /// Resize the graph. The function will fully destroy and build the graph.
477 /// This cause that the maps of the graph will reallocated
478 /// automatically and the previous values will be lost.
480 Parent::getNotifier(Edge()).clear();
481 Parent::getNotifier(UEdge()).clear();
482 Parent::getNotifier(Node()).clear();
484 Parent::getNotifier(Node()).build();
485 Parent::getNotifier(UEdge()).build();
486 Parent::getNotifier(Edge()).build();
491 class FullBpUGraphBase {
501 class NodeSetError : public LogicError {
503 virtual const char* what() const throw() {
504 return "lemon::FullBpUGraph::NodeSetError";
509 friend class FullBpUGraphBase;
513 Node(int _id) : id(_id) {}
516 Node(Invalid) { id = -1; }
517 bool operator==(const Node i) const {return id==i.id;}
518 bool operator!=(const Node i) const {return id!=i.id;}
519 bool operator<(const Node i) const {return id<i.id;}
523 friend class FullBpUGraphBase;
527 UEdge(int _id) { id = _id;}
530 UEdge (Invalid) { id = -1; }
531 bool operator==(const UEdge i) const {return id==i.id;}
532 bool operator!=(const UEdge i) const {return id!=i.id;}
533 bool operator<(const UEdge i) const {return id<i.id;}
536 void construct(int aNodeNum, int bNodeNum) {
537 _aNodeNum = aNodeNum;
538 _bNodeNum = bNodeNum;
539 _edgeNum = aNodeNum * bNodeNum;
542 void firstANode(Node& node) const {
543 node.id = 2 * _aNodeNum - 2;
544 if (node.id < 0) node.id = -1;
546 void nextANode(Node& node) const {
548 if (node.id < 0) node.id = -1;
551 void firstBNode(Node& node) const {
552 node.id = 2 * _bNodeNum - 1;
554 void nextBNode(Node& node) const {
558 void first(Node& node) const {
560 node.id = 2 * _aNodeNum - 2;
562 node.id = 2 * _bNodeNum - 1;
565 void next(Node& node) const {
568 node.id = 2 * _bNodeNum - 1;
572 void first(UEdge& edge) const {
573 edge.id = _edgeNum - 1;
575 void next(UEdge& edge) const {
579 void firstFromANode(UEdge& edge, const Node& node) const {
580 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
581 edge.id = (node.id >> 1) * _bNodeNum;
583 void nextFromANode(UEdge& edge) const {
585 if (edge.id % _bNodeNum == 0) edge.id = -1;
588 void firstFromBNode(UEdge& edge, const Node& node) const {
589 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
590 edge.id = (node.id >> 1);
592 void nextFromBNode(UEdge& edge) const {
593 edge.id += _bNodeNum;
594 if (edge.id >= _edgeNum) edge.id = -1;
597 static int id(const Node& node) {
600 static Node nodeFromId(int id) {
603 int maxNodeId() const {
604 return _aNodeNum > _bNodeNum ?
605 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
608 static int id(const UEdge& edge) {
611 static UEdge uEdgeFromId(int id) {
614 int maxUEdgeId() const {
618 static int aNodeId(const Node& node) {
621 static Node fromANodeId(int id) {
622 return Node(id << 1);
624 int maxANodeId() const {
628 static int bNodeId(const Node& node) {
631 static Node fromBNodeId(int id) {
632 return Node((id << 1) + 1);
634 int maxBNodeId() const {
638 Node aNode(const UEdge& edge) const {
639 return Node((edge.id / _bNodeNum) << 1);
641 Node bNode(const UEdge& edge) const {
642 return Node(((edge.id % _bNodeNum) << 1) + 1);
645 static bool aNode(const Node& node) {
646 return (node.id & 1) == 0;
649 static bool bNode(const Node& node) {
650 return (node.id & 1) == 1;
653 static Node aNode(int index) {
654 return Node(index << 1);
657 static Node bNode(int index) {
658 return Node((index << 1) + 1);
661 typedef True NodeNumTag;
662 int nodeNum() const { return _aNodeNum + _bNodeNum; }
663 int aNodeNum() const { return _aNodeNum; }
664 int bNodeNum() const { return _bNodeNum; }
666 typedef True EdgeNumTag;
667 int uEdgeNum() const { return _edgeNum; }
672 typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
677 /// \brief An undirected full bipartite graph class.
679 /// This is a simple and fast bipartite undirected full graph implementation.
680 /// It is completely static, so you can neither add nor delete either
683 /// \sa FullUGraphBase
686 /// \author Balazs Dezso
688 public ExtendedFullBpUGraphBase {
691 typedef ExtendedFullBpUGraphBase Parent;
694 Parent::construct(0, 0);
697 FullBpUGraph(int aNodeNum, int bNodeNum) {
698 Parent::construct(aNodeNum, bNodeNum);
701 /// \brief Resize the graph
703 void resize(int n, int m) {
704 Parent::getNotifier(Edge()).clear();
705 Parent::getNotifier(UEdge()).clear();
706 Parent::getNotifier(Node()).clear();
707 Parent::getNotifier(ANode()).clear();
708 Parent::getNotifier(BNode()).clear();
710 Parent::getNotifier(ANode()).build();
711 Parent::getNotifier(BNode()).build();
712 Parent::getNotifier(Node()).build();
713 Parent::getNotifier(UEdge()).build();
714 Parent::getNotifier(Edge()).build();
721 #endif //LEMON_FULL_GRAPH_H