Changeset 1842:8abf74160dc4 in lemon-0.x

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

Files:

• doc/graph_io.dox (modified) (4 diffs)
• lemon/Makefile.am (modified) (1 diff)
• lemon/bits/alteration_notifier.h (modified) (2 diffs)
• lemon/bits/clearable_graph_extender.h (modified) (2 diffs)
• lemon/bits/default_map.h (modified) (2 diffs)
• lemon/bits/erasable_graph_extender.h (modified) (2 diffs)
• lemon/bits/extendable_graph_extender.h (modified) (2 diffs)
• lemon/edge_set.h (added)
• lemon/graph_adaptor.h (modified) (1 diff)

doc/graph_io.dox

@@ -438 +438 @@
 In our example there is a network with symmetric links and there are assymetric
 traffic request on the network. This construction can be stored in an
-undirected graph and in a directed \c NewEdgeSetAdaptor class. The example
+undirected graph and in a directed \c ListEdgeSet class. The example
 shows the input with the \ref lemon::LemonReader "LemonReader" class:
 
@@ -444 +444 @@
 UndirListGraph network;
 UndirListGraph::UndirEdgeMap<double> capacity;
-NewEdgeSetAdaptor<UndirListGraph> traffic(network);
-NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
+ListEdgeSet<UndirListGraph> traffic(network);
+ListEdgeSet<UndirListGraph>::EdgeMap<double> request(network);
 
 LemonReader reader(std::cin);
@@ -452 +452 @@
   undirEdgesetReader(reader, network, nodesetReader);
 undirEdgesetReader.readEdgeMap("capacity", capacity);
-EdgeSetReader<NewEdgeSetAdaptor<UndirListGraph> > 
+EdgeSetReader<ListEdgeSet<UndirListGraph> > 
   edgesetReader(reader, traffic, nodesetReader);
 edgesetReader.readEdgeMap("request", request);
@@ -470 +470 @@
 UndirListGraph network;
 UndirListGraph::UndirEdgeSet<double> capacity;
-NewEdgeSetAdaptor<UndirListGraph> traffic(network);
-NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
-
-UndirGraphReader reader(std::cin, network);
+ListEdgeSet<UndirListGraph> traffic(network);
+ListEdgeSet<UndirListGraph>::EdgeMap<double> request(network);
+
+UndirGraphReader<UndirListGraph> reader(std::cin, network);
 reader.readEdgeMap("capacity", capacity);
-EdgeSetReader edgesetReader(reader, traffic, reader);
+EdgeSetReader<ListEdgeSet<UndirListGraph> > 
+  edgesetReader(reader, traffic, reader);
 edgesetReader.readEdgeMap("request", request);
 

lemon/Makefile.am

@@ -30 +30 @@
         dijkstra.h \
         dimacs.h \
+        edge_set.h \
         error.h \
         fib_heap.h \

lemon/bits/alteration_notifier.h

@@ -399 +399 @@
   };
 
+
+  template <typename _Base> 
+  class AlterableEdgeSetExtender : public _Base {
+  public:
+
+    typedef AlterableEdgeSetExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Edge Edge;
+
+    /// The edge observer registry.
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+
+  protected:
+
+    mutable EdgeNotifier edge_notifier;
+
+  public:
+
+    /// \brief Gives back the edge alteration notifier.
+    ///
+    /// Gives back the edge alteration notifier.
+    EdgeNotifier& getNotifier(Edge) const {
+      return edge_notifier;
+    }
+
+    ~AlterableEdgeSetExtender() {
+      edge_notifier.clear();
+    }
+    
+  };
+
   /// \brief Class to extend an undirected graph with the functionality of
   /// alteration observing.
@@ -438 +470 @@
     }
   };
+
+  template <typename _Base> 
+  class AlterableUndirEdgeSetExtender
+    : public AlterableEdgeSetExtender<_Base> {
+  public:
+
+    typedef AlterableUndirEdgeSetExtender Graph;
+    typedef AlterableEdgeSetExtender<_Base> Parent;
+
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
+
+  protected:
+
+    mutable UndirEdgeNotifier undir_edge_notifier;
+
+  public:
+
+    using Parent::getNotifier;
+    UndirEdgeNotifier& getNotifier(UndirEdge) const {
+      return undir_edge_notifier;
+    }
+
+    ~AlterableUndirEdgeSetExtender() {
+      undir_edge_notifier.clear();
+    }
+  };
+
 
 

lemon/bits/clearable_graph_extender.h

@@ -27 +27 @@
 
   template <typename _Base> 
+  class ClearableEdgeSetExtender : public _Base {
+  public:
+
+    typedef ClearableEdgeSetExtender Graph;
+    typedef _Base Parent;
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    void clear() {
+      Parent::getNotifier(Edge()).clear();
+      Parent::clear();
+    }
+
+  };
+
+  template <typename _Base> 
   class ClearableUndirGraphExtender : public _Base {
   public:
@@ -38 +54 @@
     void clear() {
       Parent::getNotifier(Node()).clear();
+      Parent::getNotifier(UndirEdge()).clear();
+      Parent::getNotifier(Edge()).clear();
+      Parent::clear();
+    }
+  };
+
+  template <typename _Base> 
+  class ClearableUndirEdgeSetExtender : public _Base {
+  public:
+
+    typedef ClearableUndirEdgeSetExtender Graph;
+    typedef _Base Parent;
+    typedef typename Parent::Node Node;
+    typedef typename Parent::UndirEdge UndirEdge;
+    typedef typename Parent::Edge Edge;
+
+    void clear() {
       Parent::getNotifier(UndirEdge()).clear();
       Parent::getNotifier(Edge()).clear();

lemon/bits/default_map.h

@@ -226 +226 @@
   /// \e
   template <typename _Base> 
+  class MappableEdgeSetExtender : public _Base {
+  public:
+
+    typedef MappableEdgeSetExtender<_Base> Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::EdgeIt EdgeIt;
+
+    template <typename _Value>
+    class EdgeMap 
+      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+    public:
+      typedef MappableEdgeSetExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+
+      EdgeMap(const Graph& _g) 
+        : Parent(_g) {}
+      EdgeMap(const Graph& _g, const _Value& _v) 
+        : Parent(_g, _v) {}
+
+      EdgeMap& operator=(const EdgeMap& cmap) {
+        return operator=<EdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
+        const typename Parent::Graph* graph = Parent::getGraph();
+        Edge it;
+        for (graph->first(it); it != INVALID; graph->next(it)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    };
+    
+  };
+
+  /// \e
+  template <typename _Base> 
   class MappableUndirGraphExtender : 
     public MappableGraphExtender<_Base> {
@@ -240 +281 @@
     public:
       typedef MappableUndirGraphExtender Graph;
+      typedef IterableMapExtender<
+        DefaultMap<Graph, UndirEdge, _Value> > Parent;
+
+      UndirEdgeMap(const Graph& _g) 
+        : Parent(_g) {}
+      UndirEdgeMap(const Graph& _g, const _Value& _v) 
+        : Parent(_g, _v) {}
+
+      UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
+        return operator=<UndirEdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      UndirEdgeMap& operator=(const CMap& cmap) {
+        checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
+        const typename Parent::Graph* graph = Parent::getGraph();
+        UndirEdge it;
+        for (graph->first(it); it != INVALID; graph->next(it)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    };
+
+
+  };
+
+  /// \e
+  template <typename _Base> 
+  class MappableUndirEdgeSetExtender : 
+    public MappableEdgeSetExtender<_Base> {
+  public:
+
+    typedef MappableUndirEdgeSetExtender Graph;
+    typedef MappableEdgeSetExtender<_Base> Parent;
+
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    template <typename _Value>
+    class UndirEdgeMap 
+      : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
+    public:
+      typedef MappableUndirEdgeSetExtender Graph;
       typedef IterableMapExtender<
         DefaultMap<Graph, UndirEdge, _Value> > Parent;

lemon/bits/erasable_graph_extender.h

@@ -47 +47 @@
 
   template <typename _Base> 
+  class ErasableEdgeSetExtender : public _Base {
+  public:
+
+    typedef ErasableEdgeSetExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Edge Edge;
+
+    void erase(const Edge& edge) {
+      Parent::getNotifier(Edge()).erase(edge);
+      Parent::erase(edge);
+    }
+
+  };
+
+  template <typename _Base> 
   class ErasableUndirGraphExtender : public _Base {
   public:
@@ -80 +96 @@
   };
 
+  template <typename _Base> 
+  class ErasableUndirEdgeSetExtender : public _Base {
+  public:
+
+    typedef ErasableUndirEdgeSetExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::UndirEdge UndirEdge;
+    typedef typename Parent::Edge Edge;
+
+    void erase(const UndirEdge& uedge) {
+      std::vector<Edge> edges;
+      edges.push_back(Parent::direct(uedge,true));
+      edges.push_back(Parent::direct(uedge,false));
+      Parent::getNotifier(Edge()).erase(edges);
+      Parent::getNotifier(UndirEdge()).erase(uedge);
+      Parent::erase(uedge);
+    }
+
+  };
+
 }
 

lemon/bits/extendable_graph_extender.h

@@ -31 +31 @@
 
   template <typename _Base> 
+  class ExtendableEdgeSetExtender : public _Base {
+  public:
+
+    typedef ExtendableEdgeSetExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::Node Node;
+
+    Edge addEdge(const Node& from, const Node& to) {
+      Edge edge = Parent::addEdge(from, to);
+      Parent::getNotifier(Edge()).add(edge);
+      return edge;
+    }
+
+  };
+
+  template <typename _Base> 
   class ExtendableUndirGraphExtender : public _Base {
   public:
@@ -46 +64 @@
       return node;
     }
+
+    UndirEdge addEdge(const Node& from, const Node& to) {
+      UndirEdge uedge = Parent::addEdge(from, to);
+      Parent::getNotifier(UndirEdge()).add(uedge);
+
+      std::vector<Edge> edges;
+      edges.push_back(Parent::direct(uedge, true));
+      edges.push_back(Parent::direct(uedge, false));
+      Parent::getNotifier(Edge()).add(edges);
+
+      return uedge;
+    }
+
+  };
+
+  template <typename _Base> 
+  class ExtendableUndirEdgeSetExtender : public _Base {
+  public:
+
+    typedef ExtendableUndirEdgeSetExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UndirEdge UndirEdge;
 
     UndirEdge addEdge(const Node& from, const Node& to) {

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;
-    }
-    
-  };
-
   ///@}