1.1 --- a/lemon/list_graph.h Mon Jul 24 08:11:00 2006 +0000
1.2 +++ b/lemon/list_graph.h Mon Jul 24 09:49:50 2006 +0000
1.3 @@ -366,7 +366,7 @@
1.4
1.5 /// Changes the target of \c e to \c n
1.6 ///
1.7 - ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
1.8 + ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
1.9 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
1.10 ///invalidated.
1.11 ///\warning This functionality cannot be used together with the Snapshot
1.12 @@ -378,7 +378,7 @@
1.13
1.14 /// Changes the source of \c e to \c n
1.15 ///
1.16 - ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
1.17 + ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1.18 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1.19 ///invalidated.
1.20 ///\warning This functionality cannot be used together with the Snapshot
1.21 @@ -389,7 +389,7 @@
1.22
1.23 /// Invert the direction of an edge.
1.24
1.25 - ///\note The <tt>Edge</tt>s referencing the changed edge remain
1.26 + ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
1.27 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
1.28 ///invalidated.
1.29 ///\warning This functionality cannot be used together with the Snapshot
1.30 @@ -426,9 +426,9 @@
1.31 ///The last parameter \p r controls whether to remove loops. \c true
1.32 ///means that loops will be removed.
1.33 ///
1.34 - ///\note The <tt>Edge</tt>s
1.35 + ///\note The <tt>EdgeIt</tt>s
1.36 ///referencing a moved edge remain
1.37 - ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
1.38 + ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1.39 ///may be invalidated.
1.40 ///\warning This functionality cannot be used together with the Snapshot
1.41 ///feature.
1.42 @@ -459,13 +459,13 @@
1.43 ///from \c n to the newly created node is also added.
1.44 ///\return The newly created node.
1.45 ///
1.46 - ///\note The <tt>Edge</tt>s
1.47 - ///referencing a moved edge remain
1.48 - ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
1.49 - ///may be invalidated.
1.50 - ///\warning This functionality cannot be used together with the Snapshot
1.51 - ///feature.
1.52 - ///\todo It could be implemented in a bit faster way.
1.53 + ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
1.54 + ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
1.55 + ///be invalidated.
1.56 + ///
1.57 + ///\warning This functionality cannot be used together with the
1.58 + ///Snapshot feature. \todo It could be implemented in a bit
1.59 + ///faster way.
1.60 Node split(Node n, bool connect = true) {
1.61 Node b = addNode();
1.62 for(OutEdgeIt e(*this,n);e!=INVALID;) {
1.63 @@ -676,7 +676,7 @@
1.64
1.65 public:
1.66
1.67 - /// \brief Default constructur.
1.68 + /// \brief Default constructor.
1.69 ///
1.70 /// Default constructor.
1.71 /// To actually make a snapshot you must call save().
1.72 @@ -750,9 +750,6 @@
1.73 ///
1.74 ///\sa concept::UGraph.
1.75 ///
1.76 - ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
1.77 - ///haven't been implemented yet.
1.78 - ///
1.79 class ListUGraph : public ExtendedListUGraphBase {
1.80 private:
1.81 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1.82 @@ -788,25 +785,54 @@
1.83 UEdge addEdge(const Node& s, const Node& t) {
1.84 return Parent::addEdge(s, t);
1.85 }
1.86 + /// \brief Changes the source of \c e to \c n
1.87 + ///
1.88 + /// Changes the source of \c e to \c n
1.89 + ///
1.90 + ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1.91 + ///referencing the changed edge remain
1.92 + ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1.93 + void changeSource(UEdge e, Node n) {
1.94 + Parent::changeSource(e,n);
1.95 + }
1.96 /// \brief Changes the target of \c e to \c n
1.97 ///
1.98 /// Changes the target of \c e to \c n
1.99 ///
1.100 - /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
1.101 - /// referencing the changed edge remain
1.102 - /// valid. However <tt>InEdge</tt>'s are invalidated.
1.103 + /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
1.104 + /// valid. However the other iterators may be invalidated.
1.105 void changeTarget(UEdge e, Node n) {
1.106 Parent::changeTarget(e,n);
1.107 }
1.108 - /// Changes the source of \c e to \c n
1.109 + /// \brief Changes the source of \c e to \c n
1.110 ///
1.111 - /// Changes the source of \c e to \c n
1.112 + /// Changes the source of \c e to \c n. It changes the proper
1.113 + /// node of the represented undirected edge.
1.114 ///
1.115 - ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
1.116 + ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1.117 ///referencing the changed edge remain
1.118 - ///valid. However <tt>OutEdge</tt>'s are invalidated.
1.119 - void changeSource(UEdge e, Node n) {
1.120 - Parent::changeSource(e,n);
1.121 + ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1.122 + void changeSource(Edge e, Node n) {
1.123 + if (Parent::direction(e)) {
1.124 + Parent::changeSource(e,n);
1.125 + } else {
1.126 + Parent::changeTarget(e,n);
1.127 + }
1.128 + }
1.129 + /// \brief Changes the target of \c e to \c n
1.130 + ///
1.131 + /// Changes the target of \c e to \c n. It changes the proper
1.132 + /// node of the represented undirected edge.
1.133 + ///
1.134 + ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1.135 + ///referencing the changed edge remain
1.136 + ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1.137 + void changeTarget(Edge e, Node n) {
1.138 + if (Parent::direction(e)) {
1.139 + Parent::changeTarget(e,n);
1.140 + } else {
1.141 + Parent::changeSource(e,n);
1.142 + }
1.143 }
1.144 /// \brief Contract two nodes.
1.145 ///
1.146 @@ -817,8 +843,7 @@
1.147 /// The last parameter \p r controls whether to remove loops. \c true
1.148 /// means that loops will be removed.
1.149 ///
1.150 - /// \note The <tt>Edge</tt>s
1.151 - /// referencing a moved edge remain
1.152 + /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1.153 /// valid.
1.154 void contract(Node a, Node b, bool r = true) {
1.155 for(IncEdgeIt e(*this, b); e!=INVALID;) {
1.156 @@ -841,6 +866,7 @@
1.157 public:
1.158
1.159 class NodeSetError : public LogicError {
1.160 + public:
1.161 virtual const char* what() const throw() {
1.162 return "lemon::ListBpUGraph::NodeSetError";
1.163 }
1.164 @@ -1168,10 +1194,6 @@
1.165 first_free_edge = edge.id;
1.166 }
1.167
1.168 - ///\e
1.169 -
1.170 - ///\bug Undocumented
1.171 - ///\bug Doesn't destruct the maps.
1.172 void clear() {
1.173 aNodes.clear();
1.174 bNodes.clear();
1.175 @@ -1183,6 +1205,44 @@
1.176 first_free_edge = -1;
1.177 }
1.178
1.179 + void changeANode(const UEdge& edge, const Node& node) {
1.180 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1.181 + if (edges[edge.id].prev_out != -1) {
1.182 + edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1.183 + } else {
1.184 + aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1.185 + }
1.186 + if (edges[edge.id].next_out != -1) {
1.187 + edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1.188 + }
1.189 + if (aNodes[node.id >> 1].first_edge != -1) {
1.190 + edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1.191 + }
1.192 + edges[edge.id].prev_out = -1;
1.193 + edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1.194 + aNodes[node.id >> 1].first_edge = edge.id;
1.195 + edges[edge.id].aNode = node.id;
1.196 + }
1.197 +
1.198 + void changeBNode(const UEdge& edge, const Node& node) {
1.199 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1.200 + if (edges[edge.id].prev_in != -1) {
1.201 + edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1.202 + } else {
1.203 + bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1.204 + }
1.205 + if (edges[edge.id].next_in != -1) {
1.206 + edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1.207 + }
1.208 + if (bNodes[node.id >> 1].first_edge != -1) {
1.209 + edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1.210 + }
1.211 + edges[edge.id].prev_in = -1;
1.212 + edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1.213 + bNodes[node.id >> 1].first_edge = edge.id;
1.214 + edges[edge.id].bNode = node.id;
1.215 + }
1.216 +
1.217 };
1.218
1.219
1.220 @@ -1196,7 +1256,147 @@
1.221 /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept".
1.222 /// \sa concept::BpUGraph.
1.223 ///
1.224 - class ListBpUGraph : public ExtendedListBpUGraphBase {};
1.225 + class ListBpUGraph : public ExtendedListBpUGraphBase {
1.226 + /// \brief ListBpUGraph is \e not copy constructible.
1.227 + ///
1.228 + ///ListBpUGraph is \e not copy constructible.
1.229 + ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1.230 + /// \brief Assignment of ListBpUGraph to another one is \e not
1.231 + /// allowed.
1.232 + ///
1.233 + /// Assignment of ListBpUGraph to another one is \e not allowed.
1.234 + void operator=(const ListBpUGraph &) {}
1.235 + public:
1.236 + /// \brief Constructor
1.237 + ///
1.238 + /// Constructor.
1.239 + ///
1.240 + ListBpUGraph() {}
1.241 +
1.242 + typedef ExtendedListBpUGraphBase Parent;
1.243 + /// \brief Add a new ANode to the graph.
1.244 + ///
1.245 + /// \return the new node.
1.246 + ///
1.247 + Node addANode() { return Parent::addANode(); }
1.248 +
1.249 + /// \brief Add a new BNode to the graph.
1.250 + ///
1.251 + /// \return the new node.
1.252 + ///
1.253 + Node addBNode() { return Parent::addBNode(); }
1.254 +
1.255 + /// \brief Add a new edge to the graph.
1.256 + ///
1.257 + /// Add a new edge to the graph with an ANode and a BNode.
1.258 + /// \return the new undirected edge.
1.259 + UEdge addEdge(const Node& s, const Node& t) {
1.260 + return Parent::addEdge(s, t);
1.261 + }
1.262 +
1.263 + /// \brief Changes the ANode of \c e to \c n
1.264 + ///
1.265 + /// Changes the ANode of \c e to \c n
1.266 + ///
1.267 + ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1.268 + ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1.269 + ///invalidated.
1.270 + void changeANode(UEdge e, Node n) {
1.271 + Parent::changeANode(e,n);
1.272 + }
1.273 +
1.274 + /// \brief Changes the BNode of \c e to \c n
1.275 + ///
1.276 + /// Changes the BNode of \c e to \c n
1.277 + ///
1.278 + /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1.279 + /// referencing the changed edge remain
1.280 + /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1.281 + void changeBNode(UEdge e, Node n) {
1.282 + Parent::changeBNode(e,n);
1.283 + }
1.284 +
1.285 + /// \brief Changes the source(ANode) of \c e to \c n
1.286 + ///
1.287 + /// Changes the source(ANode) of \c e to \c n
1.288 + ///
1.289 + ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1.290 + ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1.291 + ///invalidated.
1.292 + void changeSource(UEdge e, Node n) {
1.293 + Parent::changeANode(e,n);
1.294 + }
1.295 +
1.296 + /// \brief Changes the target(BNode) of \c e to \c n
1.297 + ///
1.298 + /// Changes the target(BNode) of \c e to \c n
1.299 + ///
1.300 + /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1.301 + /// referencing the changed edge remain
1.302 + /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1.303 + void changeTarget(UEdge e, Node n) {
1.304 + Parent::changeBNode(e,n);
1.305 + }
1.306 +
1.307 + /// \brief Changes the source of \c e to \c n
1.308 + ///
1.309 + /// Changes the source of \c e to \c n. It changes the proper
1.310 + /// node of the represented undirected edge.
1.311 + ///
1.312 + ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1.313 + ///referencing the changed edge remain
1.314 + ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1.315 + void changeSource(Edge e, Node n) {
1.316 + if (Parent::direction(e)) {
1.317 + Parent::changeANode(e,n);
1.318 + } else {
1.319 + Parent::changeBNode(e,n);
1.320 + }
1.321 + }
1.322 + /// \brief Changes the target of \c e to \c n
1.323 + ///
1.324 + /// Changes the target of \c e to \c n. It changes the proper
1.325 + /// node of the represented undirected edge.
1.326 + ///
1.327 + ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1.328 + ///referencing the changed edge remain
1.329 + ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1.330 + void changeTarget(Edge e, Node n) {
1.331 + if (Parent::direction(e)) {
1.332 + Parent::changeBNode(e,n);
1.333 + } else {
1.334 + Parent::changeANode(e,n);
1.335 + }
1.336 + }
1.337 + /// \brief Contract two nodes.
1.338 + ///
1.339 + /// This function contracts two nodes.
1.340 + ///
1.341 + /// Node \p b will be removed but instead of deleting its
1.342 + /// neighboring edges, they will be joined to \p a. The two nodes
1.343 + /// should be from the same nodeset, of course.
1.344 + ///
1.345 + /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1.346 + /// valid.
1.347 + void contract(const Node& a, const Node& b) {
1.348 + LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1.349 + if (Parent::aNode(a)) {
1.350 + for (IncEdgeIt e(*this, b); e!=INVALID;) {
1.351 + IncEdgeIt f = e; ++f;
1.352 + changeSource(e, a);
1.353 + e = f;
1.354 + }
1.355 + } else {
1.356 + for (IncEdgeIt e(*this, b); e!=INVALID;) {
1.357 + IncEdgeIt f = e; ++f;
1.358 + changeTarget(e, a);
1.359 + e = f;
1.360 + }
1.361 + }
1.362 + erase(b);
1.363 + }
1.364 +
1.365 + };
1.366
1.367
1.368 /// @}