Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.
Some bugfix in the adaptors
New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.
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::StaticGraph "StaticGraph" concept
218 /// \sa concept::StaticGraph.
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 Node source(Edge e) const {
308 /// \todo we may do it faster
309 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
312 Node target(Edge e) const {
313 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
314 return Node(e.id - (source) * (source - 1) / 2);
320 /// The ID of a valid Node is a nonnegative integer not greater than
321 /// \ref maxNodeId(). The range of the ID's is not surely continuous
322 /// and the greatest node ID can be actually less then \ref maxNodeId().
324 /// The ID of the \ref INVALID node is -1.
325 /// \return The ID of the node \c v.
327 static int id(Node v) { return v.id; }
331 /// The ID of a valid Edge is a nonnegative integer not greater than
332 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
333 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
335 /// The ID of the \ref INVALID edge is -1.
336 ///\return The ID of the edge \c e.
337 static int id(Edge e) { return e.id; }
339 /// \brief Finds an edge between two nodes.
341 /// Finds an edge from node \c u to node \c v.
343 /// If \c prev is \ref INVALID (this is the default value), then
344 /// It finds the first edge from \c u to \c v. Otherwise it looks for
345 /// the next edge from \c u to \c v after \c prev.
346 /// \return The found edge or INVALID if there is no such an edge.
347 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
348 if (prev.id != -1 || u.id <= v.id) return Edge(-1);
349 return Edge(u.id * (u.id - 1) / 2 + v.id);
352 typedef True FindEdgeTag;
356 friend class FullUGraphBase;
360 Node(int _id) { id = _id;}
363 Node (Invalid) { id = -1; }
364 bool operator==(const Node node) const {return id == node.id;}
365 bool operator!=(const Node node) const {return id != node.id;}
366 bool operator<(const Node node) const {return id < node.id;}
372 friend class FullUGraphBase;
375 int id; // _nodeNum * target + source;
377 Edge(int _id) : id(_id) {}
381 Edge (Invalid) { id = -1; }
382 bool operator==(const Edge edge) const {return id == edge.id;}
383 bool operator!=(const Edge edge) const {return id != edge.id;}
384 bool operator<(const Edge edge) const {return id < edge.id;}
387 void first(Node& node) const {
388 node.id = _nodeNum - 1;
391 static void next(Node& node) {
395 void first(Edge& edge) const {
396 edge.id = _edgeNum - 1;
399 static void next(Edge& edge) {
403 void firstOut(Edge& edge, const Node& node) const {
406 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
409 /// \todo with specialized iterators we can make faster iterating
410 void nextOut(Edge& edge) const {
411 int src = source(edge).id;
412 int trg = target(edge).id;
414 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
417 void firstIn(Edge& edge, const Node& node) const {
418 int src = node.id + 1;
420 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
423 void nextIn(Edge& edge) const {
424 int src = source(edge).id;
425 int trg = target(edge).id;
427 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
432 typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
433 ExtendedFullUGraphBase;
437 /// \brief An undirected full graph class.
439 /// This is a simple and fast undirected full graph implementation.
440 /// It is completely static, so you can neither add nor delete either
443 /// The main difference beetween the \e FullGraph and \e FullUGraph class
444 /// is that this class conforms to the undirected graph concept and
445 /// it does not contain the loop edges.
447 /// \sa FullUGraphBase
450 /// \author Balazs Dezso
451 class FullUGraph : public ExtendedFullUGraphBase {
454 typedef ExtendedFullUGraphBase Parent;
456 /// \brief Constructor
457 FullUGraph() { construct(0); }
459 /// \brief Constructor
460 FullUGraph(int n) { construct(n); }
462 /// \brief Resize the graph
464 /// Resize the graph. The function will fully destroy and build the graph.
465 /// This cause that the maps of the graph will reallocated
466 /// automatically and the previous values will be lost.
468 Parent::getNotifier(Edge()).clear();
469 Parent::getNotifier(UEdge()).clear();
470 Parent::getNotifier(Node()).clear();
472 Parent::getNotifier(Node()).build();
473 Parent::getNotifier(UEdge()).build();
474 Parent::getNotifier(Edge()).build();
479 class FullBpUGraphBase {
489 class NodeSetError : public LogicError {
490 virtual const char* exceptionName() const {
491 return "lemon::FullBpUGraph::NodeSetError";
496 friend class FullBpUGraphBase;
500 Node(int _id) : id(_id) {}
503 Node(Invalid) { id = -1; }
504 bool operator==(const Node i) const {return id==i.id;}
505 bool operator!=(const Node i) const {return id!=i.id;}
506 bool operator<(const Node i) const {return id<i.id;}
510 friend class FullBpUGraphBase;
514 Edge(int _id) { id = _id;}
517 Edge (Invalid) { id = -1; }
518 bool operator==(const Edge i) const {return id==i.id;}
519 bool operator!=(const Edge i) const {return id!=i.id;}
520 bool operator<(const Edge i) const {return id<i.id;}
523 void construct(int aNodeNum, int bNodeNum) {
524 _aNodeNum = aNodeNum;
525 _bNodeNum = bNodeNum;
526 _edgeNum = aNodeNum * bNodeNum;
529 void firstANode(Node& node) const {
530 node.id = 2 * _aNodeNum - 2;
531 if (node.id < 0) node.id = -1;
533 void nextANode(Node& node) const {
535 if (node.id < 0) node.id = -1;
538 void firstBNode(Node& node) const {
539 node.id = 2 * _bNodeNum - 1;
541 void nextBNode(Node& node) const {
545 void first(Node& node) const {
547 node.id = 2 * _aNodeNum - 2;
549 node.id = 2 * _bNodeNum - 1;
552 void next(Node& node) const {
555 node.id = 2 * _bNodeNum - 1;
559 void first(Edge& edge) const {
560 edge.id = _edgeNum - 1;
562 void next(Edge& edge) const {
566 void firstOut(Edge& edge, const Node& node) const {
567 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
568 edge.id = (node.id >> 1) * _bNodeNum;
570 void nextOut(Edge& edge) const {
572 if (edge.id % _bNodeNum == 0) edge.id = -1;
575 void firstIn(Edge& edge, const Node& node) const {
576 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
577 edge.id = (node.id >> 1);
579 void nextIn(Edge& edge) const {
580 edge.id += _bNodeNum;
581 if (edge.id >= _edgeNum) edge.id = -1;
584 static int id(const Node& node) {
587 static Node nodeFromId(int id) {
590 int maxNodeId() const {
591 return _aNodeNum > _bNodeNum ?
592 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
595 static int id(const Edge& edge) {
598 static Edge edgeFromId(int id) {
601 int maxEdgeId() const {
605 static int aNodeId(const Node& node) {
608 static Node fromANodeId(int id) {
609 return Node(id << 1);
611 int maxANodeId() const {
615 static int bNodeId(const Node& node) {
618 static Node fromBNodeId(int id) {
619 return Node((id << 1) + 1);
621 int maxBNodeId() const {
625 Node aNode(const Edge& edge) const {
626 return Node((edge.id / _bNodeNum) << 1);
628 Node bNode(const Edge& edge) const {
629 return Node(((edge.id % _bNodeNum) << 1) + 1);
632 static bool aNode(const Node& node) {
633 return (node.id & 1) == 0;
636 static bool bNode(const Node& node) {
637 return (node.id & 1) == 1;
640 static Node aNode(int index) {
641 return Node(index << 1);
644 static Node bNode(int index) {
645 return Node((index << 1) + 1);
648 typedef True NodeNumTag;
649 int nodeNum() const { return _aNodeNum + _bNodeNum; }
650 int aNodeNum() const { return _aNodeNum; }
651 int bNodeNum() const { return _bNodeNum; }
653 typedef True EdgeNumTag;
654 int edgeNum() const { return _edgeNum; }
659 typedef BpUGraphExtender< BpUGraphBaseExtender<
660 FullBpUGraphBase> > ExtendedFullBpUGraphBase;
665 /// \brief An undirected full bipartite graph class.
667 /// This is a simple and fast bipartite undirected full graph implementation.
668 /// It is completely static, so you can neither add nor delete either
671 /// \sa FullUGraphBase
674 /// \author Balazs Dezso
676 public ExtendedFullBpUGraphBase {
679 typedef ExtendedFullBpUGraphBase Parent;
682 Parent::construct(0, 0);
685 FullBpUGraph(int aNodeNum, int bNodeNum) {
686 Parent::construct(aNodeNum, bNodeNum);
689 /// \brief Resize the graph
691 void resize(int n, int m) {
692 Parent::getNotifier(Edge()).clear();
693 Parent::getNotifier(UEdge()).clear();
694 Parent::getNotifier(Node()).clear();
695 Parent::getNotifier(ANode()).clear();
696 Parent::getNotifier(BNode()).clear();
698 Parent::getNotifier(ANode()).build();
699 Parent::getNotifier(BNode()).build();
700 Parent::getNotifier(Node()).build();
701 Parent::getNotifier(UEdge()).build();
702 Parent::getNotifier(Edge()).build();
709 #endif //LEMON_FULL_GRAPH_H