lemon/list_graph.h
changeset 259 362415050b29
parent 238 79643f6e8c52
parent 235 b46d2787e9c2
child 280 e7f8647ce760
equal deleted inserted replaced
11:a0590c6b6d2e 12:e01f5a795e18
   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
  1114       first_node = first_free_node = first_free_arc = -1;
  1114       first_node = first_free_node = first_free_arc = -1;
  1115     }
  1115     }
  1116 
  1116 
  1117   protected:
  1117   protected:
  1118 
  1118 
  1119     void changeTarget(Edge e, Node n) {
  1119     void changeV(Edge e, Node n) {
  1120       if(arcs[2 * e.id].next_out != -1) {
  1120       if(arcs[2 * e.id].next_out != -1) {
  1121         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1121         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1122       }
  1122       }
  1123       if(arcs[2 * e.id].prev_out != -1) {
  1123       if(arcs[2 * e.id].prev_out != -1) {
  1124         arcs[arcs[2 * e.id].prev_out].next_out =
  1124         arcs[arcs[2 * e.id].prev_out].next_out =
  1135       arcs[2 * e.id].prev_out = -1;
  1135       arcs[2 * e.id].prev_out = -1;
  1136       arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1136       arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1137       nodes[n.id].first_out = 2 * e.id;
  1137       nodes[n.id].first_out = 2 * e.id;
  1138     }
  1138     }
  1139 
  1139 
  1140     void changeSource(Edge e, Node n) {
  1140     void changeU(Edge e, Node n) {
  1141       if(arcs[(2 * e.id) | 1].next_out != -1) {
  1141       if(arcs[(2 * e.id) | 1].next_out != -1) {
  1142         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1142         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1143           arcs[(2 * e.id) | 1].prev_out;
  1143           arcs[(2 * e.id) | 1].prev_out;
  1144       }
  1144       }
  1145       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1145       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1258     ///
  1258     ///
  1259     /// \warning A Edge pointing to a removed item
  1259     /// \warning A Edge pointing to a removed item
  1260     /// could become valid again later if new edges are
  1260     /// could become valid again later if new edges are
  1261     /// added to the graph.
  1261     /// added to the graph.
  1262     bool valid(Edge e) const { return Parent::valid(e); }
  1262     bool valid(Edge e) const { return Parent::valid(e); }
  1263     /// \brief Change the source of \c e to \c n
  1263     /// \brief Change the end \c u of \c e to \c n
  1264     ///
  1264     ///
  1265     /// This function changes the source of \c e to \c n.
  1265     /// This function changes the end \c u of \c e to node \c n.
  1266     ///
  1266     ///
  1267     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1267     ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
  1268     ///referencing the changed arc remain
  1268     ///changed edge are invalidated and if the changed node is the
  1269     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1269     ///base node of an iterator then this iterator is also
       
  1270     ///invalidated.
  1270     ///
  1271     ///
  1271     ///\warning This functionality cannot be used together with the
  1272     ///\warning This functionality cannot be used together with the
  1272     ///Snapshot feature.
  1273     ///Snapshot feature.
  1273     void changeSource(Edge e, Node n) {
  1274     void changeU(Edge e, Node n) {
  1274       Parent::changeSource(e,n);
  1275       Parent::changeU(e,n);
  1275     }
  1276     }
  1276     /// \brief Change the target of \c e to \c n
  1277     /// \brief Change the end \c v of \c e to \c n
  1277     ///
  1278     ///
  1278     /// This function changes the target of \c e to \c n.
  1279     /// This function changes the end \c v of \c e to \c n.
  1279     ///
  1280     ///
  1280     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
  1281     ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
  1281     /// valid. However the other iterators may be invalidated.
  1282     ///valid, however <tt>ArcIt</tt>s and if the changed node is the
       
  1283     ///base node of an iterator then this iterator is invalidated.
  1282     ///
  1284     ///
  1283     ///\warning This functionality cannot be used together with the
  1285     ///\warning This functionality cannot be used together with the
  1284     ///Snapshot feature.
  1286     ///Snapshot feature.
  1285     void changeTarget(Edge e, Node n) {
  1287     void changeV(Edge e, Node n) {
  1286       Parent::changeTarget(e,n);
  1288       Parent::changeV(e,n);
  1287     }
       
  1288     /// \brief Change the source of \c e to \c n
       
  1289     ///
       
  1290     /// This function changes the source of \c e to \c n.
       
  1291     /// It also changes the proper node of the represented edge.
       
  1292     ///
       
  1293     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
       
  1294     ///referencing the changed arc remain
       
  1295     ///valid. However <tt>OutArcIt</tt>s are invalidated.
       
  1296     ///
       
  1297     ///\warning This functionality cannot be used together with the
       
  1298     ///Snapshot feature.
       
  1299     void changeSource(Arc e, Node n) {
       
  1300       if (Parent::direction(e)) {
       
  1301         Parent::changeSource(e,n);
       
  1302       } else {
       
  1303         Parent::changeTarget(e,n);
       
  1304       }
       
  1305     }
       
  1306     /// \brief Change the target of \c e to \c n
       
  1307     ///
       
  1308     /// This function changes the target of \c e to \c n.
       
  1309     /// It also changes the proper node of the represented edge.
       
  1310     ///
       
  1311     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
       
  1312     ///referencing the changed arc remain
       
  1313     ///valid. However <tt>InArcIt</tt>s are invalidated.
       
  1314     ///
       
  1315     ///\warning This functionality cannot be used together with the
       
  1316     ///Snapshot feature.
       
  1317     void changeTarget(Arc e, Node n) {
       
  1318       if (Parent::direction(e)) {
       
  1319         Parent::changeTarget(e,n);
       
  1320       } else {
       
  1321         Parent::changeSource(e,n);
       
  1322       }
       
  1323     }
  1289     }
  1324     /// \brief Contract two nodes.
  1290     /// \brief Contract two nodes.
  1325     ///
  1291     ///
  1326     /// This function contracts two nodes.
  1292     /// This function contracts two nodes.
  1327     /// Node \p b will be removed but instead of deleting
  1293     /// Node \p b will be removed but instead of deleting
  1337     void contract(Node a, Node b, bool r = true) {
  1303     void contract(Node a, Node b, bool r = true) {
  1338       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1304       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1339         IncEdgeIt f = e; ++f;
  1305         IncEdgeIt f = e; ++f;
  1340         if (r && runningNode(e) == a) {
  1306         if (r && runningNode(e) == a) {
  1341           erase(e);
  1307           erase(e);
  1342         } else if (source(e) == b) {
  1308         } else if (u(e) == b) {
  1343           changeSource(e, a);
  1309           changeU(e, a);
  1344         } else {
  1310         } else {
  1345           changeTarget(e, a);
  1311           changeV(e, a);
  1346         }
  1312         }
  1347         e = f;
  1313         e = f;
  1348       }
  1314       }
  1349       erase(b);
  1315       erase(b);
  1350     }
  1316     }