lemon/list_graph.h
changeset 241 92f046dd7f6c
parent 234 ad6b8c47bd56
child 239 7b7e3f20bcec
equal deleted inserted replaced
9:2e4f3eb2c74d 10:86cefb1cf659
   393     /// \warning An Arc pointing to a removed item
   393     /// \warning An Arc pointing to a removed item
   394     /// could become valid again later if new nodes are
   394     /// could become valid again later if new nodes are
   395     /// added to the graph.
   395     /// added to the graph.
   396     bool valid(Arc a) const { return Parent::valid(a); }
   396     bool valid(Arc a) const { return Parent::valid(a); }
   397 
   397 
   398     /// Change the target of \c e to \c n
   398     /// Change the target of \c a to \c n
   399 
   399 
   400     /// Change the target of \c e to \c n
   400     /// Change the target of \c a to \c n
   401     ///
   401     ///
   402     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
   402     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
   403     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
   403     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
   404     ///invalidated.
   404     ///invalidated.
   405     ///
   405     ///
   406     ///\warning This functionality cannot be used together with the Snapshot
   406     ///\warning This functionality cannot be used together with the Snapshot
   407     ///feature.
   407     ///feature.
   408     void changeTarget(Arc e, Node n) {
   408     void changeTarget(Arc a, Node n) {
   409       Parent::changeTarget(e,n);
   409       Parent::changeTarget(a,n);
   410     }
   410     }
   411     /// Change the source of \c e to \c n
   411     /// Change the source of \c a to \c n
   412 
   412 
   413     /// Change the source of \c e to \c n
   413     /// Change the source of \c a to \c n
   414     ///
   414     ///
   415     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
   415     ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
   416     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
   416     ///valid. However the <tt>ArcIt<tt>s and <tt>OutArcIt</tt>s are
   417     ///invalidated.
   417     ///invalidated.
   418     ///
   418     ///
   419     ///\warning This functionality cannot be used together with the Snapshot
   419     ///\warning This functionality cannot be used together with the Snapshot
   420     ///feature.
   420     ///feature.
   421     void changeSource(Arc e, Node n) {
   421     void changeSource(Arc a, Node n) {
   422       Parent::changeSource(e,n);
   422       Parent::changeSource(a,n);
   423     }
   423     }
   424 
   424 
   425     /// Invert the direction of an arc.
   425     /// Invert the direction of an arc.
   426 
   426 
   427     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
   427     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
  1112       first_node = first_free_node = first_free_arc = -1;
  1112       first_node = first_free_node = first_free_arc = -1;
  1113     }
  1113     }
  1114 
  1114 
  1115   protected:
  1115   protected:
  1116 
  1116 
  1117     void changeTarget(Edge e, Node n) {
  1117     void changeV(Edge e, Node n) {
  1118       if(arcs[2 * e.id].next_out != -1) {
  1118       if(arcs[2 * e.id].next_out != -1) {
  1119         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1119         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1120       }
  1120       }
  1121       if(arcs[2 * e.id].prev_out != -1) {
  1121       if(arcs[2 * e.id].prev_out != -1) {
  1122         arcs[arcs[2 * e.id].prev_out].next_out =
  1122         arcs[arcs[2 * e.id].prev_out].next_out =
  1133       arcs[2 * e.id].prev_out = -1;
  1133       arcs[2 * e.id].prev_out = -1;
  1134       arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1134       arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1135       nodes[n.id].first_out = 2 * e.id;
  1135       nodes[n.id].first_out = 2 * e.id;
  1136     }
  1136     }
  1137 
  1137 
  1138     void changeSource(Edge e, Node n) {
  1138     void changeU(Edge e, Node n) {
  1139       if(arcs[(2 * e.id) | 1].next_out != -1) {
  1139       if(arcs[(2 * e.id) | 1].next_out != -1) {
  1140         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1140         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1141           arcs[(2 * e.id) | 1].prev_out;
  1141           arcs[(2 * e.id) | 1].prev_out;
  1142       }
  1142       }
  1143       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1143       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1256     ///
  1256     ///
  1257     /// \warning A Edge pointing to a removed item
  1257     /// \warning A Edge pointing to a removed item
  1258     /// could become valid again later if new edges are
  1258     /// could become valid again later if new edges are
  1259     /// added to the graph.
  1259     /// added to the graph.
  1260     bool valid(Edge e) const { return Parent::valid(e); }
  1260     bool valid(Edge e) const { return Parent::valid(e); }
  1261     /// \brief Change the source of \c e to \c n
  1261     /// \brief Change the end \c u of \c e to \c n
  1262     ///
  1262     ///
  1263     /// This function changes the source of \c e to \c n.
  1263     /// This function changes the end \c u of \c e to node \c n.
  1264     ///
  1264     ///
  1265     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1265     ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
  1266     ///referencing the changed arc remain
  1266     ///changed edge are invalidated and if the changed node is the
  1267     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1267     ///base node of an iterator then this iterator is also
       
  1268     ///invalidated.
  1268     ///
  1269     ///
  1269     ///\warning This functionality cannot be used together with the
  1270     ///\warning This functionality cannot be used together with the
  1270     ///Snapshot feature.
  1271     ///Snapshot feature.
  1271     void changeSource(Edge e, Node n) {
  1272     void changeU(Edge e, Node n) {
  1272       Parent::changeSource(e,n);
  1273       Parent::changeU(e,n);
  1273     }
  1274     }
  1274     /// \brief Change the target of \c e to \c n
  1275     /// \brief Change the end \c v of \c e to \c n
  1275     ///
  1276     ///
  1276     /// This function changes the target of \c e to \c n.
  1277     /// This function changes the end \c v of \c e to \c n.
  1277     ///
  1278     ///
  1278     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
  1279     ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
  1279     /// valid. However the other iterators may be invalidated.
  1280     ///valid, however <tt>ArcIt</tt>s and if the changed node is the
       
  1281     ///base node of an iterator then this iterator is invalidated.
  1280     ///
  1282     ///
  1281     ///\warning This functionality cannot be used together with the
  1283     ///\warning This functionality cannot be used together with the
  1282     ///Snapshot feature.
  1284     ///Snapshot feature.
  1283     void changeTarget(Edge e, Node n) {
  1285     void changeV(Edge e, Node n) {
  1284       Parent::changeTarget(e,n);
  1286       Parent::changeV(e,n);
  1285     }
       
  1286     /// \brief Change the source of \c e to \c n
       
  1287     ///
       
  1288     /// This function changes the source of \c e to \c n.
       
  1289     /// It also changes the proper node of the represented edge.
       
  1290     ///
       
  1291     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
       
  1292     ///referencing the changed arc remain
       
  1293     ///valid. However <tt>OutArcIt</tt>s are invalidated.
       
  1294     ///
       
  1295     ///\warning This functionality cannot be used together with the
       
  1296     ///Snapshot feature.
       
  1297     void changeSource(Arc e, Node n) {
       
  1298       if (Parent::direction(e)) {
       
  1299         Parent::changeSource(e,n);
       
  1300       } else {
       
  1301         Parent::changeTarget(e,n);
       
  1302       }
       
  1303     }
       
  1304     /// \brief Change the target of \c e to \c n
       
  1305     ///
       
  1306     /// This function changes the target of \c e to \c n.
       
  1307     /// It also changes the proper node of the represented edge.
       
  1308     ///
       
  1309     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
       
  1310     ///referencing the changed arc remain
       
  1311     ///valid. However <tt>InArcIt</tt>s are invalidated.
       
  1312     ///
       
  1313     ///\warning This functionality cannot be used together with the
       
  1314     ///Snapshot feature.
       
  1315     void changeTarget(Arc e, Node n) {
       
  1316       if (Parent::direction(e)) {
       
  1317         Parent::changeTarget(e,n);
       
  1318       } else {
       
  1319         Parent::changeSource(e,n);
       
  1320       }
       
  1321     }
  1287     }
  1322     /// \brief Contract two nodes.
  1288     /// \brief Contract two nodes.
  1323     ///
  1289     ///
  1324     /// This function contracts two nodes.
  1290     /// This function contracts two nodes.
  1325     /// Node \p b will be removed but instead of deleting
  1291     /// Node \p b will be removed but instead of deleting
  1335     void contract(Node a, Node b, bool r = true) {
  1301     void contract(Node a, Node b, bool r = true) {
  1336       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1302       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1337         IncEdgeIt f = e; ++f;
  1303         IncEdgeIt f = e; ++f;
  1338         if (r && runningNode(e) == a) {
  1304         if (r && runningNode(e) == a) {
  1339           erase(e);
  1305           erase(e);
  1340         } else if (source(e) == b) {
  1306         } else if (u(e) == b) {
  1341           changeSource(e, a);
  1307           changeU(e, a);
  1342         } else {
  1308         } else {
  1343           changeTarget(e, a);
  1309           changeV(e, a);
  1344         }
  1310         }
  1345         e = f;
  1311         e = f;
  1346       }
  1312       }
  1347       erase(b);
  1313       erase(b);
  1348     }
  1314     }