lemon/list_graph.h
changeset 74 9394072da54f
parent 57 c1acf0018c0a
child 149 2f7ae34e1333
equal deleted inserted replaced
2:c534af49375c 3:e51dfcdb46b1
   109     void next(Node& node) const {
   109     void next(Node& node) const {
   110       node.id = nodes[node.id].next;
   110       node.id = nodes[node.id].next;
   111     }
   111     }
   112 
   112 
   113 
   113 
   114     void first(Arc& e) const { 
   114     void first(Arc& arc) const { 
   115       int n;
   115       int n;
   116       for(n = first_node; 
   116       for(n = first_node; 
   117 	  n!=-1 && nodes[n].first_in == -1; 
   117 	  n!=-1 && nodes[n].first_in == -1; 
   118 	  n = nodes[n].next);
   118 	  n = nodes[n].next);
   119       e.id = (n == -1) ? -1 : nodes[n].first_in;
   119       arc.id = (n == -1) ? -1 : nodes[n].first_in;
   120     }
   120     }
   121 
   121 
   122     void next(Arc& arc) const {
   122     void next(Arc& arc) const {
   123       if (arcs[arc.id].next_in != -1) {
   123       if (arcs[arc.id].next_in != -1) {
   124 	arc.id = arcs[arc.id].next_in;
   124 	arc.id = arcs[arc.id].next_in;
   291 
   291 
   292   };
   292   };
   293 
   293 
   294   typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
   294   typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
   295 
   295 
   296   /// \addtogroup digraphs
   296   /// \addtogroup graphs
   297   /// @{
   297   /// @{
   298 
   298 
   299   ///A list digraph class.
   299   ///A general directed graph structure. 
   300 
   300 
   301   ///This is a simple and fast digraph implementation.
   301   ///\ref ListDigraph is a simple and fast <em>directed graph</em> 
       
   302   ///implementation based on static linked lists that are stored in 
       
   303   ///\c std::vector structures.   
   302   ///
   304   ///
   303   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
   305   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
   304   ///also provides several additional useful extra functionalities.
   306   ///also provides several useful additional functionalities.
   305   ///The most of the member functions and nested classes are
   307   ///Most of the member functions and nested classes are documented
   306   ///documented only in the concept class.
   308   ///only in the concept class.
   307   ///
   309   ///
   308   ///An important extra feature of this digraph implementation is that
   310   ///An important extra feature of this digraph implementation is that
   309   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   311   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   310   ///
   312   ///
   311   ///\sa concepts::Digraph.
   313   ///\sa concepts::Digraph
   312 
   314 
   313   class ListDigraph : public ExtendedListDigraphBase {
   315   class ListDigraph : public ExtendedListDigraphBase {
   314   private:
   316   private:
   315     ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
   317     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
   316     
   318     
   317     ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
   319     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
   318     ///
   320     ///
   319     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
   321     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
   320     ///\brief Assignment of ListDigraph to another one is \e not allowed.
   322     ///\brief Assignment of ListDigraph to another one is \e not allowed.
   321     ///Use DigraphCopy() instead.
   323     ///Use copyDigraph() instead.
   322 
   324 
   323     ///Assignment of ListDigraph to another one is \e not allowed.
   325     ///Assignment of ListDigraph to another one is \e not allowed.
   324     ///Use DigraphCopy() instead.
   326     ///Use copyDigraph() instead.
   325     void operator=(const ListDigraph &) {}
   327     void operator=(const ListDigraph &) {}
   326   public:
   328   public:
   327 
   329 
   328     typedef ExtendedListDigraphBase Parent;
   330     typedef ExtendedListDigraphBase Parent;
   329 
   331 
   333     ///
   335     ///
   334     ListDigraph() {}
   336     ListDigraph() {}
   335 
   337 
   336     ///Add a new node to the digraph.
   338     ///Add a new node to the digraph.
   337     
   339     
   338     /// \return the new node.
   340     ///Add a new node to the digraph.
   339     ///
   341     ///\return the new node.
   340     Node addNode() { return Parent::addNode(); }
   342     Node addNode() { return Parent::addNode(); }
   341 
   343 
   342     ///Add a new arc to the digraph.
   344     ///Add a new arc to the digraph.
   343     
   345     
   344     ///Add a new arc to the digraph with source node \c s
   346     ///Add a new arc to the digraph with source node \c s
   346     ///\return the new arc.
   348     ///\return the new arc.
   347     Arc addArc(const Node& s, const Node& t) { 
   349     Arc addArc(const Node& s, const Node& t) { 
   348       return Parent::addArc(s, t); 
   350       return Parent::addArc(s, t); 
   349     }
   351     }
   350 
   352 
   351     /// Changes the target of \c e to \c n
   353     /// Change the target of \c e to \c n
   352 
   354 
   353     /// Changes the target of \c e to \c n
   355     /// Change the target of \c e to \c n
   354     ///
   356     ///
   355     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
   357     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
   356     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
   358     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
   357     ///invalidated.
   359     ///invalidated.
       
   360     ///
   358     ///\warning This functionality cannot be used together with the Snapshot
   361     ///\warning This functionality cannot be used together with the Snapshot
   359     ///feature.
   362     ///feature.
   360     void changeTarget(Arc e, Node n) { 
   363     void changeTarget(Arc e, Node n) { 
   361       Parent::changeTarget(e,n); 
   364       Parent::changeTarget(e,n); 
   362     }
   365     }
   363     /// Changes the source of \c e to \c n
   366     /// Change the source of \c e to \c n
   364 
   367 
   365     /// Changes the source of \c e to \c n
   368     /// Change the source of \c e to \c n
   366     ///
   369     ///
   367     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
   370     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
   368     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
   371     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
   369     ///invalidated.
   372     ///invalidated.
       
   373     ///
   370     ///\warning This functionality cannot be used together with the Snapshot
   374     ///\warning This functionality cannot be used together with the Snapshot
   371     ///feature.
   375     ///feature.
   372     void changeSource(Arc e, Node n) { 
   376     void changeSource(Arc e, Node n) { 
   373       Parent::changeSource(e,n);
   377       Parent::changeSource(e,n);
   374     }
   378     }
   376     /// Invert the direction of an arc.
   380     /// Invert the direction of an arc.
   377 
   381 
   378     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
   382     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
   379     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
   383     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
   380     ///invalidated.
   384     ///invalidated.
       
   385     ///
   381     ///\warning This functionality cannot be used together with the Snapshot
   386     ///\warning This functionality cannot be used together with the Snapshot
   382     ///feature.
   387     ///feature.
   383     void reverseArc(Arc e) {
   388     void reverseArc(Arc e) {
   384       Node t=target(e);
   389       Node t=target(e);
   385       changeTarget(e,source(e));
   390       changeTarget(e,source(e));
   386       changeSource(e,t);
   391       changeSource(e,t);
   387     }
   392     }
   388 
   393 
   389     /// Using this it is possible to avoid the superfluous memory
   394     /// Reserve memory for nodes.
       
   395 
       
   396     /// Using this function it is possible to avoid the superfluous memory
   390     /// allocation: if you know that the digraph you want to build will
   397     /// allocation: if you know that the digraph you want to build will
   391     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   398     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   392     /// then it is worth reserving space for this amount before starting
   399     /// then it is worth reserving space for this amount before starting
   393     /// to build the digraph.
   400     /// to build the digraph.
   394     /// \sa reserveArc
   401     /// \sa reserveArc
   395     void reserveNode(int n) { nodes.reserve(n); };
   402     void reserveNode(int n) { nodes.reserve(n); };
   396 
   403 
   397     /// \brief Using this it is possible to avoid the superfluous memory
   404     /// Reserve memory for arcs.
   398     /// allocation.
   405 
   399 
   406     /// Using this function it is possible to avoid the superfluous memory
   400     /// Using this it is possible to avoid the superfluous memory
       
   401     /// allocation: if you know that the digraph you want to build will
   407     /// allocation: if you know that the digraph you want to build will
   402     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   408     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   403     /// then it is worth reserving space for this amount before starting
   409     /// then it is worth reserving space for this amount before starting
   404     /// to build the digraph.
   410     /// to build the digraph.
   405     /// \sa reserveNode
   411     /// \sa reserveNode
   406     void reserveArc(int m) { arcs.reserve(m); };
   412     void reserveArc(int m) { arcs.reserve(m); };
   407 
   413 
   408     ///Contract two nodes.
   414     ///Contract two nodes.
   409 
   415 
   410     ///This function contracts two nodes.
   416     ///This function contracts two nodes.
   411     ///
       
   412     ///Node \p b will be removed but instead of deleting
   417     ///Node \p b will be removed but instead of deleting
   413     ///incident arcs, they will be joined to \p a.
   418     ///incident arcs, they will be joined to \p a.
   414     ///The last parameter \p r controls whether to remove loops. \c true
   419     ///The last parameter \p r controls whether to remove loops. \c true
   415     ///means that loops will be removed.
   420     ///means that loops will be removed.
   416     ///
   421     ///
   417     ///\note The <tt>ArcIt</tt>s
   422     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   418     ///referencing a moved arc remain
       
   419     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
   423     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
   420     ///may be invalidated.
   424     ///may be invalidated.
       
   425     ///
   421     ///\warning This functionality cannot be used together with the Snapshot
   426     ///\warning This functionality cannot be used together with the Snapshot
   422     ///feature.
   427     ///feature.
   423     void contract(Node a, Node b, bool r = true) 
   428     void contract(Node a, Node b, bool r = true) 
   424     {
   429     {
   425       for(OutArcIt e(*this,b);e!=INVALID;) {
   430       for(OutArcIt e(*this,b);e!=INVALID;) {
   450     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   455     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   451     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
   456     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
   452     ///be invalidated.  
   457     ///be invalidated.  
   453     ///
   458     ///
   454     ///\warning This functionality cannot be used together with the
   459     ///\warning This functionality cannot be used together with the
   455     ///Snapshot feature.  \todo It could be implemented in a bit
   460     ///Snapshot feature.
   456     ///faster way.
   461     ///
       
   462     ///\todo It could be implemented in a bit faster way.
   457     Node split(Node n, bool connect = true) {
   463     Node split(Node n, bool connect = true) {
   458       Node b = addNode();
   464       Node b = addNode();
   459       for(OutArcIt e(*this,n);e!=INVALID;) {
   465       for(OutArcIt e(*this,n);e!=INVALID;) {
   460  	OutArcIt f=e;
   466  	OutArcIt f=e;
   461 	++f;
   467 	++f;
   469     ///Split an arc.
   475     ///Split an arc.
   470 
   476 
   471     ///This function splits an arc. First a new node \c b is added to
   477     ///This function splits an arc. First a new node \c b is added to
   472     ///the digraph, then the original arc is re-targeted to \c
   478     ///the digraph, then the original arc is re-targeted to \c
   473     ///b. Finally an arc from \c b to the original target is added.
   479     ///b. Finally an arc from \c b to the original target is added.
   474     ///\return The newly created node.  
   480     ///
   475     ///\warning This functionality
   481     ///\return The newly created node.
   476     ///cannot be used together with the Snapshot feature.
   482     ///
       
   483     ///\warning This functionality cannot be used together with the
       
   484     ///Snapshot feature.
   477     Node split(Arc e) {
   485     Node split(Arc e) {
   478       Node b = addNode();
   486       Node b = addNode();
   479       addArc(b,target(e));
   487       addArc(b,target(e));
   480       changeTarget(e,b);
   488       changeTarget(e,b);
   481       return b;
   489       return b;
   482     }
   490     }
   483       
   491       
   484     /// \brief Class to make a snapshot of the digraph and restore
   492     /// \brief Class to make a snapshot of the digraph and restore
   485     /// to it later.
   493     /// it later.
   486     ///
   494     ///
   487     /// Class to make a snapshot of the digraph and to restore it
   495     /// Class to make a snapshot of the digraph and restore it later.
   488     /// later.
       
   489     ///
   496     ///
   490     /// The newly added nodes and arcs can be removed using the
   497     /// The newly added nodes and arcs can be removed using the
   491     /// restore() function.
   498     /// restore() function.
   492     ///
   499     ///
   493     /// \warning Arc and node deletions cannot be restored. This
   500     /// \warning Arc and node deletions and other modifications (e.g.
   494     /// events invalidate the snapshot. 
   501     /// contracting, splitting, reversing arcs or nodes) cannot be 
       
   502     /// restored. These events invalidate the snapshot. 
   495     class Snapshot {
   503     class Snapshot {
   496     protected:
   504     protected:
   497 
   505 
   498       typedef Parent::NodeNotifier NodeNotifier;
   506       typedef Parent::NodeNotifier NodeNotifier;
   499 
   507 
   774       explicit Edge(int pid) { id = pid;}
   782       explicit Edge(int pid) { id = pid;}
   775 
   783 
   776     public:
   784     public:
   777       Edge() {}
   785       Edge() {}
   778       Edge (Invalid) { id = -1; }
   786       Edge (Invalid) { id = -1; }
   779       bool operator==(const Edge& arc) const {return id == arc.id;}
   787       bool operator==(const Edge& edge) const {return id == edge.id;}
   780       bool operator!=(const Edge& arc) const {return id != arc.id;}
   788       bool operator!=(const Edge& edge) const {return id != edge.id;}
   781       bool operator<(const Edge& arc) const {return id < arc.id;}
   789       bool operator<(const Edge& edge) const {return id < edge.id;}
   782     };
   790     };
   783 
   791 
   784     class Arc {
   792     class Arc {
   785       friend class ListGraphBase;
   793       friend class ListGraphBase;
   786     protected:
   794     protected:
   907       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   915       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   908       if (e.id == -2) e.id = -1;
   916       if (e.id == -2) e.id = -1;
   909     }
   917     }
   910 
   918 
   911     void firstInc(Edge &e, bool& d, const Node& v) const {
   919     void firstInc(Edge &e, bool& d, const Node& v) const {
   912       int de = nodes[v.id].first_out;
   920       int a = nodes[v.id].first_out;
   913       if (de != -1 ) {
   921       if (a != -1 ) {
   914         e.id = de / 2;
   922         e.id = a / 2;
   915         d = ((de & 1) == 1);
   923         d = ((a & 1) == 1);
   916       } else {
   924       } else {
   917         e.id = -1;
   925         e.id = -1;
   918         d = true;
   926         d = true;
   919       }
   927       }
   920     }
   928     }
   921     void nextInc(Edge &e, bool& d) const {
   929     void nextInc(Edge &e, bool& d) const {
   922       int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   930       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   923       if (de != -1 ) {
   931       if (a != -1 ) {
   924         e.id = de / 2;
   932         e.id = a / 2;
   925         d = ((de & 1) == 1);
   933         d = ((a & 1) == 1);
   926       } else {
   934       } else {
   927         e.id = -1;
   935         e.id = -1;
   928         d = true;
   936         d = true;
   929       }
   937       }
   930     }
   938     }
  1006       nodes[n].next = first_free_node;
  1014       nodes[n].next = first_free_node;
  1007       first_free_node = n;
  1015       first_free_node = n;
  1008 
  1016 
  1009     }
  1017     }
  1010     
  1018     
  1011     void erase(const Edge& arc) {
  1019     void erase(const Edge& edge) {
  1012       int n = arc.id * 2;
  1020       int n = edge.id * 2;
  1013       
  1021       
  1014       if (arcs[n].next_out != -1) {
  1022       if (arcs[n].next_out != -1) {
  1015 	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1023 	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1016       } 
  1024       } 
  1017 
  1025 
  1087       nodes[n.id].first_out = ((2 * e.id) | 1);
  1095       nodes[n.id].first_out = ((2 * e.id) | 1);
  1088     }
  1096     }
  1089 
  1097 
  1090   };
  1098   };
  1091 
  1099 
  1092 //   typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > 
       
  1093 //   ExtendedListGraphBase;
       
  1094 
       
  1095   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
  1100   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
  1096 
  1101 
  1097 
  1102 
  1098 
  1103   /// \addtogroup graphs
  1099   /// \addtogroup digraphs
       
  1100   /// @{
  1104   /// @{
  1101 
  1105 
  1102   ///An undirected list digraph class.
  1106   ///A general undirected graph structure.
  1103 
  1107 
  1104   ///This is a simple and fast undirected digraph implementation.
  1108   ///\ref ListGraph is a simple and fast <em>undirected graph</em> 
       
  1109   ///implementation based on static linked lists that are stored in 
       
  1110   ///\c std::vector structures. 
  1105   ///
  1111   ///
  1106   ///An important extra feature of this digraph implementation is that
  1112   ///It conforms to the \ref concepts::Graph "Graph concept" and it
       
  1113   ///also provides several useful additional functionalities.
       
  1114   ///Most of the member functions and nested classes are documented
       
  1115   ///only in the concept class.
       
  1116   ///
       
  1117   ///An important extra feature of this graph implementation is that
  1107   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
  1118   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
  1108   ///
  1119   ///
  1109   ///It conforms to the
  1120   ///\sa concepts::Graph
  1110   ///\ref concepts::Graph "Graph concept".
  1121 
  1111   ///
       
  1112   ///\sa concepts::Graph.
       
  1113   ///
       
  1114   class ListGraph : public ExtendedListGraphBase {
  1122   class ListGraph : public ExtendedListGraphBase {
  1115   private:
  1123   private:
  1116     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
  1124     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
  1117 
  1125 
  1118     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
  1126     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
  1119     ///
  1127     ///
  1120     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
  1128     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
  1121     ///\brief Assignment of ListGraph to another one is \e not allowed.
  1129     ///\brief Assignment of ListGraph to another one is \e not allowed.
  1122     ///Use GraphCopy() instead.
  1130     ///Use copyGraph() instead.
  1123 
  1131 
  1124     ///Assignment of ListGraph to another one is \e not allowed.
  1132     ///Assignment of ListGraph to another one is \e not allowed.
  1125     ///Use GraphCopy() instead.
  1133     ///Use copyGraph() instead.
  1126     void operator=(const ListGraph &) {}
  1134     void operator=(const ListGraph &) {}
  1127   public:
  1135   public:
  1128     /// Constructor
  1136     /// Constructor
  1129     
  1137     
  1130     /// Constructor.
  1138     /// Constructor.
  1131     ///
  1139     ///
  1132     ListGraph() {}
  1140     ListGraph() {}
  1133 
  1141 
  1134     typedef ExtendedListGraphBase Parent;
  1142     typedef ExtendedListGraphBase Parent;
  1135 
  1143 
  1136     typedef Parent::OutArcIt IncArcIt;
  1144     typedef Parent::OutArcIt IncEdgeIt;
  1137 
  1145 
  1138     /// \brief Add a new node to the digraph.
  1146     /// \brief Add a new node to the graph.
  1139     ///
  1147     ///
       
  1148     /// Add a new node to the graph.
  1140     /// \return the new node.
  1149     /// \return the new node.
  1141     ///
       
  1142     Node addNode() { return Parent::addNode(); }
  1150     Node addNode() { return Parent::addNode(); }
  1143 
  1151 
  1144     /// \brief Add a new edge to the digraph.
  1152     /// \brief Add a new edge to the graph.
  1145     ///
  1153     ///
  1146     /// Add a new arc to the digraph with source node \c s
  1154     /// Add a new edge to the graph with source node \c s
  1147     /// and target node \c t.
  1155     /// and target node \c t.
  1148     /// \return the new edge.
  1156     /// \return the new edge.
  1149     Edge addEdge(const Node& s, const Node& t) { 
  1157     Edge addEdge(const Node& s, const Node& t) { 
  1150       return Parent::addEdge(s, t); 
  1158       return Parent::addEdge(s, t); 
  1151     }
  1159     }
  1152     /// \brief Changes the source of \c e to \c n
  1160     /// \brief Change the source of \c e to \c n
  1153     ///
  1161     ///
  1154     /// Changes the source of \c e to \c n
  1162     /// This function changes the source of \c e to \c n.
  1155     ///
  1163     ///
  1156     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1164     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1157     ///referencing the changed arc remain
  1165     ///referencing the changed arc remain
  1158     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1166     ///valid. However <tt>OutArcIt</tt>s are invalidated.
       
  1167     ///
       
  1168     ///\warning This functionality cannot be used together with the
       
  1169     ///Snapshot feature.
  1159     void changeSource(Edge e, Node n) { 
  1170     void changeSource(Edge e, Node n) { 
  1160       Parent::changeSource(e,n); 
  1171       Parent::changeSource(e,n); 
  1161     }    
  1172     }    
  1162     /// \brief Changes the target of \c e to \c n
  1173     /// \brief Change the target of \c e to \c n
  1163     ///
  1174     ///
  1164     /// Changes the target of \c e to \c n
  1175     /// This function changes the target of \c e to \c n.
  1165     ///
  1176     ///
  1166     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
  1177     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
  1167     /// valid. However the other iterators may be invalidated.
  1178     /// valid. However the other iterators may be invalidated.
       
  1179     ///
       
  1180     ///\warning This functionality cannot be used together with the
       
  1181     ///Snapshot feature.
  1168     void changeTarget(Edge e, Node n) { 
  1182     void changeTarget(Edge e, Node n) { 
  1169       Parent::changeTarget(e,n); 
  1183       Parent::changeTarget(e,n); 
  1170     }
  1184     }
  1171     /// \brief Changes the source of \c e to \c n
  1185     /// \brief Change the source of \c e to \c n
  1172     ///
  1186     ///
  1173     /// Changes the source of \c e to \c n. It changes the proper
  1187     /// This function changes the source of \c e to \c n. 
  1174     /// node of the represented edge.
  1188     /// It also changes the proper node of the represented edge.
  1175     ///
  1189     ///
  1176     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1190     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1177     ///referencing the changed arc remain
  1191     ///referencing the changed arc remain
  1178     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1192     ///valid. However <tt>OutArcIt</tt>s are invalidated.
       
  1193     ///
       
  1194     ///\warning This functionality cannot be used together with the
       
  1195     ///Snapshot feature.
  1179     void changeSource(Arc e, Node n) { 
  1196     void changeSource(Arc e, Node n) { 
  1180       if (Parent::direction(e)) {
  1197       if (Parent::direction(e)) {
  1181         Parent::changeSource(e,n);
  1198         Parent::changeSource(e,n);
  1182       } else {
  1199       } else {
  1183         Parent::changeTarget(e,n);
  1200         Parent::changeTarget(e,n);
  1184       } 
  1201       } 
  1185     }
  1202     }
  1186     /// \brief Changes the target of \c e to \c n
  1203     /// \brief Change the target of \c e to \c n
  1187     ///
  1204     ///
  1188     /// Changes the target of \c e to \c n. It changes the proper
  1205     /// This function changes the target of \c e to \c n. 
  1189     /// node of the represented edge.
  1206     /// It also changes the proper node of the represented edge.
  1190     ///
  1207     ///
  1191     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
  1208     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
  1192     ///referencing the changed arc remain
  1209     ///referencing the changed arc remain
  1193     ///valid. However <tt>InArcIt</tt>s are invalidated.
  1210     ///valid. However <tt>InArcIt</tt>s are invalidated.
       
  1211     ///
       
  1212     ///\warning This functionality cannot be used together with the
       
  1213     ///Snapshot feature.
  1194     void changeTarget(Arc e, Node n) { 
  1214     void changeTarget(Arc e, Node n) { 
  1195       if (Parent::direction(e)) {
  1215       if (Parent::direction(e)) {
  1196         Parent::changeTarget(e,n);
  1216         Parent::changeTarget(e,n);
  1197       } else {
  1217       } else {
  1198         Parent::changeSource(e,n);
  1218         Parent::changeSource(e,n);
  1199       } 
  1219       } 
  1200     }
  1220     }
  1201     /// \brief Contract two nodes.
  1221     /// \brief Contract two nodes.
  1202     ///
  1222     ///
  1203     /// This function contracts two nodes.
  1223     /// This function contracts two nodes.
  1204     ///
       
  1205     /// Node \p b will be removed but instead of deleting
  1224     /// Node \p b will be removed but instead of deleting
  1206     /// its neighboring arcs, they will be joined to \p a.
  1225     /// its neighboring arcs, they will be joined to \p a.
  1207     /// The last parameter \p r controls whether to remove loops. \c true
  1226     /// The last parameter \p r controls whether to remove loops. \c true
  1208     /// means that loops will be removed.
  1227     /// means that loops will be removed.
  1209     ///
  1228     ///
  1210     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
  1229     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
  1211     /// valid.
  1230     /// valid.
       
  1231     ///
       
  1232     ///\warning This functionality cannot be used together with the
       
  1233     ///Snapshot feature.
  1212     void contract(Node a, Node b, bool r = true) {
  1234     void contract(Node a, Node b, bool r = true) {
  1213       for(IncArcIt e(*this, b); e!=INVALID;) {
  1235       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1214 	IncArcIt f = e; ++f;
  1236 	IncEdgeIt f = e; ++f;
  1215 	if (r && runningNode(e) == a) {
  1237 	if (r && runningNode(e) == a) {
  1216 	  erase(e);
  1238 	  erase(e);
  1217 	} else if (source(e) == b) {
  1239 	} else if (source(e) == b) {
  1218 	  changeSource(e, a);
  1240 	  changeSource(e, a);
  1219 	} else {
  1241 	} else {
  1223       }
  1245       }
  1224       erase(b);
  1246       erase(b);
  1225     }
  1247     }
  1226 
  1248 
  1227 
  1249 
  1228     /// \brief Class to make a snapshot of the digraph and restore
  1250     /// \brief Class to make a snapshot of the graph and restore
  1229     /// to it later.
  1251     /// it later.
  1230     ///
  1252     ///
  1231     /// Class to make a snapshot of the digraph and to restore it
  1253     /// Class to make a snapshot of the graph and restore it later.
  1232     /// later.
       
  1233     ///
  1254     ///
  1234     /// The newly added nodes and edges can be removed
  1255     /// The newly added nodes and edges can be removed
  1235     /// using the restore() function.
  1256     /// using the restore() function.
  1236     ///
  1257     ///
  1237     /// \warning Arc and node deletions cannot be restored. This
  1258     /// \warning Edge and node deletions and other modifications
  1238     /// events invalidate the snapshot. 
  1259     /// (e.g. changing nodes of edges, contracting nodes) cannot be 
       
  1260     /// restored. These events invalidate the snapshot.
  1239     class Snapshot {
  1261     class Snapshot {
  1240     protected:
  1262     protected:
  1241 
  1263 
  1242       typedef Parent::NodeNotifier NodeNotifier;
  1264       typedef Parent::NodeNotifier NodeNotifier;
  1243 
  1265 
  1301         using EdgeNotifier::ObserverBase::detach;
  1323         using EdgeNotifier::ObserverBase::detach;
  1302         using EdgeNotifier::ObserverBase::attached;
  1324         using EdgeNotifier::ObserverBase::attached;
  1303         
  1325         
  1304       protected:
  1326       protected:
  1305 
  1327 
  1306         virtual void add(const Edge& arc) {
  1328         virtual void add(const Edge& edge) {
  1307           snapshot.addEdge(arc);
  1329           snapshot.addEdge(edge);
  1308         }
  1330         }
  1309         virtual void add(const std::vector<Edge>& arcs) {
  1331         virtual void add(const std::vector<Edge>& edges) {
  1310           for (int i = arcs.size() - 1; i >= 0; ++i) {
  1332           for (int i = edges.size() - 1; i >= 0; ++i) {
  1311             snapshot.addEdge(arcs[i]);
  1333             snapshot.addEdge(edges[i]);
  1312           }
  1334           }
  1313         }
  1335         }
  1314         virtual void erase(const Edge& arc) {
  1336         virtual void erase(const Edge& edge) {
  1315           snapshot.eraseEdge(arc);
  1337           snapshot.eraseEdge(edge);
  1316         }
  1338         }
  1317         virtual void erase(const std::vector<Edge>& arcs) {
  1339         virtual void erase(const std::vector<Edge>& edges) {
  1318           for (int i = 0; i < int(arcs.size()); ++i) {
  1340           for (int i = 0; i < int(edges.size()); ++i) {
  1319             snapshot.eraseEdge(arcs[i]);
  1341             snapshot.eraseEdge(edges[i]);
  1320           }
  1342           }
  1321         }
  1343         }
  1322         virtual void build() {
  1344         virtual void build() {
  1323           Edge arc;
  1345           Edge edge;
  1324           std::vector<Edge> arcs;
  1346           std::vector<Edge> edges;
  1325           for (notifier()->first(arc); arc != INVALID; 
  1347           for (notifier()->first(edge); edge != INVALID; 
  1326                notifier()->next(arc)) {
  1348                notifier()->next(edge)) {
  1327             arcs.push_back(arc);
  1349             edges.push_back(edge);
  1328           }
  1350           }
  1329           for (int i = arcs.size() - 1; i >= 0; --i) {
  1351           for (int i = edges.size() - 1; i >= 0; --i) {
  1330             snapshot.addEdge(arcs[i]);
  1352             snapshot.addEdge(edges[i]);
  1331           }
  1353           }
  1332         }
  1354         }
  1333         virtual void clear() {
  1355         virtual void clear() {
  1334           Edge arc;
  1356           Edge edge;
  1335           for (notifier()->first(arc); arc != INVALID; 
  1357           for (notifier()->first(edge); edge != INVALID; 
  1336                notifier()->next(arc)) {
  1358                notifier()->next(edge)) {
  1337             snapshot.eraseEdge(arc);
  1359             snapshot.eraseEdge(edge);
  1338           }
  1360           }
  1339         }
  1361         }
  1340 
  1362 
  1341         Snapshot& snapshot;
  1363         Snapshot& snapshot;
  1342       };
  1364       };
  1343       
  1365 
  1344       ListGraph *digraph;
  1366       ListGraph *graph;
  1345 
  1367 
  1346       NodeObserverProxy node_observer_proxy;
  1368       NodeObserverProxy node_observer_proxy;
  1347       EdgeObserverProxy arc_observer_proxy;
  1369       EdgeObserverProxy edge_observer_proxy;
  1348 
  1370 
  1349       std::list<Node> added_nodes;
  1371       std::list<Node> added_nodes;
  1350       std::list<Edge> added_arcs;
  1372       std::list<Edge> added_edges;
  1351 
  1373 
  1352 
  1374 
  1353       void addNode(const Node& node) {
  1375       void addNode(const Node& node) {
  1354         added_nodes.push_front(node);        
  1376         added_nodes.push_front(node);        
  1355       }
  1377       }
  1356       void eraseNode(const Node& node) {
  1378       void eraseNode(const Node& node) {
  1357         std::list<Node>::iterator it = 
  1379         std::list<Node>::iterator it = 
  1358           std::find(added_nodes.begin(), added_nodes.end(), node);
  1380           std::find(added_nodes.begin(), added_nodes.end(), node);
  1359         if (it == added_nodes.end()) {
  1381         if (it == added_nodes.end()) {
  1360           clear();
  1382           clear();
  1361           arc_observer_proxy.detach();
  1383           edge_observer_proxy.detach();
  1362           throw NodeNotifier::ImmediateDetach();
  1384           throw NodeNotifier::ImmediateDetach();
  1363         } else {
  1385         } else {
  1364           added_nodes.erase(it);
  1386           added_nodes.erase(it);
  1365         }
  1387         }
  1366       }
  1388       }
  1367 
  1389 
  1368       void addEdge(const Edge& arc) {
  1390       void addEdge(const Edge& edge) {
  1369         added_arcs.push_front(arc);        
  1391         added_edges.push_front(edge);        
  1370       }
  1392       }
  1371       void eraseEdge(const Edge& arc) {
  1393       void eraseEdge(const Edge& edge) {
  1372         std::list<Edge>::iterator it = 
  1394         std::list<Edge>::iterator it = 
  1373           std::find(added_arcs.begin(), added_arcs.end(), arc);
  1395           std::find(added_edges.begin(), added_edges.end(), edge);
  1374         if (it == added_arcs.end()) {
  1396         if (it == added_edges.end()) {
  1375           clear();
  1397           clear();
  1376           node_observer_proxy.detach();
  1398           node_observer_proxy.detach();
  1377           throw EdgeNotifier::ImmediateDetach();
  1399           throw EdgeNotifier::ImmediateDetach();
  1378         } else {
  1400         } else {
  1379           added_arcs.erase(it);
  1401           added_edges.erase(it);
  1380         }        
  1402         }
  1381       }
  1403       }
  1382 
  1404 
  1383       void attach(ListGraph &_digraph) {
  1405       void attach(ListGraph &_graph) {
  1384 	digraph = &_digraph;
  1406 	graph = &_graph;
  1385 	node_observer_proxy.attach(digraph->notifier(Node()));
  1407 	node_observer_proxy.attach(graph->notifier(Node()));
  1386         arc_observer_proxy.attach(digraph->notifier(Edge()));
  1408         edge_observer_proxy.attach(graph->notifier(Edge()));
  1387       }
  1409       }
  1388             
  1410             
  1389       void detach() {
  1411       void detach() {
  1390 	node_observer_proxy.detach();
  1412 	node_observer_proxy.detach();
  1391 	arc_observer_proxy.detach();
  1413 	edge_observer_proxy.detach();
  1392       }
  1414       }
  1393 
  1415 
  1394       bool attached() const {
  1416       bool attached() const {
  1395         return node_observer_proxy.attached();
  1417         return node_observer_proxy.attached();
  1396       }
  1418       }
  1397 
  1419 
  1398       void clear() {
  1420       void clear() {
  1399         added_nodes.clear();
  1421         added_nodes.clear();
  1400         added_arcs.clear();        
  1422         added_edges.clear();        
  1401       }
  1423       }
  1402 
  1424 
  1403     public:
  1425     public:
  1404 
  1426 
  1405       /// \brief Default constructor.
  1427       /// \brief Default constructor.
  1406       ///
  1428       ///
  1407       /// Default constructor.
  1429       /// Default constructor.
  1408       /// To actually make a snapshot you must call save().
  1430       /// To actually make a snapshot you must call save().
  1409       Snapshot() 
  1431       Snapshot() 
  1410         : digraph(0), node_observer_proxy(*this), 
  1432         : graph(0), node_observer_proxy(*this), 
  1411           arc_observer_proxy(*this) {}
  1433           edge_observer_proxy(*this) {}
  1412       
  1434       
  1413       /// \brief Constructor that immediately makes a snapshot.
  1435       /// \brief Constructor that immediately makes a snapshot.
  1414       ///      
  1436       ///      
  1415       /// This constructor immediately makes a snapshot of the digraph.
  1437       /// This constructor immediately makes a snapshot of the graph.
  1416       /// \param _digraph The digraph we make a snapshot of.
  1438       /// \param _graph The graph we make a snapshot of.
  1417       Snapshot(ListGraph &_digraph) 
  1439       Snapshot(ListGraph &_graph) 
  1418         : node_observer_proxy(*this), 
  1440         : node_observer_proxy(*this), 
  1419           arc_observer_proxy(*this) {
  1441           edge_observer_proxy(*this) {
  1420 	attach(_digraph);
  1442 	attach(_graph);
  1421       }
  1443       }
  1422       
  1444       
  1423       /// \brief Make a snapshot.
  1445       /// \brief Make a snapshot.
  1424       ///
  1446       ///
  1425       /// Make a snapshot of the digraph.
  1447       /// Make a snapshot of the graph.
  1426       ///
  1448       ///
  1427       /// This function can be called more than once. In case of a repeated
  1449       /// This function can be called more than once. In case of a repeated
  1428       /// call, the previous snapshot gets lost.
  1450       /// call, the previous snapshot gets lost.
  1429       /// \param _digraph The digraph we make the snapshot of.
  1451       /// \param _graph The graph we make the snapshot of.
  1430       void save(ListGraph &_digraph) {
  1452       void save(ListGraph &_graph) {
  1431         if (attached()) {
  1453         if (attached()) {
  1432           detach();
  1454           detach();
  1433           clear();
  1455           clear();
  1434         }
  1456         }
  1435         attach(_digraph);
  1457         attach(_graph);
  1436       }
  1458       }
  1437       
  1459       
  1438       /// \brief Undo the changes until the last snapshot.
  1460       /// \brief Undo the changes until the last snapshot.
  1439       // 
  1461       // 
  1440       /// Undo the changes until the last snapshot created by save().
  1462       /// Undo the changes until the last snapshot created by save().
  1441       void restore() {
  1463       void restore() {
  1442 	detach();
  1464 	detach();
  1443 	for(std::list<Edge>::iterator it = added_arcs.begin(); 
  1465 	for(std::list<Edge>::iterator it = added_edges.begin(); 
  1444             it != added_arcs.end(); ++it) {
  1466             it != added_edges.end(); ++it) {
  1445 	  digraph->erase(*it);
  1467 	  graph->erase(*it);
  1446 	}
  1468 	}
  1447 	for(std::list<Node>::iterator it = added_nodes.begin(); 
  1469 	for(std::list<Node>::iterator it = added_nodes.begin(); 
  1448             it != added_nodes.end(); ++it) {
  1470             it != added_nodes.end(); ++it) {
  1449 	  digraph->erase(*it);
  1471 	  graph->erase(*it);
  1450 	}
  1472 	}
  1451         clear();
  1473         clear();
  1452       }
  1474       }
  1453 
  1475 
  1454       /// \brief Gives back true when the snapshot is valid.
  1476       /// \brief Gives back true when the snapshot is valid.