lemon/smart_graph.h
changeset 735 853fcddcf282
parent 617 4137ef9aacc6
child 736 2e20aad15754
equal deleted inserted replaced
21:2f6ac1f7bb87 22:d03e112b375a
    30 #include <lemon/bits/graph_extender.h>
    30 #include <lemon/bits/graph_extender.h>
    31 
    31 
    32 namespace lemon {
    32 namespace lemon {
    33 
    33 
    34   class SmartDigraph;
    34   class SmartDigraph;
    35   ///Base of SmartDigraph
    35 
    36 
       
    37   ///Base of SmartDigraph
       
    38   ///
       
    39   class SmartDigraphBase {
    36   class SmartDigraphBase {
    40   protected:
    37   protected:
    41 
    38 
    42     struct NodeT
    39     struct NodeT
    43     {
    40     {
   185 
   182 
   186   ///\ingroup graphs
   183   ///\ingroup graphs
   187   ///
   184   ///
   188   ///\brief A smart directed graph class.
   185   ///\brief A smart directed graph class.
   189   ///
   186   ///
   190   ///This is a simple and fast digraph implementation.
   187   ///\ref SmartDigraph is a simple and fast digraph implementation.
   191   ///It is also quite memory efficient, but at the price
   188   ///It is also quite memory efficient but at the price
   192   ///that <b> it does support only limited (only stack-like)
   189   ///that it does not support node and arc deletion 
   193   ///node and arc deletions</b>.
   190   ///(except for the Snapshot feature).
   194   ///It fully conforms to the \ref concepts::Digraph "Digraph concept".
       
   195   ///
   191   ///
   196   ///\sa concepts::Digraph.
   192   ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
       
   193   ///and it also provides some additional functionalities.
       
   194   ///Most of its member functions and nested classes are documented
       
   195   ///only in the concept class.
       
   196   ///
       
   197   ///\sa concepts::Digraph
       
   198   ///\sa SmartGraph
   197   class SmartDigraph : public ExtendedSmartDigraphBase {
   199   class SmartDigraph : public ExtendedSmartDigraphBase {
   198     typedef ExtendedSmartDigraphBase Parent;
   200     typedef ExtendedSmartDigraphBase Parent;
   199 
   201 
   200   private:
   202   private:
   201 
   203     /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
   202     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
       
   203 
       
   204     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
       
   205     ///
       
   206     SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
   204     SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
   207     ///\brief Assignment of SmartDigraph to another one is \e not allowed.
   205     /// \brief Assignment of a digraph to another one is \e not allowed.
   208     ///Use DigraphCopy() instead.
   206     /// Use DigraphCopy instead.
   209 
       
   210     ///Assignment of SmartDigraph to another one is \e not allowed.
       
   211     ///Use DigraphCopy() instead.
       
   212     void operator=(const SmartDigraph &) {}
   207     void operator=(const SmartDigraph &) {}
   213 
   208 
   214   public:
   209   public:
   215 
   210 
   216     /// Constructor
   211     /// Constructor
   219     ///
   214     ///
   220     SmartDigraph() {};
   215     SmartDigraph() {};
   221 
   216 
   222     ///Add a new node to the digraph.
   217     ///Add a new node to the digraph.
   223 
   218 
   224     /// Add a new node to the digraph.
   219     ///This function adds a new node to the digraph.
   225     /// \return The new node.
   220     ///\return The new node.
   226     Node addNode() { return Parent::addNode(); }
   221     Node addNode() { return Parent::addNode(); }
   227 
   222 
   228     ///Add a new arc to the digraph.
   223     ///Add a new arc to the digraph.
   229 
   224 
   230     ///Add a new arc to the digraph with source node \c s
   225     ///This function adds a new arc to the digraph with source node \c s
   231     ///and target node \c t.
   226     ///and target node \c t.
   232     ///\return The new arc.
   227     ///\return The new arc.
   233     Arc addArc(const Node& s, const Node& t) {
   228     Arc addArc(Node s, Node t) {
   234       return Parent::addArc(s, t);
   229       return Parent::addArc(s, t);
   235     }
   230     }
   236 
   231 
   237     /// \brief Using this it is possible to avoid the superfluous memory
       
   238     /// allocation.
       
   239 
       
   240     /// Using this it is possible to avoid the superfluous memory
       
   241     /// allocation: if you know that the digraph you want to build will
       
   242     /// be very large (e.g. it will contain millions of nodes and/or arcs)
       
   243     /// then it is worth reserving space for this amount before starting
       
   244     /// to build the digraph.
       
   245     /// \sa reserveArc
       
   246     void reserveNode(int n) { nodes.reserve(n); };
       
   247 
       
   248     /// \brief Using this it is possible to avoid the superfluous memory
       
   249     /// allocation.
       
   250 
       
   251     /// Using this it is possible to avoid the superfluous memory
       
   252     /// allocation: if you know that the digraph you want to build will
       
   253     /// be very large (e.g. it will contain millions of nodes and/or arcs)
       
   254     /// then it is worth reserving space for this amount before starting
       
   255     /// to build the digraph.
       
   256     /// \sa reserveNode
       
   257     void reserveArc(int m) { arcs.reserve(m); };
       
   258 
       
   259     /// \brief Node validity check
   232     /// \brief Node validity check
   260     ///
   233     ///
   261     /// This function gives back true if the given node is valid,
   234     /// This function gives back \c true if the given node is valid,
   262     /// ie. it is a real node of the graph.
   235     /// i.e. it is a real node of the digraph.
   263     ///
   236     ///
   264     /// \warning A removed node (using Snapshot) could become valid again
   237     /// \warning A removed node (using Snapshot) could become valid again
   265     /// when new nodes are added to the graph.
   238     /// if new nodes are added to the digraph.
   266     bool valid(Node n) const { return Parent::valid(n); }
   239     bool valid(Node n) const { return Parent::valid(n); }
   267 
   240 
   268     /// \brief Arc validity check
   241     /// \brief Arc validity check
   269     ///
   242     ///
   270     /// This function gives back true if the given arc is valid,
   243     /// This function gives back \c true if the given arc is valid,
   271     /// ie. it is a real arc of the graph.
   244     /// i.e. it is a real arc of the digraph.
   272     ///
   245     ///
   273     /// \warning A removed arc (using Snapshot) could become valid again
   246     /// \warning A removed arc (using Snapshot) could become valid again
   274     /// when new arcs are added to the graph.
   247     /// if new arcs are added to the graph.
   275     bool valid(Arc a) const { return Parent::valid(a); }
   248     bool valid(Arc a) const { return Parent::valid(a); }
   276 
   249 
   277     ///Clear the digraph.
       
   278 
       
   279     ///Erase all the nodes and arcs from the digraph.
       
   280     ///
       
   281     void clear() {
       
   282       Parent::clear();
       
   283     }
       
   284 
       
   285     ///Split a node.
   250     ///Split a node.
   286 
   251 
   287     ///This function splits a node. First a new node is added to the digraph,
   252     ///This function splits the given node. First, a new node is added
   288     ///then the source of each outgoing arc of \c n is moved to this new node.
   253     ///to the digraph, then the source of each outgoing arc of node \c n
   289     ///If \c connect is \c true (this is the default value), then a new arc
   254     ///is moved to this new node.
   290     ///from \c n to the newly created node is also added.
   255     ///If the second parameter \c connect is \c true (this is the default
       
   256     ///value), then a new arc from node \c n to the newly created node
       
   257     ///is also added.
   291     ///\return The newly created node.
   258     ///\return The newly created node.
   292     ///
   259     ///
   293     ///\note The <tt>Arc</tt>s
   260     ///\note All iterators remain valid.
   294     ///referencing a moved arc remain
   261     ///
   295     ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
       
   296     ///may be invalidated.
       
   297     ///\warning This functionality cannot be used together with the Snapshot
   262     ///\warning This functionality cannot be used together with the Snapshot
   298     ///feature.
   263     ///feature.
   299     Node split(Node n, bool connect = true)
   264     Node split(Node n, bool connect = true)
   300     {
   265     {
   301       Node b = addNode();
   266       Node b = addNode();
   306       }
   271       }
   307       if(connect) addArc(n,b);
   272       if(connect) addArc(n,b);
   308       return b;
   273       return b;
   309     }
   274     }
   310 
   275 
       
   276     ///Clear the digraph.
       
   277 
       
   278     ///This function erases all nodes and arcs from the digraph.
       
   279     ///
       
   280     void clear() {
       
   281       Parent::clear();
       
   282     }
       
   283 
       
   284     /// Reserve memory for nodes.
       
   285 
       
   286     /// Using this function, it is possible to avoid superfluous memory
       
   287     /// allocation: if you know that the digraph you want to build will
       
   288     /// be large (e.g. it will contain millions of nodes and/or arcs),
       
   289     /// then it is worth reserving space for this amount before starting
       
   290     /// to build the digraph.
       
   291     /// \sa reserveArc()
       
   292     void reserveNode(int n) { nodes.reserve(n); };
       
   293 
       
   294     /// Reserve memory for arcs.
       
   295 
       
   296     /// Using this function, it is possible to avoid superfluous memory
       
   297     /// allocation: if you know that the digraph you want to build will
       
   298     /// be large (e.g. it will contain millions of nodes and/or arcs),
       
   299     /// then it is worth reserving space for this amount before starting
       
   300     /// to build the digraph.
       
   301     /// \sa reserveNode()
       
   302     void reserveArc(int m) { arcs.reserve(m); };
       
   303 
   311   public:
   304   public:
   312 
   305 
   313     class Snapshot;
   306     class Snapshot;
   314 
   307 
   315   protected:
   308   protected:
   330       }
   323       }
   331     }
   324     }
   332 
   325 
   333   public:
   326   public:
   334 
   327 
   335     ///Class to make a snapshot of the digraph and to restrore to it later.
   328     ///Class to make a snapshot of the digraph and to restore it later.
   336 
   329 
   337     ///Class to make a snapshot of the digraph and to restrore to it later.
   330     ///Class to make a snapshot of the digraph and to restore it later.
   338     ///
   331     ///
   339     ///The newly added nodes and arcs can be removed using the
   332     ///The newly added nodes and arcs can be removed using the
   340     ///restore() function.
   333     ///restore() function. This is the only way for deleting nodes and/or
   341     ///\note After you restore a state, you cannot restore
   334     ///arcs from a SmartDigraph structure.
   342     ///a later state, in other word you cannot add again the arcs deleted
   335     ///
   343     ///by restore() using another one Snapshot instance.
   336     ///\note After a state is restored, you cannot restore a later state, 
   344     ///
   337     ///i.e. you cannot add the removed nodes and arcs again using
   345     ///\warning If you do not use correctly the snapshot that can cause
   338     ///another Snapshot instance.
   346     ///either broken program, invalid state of the digraph, valid but
   339     ///
   347     ///not the restored digraph or no change. Because the runtime performance
   340     ///\warning Node splitting cannot be restored.
   348     ///the validity of the snapshot is not stored.
   341     ///\warning The validity of the snapshot is not stored due to
       
   342     ///performance reasons. If you do not use the snapshot correctly,
       
   343     ///it can cause broken program, invalid or not restored state of
       
   344     ///the digraph or no change.
   349     class Snapshot
   345     class Snapshot
   350     {
   346     {
   351       SmartDigraph *_graph;
   347       SmartDigraph *_graph;
   352     protected:
   348     protected:
   353       friend class SmartDigraph;
   349       friend class SmartDigraph;
   355       unsigned int arc_num;
   351       unsigned int arc_num;
   356     public:
   352     public:
   357       ///Default constructor.
   353       ///Default constructor.
   358 
   354 
   359       ///Default constructor.
   355       ///Default constructor.
   360       ///To actually make a snapshot you must call save().
   356       ///You have to call save() to actually make a snapshot.
   361       ///
       
   362       Snapshot() : _graph(0) {}
   357       Snapshot() : _graph(0) {}
   363       ///Constructor that immediately makes a snapshot
   358       ///Constructor that immediately makes a snapshot
   364 
   359 
   365       ///This constructor immediately makes a snapshot of the digraph.
   360       ///This constructor immediately makes a snapshot of the given digraph.
   366       ///\param graph The digraph we make a snapshot of.
   361       ///
   367       Snapshot(SmartDigraph &graph) : _graph(&graph) {
   362       Snapshot(SmartDigraph &gr) : _graph(&gr) {
   368         node_num=_graph->nodes.size();
   363         node_num=_graph->nodes.size();
   369         arc_num=_graph->arcs.size();
   364         arc_num=_graph->arcs.size();
   370       }
   365       }
   371 
   366 
   372       ///Make a snapshot.
   367       ///Make a snapshot.
   373 
   368 
   374       ///Make a snapshot of the digraph.
   369       ///This function makes a snapshot of the given digraph.
   375       ///
   370       ///It can be called more than once. In case of a repeated
   376       ///This function can be called more than once. In case of a repeated
       
   377       ///call, the previous snapshot gets lost.
   371       ///call, the previous snapshot gets lost.
   378       ///\param graph The digraph we make the snapshot of.
   372       void save(SmartDigraph &gr) {
   379       void save(SmartDigraph &graph)
   373         _graph=&gr;
   380       {
       
   381         _graph=&graph;
       
   382         node_num=_graph->nodes.size();
   374         node_num=_graph->nodes.size();
   383         arc_num=_graph->arcs.size();
   375         arc_num=_graph->arcs.size();
   384       }
   376       }
   385 
   377 
   386       ///Undo the changes until a snapshot.
   378       ///Undo the changes until a snapshot.
   387 
   379 
   388       ///Undo the changes until a snapshot created by save().
   380       ///This function undos the changes until the last snapshot
   389       ///
   381       ///created by save() or Snapshot(SmartDigraph&).
   390       ///\note After you restored a state, you cannot restore
       
   391       ///a later state, in other word you cannot add again the arcs deleted
       
   392       ///by restore().
       
   393       void restore()
   382       void restore()
   394       {
   383       {
   395         _graph->restoreSnapshot(*this);
   384         _graph->restoreSnapshot(*this);
   396       }
   385       }
   397     };
   386     };
   619 
   608 
   620   /// \ingroup graphs
   609   /// \ingroup graphs
   621   ///
   610   ///
   622   /// \brief A smart undirected graph class.
   611   /// \brief A smart undirected graph class.
   623   ///
   612   ///
   624   /// This is a simple and fast graph implementation.
   613   /// \ref SmartGraph is a simple and fast graph implementation.
   625   /// It is also quite memory efficient, but at the price
   614   /// It is also quite memory efficient but at the price
   626   /// that <b> it does support only limited (only stack-like)
   615   /// that it does not support node and edge deletion 
   627   /// node and arc deletions</b>.
   616   /// (except for the Snapshot feature).
   628   /// It fully conforms to the \ref concepts::Graph "Graph concept".
       
   629   ///
   617   ///
   630   /// \sa concepts::Graph.
   618   /// This type fully conforms to the \ref concepts::Graph "Graph concept"
       
   619   /// and it also provides some additional functionalities.
       
   620   /// Most of its member functions and nested classes are documented
       
   621   /// only in the concept class.
       
   622   ///
       
   623   /// \sa concepts::Graph
       
   624   /// \sa SmartDigraph
   631   class SmartGraph : public ExtendedSmartGraphBase {
   625   class SmartGraph : public ExtendedSmartGraphBase {
   632     typedef ExtendedSmartGraphBase Parent;
   626     typedef ExtendedSmartGraphBase Parent;
   633 
   627 
   634   private:
   628   private:
   635 
   629     /// Graphs are \e not copy constructible. Use GraphCopy instead.
   636     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
       
   637 
       
   638     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
       
   639     ///
       
   640     SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
   630     SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
   641 
   631     /// \brief Assignment of a graph to another one is \e not allowed.
   642     ///\brief Assignment of SmartGraph to another one is \e not allowed.
   632     /// Use GraphCopy instead.
   643     ///Use GraphCopy() instead.
       
   644 
       
   645     ///Assignment of SmartGraph to another one is \e not allowed.
       
   646     ///Use GraphCopy() instead.
       
   647     void operator=(const SmartGraph &) {}
   633     void operator=(const SmartGraph &) {}
   648 
   634 
   649   public:
   635   public:
   650 
   636 
   651     /// Constructor
   637     /// Constructor
   652 
   638 
   653     /// Constructor.
   639     /// Constructor.
   654     ///
   640     ///
   655     SmartGraph() {}
   641     SmartGraph() {}
   656 
   642 
   657     ///Add a new node to the graph.
   643     /// \brief Add a new node to the graph.
   658 
   644     ///
   659     /// Add a new node to the graph.
   645     /// This function adds a new node to the graph.
   660     /// \return The new node.
   646     /// \return The new node.
   661     Node addNode() { return Parent::addNode(); }
   647     Node addNode() { return Parent::addNode(); }
   662 
   648 
   663     ///Add a new edge to the graph.
   649     /// \brief Add a new edge to the graph.
   664 
   650     ///
   665     ///Add a new edge to the graph with node \c s
   651     /// This function adds a new edge to the graph between nodes
   666     ///and \c t.
   652     /// \c u and \c v with inherent orientation from node \c u to
   667     ///\return The new edge.
   653     /// node \c v.
   668     Edge addEdge(const Node& s, const Node& t) {
   654     /// \return The new edge.
   669       return Parent::addEdge(s, t);
   655     Edge addEdge(Node u, Node v) {
       
   656       return Parent::addEdge(u, v);
   670     }
   657     }
   671 
   658 
   672     /// \brief Node validity check
   659     /// \brief Node validity check
   673     ///
   660     ///
   674     /// This function gives back true if the given node is valid,
   661     /// This function gives back \c true if the given node is valid,
   675     /// ie. it is a real node of the graph.
   662     /// i.e. it is a real node of the graph.
   676     ///
   663     ///
   677     /// \warning A removed node (using Snapshot) could become valid again
   664     /// \warning A removed node (using Snapshot) could become valid again
   678     /// when new nodes are added to the graph.
   665     /// if new nodes are added to the graph.
   679     bool valid(Node n) const { return Parent::valid(n); }
   666     bool valid(Node n) const { return Parent::valid(n); }
   680 
   667 
       
   668     /// \brief Edge validity check
       
   669     ///
       
   670     /// This function gives back \c true if the given edge is valid,
       
   671     /// i.e. it is a real edge of the graph.
       
   672     ///
       
   673     /// \warning A removed edge (using Snapshot) could become valid again
       
   674     /// if new edges are added to the graph.
       
   675     bool valid(Edge e) const { return Parent::valid(e); }
       
   676 
   681     /// \brief Arc validity check
   677     /// \brief Arc validity check
   682     ///
   678     ///
   683     /// This function gives back true if the given arc is valid,
   679     /// This function gives back \c true if the given arc is valid,
   684     /// ie. it is a real arc of the graph.
   680     /// i.e. it is a real arc of the graph.
   685     ///
   681     ///
   686     /// \warning A removed arc (using Snapshot) could become valid again
   682     /// \warning A removed arc (using Snapshot) could become valid again
   687     /// when new edges are added to the graph.
   683     /// if new edges are added to the graph.
   688     bool valid(Arc a) const { return Parent::valid(a); }
   684     bool valid(Arc a) const { return Parent::valid(a); }
   689 
   685 
   690     /// \brief Edge validity check
       
   691     ///
       
   692     /// This function gives back true if the given edge is valid,
       
   693     /// ie. it is a real edge of the graph.
       
   694     ///
       
   695     /// \warning A removed edge (using Snapshot) could become valid again
       
   696     /// when new edges are added to the graph.
       
   697     bool valid(Edge e) const { return Parent::valid(e); }
       
   698 
       
   699     ///Clear the graph.
   686     ///Clear the graph.
   700 
   687 
   701     ///Erase all the nodes and edges from the graph.
   688     ///This function erases all nodes and arcs from the graph.
   702     ///
   689     ///
   703     void clear() {
   690     void clear() {
   704       Parent::clear();
   691       Parent::clear();
   705     }
   692     }
   706 
   693 
   740       }
   727       }
   741     }
   728     }
   742 
   729 
   743   public:
   730   public:
   744 
   731 
   745     ///Class to make a snapshot of the digraph and to restrore to it later.
   732     ///Class to make a snapshot of the graph and to restore it later.
   746 
   733 
   747     ///Class to make a snapshot of the digraph and to restrore to it later.
   734     ///Class to make a snapshot of the graph and to restore it later.
   748     ///
   735     ///
   749     ///The newly added nodes and arcs can be removed using the
   736     ///The newly added nodes and edges can be removed using the
   750     ///restore() function.
   737     ///restore() function. This is the only way for deleting nodes and/or
   751     ///
   738     ///edges from a SmartGraph structure.
   752     ///\note After you restore a state, you cannot restore
   739     ///
   753     ///a later state, in other word you cannot add again the arcs deleted
   740     ///\note After a state is restored, you cannot restore a later state, 
   754     ///by restore() using another one Snapshot instance.
   741     ///i.e. you cannot add the removed nodes and edges again using
   755     ///
   742     ///another Snapshot instance.
   756     ///\warning If you do not use correctly the snapshot that can cause
   743     ///
   757     ///either broken program, invalid state of the digraph, valid but
   744     ///\warning The validity of the snapshot is not stored due to
   758     ///not the restored digraph or no change. Because the runtime performance
   745     ///performance reasons. If you do not use the snapshot correctly,
   759     ///the validity of the snapshot is not stored.
   746     ///it can cause broken program, invalid or not restored state of
       
   747     ///the graph or no change.
   760     class Snapshot
   748     class Snapshot
   761     {
   749     {
   762       SmartGraph *_graph;
   750       SmartGraph *_graph;
   763     protected:
   751     protected:
   764       friend class SmartGraph;
   752       friend class SmartGraph;
   766       unsigned int arc_num;
   754       unsigned int arc_num;
   767     public:
   755     public:
   768       ///Default constructor.
   756       ///Default constructor.
   769 
   757 
   770       ///Default constructor.
   758       ///Default constructor.
   771       ///To actually make a snapshot you must call save().
   759       ///You have to call save() to actually make a snapshot.
   772       ///
       
   773       Snapshot() : _graph(0) {}
   760       Snapshot() : _graph(0) {}
   774       ///Constructor that immediately makes a snapshot
   761       ///Constructor that immediately makes a snapshot
   775 
   762 
   776       ///This constructor immediately makes a snapshot of the digraph.
   763       /// This constructor immediately makes a snapshot of the given graph.
   777       ///\param graph The digraph we make a snapshot of.
   764       ///
   778       Snapshot(SmartGraph &graph) {
   765       Snapshot(SmartGraph &gr) {
   779         graph.saveSnapshot(*this);
   766         gr.saveSnapshot(*this);
   780       }
   767       }
   781 
   768 
   782       ///Make a snapshot.
   769       ///Make a snapshot.
   783 
   770 
   784       ///Make a snapshot of the graph.
   771       ///This function makes a snapshot of the given graph.
   785       ///
   772       ///It can be called more than once. In case of a repeated
   786       ///This function can be called more than once. In case of a repeated
       
   787       ///call, the previous snapshot gets lost.
   773       ///call, the previous snapshot gets lost.
   788       ///\param graph The digraph we make the snapshot of.
   774       void save(SmartGraph &gr)
   789       void save(SmartGraph &graph)
       
   790       {
   775       {
   791         graph.saveSnapshot(*this);
   776         gr.saveSnapshot(*this);
   792       }
   777       }
   793 
   778 
   794       ///Undo the changes until a snapshot.
   779       ///Undo the changes until the last snapshot.
   795 
   780 
   796       ///Undo the changes until a snapshot created by save().
   781       ///This function undos the changes until the last snapshot
   797       ///
   782       ///created by save() or Snapshot(SmartGraph&).
   798       ///\note After you restored a state, you cannot restore
       
   799       ///a later state, in other word you cannot add again the arcs deleted
       
   800       ///by restore().
       
   801       void restore()
   783       void restore()
   802       {
   784       {
   803         _graph->restoreSnapshot(*this);
   785         _graph->restoreSnapshot(*this);
   804       }
   786       }
   805     };
   787     };