Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/list_graph.h

Timestamp:

06/30/06 14:14:36 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821

Message:

Splitted graph files

File:

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

lemon/list_graph.h

@@ -22 +22 @@
 ///\ingroup graphs
 ///\file
-///\brief ListGraph, ListUGraph classes.
-
-#include <lemon/bits/base_extender.h>
+///\brief ListGraph class.
+
 #include <lemon/bits/graph_extender.h>
-
-#include <lemon/error.h>
 
 #include <vector>
@@ -310 +307 @@
   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
 
-  /// \addtogroup graphs
-  /// @{
+  /// \ingroup graphs
 
   ///A list graph class.
@@ -706 +702 @@
   };
 
-  ///@}
-
-  /**************** Undirected List Graph ****************/
-
-  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
-  ExtendedListUGraphBase;
-
-  /// \addtogroup graphs
-  /// @{
-
-  ///An undirected list graph class.
-
-  ///This is a simple and fast erasable undirected graph implementation.
-  ///
-  ///It conforms to the
-  ///\ref concept::UGraph "UGraph" concept.
-  ///
-  ///\sa concept::UGraph.
-  ///
-  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
-  ///haven't been implemented yet.
-  ///
-  class ListUGraph : public ExtendedListUGraphBase {
-  public:
-    typedef ExtendedListUGraphBase Parent;
-    /// \brief Add a new node to the graph.
-    ///
-    /// \return the new node.
-    ///
-    Node addNode() { return Parent::addNode(); }
-
-    /// \brief Add a new edge to the graph.
-    ///
-    /// Add a new edge to the graph with source node \c s
-    /// and target node \c t.
-    /// \return the new undirected edge.
-    UEdge addEdge(const Node& s, const Node& t) { 
-      return Parent::addEdge(s, t); 
-    }
-    /// \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.
-    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
-    ///referencing the changed edge remain
-    ///valid. However <tt>OutEdge</tt>'s are invalidated.
-    void changeSource(UEdge e, Node n) { 
-      Parent::changeSource(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 last parameter \p r controls whether to remove loops. \c true
-    /// means that loops will be removed.
-    ///
-    /// \note The <tt>Edge</tt>s
-    /// referencing a moved edge remain
-    /// valid.
-    void contract(Node a, Node b, bool r = true) {
-      for(IncEdgeIt e(*this, b); e!=INVALID;) {
-        IncEdgeIt f = e; ++f;
-        if (r && runningNode(e) == a) {
-          erase(e);
-        } else if (source(e) == b) {
-          changeSource(e, a);
-        } else {
-          changeTarget(e, a);
-        }
-        e = f;
-      }
-      erase(b);
-    }
-  };
-
-
-  class ListBpUGraphBase {
-  public:
-
-    class NodeSetError : public LogicError {
-      virtual const char* exceptionName() const { 
-        return "lemon::ListBpUGraph::NodeSetError";
-      }
-    };
-
-  protected:
-
-    struct NodeT {
-      int first_edge, prev, next;
-    };
-
-    struct UEdgeT {
-      int aNode, prev_out, next_out;
-      int bNode, prev_in, next_in;
-    };
-
-    std::vector<NodeT> aNodes;
-    std::vector<NodeT> bNodes;
-
-    std::vector<UEdgeT> edges;
-
-    int first_anode;
-    int first_free_anode;
-
-    int first_bnode;
-    int first_free_bnode;
-
-    int first_free_edge;
-
-  public:
-  
-    class Node {
-      friend class ListBpUGraphBase;
-    protected:
-      int id;
-
-      explicit Node(int _id) : id(_id) {}
-    public:
-      Node() {}
-      Node(Invalid) { id = -1; }
-      bool operator==(const Node i) const {return id==i.id;}
-      bool operator!=(const Node i) const {return id!=i.id;}
-      bool operator<(const Node i) const {return id<i.id;}
-    };
-
-    class UEdge {
-      friend class ListBpUGraphBase;
-    protected:
-      int id;
-
-      explicit UEdge(int _id) { id = _id;}
-    public:
-      UEdge() {}
-      UEdge (Invalid) { id = -1; }
-      bool operator==(const UEdge i) const {return id==i.id;}
-      bool operator!=(const UEdge i) const {return id!=i.id;}
-      bool operator<(const UEdge i) const {return id<i.id;}
-    };
-
-    ListBpUGraphBase()
-      : first_anode(-1), first_free_anode(-1),
-        first_bnode(-1), first_free_bnode(-1),
-        first_free_edge(-1) {}
-
-    void firstANode(Node& node) const {
-      node.id = first_anode != -1 ? (first_anode << 1) : -1;
-    }
-    void nextANode(Node& node) const {
-      node.id = aNodes[node.id >> 1].next;
-    }
-
-    void firstBNode(Node& node) const {
-      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
-    }
-    void nextBNode(Node& node) const {
-      node.id = bNodes[node.id >> 1].next;
-    }
-
-    void first(Node& node) const {
-      if (first_anode != -1) {
-        node.id = (first_anode << 1);
-      } else if (first_bnode != -1) {
-        node.id = (first_bnode << 1) + 1;
-      } else {
-        node.id = -1;
-      }
-    }
-    void next(Node& node) const {
-      if (aNode(node)) {
-        node.id = aNodes[node.id >> 1].next;
-        if (node.id == -1) {
-          if (first_bnode != -1) {
-            node.id = (first_bnode << 1) + 1;
-          }
-        }
-      } else {
-        node.id = bNodes[node.id >> 1].next;
-      }
-    }
-  
-    void first(UEdge& edge) const {
-      int aNodeId = first_anode;
-      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
-        aNodeId = aNodes[aNodeId].next != -1 ? 
-          aNodes[aNodeId].next >> 1 : -1;
-      }
-      if (aNodeId != -1) {
-        edge.id = aNodes[aNodeId].first_edge;
-      } else {
-        edge.id = -1;
-      }
-    }
-    void next(UEdge& edge) const {
-      int aNodeId = edges[edge.id].aNode >> 1;
-      edge.id = edges[edge.id].next_out;
-      if (edge.id == -1) {
-        aNodeId = aNodes[aNodeId].next != -1 ? 
-          aNodes[aNodeId].next >> 1 : -1;
-        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
-          aNodeId = aNodes[aNodeId].next != -1 ? 
-          aNodes[aNodeId].next >> 1 : -1;
-        }
-        if (aNodeId != -1) {
-          edge.id = aNodes[aNodeId].first_edge;
-        } else {
-          edge.id = -1;
-        }
-      }
-    }
-
-    void firstFromANode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
-      edge.id = aNodes[node.id >> 1].first_edge;
-    }
-    void nextFromANode(UEdge& edge) const {
-      edge.id = edges[edge.id].next_out;
-    }
-
-    void firstFromBNode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
-      edge.id = bNodes[node.id >> 1].first_edge;
-    }
-    void nextFromBNode(UEdge& edge) const {
-      edge.id = edges[edge.id].next_in;
-    }
-
-    static int id(const Node& node) {
-      return node.id;
-    }
-    static Node nodeFromId(int id) {
-      return Node(id);
-    }
-    int maxNodeId() const {
-      return aNodes.size() > bNodes.size() ?
-        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
-    }
-  
-    static int id(const UEdge& edge) {
-      return edge.id;
-    }
-    static UEdge uEdgeFromId(int id) {
-      return UEdge(id);
-    }
-    int maxUEdgeId() const {
-      return edges.size();
-    }
-  
-    static int aNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromANodeId(int id) {
-      return Node(id << 1);
-    }
-    int maxANodeId() const {
-      return aNodes.size();
-    }
-
-    static int bNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromBNodeId(int id) {
-      return Node((id << 1) + 1);
-    }
-    int maxBNodeId() const {
-      return bNodes.size();
-    }
-
-    Node aNode(const UEdge& edge) const {
-      return Node(edges[edge.id].aNode);
-    }
-    Node bNode(const UEdge& edge) const {
-      return Node(edges[edge.id].bNode);
-    }
-
-    static bool aNode(const Node& node) {
-      return (node.id & 1) == 0;
-    }
-
-    static bool bNode(const Node& node) {
-      return (node.id & 1) == 1;
-    }
-
-    Node addANode() {
-      int aNodeId;
-      if (first_free_anode == -1) {
-        aNodeId = aNodes.size();
-        aNodes.push_back(NodeT());
-      } else {
-        aNodeId = first_free_anode;
-        first_free_anode = aNodes[first_free_anode].next;
-      }
-      if (first_anode != -1) {
-        aNodes[aNodeId].next = first_anode << 1;
-        aNodes[first_anode].prev = aNodeId << 1;
-      } else {
-        aNodes[aNodeId].next = -1;
-      }
-      aNodes[aNodeId].prev = -1;
-      first_anode = aNodeId;
-      aNodes[aNodeId].first_edge = -1;
-      return Node(aNodeId << 1);
-    }
-
-    Node addBNode() {
-      int bNodeId;
-      if (first_free_bnode == -1) {
-        bNodeId = bNodes.size();
-        bNodes.push_back(NodeT());
-      } else {
-        bNodeId = first_free_bnode;
-        first_free_bnode = bNodes[first_free_bnode].next;
-      }
-      if (first_bnode != -1) {
-        bNodes[bNodeId].next = (first_bnode << 1) + 1;
-        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
-      } else {
-        bNodes[bNodeId].next = -1;
-      }
-      first_bnode = bNodeId;
-      bNodes[bNodeId].first_edge = -1;
-      return Node((bNodeId << 1) + 1);
-    }
-
-    UEdge addEdge(const Node& source, const Node& target) {
-      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
-      int edgeId;
-      if (first_free_edge != -1) {
-        edgeId = first_free_edge;
-        first_free_edge = edges[edgeId].next_out;
-      } else {
-        edgeId = edges.size();
-        edges.push_back(UEdgeT());
-      }
-      if ((source.id & 1) == 0) {
-        edges[edgeId].aNode = source.id;
-        edges[edgeId].bNode = target.id;
-      } else {
-        edges[edgeId].aNode = target.id;
-        edges[edgeId].bNode = source.id;
-      }
-      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
-      edges[edgeId].prev_out = -1;
-      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
-        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
-      }
-      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
-      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
-      edges[edgeId].prev_in = -1;
-      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
-        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
-      }
-      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
-      return UEdge(edgeId);
-    }
-
-    void erase(const Node& node) {
-      if (aNode(node)) {
-        int aNodeId = node.id >> 1;
-        if (aNodes[aNodeId].prev != -1) {
-          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
-        } else {
-          first_anode = aNodes[aNodeId].next >> 1;
-        }
-        if (aNodes[aNodeId].next != -1) {
-          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
-        }
-        aNodes[aNodeId].next = first_free_anode;
-        first_free_anode = aNodeId;
-      } else {
-        int bNodeId = node.id >> 1;
-        if (bNodes[bNodeId].prev != -1) {
-          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
-        } else {
-          first_bnode = bNodes[bNodeId].next >> 1;
-        }
-        if (bNodes[bNodeId].next != -1) {
-          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
-        }
-        bNodes[bNodeId].next = first_free_bnode;
-        first_free_bnode = bNodeId;
-      }
-    }
-
-    void erase(const UEdge& edge) {
-
-      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 (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;
-      }
-
-      edges[edge.id].next_out = first_free_edge;
-      first_free_edge = edge.id;
-    }
-
-    void clear() {
-      aNodes.clear();
-      bNodes.clear();
-      edges.clear();
-      first_anode = -1;
-      first_free_anode = -1;
-      first_bnode = -1;
-      first_free_bnode = -1;
-      first_free_edge = -1;
-    }
-
-  };
-
-
-  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
-
-  /// \ingroup graphs
-  ///
-  /// \brief A smart bipartite undirected graph class.
-  ///
-  /// This is a bipartite undirected graph implementation.
-  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 
-  /// concept.
-  /// \sa concept::BpUGraph.
-  ///
-  class ListBpUGraph : public ExtendedListBpUGraphBase {};
-
-  
-  /// @}  
 } //namespace lemon