Changeset 1842:8abf74160dc4 in lemon-0.x for lemon/graph_adaptor.h

Timestamp:

12/01/05 16:08:46 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

NewEdgeSetAdaptor? -> ListEdgeSet?
and moved to edge_set.h

File:

• lemon/graph_adaptor.h (modified) (1 diff)

lemon/graph_adaptor.h

@@ -1674 +1674 @@
   };
 
-  template <typename _Graph>
-  class NewEdgeSetAdaptorBase {
-  public:
-
-    typedef _Graph Graph;
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
-
-  protected:
-
-    struct NodeT {
-      int first_out, first_in;
-      NodeT() : first_out(-1), first_in(-1) {}
-    };
-    
-    class NodesImpl : protected Graph::template NodeMap<NodeT> {
-
-      typedef typename Graph::template NodeMap<NodeT> Parent;
-      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
-
-      Adaptor& adaptor;
-
-    public:
-
-      NodesImpl(Adaptor& _adaptor, const Graph& _graph) 
-        : Parent(_graph), adaptor(_adaptor) {}
-
-      virtual ~NodesImpl() {}
-
-      virtual void build() {
-        Parent::build();
-      }
-
-      virtual void clear() {
-        adaptor._clear();
-        Parent::clear();
-      }
-      
-      virtual void add(const Node& node) {
-        Parent::add(node);
-        adaptor._add(node);
-      }
-      
-      virtual void erase(const Node& node) {
-        adaptor._erase(node);
-        Parent::erase(node);
-      }
-
-      NodeT& operator[](const Node& node) {
-        return Parent::operator[](node);
-      }
-
-      const NodeT& operator[](const Node& node) const {
-        return Parent::operator[](node);
-      }
-      
-    };
-
-    NodesImpl* nodes;
-
-    struct EdgeT {
-      Node source, target;
-      int next_out, next_in;
-      int prev_out, prev_in;
-      EdgeT() : prev_out(-1), prev_in(-1) {}
-    };
-
-    std::vector<EdgeT> edges;
-
-    int first_edge;
-    int first_free_edge;
-
-    virtual void _clear() = 0;
-    virtual void _add(const Node& node) = 0;
-    virtual void _erase(const Node& node) = 0;
-    
-    const Graph* graph;
-
-    void initalize(const Graph& _graph, NodesImpl& _nodes) {
-      graph = &_graph;
-      nodes = &_nodes;
-    }
-    
-  public:
-
-    class Edge {
-      friend class NewEdgeSetAdaptorBase<Graph>;
-    protected:
-      Edge(int _id) : id(_id) {}
-      int id;
-    public:
-      Edge() {}
-      Edge(Invalid) : id(-1) {}
-      bool operator==(const Edge& edge) const { return id == edge.id; }
-      bool operator!=(const Edge& edge) const { return id != edge.id; }
-      bool operator<(const Edge& edge) const { return id < edge.id; }
-    };
-
-    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 
-    virtual ~NewEdgeSetAdaptorBase() {}
-
-    Edge addEdge(const Node& source, const Node& target) {
-      int n;
-      if (first_free_edge == -1) {
-        n = edges.size();
-        edges.push_back(EdgeT());
-      } else {
-        n = first_free_edge;
-        first_free_edge = edges[first_free_edge].next_in;
-      }
-      edges[n].next_in = (*nodes)[target].first_in;
-      (*nodes)[target].first_in = n;
-      edges[n].next_out = (*nodes)[source].first_out;
-      (*nodes)[source].first_out = n;
-      edges[n].source = source;
-      edges[n].target = target;
-      return Edge(n);
-    }
-
-    void erase(const Edge& edge) {
-      int n = edge.id;
-      if (edges[n].prev_in != -1) {
-        edges[edges[n].prev_in].next_in = edges[n].next_in;
-      } else {
-        (*nodes)[edges[n].target].first_in = edges[n].next_in;
-      }
-      if (edges[n].next_in != -1) {
-        edges[edges[n].next_in].prev_in = edges[n].prev_in;
-      }
-
-      if (edges[n].prev_out != -1) {
-        edges[edges[n].prev_out].next_out = edges[n].next_out;
-      } else {
-        (*nodes)[edges[n].source].first_out = edges[n].next_out;
-      }
-      if (edges[n].next_out != -1) {
-        edges[edges[n].next_out].prev_out = edges[n].prev_out;
-      }
-           
-    }
-
-    void first(Node& node) const {
-      graph->first(node);
-    }
-
-    void next(Node& node) const {
-      graph->next(node);
-    }
-
-    void first(Edge& edge) const {
-      Node node;
-      for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
-           next(node));
-      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
-    }
-
-    void next(Edge& edge) const {
-      if (edges[edge.id].next_in != -1) {
-        edge.id = edges[edge.id].next_in;
-      } else {
-        Node node = edges[edge.id].target;
-        for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
-             next(node));
-        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
-      }      
-    }
-
-    void firstOut(Edge& edge, const Node& node) const {
-      edge.id = (*nodes)[node].first_out;    
-    }
-    
-    void nextOut(Edge& edge) const {
-      edge.id = edges[edge.id].next_out;        
-    }
-
-    void firstIn(Edge& edge, const Node& node) const {
-      edge.id = (*nodes)[node].first_in;          
-    }
-
-    void nextIn(Edge& edge) const {
-      edge.id = edges[edge.id].next_in;    
-    }
-
-    int id(const Node& node) const { return graph->id(node); }
-    int id(const Edge& edge) const { return edge.id; }
-
-    Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
-    Edge edgeFromId(int id) const { return Edge(id); }
-
-    int maxNodeId() const { return graph->maxId(Node()); };
-    int maxEdgeId() const { return edges.size() - 1; }
-
-    Node source(const Edge& edge) const { return edges[edge.id].source;}
-    Node target(const Edge& edge) const { return edges[edge.id].target;}
-
-  };
-
-
-  /// \brief Graph adaptor using a node set of another graph and an
-  /// own edge set.
-  ///
-  /// This structure can be used to establish another graph over a node set
-  /// of an existing one. The node iterator will go through the nodes of the
-  /// original graph.
-  ///
-  /// \param _Graph The type of the graph which shares its node set with 
-  /// this class. Its interface must conform to the \ref concept::StaticGraph
-  /// "StaticGraph" concept.
-  ///
-  /// In the edge extension and removing it conforms to the 
-  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
-  template <typename _Graph>
-  class NewEdgeSetAdaptor :
-    public ErasableGraphExtender<
-    ClearableGraphExtender<
-    ExtendableGraphExtender<
-    MappableGraphExtender<
-    IterableGraphExtender<
-    AlterableGraphExtender<
-    GraphExtender<
-    NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
-
-  public:
-
-    typedef ErasableGraphExtender<
-      ClearableGraphExtender<
-      ExtendableGraphExtender<
-      MappableGraphExtender<
-      IterableGraphExtender<
-      AlterableGraphExtender<
-      GraphExtender<
-      NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
-    
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-  private:
-
-    virtual void _clear() {
-      Parent::edges.clear();
-      Parent::first_edge = -1;
-      Parent::first_free_edge = -1;
-      Parent::getNotifier(Edge()).clear();
-      Parent::getNotifier(Node()).clear();
-    }
-
-    virtual void _add(const Node& node) {
-      Parent::getNotifier(Node()).add(node);
-    }
-
-    virtual void _erase(const Node& node) {
-      Edge edge;
-      Parent::firstOut(edge, node);
-      while (edge != INVALID) {
-        Parent::erase(edge);
-        Parent::firstOut(edge, node);
-      }
-
-      Parent::firstIn(edge, node);
-      while (edge != INVALID) {
-        Parent::erase(edge);
-        Parent::firstIn(edge, node);
-      }
-      
-      Parent::getNotifier(Node()).erase(node);
-    }
-
-
-    typedef typename Parent::NodesImpl NodesImpl;
-
-    NodesImpl nodes;
-    
-  public:
-
-    /// \brief Constructor of the adaptor.
-    /// 
-    /// Constructor of the adaptor.
-    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
-      Parent::initalize(_graph, nodes);
-    }
-
-    void clear() {
-      Parent::getNotifier(Edge()).clear();      
-
-      Parent::edges.clear();
-      Parent::first_edge = -1;
-      Parent::first_free_edge = -1;
-    }
-    
-  };
-
-  /// \brief Graph adaptor using a node set of another graph and an
-  /// own undir edge set.
-  ///
-  /// This structure can be used to establish another undirected graph over 
-  /// a node set of an existing one. The node iterator will go through the 
-  /// nodes of the original graph.
-  ///
-  /// \param _Graph The type of the graph which shares its node set with 
-  /// this class. Its interface must conform to the \ref concept::StaticGraph
-  /// "StaticGraph" concept.
-  ///
-  /// In the edge extension and removing it conforms to the 
-  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
-  template <typename _Graph>
-  class NewUndirEdgeSetAdaptor :
-    public ErasableUndirGraphExtender<
-    ClearableUndirGraphExtender<
-    ExtendableUndirGraphExtender<
-    MappableUndirGraphExtender<
-    IterableUndirGraphExtender<
-    AlterableUndirGraphExtender<
-    UndirGraphExtender<
-    NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
-
-  public:
-
-    typedef ErasableUndirGraphExtender<
-      ClearableUndirGraphExtender<
-      ExtendableUndirGraphExtender<
-      MappableUndirGraphExtender<
-      IterableUndirGraphExtender<
-      AlterableUndirGraphExtender<
-      UndirGraphExtender<
-      NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
-    
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UndirEdge UndirEdge;
-
-  private:
-
-    virtual void _clear() {
-      Parent::edges.clear();
-      Parent::first_edge = -1;
-      Parent::first_free_edge = -1;
-      Parent::getNotifier(Edge()).clear();
-      Parent::getNotifier(Node()).clear();
-    }
-
-    virtual void _add(const Node& node) {
-      Parent::getNotifier(Node()).add(node);
-    }
-
-    virtual void _erase(const Node& node) {
-      Edge edge;
-      Parent::firstOut(edge, node);
-      while (edge != INVALID) {
-        Parent::erase(edge);
-        Parent::firstOut(edge, node);
-      }
-
-      Parent::firstIn(edge, node);
-      while (edge != INVALID) {
-        Parent::erase(edge);
-        Parent::firstIn(edge, node);
-      }
-      
-      Parent::getNotifier(Node()).erase(node);
-    }
-
-    typedef typename Parent::NodesImpl NodesImpl;
-
-    NodesImpl nodes;
-    
-  public:
-
-
-    /// \brief Constructor of the adaptor.
-    /// 
-    /// Constructor of the adaptor.
-    NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
-      Parent::initalize(_graph, nodes);
-    }
-
-    void clear() {
-      Parent::getNotifier(Edge()).clear();      
-      Parent::getNotifier(UndirEdge()).clear();      
-
-      Parent::edges.clear();
-      Parent::first_edge = -1;
-      Parent::first_free_edge = -1;
-    }
-    
-  };
-
   ///@}