The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
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
25 #include <lemon/bits/graph_extender.h>
28 #include <lemon/invalid.h>
29 #include <lemon/utility.h>
34 ///\brief FullGraph and FullUGraph classes.
39 /// \brief Base of the FullGrpah.
41 /// Base of the FullGrpah.
47 typedef FullGraphBase Graph;
57 ///Creates a full graph with \c n nodes.
58 void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
60 typedef True NodeNumTag;
61 typedef True EdgeNumTag;
63 /// \brief Returns the node with the given index.
65 /// Returns the node with the given index. Because it is a
66 /// static size graph the node's of the graph can be indiced
67 /// by the range from 0 to \e nodeNum()-1 and the index of
68 /// the node can accessed by the \e index() member.
69 Node operator()(int index) const { return Node(index); }
71 /// \brief Returns the index of the node.
73 /// Returns the index of the node. Because it is a
74 /// static size graph the node's of the graph can be indiced
75 /// by the range from 0 to \e nodeNum()-1 and the index of
76 /// the node can accessed by the \e index() member.
77 int index(const Node& node) const { return node.id; }
80 int nodeNum() const { return _nodeNum; }
82 int edgeNum() const { return _edgeNum; }
88 int maxNodeId() const { return _nodeNum-1; }
93 int maxEdgeId() const { return _edgeNum-1; }
95 Node source(Edge e) const { return e.id % _nodeNum; }
96 Node target(Edge e) const { return e.id / _nodeNum; }
101 /// The ID of a valid Node is a nonnegative integer not greater than
102 /// \ref maxNodeId(). The range of the ID's is not surely continuous
103 /// and the greatest node ID can be actually less then \ref maxNodeId().
105 /// The ID of the \ref INVALID node is -1.
106 ///\return The ID of the node \c v.
108 static int id(Node v) { return v.id; }
111 /// The ID of a valid Edge is a nonnegative integer not greater than
112 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
113 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
115 /// The ID of the \ref INVALID edge is -1.
116 ///\return The ID of the edge \c e.
117 static int id(Edge e) { return e.id; }
119 static Node nodeFromId(int id) { return Node(id);}
121 static Edge edgeFromId(int id) { return Edge(id);}
123 typedef True FindEdgeTag;
125 /// Finds an edge between two nodes.
127 /// Finds an edge from node \c u to node \c v.
129 /// If \c prev is \ref INVALID (this is the default value), then
130 /// It finds the first edge from \c u to \c v. Otherwise it looks for
131 /// the next edge from \c u to \c v after \c prev.
132 /// \return The found edge or INVALID if there is no such an edge.
133 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
134 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
139 friend class FullGraphBase;
143 Node(int _id) : id(_id) {}
146 Node (Invalid) : id(-1) {}
147 bool operator==(const Node node) const {return id == node.id;}
148 bool operator!=(const Node node) const {return id != node.id;}
149 bool operator<(const Node node) const {return id < node.id;}
155 friend class FullGraphBase;
158 int id; // _nodeNum * target + source;
160 Edge(int _id) : id(_id) {}
162 Edge(const FullGraphBase& _graph, int source, int target)
163 : id(_graph._nodeNum * target+source) {}
166 Edge (Invalid) { id = -1; }
167 bool operator==(const Edge edge) const {return id == edge.id;}
168 bool operator!=(const Edge edge) const {return id != edge.id;}
169 bool operator<(const Edge edge) const {return id < edge.id;}
172 void first(Node& node) const {
173 node.id = _nodeNum-1;
176 static void next(Node& node) {
180 void first(Edge& edge) const {
181 edge.id = _edgeNum-1;
184 static void next(Edge& edge) {
188 void firstOut(Edge& edge, const Node& node) const {
189 edge.id = _edgeNum + node.id - _nodeNum;
192 void nextOut(Edge& edge) const {
194 if (edge.id < 0) edge.id = -1;
197 void firstIn(Edge& edge, const Node& node) const {
198 edge.id = node.id * _nodeNum;
201 void nextIn(Edge& edge) const {
203 if (edge.id % _nodeNum == 0) edge.id = -1;
208 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
212 /// \brief A full graph class.
214 /// This is a simple and fast directed full graph implementation.
215 /// It is completely static, so you can neither add nor delete either
217 /// Thus it conforms to
218 /// the \ref concept::StaticGraph "StaticGraph" concept
219 /// \sa concept::StaticGraph.
221 /// \sa FullGraphBase
224 /// \author Alpar Juttner
225 class FullGraph : public ExtendedFullGraphBase {
228 typedef ExtendedFullGraphBase Parent;
230 /// \brief Constructor
231 FullGraph() { construct(0); }
233 /// \brief Constructor
235 FullGraph(int n) { construct(n); }
237 /// \brief Resize the graph
239 /// Resize the graph. The function will fully destroy and build the graph.
240 /// This cause that the maps of the graph will reallocated
241 /// automatically and the previous values will be lost.
243 Parent::getNotifier(Edge()).clear();
244 Parent::getNotifier(Node()).clear();
246 Parent::getNotifier(Node()).build();
247 Parent::getNotifier(Edge()).build();
252 /// \brief Base of the FullUGrpah.
254 /// Base of the FullUGrpah.
255 class FullUGraphBase {
260 typedef FullUGraphBase Graph;
270 ///Creates a full graph with \c n nodes.
271 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
273 /// \brief Returns the node with the given index.
275 /// Returns the node with the given index. Because it is a
276 /// static size graph the node's of the graph can be indiced
277 /// by the range from 0 to \e nodeNum()-1 and the index of
278 /// the node can accessed by the \e index() member.
279 Node operator()(int index) const { return Node(index); }
281 /// \brief Returns the index of the node.
283 /// Returns the index of the node. Because it is a
284 /// static size graph the node's of the graph can be indiced
285 /// by the range from 0 to \e nodeNum()-1 and the index of
286 /// the node can accessed by the \e index() member.
287 int index(const Node& node) const { return node.id; }
289 typedef True NodeNumTag;
290 typedef True EdgeNumTag;
293 int nodeNum() const { return _nodeNum; }
295 int edgeNum() const { return _edgeNum; }
301 int maxNodeId() const { return _nodeNum-1; }
306 int maxEdgeId() const { return _edgeNum-1; }
308 Node source(Edge e) const {
309 /// \todo we may do it faster
310 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
313 Node target(Edge e) const {
314 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
315 return Node(e.id - (source) * (source - 1) / 2);
321 /// The ID of a valid Node is a nonnegative integer not greater than
322 /// \ref maxNodeId(). The range of the ID's is not surely continuous
323 /// and the greatest node ID can be actually less then \ref maxNodeId().
325 /// The ID of the \ref INVALID node is -1.
326 /// \return The ID of the node \c v.
328 static int id(Node v) { return v.id; }
332 /// The ID of a valid Edge is a nonnegative integer not greater than
333 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
334 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
336 /// The ID of the \ref INVALID edge is -1.
337 ///\return The ID of the edge \c e.
338 static int id(Edge e) { return e.id; }
340 /// \brief Finds an edge between two nodes.
342 /// Finds an edge from node \c u to node \c v.
344 /// If \c prev is \ref INVALID (this is the default value), then
345 /// It finds the first edge from \c u to \c v. Otherwise it looks for
346 /// the next edge from \c u to \c v after \c prev.
347 /// \return The found edge or INVALID if there is no such an edge.
348 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
349 if (prev.id != -1 || u.id <= v.id) return Edge(-1);
350 return Edge(u.id * (u.id - 1) / 2 + v.id);
353 typedef True FindEdgeTag;
357 friend class FullUGraphBase;
361 Node(int _id) { id = _id;}
364 Node (Invalid) { id = -1; }
365 bool operator==(const Node node) const {return id == node.id;}
366 bool operator!=(const Node node) const {return id != node.id;}
367 bool operator<(const Node node) const {return id < node.id;}
373 friend class FullUGraphBase;
376 int id; // _nodeNum * target + source;
378 Edge(int _id) : id(_id) {}
382 Edge (Invalid) { id = -1; }
383 bool operator==(const Edge edge) const {return id == edge.id;}
384 bool operator!=(const Edge edge) const {return id != edge.id;}
385 bool operator<(const Edge edge) const {return id < edge.id;}
388 void first(Node& node) const {
389 node.id = _nodeNum - 1;
392 static void next(Node& node) {
396 void first(Edge& edge) const {
397 edge.id = _edgeNum - 1;
400 static void next(Edge& edge) {
404 void firstOut(Edge& edge, const Node& node) const {
407 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
410 /// \todo with specialized iterators we can make faster iterating
411 void nextOut(Edge& edge) const {
412 int src = source(edge).id;
413 int trg = target(edge).id;
415 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
418 void firstIn(Edge& edge, const Node& node) const {
419 int src = node.id + 1;
421 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
424 void nextIn(Edge& edge) const {
425 int src = source(edge).id;
426 int trg = target(edge).id;
428 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
433 typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
434 ExtendedFullUGraphBase;
438 /// \brief An undirected full graph class.
440 /// This is a simple and fast undirected full graph implementation.
441 /// It is completely static, so you can neither add nor delete either
444 /// The main difference beetween the \e FullGraph and \e FullUGraph class
445 /// is that this class conforms to the undirected graph concept and
446 /// it does not contain the loop edges.
448 /// \sa FullUGraphBase
451 /// \author Balazs Dezso
452 class FullUGraph : public ExtendedFullUGraphBase {
455 typedef ExtendedFullUGraphBase Parent;
457 /// \brief Constructor
458 FullUGraph() { construct(0); }
460 /// \brief Constructor
461 FullUGraph(int n) { construct(n); }
463 /// \brief Resize the graph
465 /// Resize the graph. The function will fully destroy and build the graph.
466 /// This cause that the maps of the graph will reallocated
467 /// automatically and the previous values will be lost.
469 Parent::getNotifier(Edge()).clear();
470 Parent::getNotifier(UEdge()).clear();
471 Parent::getNotifier(Node()).clear();
473 Parent::getNotifier(Node()).build();
474 Parent::getNotifier(UEdge()).build();
475 Parent::getNotifier(Edge()).build();
480 class FullBpUGraphBase {
490 class NodeSetError : public LogicError {
491 virtual const char* exceptionName() const {
492 return "lemon::FullBpUGraph::NodeSetError";
497 friend class FullBpUGraphBase;
501 Node(int _id) : id(_id) {}
504 Node(Invalid) { id = -1; }
505 bool operator==(const Node i) const {return id==i.id;}
506 bool operator!=(const Node i) const {return id!=i.id;}
507 bool operator<(const Node i) const {return id<i.id;}
511 friend class FullBpUGraphBase;
515 Edge(int _id) { id = _id;}
518 Edge (Invalid) { id = -1; }
519 bool operator==(const Edge i) const {return id==i.id;}
520 bool operator!=(const Edge i) const {return id!=i.id;}
521 bool operator<(const Edge i) const {return id<i.id;}
524 void construct(int aNodeNum, int bNodeNum) {
525 _aNodeNum = aNodeNum;
526 _bNodeNum = bNodeNum;
527 _edgeNum = aNodeNum * bNodeNum;
530 void firstANode(Node& node) const {
531 node.id = 2 * _aNodeNum - 2;
532 if (node.id < 0) node.id = -1;
534 void nextANode(Node& node) const {
536 if (node.id < 0) node.id = -1;
539 void firstBNode(Node& node) const {
540 node.id = 2 * _bNodeNum - 1;
542 void nextBNode(Node& node) const {
546 void first(Node& node) const {
548 node.id = 2 * _aNodeNum - 2;
550 node.id = 2 * _bNodeNum - 1;
553 void next(Node& node) const {
556 node.id = 2 * _bNodeNum - 1;
560 void first(Edge& edge) const {
561 edge.id = _edgeNum - 1;
563 void next(Edge& edge) const {
567 void firstOut(Edge& edge, const Node& node) const {
568 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
569 edge.id = (node.id >> 1) * _bNodeNum;
571 void nextOut(Edge& edge) const {
573 if (edge.id % _bNodeNum == 0) edge.id = -1;
576 void firstIn(Edge& edge, const Node& node) const {
577 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
578 edge.id = (node.id >> 1);
580 void nextIn(Edge& edge) const {
581 edge.id += _bNodeNum;
582 if (edge.id >= _edgeNum) edge.id = -1;
585 static int id(const Node& node) {
588 static Node nodeFromId(int id) {
591 int maxNodeId() const {
592 return _aNodeNum > _bNodeNum ?
593 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
596 static int id(const Edge& edge) {
599 static Edge edgeFromId(int id) {
602 int maxEdgeId() const {
606 static int aNodeId(const Node& node) {
609 static Node fromANodeId(int id, Node) {
610 return Node(id << 1);
612 int maxANodeId() const {
616 static int bNodeId(const Node& node) {
619 static Node fromBNodeId(int id) {
620 return Node((id << 1) + 1);
622 int maxBNodeId() const {
626 Node aNode(const Edge& edge) const {
627 return Node((edge.id / _bNodeNum) << 1);
629 Node bNode(const Edge& edge) const {
630 return Node(((edge.id % _bNodeNum) << 1) + 1);
633 static bool aNode(const Node& node) {
634 return (node.id & 1) == 0;
637 static bool bNode(const Node& node) {
638 return (node.id & 1) == 1;
641 static Node aNode(int index) {
642 return Node(index << 1);
645 static Node bNode(int index) {
646 return Node((index << 1) + 1);
652 typedef BpUGraphExtender< BpUGraphBaseExtender<
653 FullBpUGraphBase> > ExtendedFullBpUGraphBase;
658 /// \brief An undirected full bipartite graph class.
660 /// This is a simple and fast bipartite undirected full graph implementation.
661 /// It is completely static, so you can neither add nor delete either
664 /// \sa FullUGraphBase
667 /// \author Balazs Dezso
669 public ExtendedFullBpUGraphBase {
672 typedef ExtendedFullBpUGraphBase Parent;
675 Parent::construct(0, 0);
678 FullBpUGraph(int aNodeNum, int bNodeNum) {
679 Parent::construct(aNodeNum, bNodeNum);
682 /// \brief Resize the graph
684 void resize(int n, int m) {
685 Parent::getNotifier(Edge()).clear();
686 Parent::getNotifier(UEdge()).clear();
687 Parent::getNotifier(Node()).clear();
688 Parent::getNotifier(ANode()).clear();
689 Parent::getNotifier(BNode()).clear();
691 Parent::getNotifier(ANode()).build();
692 Parent::getNotifier(BNode()).build();
693 Parent::getNotifier(Node()).build();
694 Parent::getNotifier(UEdge()).build();
695 Parent::getNotifier(Edge()).build();
702 #endif //LEMON_FULL_GRAPH_H