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_SMART_GRAPH_H
20 #define LEMON_SMART_GRAPH_H
24 ///\brief SmartGraph and SmartUGraph classes.
28 #include <lemon/bits/invalid.h>
30 #include <lemon/bits/base_extender.h>
31 #include <lemon/bits/graph_extender.h>
33 #include <lemon/bits/utility.h>
34 #include <lemon/error.h>
36 #include <lemon/bits/graph_extender.h>
45 class SmartGraphBase {
47 friend class SmatGraph;
52 int first_in,first_out;
53 NodeT() : first_in(-1), first_out(-1) {}
57 int target, source, next_in, next_out;
58 //FIXME: is this necessary?
59 EdgeT() : next_in(-1), next_out(-1) {}
62 std::vector<NodeT> nodes;
64 std::vector<EdgeT> edges;
69 typedef SmartGraphBase Graph;
77 SmartGraphBase() : nodes(), edges() { }
78 SmartGraphBase(const SmartGraphBase &_g)
79 : nodes(_g.nodes), edges(_g.edges) { }
81 typedef True NodeNumTag;
82 typedef True EdgeNumTag;
85 int nodeNum() const { return nodes.size(); }
87 int edgeNum() const { return edges.size(); }
93 int maxNodeId() const { return nodes.size()-1; }
98 int maxEdgeId() const { return edges.size()-1; }
100 Node source(Edge e) const { return edges[e.n].source; }
101 Node target(Edge e) const { return edges[e.n].target; }
105 /// The ID of a valid Node is a nonnegative integer not greater than
106 /// \ref maxNodeId(). The range of the ID's is not surely continuous
107 /// and the greatest node ID can be actually less then \ref maxNodeId().
109 /// The ID of the \ref INVALID node is -1.
110 ///\return The ID of the node \c v.
111 static int id(Node v) { return v.n; }
114 /// The ID of a valid Edge is a nonnegative integer not greater than
115 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
116 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
118 /// The ID of the \ref INVALID edge is -1.
119 ///\return The ID of the edge \c e.
120 static int id(Edge e) { return e.n; }
122 static Node nodeFromId(int id) { return Node(id);}
124 static Edge edgeFromId(int id) { return Edge(id);}
127 Node n; n.n=nodes.size();
128 nodes.push_back(NodeT()); //FIXME: Hmmm...
132 Edge addEdge(Node u, Node v) {
133 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
134 edges[e.n].source=u.n; edges[e.n].target=v.n;
135 edges[e.n].next_out=nodes[u.n].first_out;
136 edges[e.n].next_in=nodes[v.n].first_in;
137 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
149 friend class SmartGraphBase;
150 friend class SmartGraph;
157 Node (Invalid) { n=-1; }
158 bool operator==(const Node i) const {return n==i.n;}
159 bool operator!=(const Node i) const {return n!=i.n;}
160 bool operator<(const Node i) const {return n<i.n;}
165 friend class SmartGraphBase;
166 friend class SmartGraph;
173 Edge (Invalid) { n=-1; }
174 bool operator==(const Edge i) const {return n==i.n;}
175 bool operator!=(const Edge i) const {return n!=i.n;}
176 bool operator<(const Edge i) const {return n<i.n;}
179 void first(Node& node) const {
180 node.n = nodes.size() - 1;
183 static void next(Node& node) {
187 void first(Edge& edge) const {
188 edge.n = edges.size() - 1;
191 static void next(Edge& edge) {
195 void firstOut(Edge& edge, const Node& node) const {
196 edge.n = nodes[node.n].first_out;
199 void nextOut(Edge& edge) const {
200 edge.n = edges[edge.n].next_out;
203 void firstIn(Edge& edge, const Node& node) const {
204 edge.n = nodes[node.n].first_in;
207 void nextIn(Edge& edge) const {
208 edge.n = edges[edge.n].next_in;
211 Node _split(Node n, bool connect = true)
214 nodes[b.n].first_out=nodes[n.n].first_out;
215 nodes[n.n].first_out=-1;
216 for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
217 if(connect) addEdge(n,b);
223 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
227 ///A smart graph class.
229 ///This is a simple and fast graph implementation.
230 ///It is also quite memory efficient, but at the price
231 ///that <b> it does support only limited (only stack-like)
232 ///node and edge deletions</b>.
234 ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
235 ///\sa concept::ExtendableGraph.
237 ///\author Alpar Juttner
238 class SmartGraph : public ExtendedSmartGraphBase {
241 typedef ExtendedSmartGraphBase Parent;
244 friend class Snapshot;
247 void restoreSnapshot(const Snapshot &s)
249 while(s.edge_num<edges.size()) {
250 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
251 nodes[edges.back().target].first_in=edges.back().next_in;
252 nodes[edges.back().source].first_out=edges.back().next_out;
255 //nodes.resize(s.nodes_num);
256 while(s.node_num<nodes.size()) {
257 Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
266 ///This function splits a node. First a new node is added to the graph,
267 ///then the source of each outgoing edge of \c n is moved to this new node.
268 ///If \c connect is \c true (this is the default value), then a new edge
269 ///from \c n to the newly created node is also added.
270 ///\return The newly created node.
272 ///\note The <tt>Edge</tt>s
273 ///referencing a moved edge remain
274 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
275 ///may be invalidated.
276 ///\warning This functionality cannot be used together with the Snapshot
278 ///\todo It could be implemented in a bit faster way.
279 Node split(Node n, bool connect = true)
281 Node b = _split(n,connect);
286 ///Class to make a snapshot of the graph and to restrore to it later.
288 ///Class to make a snapshot of the graph and to restrore to it later.
290 ///The newly added nodes and edges can be removed using the
291 ///restore() function.
292 ///\note After you restore a state, you cannot restore
293 ///a later state, in other word you cannot add again the edges deleted
294 ///by restore() using another Snapshot instance.
300 friend class SmartGraph;
301 unsigned int node_num;
302 unsigned int edge_num;
304 ///Default constructor.
306 ///Default constructor.
307 ///To actually make a snapshot you must call save().
310 ///Constructor that immediately makes a snapshot
312 ///This constructor immediately makes a snapshot of the graph.
313 ///\param _g The graph we make a snapshot of.
314 Snapshot(SmartGraph &_g) :g(&_g) {
315 node_num=g->nodes.size();
316 edge_num=g->edges.size();
321 ///Make a snapshot of the graph.
323 ///This function can be called more than once. In case of a repeated
324 ///call, the previous snapshot gets lost.
325 ///\param _g The graph we make the snapshot of.
326 void save(SmartGraph &_g)
329 node_num=g->nodes.size();
330 edge_num=g->edges.size();
333 ///Undo the changes until a snapshot.
335 ///Undo the changes until a snapshot created by save().
337 ///\note After you restored a state, you cannot restore
338 ///a later state, in other word you cannot add again the edges deleted
341 ///\todo This function might be called undo().
345 g->restoreSnapshot(*this);
351 /**************** Undirected List Graph ****************/
353 typedef UGraphExtender<UGraphBaseExtender<SmartGraphBase> >
354 ExtendedSmartUGraphBase;
358 /// \brief A smart undirected graph class.
360 /// This is a simple and fast undirected graph implementation.
361 /// It is also quite memory efficient, but at the price
362 /// that <b> it does support only limited (only stack-like)
363 /// node and edge deletions</b>.
364 /// Except from this it conforms to
365 /// the \ref concept::UGraph "UGraph" concept.
366 /// \sa concept::UGraph.
368 /// \todo Snapshot hasn't been implemented yet.
370 class SmartUGraph : public ExtendedSmartUGraphBase {
374 class SmartBpUGraphBase {
377 class NodeSetError : public LogicError {
378 virtual const char* exceptionName() const {
379 return "lemon::SmartBpUGraph::NodeSetError";
388 NodeT(int _first) : first(_first) {}
396 std::vector<NodeT> aNodes;
397 std::vector<NodeT> bNodes;
399 std::vector<EdgeT> edges;
404 friend class SmartBpUGraphBase;
408 Node(int _id) : id(_id) {}
411 Node(Invalid) { id = -1; }
412 bool operator==(const Node i) const {return id==i.id;}
413 bool operator!=(const Node i) const {return id!=i.id;}
414 bool operator<(const Node i) const {return id<i.id;}
418 friend class SmartBpUGraphBase;
422 Edge(int _id) { id = _id;}
425 Edge (Invalid) { id = -1; }
426 bool operator==(const Edge i) const {return id==i.id;}
427 bool operator!=(const Edge i) const {return id!=i.id;}
428 bool operator<(const Edge i) const {return id<i.id;}
431 void firstANode(Node& node) const {
432 node.id = 2 * aNodes.size() - 2;
433 if (node.id < 0) node.id = -1;
435 void nextANode(Node& node) const {
437 if (node.id < 0) node.id = -1;
440 void firstBNode(Node& node) const {
441 node.id = 2 * bNodes.size() - 1;
443 void nextBNode(Node& node) const {
447 void first(Node& node) const {
448 if (aNodes.size() > 0) {
449 node.id = 2 * aNodes.size() - 2;
451 node.id = 2 * bNodes.size() - 1;
454 void next(Node& node) const {
457 node.id = 2 * bNodes.size() - 1;
461 void first(Edge& edge) const {
462 edge.id = edges.size() - 1;
464 void next(Edge& edge) const {
468 void firstOut(Edge& edge, const Node& node) const {
469 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
470 edge.id = aNodes[node.id >> 1].first;
472 void nextOut(Edge& edge) const {
473 edge.id = edges[edge.id].next_out;
476 void firstIn(Edge& edge, const Node& node) const {
477 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
478 edge.id = bNodes[node.id >> 1].first;
480 void nextIn(Edge& edge) const {
481 edge.id = edges[edge.id].next_in;
484 static int id(const Node& node) {
487 static Node nodeFromId(int id) {
490 int maxNodeId() const {
491 return aNodes.size() > bNodes.size() ?
492 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
495 static int id(const Edge& edge) {
498 static Edge edgeFromId(int id) {
501 int maxEdgeId() const {
505 static int aNodeId(const Node& node) {
508 static Node fromANodeId(int id) {
509 return Node(id << 1);
511 int maxANodeId() const {
512 return aNodes.size();
515 static int bNodeId(const Node& node) {
518 static Node fromBNodeId(int id) {
519 return Node((id << 1) + 1);
521 int maxBNodeId() const {
522 return bNodes.size();
525 Node aNode(const Edge& edge) const {
526 return Node(edges[edge.id].aNode);
528 Node bNode(const Edge& edge) const {
529 return Node(edges[edge.id].bNode);
532 static bool aNode(const Node& node) {
533 return (node.id & 1) == 0;
536 static bool bNode(const Node& node) {
537 return (node.id & 1) == 1;
543 aNodes.push_back(nodeT);
544 return Node(aNodes.size() * 2 - 2);
550 bNodes.push_back(nodeT);
551 return Node(bNodes.size() * 2 - 1);
554 Edge addEdge(const Node& source, const Node& target) {
555 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
557 if ((source.id & 1) == 0) {
558 edgeT.aNode = source.id;
559 edgeT.bNode = target.id;
561 edgeT.aNode = target.id;
562 edgeT.bNode = source.id;
564 edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
565 aNodes[edgeT.aNode >> 1].first = edges.size();
566 edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
567 bNodes[edgeT.bNode >> 1].first = edges.size();
568 edges.push_back(edgeT);
569 return Edge(edges.size() - 1);
578 typedef True NodeNumTag;
579 int nodeNum() const { return aNodes.size() + bNodes.size(); }
580 int aNodeNum() const { return aNodes.size(); }
581 int bNodeNum() const { return bNodes.size(); }
583 typedef True EdgeNumTag;
584 int edgeNum() const { return edges.size(); }
589 typedef BpUGraphExtender< BpUGraphBaseExtender<
590 SmartBpUGraphBase> > ExtendedSmartBpUGraphBase;
594 /// \brief A smart bipartite undirected graph class.
596 /// This is a simple and fast bipartite undirected graph implementation.
597 /// It is also quite memory efficient, but at the price
598 /// that <b> it does not support node and edge deletions</b>.
599 /// Except from this it conforms to
600 /// the \ref concept::BpUGraph "BpUGraph" concept.
601 /// \sa concept::BpUGraph.
603 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
610 #endif //LEMON_SMART_GRAPH_H