# HG changeset patch
# User deba
# Date 1153734590 0
# Node ID abd867cf8a9c158f9b861157170e2cb849a37bb2
# Parent dd3181a462d004873bcaadb91fa6366b85a1c5fa
Change source and target for the bipartite list graph
Some documentation corrections
diff -r dd3181a462d0 -r abd867cf8a9c lemon/list_graph.h
--- a/lemon/list_graph.h Mon Jul 24 08:11:00 2006 +0000
+++ b/lemon/list_graph.h Mon Jul 24 09:49:50 2006 +0000
@@ -366,7 +366,7 @@
/// Changes the target of \c e to \c n
///
- ///\note The Edges and OutEdgeIts referencing
+ ///\note The EdgeIts and OutEdgeIts referencing
///the changed edge remain valid. However InEdgeIts are
///invalidated.
///\warning This functionality cannot be used together with the Snapshot
@@ -378,7 +378,7 @@
/// Changes the source of \c e to \c n
///
- ///\note The Edges and InEdgeIts referencing
+ ///\note The EdgeIts and InEdgeIts referencing
///the changed edge remain valid. However OutEdgeIts are
///invalidated.
///\warning This functionality cannot be used together with the Snapshot
@@ -389,7 +389,7 @@
/// Invert the direction of an edge.
- ///\note The Edges referencing the changed edge remain
+ ///\note The EdgeIts referencing the changed edge remain
///valid. However OutEdgeIts and InEdgeIts are
///invalidated.
///\warning This functionality cannot be used together with the Snapshot
@@ -426,9 +426,9 @@
///The last parameter \p r controls whether to remove loops. \c true
///means that loops will be removed.
///
- ///\note The Edges
+ ///\note The EdgeIts
///referencing a moved edge remain
- ///valid. However InEdges and OutEdges
+ ///valid. However InEdgeIts and OutEdgeIts
///may be invalidated.
///\warning This functionality cannot be used together with the Snapshot
///feature.
@@ -459,13 +459,13 @@
///from \c n to the newly created node is also added.
///\return The newly created node.
///
- ///\note The Edges
- ///referencing a moved edge remain
- ///valid. However InEdges and OutEdges
- ///may be invalidated.
- ///\warning This functionality cannot be used together with the Snapshot
- ///feature.
- ///\todo It could be implemented in a bit faster way.
+ ///\note The EdgeIts referencing a moved edge remain
+ ///valid. However InEdgeIts and OutEdgeIts may
+ ///be invalidated.
+ ///
+ ///\warning This functionality cannot be used together with the
+ ///Snapshot feature. \todo It could be implemented in a bit
+ ///faster way.
Node split(Node n, bool connect = true) {
Node b = addNode();
for(OutEdgeIt e(*this,n);e!=INVALID;) {
@@ -676,7 +676,7 @@
public:
- /// \brief Default constructur.
+ /// \brief Default constructor.
///
/// Default constructor.
/// To actually make a snapshot you must call save().
@@ -750,9 +750,6 @@
///
///\sa concept::UGraph.
///
- ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
- ///haven't been implemented yet.
- ///
class ListUGraph : public ExtendedListUGraphBase {
private:
///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
@@ -788,25 +785,54 @@
UEdge addEdge(const Node& s, const Node& t) {
return Parent::addEdge(s, t);
}
+ /// \brief Changes the source of \c e to \c n
+ ///
+ /// Changes the source of \c e to \c n
+ ///
+ ///\note The EdgeIts and InEdgeIts
+ ///referencing the changed edge remain
+ ///valid. However OutEdgeIts are invalidated.
+ void changeSource(UEdge e, Node n) {
+ Parent::changeSource(e,n);
+ }
/// \brief Changes the target of \c e to \c n
///
/// Changes the target of \c e to \c n
///
- /// \note The Edge's and OutEdge's
- /// referencing the changed edge remain
- /// valid. However InEdge's are invalidated.
+ /// \note The EdgeIts referencing the changed edge remain
+ /// valid. However the other iterators may be invalidated.
void changeTarget(UEdge e, Node n) {
Parent::changeTarget(e,n);
}
- /// Changes the source of \c e to \c n
+ /// \brief Changes the source of \c e to \c n
///
- /// Changes the source of \c e to \c n
+ /// Changes the source of \c e to \c n. It changes the proper
+ /// node of the represented undirected edge.
///
- ///\note The Edge's and InEdge's
+ ///\note The EdgeIts and InEdgeIts
///referencing the changed edge remain
- ///valid. However OutEdge's are invalidated.
- void changeSource(UEdge e, Node n) {
- Parent::changeSource(e,n);
+ ///valid. However OutEdgeIts are invalidated.
+ void changeSource(Edge e, Node n) {
+ if (Parent::direction(e)) {
+ Parent::changeSource(e,n);
+ } else {
+ Parent::changeTarget(e,n);
+ }
+ }
+ /// \brief Changes the target of \c e to \c n
+ ///
+ /// Changes the target of \c e to \c n. It changes the proper
+ /// node of the represented undirected edge.
+ ///
+ ///\note The EdgeIts and OutEdgeIts
+ ///referencing the changed edge remain
+ ///valid. However InEdgeIts are invalidated.
+ void changeTarget(Edge e, Node n) {
+ if (Parent::direction(e)) {
+ Parent::changeTarget(e,n);
+ } else {
+ Parent::changeSource(e,n);
+ }
}
/// \brief Contract two nodes.
///
@@ -817,8 +843,7 @@
/// The last parameter \p r controls whether to remove loops. \c true
/// means that loops will be removed.
///
- /// \note The Edges
- /// referencing a moved edge remain
+ /// \note The EdgeIts referencing a moved edge remain
/// valid.
void contract(Node a, Node b, bool r = true) {
for(IncEdgeIt e(*this, b); e!=INVALID;) {
@@ -841,6 +866,7 @@
public:
class NodeSetError : public LogicError {
+ public:
virtual const char* what() const throw() {
return "lemon::ListBpUGraph::NodeSetError";
}
@@ -1168,10 +1194,6 @@
first_free_edge = edge.id;
}
- ///\e
-
- ///\bug Undocumented
- ///\bug Doesn't destruct the maps.
void clear() {
aNodes.clear();
bNodes.clear();
@@ -1183,6 +1205,44 @@
first_free_edge = -1;
}
+ void changeANode(const UEdge& edge, const Node& node) {
+ LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+ if (edges[edge.id].prev_out != -1) {
+ edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
+ } else {
+ aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
+ }
+ if (edges[edge.id].next_out != -1) {
+ edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
+ }
+ if (aNodes[node.id >> 1].first_edge != -1) {
+ edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
+ }
+ edges[edge.id].prev_out = -1;
+ edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
+ aNodes[node.id >> 1].first_edge = edge.id;
+ edges[edge.id].aNode = node.id;
+ }
+
+ void changeBNode(const UEdge& edge, const Node& node) {
+ LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+ if (edges[edge.id].prev_in != -1) {
+ edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
+ } else {
+ bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
+ }
+ if (edges[edge.id].next_in != -1) {
+ edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
+ }
+ if (bNodes[node.id >> 1].first_edge != -1) {
+ edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
+ }
+ edges[edge.id].prev_in = -1;
+ edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
+ bNodes[node.id >> 1].first_edge = edge.id;
+ edges[edge.id].bNode = node.id;
+ }
+
};
@@ -1196,7 +1256,147 @@
/// It is conforms to the \ref concept::BpUGraph "BpUGraph concept".
/// \sa concept::BpUGraph.
///
- class ListBpUGraph : public ExtendedListBpUGraphBase {};
+ class ListBpUGraph : public ExtendedListBpUGraphBase {
+ /// \brief ListBpUGraph is \e not copy constructible.
+ ///
+ ///ListBpUGraph is \e not copy constructible.
+ ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
+ /// \brief Assignment of ListBpUGraph to another one is \e not
+ /// allowed.
+ ///
+ /// Assignment of ListBpUGraph to another one is \e not allowed.
+ void operator=(const ListBpUGraph &) {}
+ public:
+ /// \brief Constructor
+ ///
+ /// Constructor.
+ ///
+ ListBpUGraph() {}
+
+ typedef ExtendedListBpUGraphBase Parent;
+ /// \brief Add a new ANode to the graph.
+ ///
+ /// \return the new node.
+ ///
+ Node addANode() { return Parent::addANode(); }
+
+ /// \brief Add a new BNode to the graph.
+ ///
+ /// \return the new node.
+ ///
+ Node addBNode() { return Parent::addBNode(); }
+
+ /// \brief Add a new edge to the graph.
+ ///
+ /// Add a new edge to the graph with an ANode and a BNode.
+ /// \return the new undirected edge.
+ UEdge addEdge(const Node& s, const Node& t) {
+ return Parent::addEdge(s, t);
+ }
+
+ /// \brief Changes the ANode of \c e to \c n
+ ///
+ /// Changes the ANode of \c e to \c n
+ ///
+ ///\note The EdgeIts and InEdgeIts referencing
+ ///the changed edge remain valid. However OutEdgeIts are
+ ///invalidated.
+ void changeANode(UEdge e, Node n) {
+ Parent::changeANode(e,n);
+ }
+
+ /// \brief Changes the BNode of \c e to \c n
+ ///
+ /// Changes the BNode of \c e to \c n
+ ///
+ /// \note The EdgeIts and OutEdgeIts
+ /// referencing the changed edge remain
+ /// valid. However InEdgeIts are invalidated.
+ void changeBNode(UEdge e, Node n) {
+ Parent::changeBNode(e,n);
+ }
+
+ /// \brief Changes the source(ANode) of \c e to \c n
+ ///
+ /// Changes the source(ANode) of \c e to \c n
+ ///
+ ///\note The EdgeIts and InEdgeIts referencing
+ ///the changed edge remain valid. However OutEdgeIts are
+ ///invalidated.
+ void changeSource(UEdge e, Node n) {
+ Parent::changeANode(e,n);
+ }
+
+ /// \brief Changes the target(BNode) of \c e to \c n
+ ///
+ /// Changes the target(BNode) of \c e to \c n
+ ///
+ /// \note The EdgeIts and OutEdgeIts
+ /// referencing the changed edge remain
+ /// valid. However InEdgeIts are invalidated.
+ void changeTarget(UEdge e, Node n) {
+ Parent::changeBNode(e,n);
+ }
+
+ /// \brief Changes the source of \c e to \c n
+ ///
+ /// Changes the source of \c e to \c n. It changes the proper
+ /// node of the represented undirected edge.
+ ///
+ ///\note The EdgeIts and InEdgeIts
+ ///referencing the changed edge remain
+ ///valid. However OutEdgeIts are invalidated.
+ void changeSource(Edge e, Node n) {
+ if (Parent::direction(e)) {
+ Parent::changeANode(e,n);
+ } else {
+ Parent::changeBNode(e,n);
+ }
+ }
+ /// \brief Changes the target of \c e to \c n
+ ///
+ /// Changes the target of \c e to \c n. It changes the proper
+ /// node of the represented undirected edge.
+ ///
+ ///\note The EdgeIts and OutEdgeIts
+ ///referencing the changed edge remain
+ ///valid. However InEdgeIts are invalidated.
+ void changeTarget(Edge e, Node n) {
+ if (Parent::direction(e)) {
+ Parent::changeBNode(e,n);
+ } else {
+ Parent::changeANode(e,n);
+ }
+ }
+ /// \brief Contract two nodes.
+ ///
+ /// This function contracts two nodes.
+ ///
+ /// Node \p b will be removed but instead of deleting its
+ /// neighboring edges, they will be joined to \p a. The two nodes
+ /// should be from the same nodeset, of course.
+ ///
+ /// \note The EdgeIts referencing a moved edge remain
+ /// valid.
+ void contract(const Node& a, const Node& b) {
+ LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
+ if (Parent::aNode(a)) {
+ for (IncEdgeIt e(*this, b); e!=INVALID;) {
+ IncEdgeIt f = e; ++f;
+ changeSource(e, a);
+ e = f;
+ }
+ } else {
+ for (IncEdgeIt e(*this, b); e!=INVALID;) {
+ IncEdgeIt f = e; ++f;
+ changeTarget(e, a);
+ e = f;
+ }
+ }
+ erase(b);
+ }
+
+ };
/// @}