Changeset 2160:abd867cf8a9c in lemon-0.x

Timestamp:

07/24/06 11:49:50 (18 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:

• lemon/list_graph.h (modified) (13 diffs)

lemon/list_graph.h

@@ -367 +367 @@
     /// Changes the target of \c e to \c n
     ///
-    ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
+    ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
     ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
     ///invalidated.
@@ -379 +379 @@
     /// Changes the source of \c e to \c n
     ///
-    ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
+    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
     ///invalidated.
@@ -390 +390 @@
     /// Invert the direction of an edge.
 
-    ///\note The <tt>Edge</tt>s referencing the changed edge remain
+    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
     ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
     ///invalidated.
@@ -427 +427 @@
     ///means that loops will be removed.
     ///
-    ///\note The <tt>Edge</tt>s
+    ///\note The <tt>EdgeIt</tt>s
     ///referencing a moved edge remain
-    ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
+    ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
     ///may be invalidated.
     ///\warning This functionality cannot be used together with the Snapshot
@@ -460 +460 @@
     ///\return The newly created node.
     ///
-    ///\note The <tt>Edge</tt>s
-    ///referencing a moved edge remain
-    ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
-    ///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 <tt>EdgeIt</tt>s referencing a moved edge remain
+    ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s 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();
@@ -677 +677 @@
     public:
 
-      /// \brief Default constructur.
+      /// \brief Default constructor.
       ///
       /// Default constructor.
@@ -751 +751 @@
   ///\sa concept::UGraph.
   ///
-  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
-  ///haven't been implemented yet.
-  ///
   class ListUGraph : public ExtendedListUGraphBase {
   private:
@@ -789 +786 @@
       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 <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
+    ///referencing the changed edge remain
+    ///valid. However <tt>OutEdgeIt</tt>s 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 <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
-    /// referencing the changed edge remain
-    /// valid. However <tt>InEdge</tt>'s are invalidated.
+    /// \note The <tt>EdgeIt</tt>s 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
-    ///
-    /// Changes the source of \c e to \c n
-    ///
-    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
+    /// \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 <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
     ///referencing the changed edge remain
-    ///valid. However <tt>OutEdge</tt>'s are invalidated.
-    void changeSource(UEdge e, Node n) { 
-      Parent::changeSource(e,n); 
+    ///valid. However <tt>OutEdgeIt</tt>s 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 <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
+    ///referencing the changed edge remain
+    ///valid. However <tt>InEdgeIt</tt>s 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.
@@ -818 +844 @@
     /// means that loops will be removed.
     ///
-    /// \note The <tt>Edge</tt>s
-    /// referencing a moved edge remain
+    /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
     /// valid.
     void contract(Node a, Node b, bool r = true) {
@@ -842 +867 @@
 
     class NodeSetError : public LogicError {
+    public:
       virtual const char* what() const throw() { 
         return "lemon::ListBpUGraph::NodeSetError";
@@ -1169 +1195 @@
     }
  
-    ///\e
-    
-    ///\bug Undocumented
-    ///\bug Doesn't destruct the maps.
     void clear() {
       aNodes.clear();
@@ -1184 +1206 @@
     }
 
+    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;
+    } 
+
   };
 
@@ -1197 +1257 @@
   /// \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 <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
+    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s 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 <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
+    /// referencing the changed edge remain
+    /// valid. However <tt>InEdgeIt</tt>s 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 <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
+    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s 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 <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
+    /// referencing the changed edge remain
+    /// valid. However <tt>InEdgeIt</tt>s 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 <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
+    ///referencing the changed edge remain
+    ///valid. However <tt>OutEdgeIt</tt>s 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 <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
+    ///referencing the changed edge remain
+    ///valid. However <tt>InEdgeIt</tt>s 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 <tt>EdgeIt</tt>s 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);
+    }
+
+  };