COIN-OR::LEMON - Graph Library

Changeset 2160:abd867cf8a9c in lemon-0.x


Ignore:
Timestamp:
07/24/06 11:49:50 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2875
Message:

Change source and target for the bipartite list graph
Some documentation corrections

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r2151 r2160  
    367367    /// Changes the target of \c e to \c n
    368368    ///
    369     ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
     369    ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
    370370    ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
    371371    ///invalidated.
     
    379379    /// Changes the source of \c e to \c n
    380380    ///
    381     ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
     381    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
    382382    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
    383383    ///invalidated.
     
    390390    /// Invert the direction of an edge.
    391391
    392     ///\note The <tt>Edge</tt>s referencing the changed edge remain
     392    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
    393393    ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
    394394    ///invalidated.
     
    427427    ///means that loops will be removed.
    428428    ///
    429     ///\note The <tt>Edge</tt>s
     429    ///\note The <tt>EdgeIt</tt>s
    430430    ///referencing a moved edge remain
    431     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
     431    ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
    432432    ///may be invalidated.
    433433    ///\warning This functionality cannot be used together with the Snapshot
     
    460460    ///\return The newly created node.
    461461    ///
    462     ///\note The <tt>Edge</tt>s
    463     ///referencing a moved edge remain
    464     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
    465     ///may be invalidated.
    466     ///\warning This functionality cannot be used together with the Snapshot
    467     ///feature.
    468     ///\todo It could be implemented in a bit faster way.
     462    ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
     463    ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
     464    ///be invalidated. 
     465    ///
     466    ///\warning This functionality cannot be used together with the
     467    ///Snapshot feature.  \todo It could be implemented in a bit
     468    ///faster way.
    469469    Node split(Node n, bool connect = true) {
    470470      Node b = addNode();
     
    677677    public:
    678678
    679       /// \brief Default constructur.
     679      /// \brief Default constructor.
    680680      ///
    681681      /// Default constructor.
     
    751751  ///\sa concept::UGraph.
    752752  ///
    753   ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
    754   ///haven't been implemented yet.
    755   ///
    756753  class ListUGraph : public ExtendedListUGraphBase {
    757754  private:
     
    789786      return Parent::addEdge(s, t);
    790787    }
     788    /// \brief Changes the source of \c e to \c n
     789    ///
     790    /// Changes the source of \c e to \c n
     791    ///
     792    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
     793    ///referencing the changed edge remain
     794    ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
     795    void changeSource(UEdge e, Node n) {
     796      Parent::changeSource(e,n);
     797    }   
    791798    /// \brief Changes the target of \c e to \c n
    792799    ///
    793800    /// Changes the target of \c e to \c n
    794801    ///
    795     /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
    796     /// referencing the changed edge remain
    797     /// valid. However <tt>InEdge</tt>'s are invalidated.
     802    /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
     803    /// valid. However the other iterators may be invalidated.
    798804    void changeTarget(UEdge e, Node n) {
    799805      Parent::changeTarget(e,n);
    800806    }
    801     /// Changes the source of \c e to \c n
    802     ///
    803     /// Changes the source of \c e to \c n
    804     ///
    805     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
     807    /// \brief Changes the source of \c e to \c n
     808    ///
     809    /// Changes the source of \c e to \c n. It changes the proper
     810    /// node of the represented undirected edge.
     811    ///
     812    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
    806813    ///referencing the changed edge remain
    807     ///valid. However <tt>OutEdge</tt>'s are invalidated.
    808     void changeSource(UEdge e, Node n) {
    809       Parent::changeSource(e,n);
     814    ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
     815    void changeSource(Edge e, Node n) {
     816      if (Parent::direction(e)) {
     817        Parent::changeSource(e,n);
     818      } else {
     819        Parent::changeTarget(e,n);
     820      }
     821    }
     822    /// \brief Changes the target of \c e to \c n
     823    ///
     824    /// Changes the target of \c e to \c n. It changes the proper
     825    /// node of the represented undirected edge.
     826    ///
     827    ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
     828    ///referencing the changed edge remain
     829    ///valid. However <tt>InEdgeIt</tt>s are invalidated.
     830    void changeTarget(Edge e, Node n) {
     831      if (Parent::direction(e)) {
     832        Parent::changeTarget(e,n);
     833      } else {
     834        Parent::changeSource(e,n);
     835      }
    810836    }
    811837    /// \brief Contract two nodes.
     
    818844    /// means that loops will be removed.
    819845    ///
    820     /// \note The <tt>Edge</tt>s
    821     /// referencing a moved edge remain
     846    /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
    822847    /// valid.
    823848    void contract(Node a, Node b, bool r = true) {
     
    842867
    843868    class NodeSetError : public LogicError {
     869    public:
    844870      virtual const char* what() const throw() {
    845871        return "lemon::ListBpUGraph::NodeSetError";
     
    11691195    }
    11701196 
    1171     ///\e
    1172    
    1173     ///\bug Undocumented
    1174     ///\bug Doesn't destruct the maps.
    11751197    void clear() {
    11761198      aNodes.clear();
     
    11841206    }
    11851207
     1208    void changeANode(const UEdge& edge, const Node& node) {
     1209      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     1210      if (edges[edge.id].prev_out != -1) {
     1211        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
     1212      } else {
     1213        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
     1214      }
     1215      if (edges[edge.id].next_out != -1) {
     1216        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; 
     1217      }
     1218      if (aNodes[node.id >> 1].first_edge != -1) {
     1219        edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
     1220      }
     1221      edges[edge.id].prev_out = -1;
     1222      edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
     1223      aNodes[node.id >> 1].first_edge = edge.id;
     1224      edges[edge.id].aNode = node.id;
     1225    }
     1226
     1227    void changeBNode(const UEdge& edge, const Node& node) {
     1228      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     1229      if (edges[edge.id].prev_in != -1) {
     1230        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
     1231      } else {
     1232        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
     1233      }
     1234      if (edges[edge.id].next_in != -1) {
     1235        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; 
     1236      }
     1237      if (bNodes[node.id >> 1].first_edge != -1) {
     1238        edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
     1239      }
     1240      edges[edge.id].prev_in = -1;
     1241      edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
     1242      bNodes[node.id >> 1].first_edge = edge.id;
     1243      edges[edge.id].bNode = node.id;
     1244    }
     1245
    11861246  };
    11871247
     
    11971257  /// \sa concept::BpUGraph.
    11981258  ///
    1199   class ListBpUGraph : public ExtendedListBpUGraphBase {};
     1259  class ListBpUGraph : public ExtendedListBpUGraphBase {
     1260    /// \brief ListBpUGraph is \e not copy constructible.
     1261    ///
     1262    ///ListBpUGraph is \e not copy constructible.
     1263    ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase()  {};
     1264    /// \brief Assignment of ListBpUGraph to another one is \e not
     1265    /// allowed.
     1266    ///
     1267    /// Assignment of ListBpUGraph to another one is \e not allowed.
     1268    void operator=(const ListBpUGraph &) {}
     1269  public:
     1270    /// \brief Constructor
     1271    ///   
     1272    /// Constructor.
     1273    ///
     1274    ListBpUGraph() {}
     1275
     1276    typedef ExtendedListBpUGraphBase Parent;
     1277    /// \brief Add a new ANode to the graph.
     1278    ///
     1279    /// \return the new node.
     1280    ///
     1281    Node addANode() { return Parent::addANode(); }
     1282
     1283    /// \brief Add a new BNode to the graph.
     1284    ///
     1285    /// \return the new node.
     1286    ///
     1287    Node addBNode() { return Parent::addBNode(); }
     1288
     1289    /// \brief Add a new edge to the graph.
     1290    ///
     1291    /// Add a new edge to the graph with an ANode and a BNode.
     1292    /// \return the new undirected edge.
     1293    UEdge addEdge(const Node& s, const Node& t) {
     1294      return Parent::addEdge(s, t);
     1295    }
     1296
     1297    /// \brief Changes the ANode of \c e to \c n
     1298    ///
     1299    /// Changes the ANode of \c e to \c n
     1300    ///
     1301    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
     1302    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
     1303    ///invalidated.
     1304    void changeANode(UEdge e, Node n) {
     1305      Parent::changeANode(e,n);
     1306    }
     1307
     1308    /// \brief Changes the BNode of \c e to \c n
     1309    ///
     1310    /// Changes the BNode of \c e to \c n
     1311    ///
     1312    /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
     1313    /// referencing the changed edge remain
     1314    /// valid. However <tt>InEdgeIt</tt>s are invalidated.
     1315    void changeBNode(UEdge e, Node n) {
     1316      Parent::changeBNode(e,n);
     1317    }
     1318
     1319    /// \brief Changes the source(ANode) of \c e to \c n
     1320    ///
     1321    /// Changes the source(ANode) of \c e to \c n
     1322    ///
     1323    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
     1324    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
     1325    ///invalidated.
     1326    void changeSource(UEdge e, Node n) {
     1327      Parent::changeANode(e,n);
     1328    }
     1329
     1330    /// \brief Changes the target(BNode) of \c e to \c n
     1331    ///
     1332    /// Changes the target(BNode) of \c e to \c n
     1333    ///
     1334    /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
     1335    /// referencing the changed edge remain
     1336    /// valid. However <tt>InEdgeIt</tt>s are invalidated.
     1337    void changeTarget(UEdge e, Node n) {
     1338      Parent::changeBNode(e,n);
     1339    }
     1340
     1341    /// \brief Changes the source of \c e to \c n
     1342    ///
     1343    /// Changes the source of \c e to \c n. It changes the proper
     1344    /// node of the represented undirected edge.
     1345    ///
     1346    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
     1347    ///referencing the changed edge remain
     1348    ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
     1349    void changeSource(Edge e, Node n) {
     1350      if (Parent::direction(e)) {
     1351        Parent::changeANode(e,n);
     1352      } else {
     1353        Parent::changeBNode(e,n);
     1354      }
     1355    }
     1356    /// \brief Changes the target of \c e to \c n
     1357    ///
     1358    /// Changes the target of \c e to \c n. It changes the proper
     1359    /// node of the represented undirected edge.
     1360    ///
     1361    ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
     1362    ///referencing the changed edge remain
     1363    ///valid. However <tt>InEdgeIt</tt>s are invalidated.
     1364    void changeTarget(Edge e, Node n) {
     1365      if (Parent::direction(e)) {
     1366        Parent::changeBNode(e,n);
     1367      } else {
     1368        Parent::changeANode(e,n);
     1369      }
     1370    }
     1371    /// \brief Contract two nodes.
     1372    ///
     1373    /// This function contracts two nodes.
     1374    ///
     1375    /// Node \p b will be removed but instead of deleting its
     1376    /// neighboring edges, they will be joined to \p a.  The two nodes
     1377    /// should be from the same nodeset, of course.
     1378    ///
     1379    /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
     1380    /// valid.
     1381    void contract(const Node& a, const Node& b) {
     1382      LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
     1383      if (Parent::aNode(a)) {
     1384        for (IncEdgeIt e(*this, b); e!=INVALID;) {
     1385          IncEdgeIt f = e; ++f;
     1386          changeSource(e, a);
     1387          e = f;
     1388        }
     1389      } else {
     1390        for (IncEdgeIt e(*this, b); e!=INVALID;) {
     1391          IncEdgeIt f = e; ++f;
     1392          changeTarget(e, a);
     1393          e = f;
     1394        }
     1395      }
     1396      erase(b);
     1397    }
     1398
     1399  };
    12001400
    12011401 
Note: See TracChangeset for help on using the changeset viewer.