Update README file.
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
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 SmartDigraph and SmartGraph classes.
28 #include <lemon/core.h>
29 #include <lemon/error.h>
30 #include <lemon/bits/graph_extender.h>
35 ///Base of SmartDigraph
37 ///Base of SmartDigraph
39 class SmartDigraphBase {
44 int first_in, first_out;
49 int target, source, next_in, next_out;
53 std::vector<NodeT> nodes;
54 std::vector<ArcT> arcs;
58 typedef SmartDigraphBase Graph;
65 SmartDigraphBase() : nodes(), arcs() { }
66 SmartDigraphBase(const SmartDigraphBase &_g)
67 : nodes(_g.nodes), arcs(_g.arcs) { }
69 typedef True NodeNumTag;
70 typedef True EdgeNumTag;
72 int nodeNum() const { return nodes.size(); }
73 int arcNum() const { return arcs.size(); }
75 int maxNodeId() const { return nodes.size()-1; }
76 int maxArcId() const { return arcs.size()-1; }
80 nodes.push_back(NodeT());
81 nodes[n].first_in = -1;
82 nodes[n].first_out = -1;
86 Arc addArc(Node u, Node v) {
88 arcs.push_back(ArcT());
89 arcs[n].source = u._id;
90 arcs[n].target = v._id;
91 arcs[n].next_out = nodes[u._id].first_out;
92 arcs[n].next_in = nodes[v._id].first_in;
93 nodes[u._id].first_out = nodes[v._id].first_in = n;
103 Node source(Arc a) const { return Node(arcs[a._id].source); }
104 Node target(Arc a) const { return Node(arcs[a._id].target); }
106 static int id(Node v) { return v._id; }
107 static int id(Arc a) { return a._id; }
109 static Node nodeFromId(int id) { return Node(id);}
110 static Arc arcFromId(int id) { return Arc(id);}
112 bool valid(Node n) const {
113 return n._id >= 0 && n._id < static_cast<int>(nodes.size());
115 bool valid(Arc a) const {
116 return a._id >= 0 && a._id < static_cast<int>(arcs.size());
120 friend class SmartDigraphBase;
121 friend class SmartDigraph;
125 explicit Node(int id) : _id(id) {}
128 Node (Invalid) : _id(-1) {}
129 bool operator==(const Node i) const {return _id == i._id;}
130 bool operator!=(const Node i) const {return _id != i._id;}
131 bool operator<(const Node i) const {return _id < i._id;}
136 friend class SmartDigraphBase;
137 friend class SmartDigraph;
141 explicit Arc(int id) : _id(id) {}
144 Arc (Invalid) : _id(-1) {}
145 bool operator==(const Arc i) const {return _id == i._id;}
146 bool operator!=(const Arc i) const {return _id != i._id;}
147 bool operator<(const Arc i) const {return _id < i._id;}
150 void first(Node& node) const {
151 node._id = nodes.size() - 1;
154 static void next(Node& node) {
158 void first(Arc& arc) const {
159 arc._id = arcs.size() - 1;
162 static void next(Arc& arc) {
166 void firstOut(Arc& arc, const Node& node) const {
167 arc._id = nodes[node._id].first_out;
170 void nextOut(Arc& arc) const {
171 arc._id = arcs[arc._id].next_out;
174 void firstIn(Arc& arc, const Node& node) const {
175 arc._id = nodes[node._id].first_in;
178 void nextIn(Arc& arc) const {
179 arc._id = arcs[arc._id].next_in;
184 typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
188 ///\brief A smart directed graph class.
190 ///This is a simple and fast digraph implementation.
191 ///It is also quite memory efficient, but at the price
192 ///that <b> it does support only limited (only stack-like)
193 ///node and arc deletions</b>.
194 ///It conforms to the \ref concepts::Digraph "Digraph concept" with
195 ///an important extra feature that its maps are real \ref
196 ///concepts::ReferenceMap "reference map"s.
198 ///\sa concepts::Digraph.
199 class SmartDigraph : public ExtendedSmartDigraphBase {
202 typedef ExtendedSmartDigraphBase Parent;
206 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
208 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
210 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
211 ///\brief Assignment of SmartDigraph to another one is \e not allowed.
212 ///Use DigraphCopy() instead.
214 ///Assignment of SmartDigraph to another one is \e not allowed.
215 ///Use DigraphCopy() instead.
216 void operator=(const SmartDigraph &) {}
226 ///Add a new node to the digraph.
228 /// \return the new node.
230 Node addNode() { return Parent::addNode(); }
232 ///Add a new arc to the digraph.
234 ///Add a new arc to the digraph with source node \c s
235 ///and target node \c t.
236 ///\return the new arc.
237 Arc addArc(const Node& s, const Node& t) {
238 return Parent::addArc(s, t);
241 /// \brief Using this it is possible to avoid the superfluous memory
244 /// Using this it is possible to avoid the superfluous memory
245 /// allocation: if you know that the digraph you want to build will
246 /// be very large (e.g. it will contain millions of nodes and/or arcs)
247 /// then it is worth reserving space for this amount before starting
248 /// to build the digraph.
250 void reserveNode(int n) { nodes.reserve(n); };
252 /// \brief Using this it is possible to avoid the superfluous memory
255 /// Using this it is possible to avoid the superfluous memory
256 /// allocation: if you know that the digraph you want to build will
257 /// be very large (e.g. it will contain millions of nodes and/or arcs)
258 /// then it is worth reserving space for this amount before starting
259 /// to build the digraph.
261 void reserveArc(int m) { arcs.reserve(m); };
263 /// \brief Node validity check
265 /// This function gives back true if the given node is valid,
266 /// ie. it is a real node of the graph.
268 /// \warning A removed node (using Snapshot) could become valid again
269 /// when new nodes are added to the graph.
270 bool valid(Node n) const { return Parent::valid(n); }
272 /// \brief Arc validity check
274 /// This function gives back true if the given arc is valid,
275 /// ie. it is a real arc of the graph.
277 /// \warning A removed arc (using Snapshot) could become valid again
278 /// when new arcs are added to the graph.
279 bool valid(Arc a) const { return Parent::valid(a); }
281 ///Clear the digraph.
283 ///Erase all the nodes and arcs from the digraph.
291 ///This function splits a node. First a new node is added to the digraph,
292 ///then the source of each outgoing arc of \c n is moved to this new node.
293 ///If \c connect is \c true (this is the default value), then a new arc
294 ///from \c n to the newly created node is also added.
295 ///\return The newly created node.
297 ///\note The <tt>Arc</tt>s
298 ///referencing a moved arc remain
299 ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
300 ///may be invalidated.
301 ///\warning This functionality cannot be used together with the Snapshot
303 ///\todo It could be implemented in a bit faster way.
304 Node split(Node n, bool connect = true)
307 nodes[b._id].first_out=nodes[n._id].first_out;
308 nodes[n._id].first_out=-1;
309 for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
310 if(connect) addArc(n,b);
320 void restoreSnapshot(const Snapshot &s)
322 while(s.arc_num<arcs.size()) {
323 Arc arc = arcFromId(arcs.size()-1);
324 Parent::notifier(Arc()).erase(arc);
325 nodes[arcs.back().source].first_out=arcs.back().next_out;
326 nodes[arcs.back().target].first_in=arcs.back().next_in;
329 while(s.node_num<nodes.size()) {
330 Node node = nodeFromId(nodes.size()-1);
331 Parent::notifier(Node()).erase(node);
338 ///Class to make a snapshot of the digraph and to restrore to it later.
340 ///Class to make a snapshot of the digraph and to restrore to it later.
342 ///The newly added nodes and arcs can be removed using the
343 ///restore() function.
344 ///\note After you restore a state, you cannot restore
345 ///a later state, in other word you cannot add again the arcs deleted
346 ///by restore() using another one Snapshot instance.
348 ///\warning If you do not use correctly the snapshot that can cause
349 ///either broken program, invalid state of the digraph, valid but
350 ///not the restored digraph or no change. Because the runtime performance
351 ///the validity of the snapshot is not stored.
354 SmartDigraph *_graph;
356 friend class SmartDigraph;
357 unsigned int node_num;
358 unsigned int arc_num;
360 ///Default constructor.
362 ///Default constructor.
363 ///To actually make a snapshot you must call save().
365 Snapshot() : _graph(0) {}
366 ///Constructor that immediately makes a snapshot
368 ///This constructor immediately makes a snapshot of the digraph.
369 ///\param _g The digraph we make a snapshot of.
370 Snapshot(SmartDigraph &graph) : _graph(&graph) {
371 node_num=_graph->nodes.size();
372 arc_num=_graph->arcs.size();
377 ///Make a snapshot of the digraph.
379 ///This function can be called more than once. In case of a repeated
380 ///call, the previous snapshot gets lost.
381 ///\param _g The digraph we make the snapshot of.
382 void save(SmartDigraph &graph)
385 node_num=_graph->nodes.size();
386 arc_num=_graph->arcs.size();
389 ///Undo the changes until a snapshot.
391 ///Undo the changes until a snapshot created by save().
393 ///\note After you restored a state, you cannot restore
394 ///a later state, in other word you cannot add again the arcs deleted
398 _graph->restoreSnapshot(*this);
404 class SmartGraphBase {
417 std::vector<NodeT> nodes;
418 std::vector<ArcT> arcs;
424 typedef SmartGraphBase Digraph;
431 friend class SmartGraphBase;
435 explicit Node(int id) { _id = id;}
439 Node (Invalid) { _id = -1; }
440 bool operator==(const Node& node) const {return _id == node._id;}
441 bool operator!=(const Node& node) const {return _id != node._id;}
442 bool operator<(const Node& node) const {return _id < node._id;}
446 friend class SmartGraphBase;
450 explicit Edge(int id) { _id = id;}
454 Edge (Invalid) { _id = -1; }
455 bool operator==(const Edge& arc) const {return _id == arc._id;}
456 bool operator!=(const Edge& arc) const {return _id != arc._id;}
457 bool operator<(const Edge& arc) const {return _id < arc._id;}
461 friend class SmartGraphBase;
465 explicit Arc(int id) { _id = id;}
468 operator Edge() const {
469 return _id != -1 ? edgeFromId(_id / 2) : INVALID;
473 Arc (Invalid) { _id = -1; }
474 bool operator==(const Arc& arc) const {return _id == arc._id;}
475 bool operator!=(const Arc& arc) const {return _id != arc._id;}
476 bool operator<(const Arc& arc) const {return _id < arc._id;}
485 int maxNodeId() const { return nodes.size()-1; }
486 int maxEdgeId() const { return arcs.size() / 2 - 1; }
487 int maxArcId() const { return arcs.size()-1; }
489 Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
490 Node target(Arc e) const { return Node(arcs[e._id].target); }
492 Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
493 Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
495 static bool direction(Arc e) {
496 return (e._id & 1) == 1;
499 static Arc direct(Edge e, bool d) {
500 return Arc(e._id * 2 + (d ? 1 : 0));
503 void first(Node& node) const {
504 node._id = nodes.size() - 1;
507 void next(Node& node) const {
511 void first(Arc& arc) const {
512 arc._id = arcs.size() - 1;
515 void next(Arc& arc) const {
519 void first(Edge& arc) const {
520 arc._id = arcs.size() / 2 - 1;
523 void next(Edge& arc) const {
527 void firstOut(Arc &arc, const Node& v) const {
528 arc._id = nodes[v._id].first_out;
530 void nextOut(Arc &arc) const {
531 arc._id = arcs[arc._id].next_out;
534 void firstIn(Arc &arc, const Node& v) const {
535 arc._id = ((nodes[v._id].first_out) ^ 1);
536 if (arc._id == -2) arc._id = -1;
538 void nextIn(Arc &arc) const {
539 arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
540 if (arc._id == -2) arc._id = -1;
543 void firstInc(Edge &arc, bool& d, const Node& v) const {
544 int de = nodes[v._id].first_out;
553 void nextInc(Edge &arc, bool& d) const {
554 int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
564 static int id(Node v) { return v._id; }
565 static int id(Arc e) { return e._id; }
566 static int id(Edge e) { return e._id; }
568 static Node nodeFromId(int id) { return Node(id);}
569 static Arc arcFromId(int id) { return Arc(id);}
570 static Edge edgeFromId(int id) { return Edge(id);}
572 bool valid(Node n) const {
573 return n._id >= 0 && n._id < static_cast<int>(nodes.size());
575 bool valid(Arc a) const {
576 return a._id >= 0 && a._id < static_cast<int>(arcs.size());
578 bool valid(Edge e) const {
579 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
583 int n = nodes.size();
584 nodes.push_back(NodeT());
585 nodes[n].first_out = -1;
590 Edge addEdge(Node u, Node v) {
592 arcs.push_back(ArcT());
593 arcs.push_back(ArcT());
595 arcs[n].target = u._id;
596 arcs[n | 1].target = v._id;
598 arcs[n].next_out = nodes[v._id].first_out;
599 nodes[v._id].first_out = n;
601 arcs[n | 1].next_out = nodes[u._id].first_out;
602 nodes[u._id].first_out = (n | 1);
614 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
618 /// \brief A smart undirected graph class.
620 /// This is a simple and fast graph implementation.
621 /// It is also quite memory efficient, but at the price
622 /// that <b> it does support only limited (only stack-like)
623 /// node and arc deletions</b>.
624 /// Except from this it conforms to
625 /// the \ref concepts::Graph "Graph concept".
628 /// important extra feature that
629 /// its maps are real \ref concepts::ReferenceMap "reference map"s.
631 /// \sa concepts::Graph.
633 class SmartGraph : public ExtendedSmartGraphBase {
636 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
638 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
640 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
642 ///\brief Assignment of SmartGraph to another one is \e not allowed.
643 ///Use GraphCopy() instead.
645 ///Assignment of SmartGraph to another one is \e not allowed.
646 ///Use GraphCopy() instead.
647 void operator=(const SmartGraph &) {}
651 typedef ExtendedSmartGraphBase Parent;
659 ///Add a new node to the graph.
661 /// \return the new node.
663 Node addNode() { return Parent::addNode(); }
665 ///Add a new edge to the graph.
667 ///Add a new edge to the graph with node \c s
669 ///\return the new edge.
670 Edge addEdge(const Node& s, const Node& t) {
671 return Parent::addEdge(s, t);
674 /// \brief Node validity check
676 /// This function gives back true if the given node is valid,
677 /// ie. it is a real node of the graph.
679 /// \warning A removed node (using Snapshot) could become valid again
680 /// when new nodes are added to the graph.
681 bool valid(Node n) const { return Parent::valid(n); }
683 /// \brief Arc validity check
685 /// This function gives back true if the given arc is valid,
686 /// ie. it is a real arc of the graph.
688 /// \warning A removed arc (using Snapshot) could become valid again
689 /// when new edges are added to the graph.
690 bool valid(Arc a) const { return Parent::valid(a); }
692 /// \brief Edge validity check
694 /// This function gives back true if the given edge is valid,
695 /// ie. it is a real edge of the graph.
697 /// \warning A removed edge (using Snapshot) could become valid again
698 /// when new edges are added to the graph.
699 bool valid(Edge e) const { return Parent::valid(e); }
703 ///Erase all the nodes and edges from the graph.
715 void saveSnapshot(Snapshot &s)
718 s.node_num = nodes.size();
719 s.arc_num = arcs.size();
722 void restoreSnapshot(const Snapshot &s)
724 while(s.arc_num<arcs.size()) {
726 Edge arc=edgeFromId(n/2);
727 Parent::notifier(Edge()).erase(arc);
728 std::vector<Arc> dir;
729 dir.push_back(arcFromId(n));
730 dir.push_back(arcFromId(n-1));
731 Parent::notifier(Arc()).erase(dir);
732 nodes[arcs[n].target].first_out=arcs[n].next_out;
733 nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
737 while(s.node_num<nodes.size()) {
738 int n=nodes.size()-1;
739 Node node = nodeFromId(n);
740 Parent::notifier(Node()).erase(node);
747 ///Class to make a snapshot of the digraph and to restrore to it later.
749 ///Class to make a snapshot of the digraph and to restrore to it later.
751 ///The newly added nodes and arcs can be removed using the
752 ///restore() function.
754 ///\note After you restore a state, you cannot restore
755 ///a later state, in other word you cannot add again the arcs deleted
756 ///by restore() using another one Snapshot instance.
758 ///\warning If you do not use correctly the snapshot that can cause
759 ///either broken program, invalid state of the digraph, valid but
760 ///not the restored digraph or no change. Because the runtime performance
761 ///the validity of the snapshot is not stored.
766 friend class SmartGraph;
767 unsigned int node_num;
768 unsigned int arc_num;
770 ///Default constructor.
772 ///Default constructor.
773 ///To actually make a snapshot you must call save().
775 Snapshot() : _graph(0) {}
776 ///Constructor that immediately makes a snapshot
778 ///This constructor immediately makes a snapshot of the digraph.
779 ///\param g The digraph we make a snapshot of.
780 Snapshot(SmartGraph &graph) {
781 graph.saveSnapshot(*this);
786 ///Make a snapshot of the graph.
788 ///This function can be called more than once. In case of a repeated
789 ///call, the previous snapshot gets lost.
790 ///\param g The digraph we make the snapshot of.
791 void save(SmartGraph &graph)
793 graph.saveSnapshot(*this);
796 ///Undo the changes until a snapshot.
798 ///Undo the changes until a snapshot created by save().
800 ///\note After you restored a state, you cannot restore
801 ///a later state, in other word you cannot add again the arcs deleted
805 _graph->restoreSnapshot(*this);
813 #endif //LEMON_SMART_GRAPH_H