COIN-OR::LEMON - Graph Library

Changeset 1962:c1c3a0fae8a1 in lemon-0.x


Ignore:
Timestamp:
02/06/06 17:58:39 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2538
Message:

Bug fixes in ListEdgeSet?
Added SmartEdgeSet?

Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/edge_set.h

    r1956 r1962  
    2020#define LEMON_EDGE_SET_H
    2121
     22#include <lemon/bits/erasable_graph_extender.h>
     23#include <lemon/bits/clearable_graph_extender.h>
     24#include <lemon/bits/extendable_graph_extender.h>
     25#include <lemon/bits/iterable_graph_extender.h>
     26#include <lemon/bits/alteration_notifier.h>
     27#include <lemon/bits/default_map.h>
     28#include <lemon/bits/graph_extender.h>
     29
    2230/// \ingroup graphs
    2331/// \file
     
    93101      }
    94102      edges[n].next_in = (*nodes)[target].first_in;
     103      if ((*nodes)[target].first_in != -1) {
     104        edges[(*nodes)[target].first_in].prev_in = n;
     105      }
    95106      (*nodes)[target].first_in = n;
    96107      edges[n].next_out = (*nodes)[source].first_out;
     108      if ((*nodes)[source].first_out != -1) {
     109        edges[(*nodes)[source].first_out].prev_out = n;
     110      }
    97111      (*nodes)[source].first_out = n;
    98112      edges[n].source = source;
     
    124138
    125139    void clear() {
     140      Node node;
     141      for (first(node); node != INVALID; next(node)) {
     142        (*nodes)[node].first_in = -1;
     143        (*nodes)[node].first_out = -1;
     144      }
    126145      edges.clear();
    127146      first_edge = -1;
     
    174193    int id(const Edge& edge) const { return edge.id; }
    175194
    176     Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
     195    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
    177196    Edge edgeFromId(int id) const { return Edge(id); }
    178197
    179     int maxNodeId() const { return graph->maxId(Node()); };
     198    int maxNodeId() const { return graph->maxNodeId(); };
    180199    int maxEdgeId() const { return edges.size() - 1; }
    181200
     
    209228  ///
    210229  /// In the edge extension and removing it conforms to the
    211   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
     230  /// \ref concept::ErasableGraph "ErasableGraph" concept.
    212231  template <typename _Graph>
    213232  class ListEdgeSet :
     
    265284      NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
    266285        : Parent(graph), _edgeset(edgeset) {}
     286
     287      virtual ~NodesImpl() {}
    267288     
    268289    protected:
     
    271292        _edgeset.eraseNode(node);
    272293        Parent::erase(node);
     294      }
     295      virtual void erase(const std::vector<Node>& nodes) {
     296        for (int i = 0; i < (int)nodes.size(); ++i) {
     297          _edgeset.eraseNode(nodes[i]);
     298        }
     299        Parent::erase(nodes);
    273300      }
    274301      virtual void clear() {
     
    308335  ///
    309336  /// In the edge extension and removing it conforms to the
    310   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
     337  /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
    311338  template <typename _Graph>
    312339  class ListUEdgeSet :
     
    359386      NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
    360387        : Parent(graph), _edgeset(edgeset) {}
     388
     389      virtual ~NodesImpl() {}
    361390     
    362391    protected:
     
    367396      }
    368397      virtual void erase(const std::vector<Node>& nodes) {
    369         for (int i = 0; i < nodes.size(); ++i) {
     398        for (int i = 0; i < (int)nodes.size(); ++i) {
    370399          _edgeset.eraseNode(nodes[i]);
    371400        }
     
    394423  };
    395424
     425  template <typename _Graph>
     426  class SmartEdgeSetBase {
     427  public:
     428
     429    typedef _Graph Graph;
     430    typedef typename Graph::Node Node;
     431    typedef typename Graph::NodeIt NodeIt;
     432
     433  protected:
     434
     435    struct NodeT {
     436      int first_out, first_in;
     437      NodeT() : first_out(-1), first_in(-1) {}
     438    };
     439
     440    typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
     441
     442    NodesImplBase* nodes;
     443
     444    struct EdgeT {
     445      Node source, target;
     446      int next_out, next_in;
     447      EdgeT() {}
     448    };
     449
     450    std::vector<EdgeT> edges;
     451
     452    const Graph* graph;
     453
     454    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
     455      graph = &_graph;
     456      nodes = &_nodes;
     457    }
     458   
     459  public:
     460
     461    class Edge {
     462      friend class SmartEdgeSetBase<Graph>;
     463    protected:
     464      Edge(int _id) : id(_id) {}
     465      int id;
     466    public:
     467      Edge() {}
     468      Edge(Invalid) : id(-1) {}
     469      bool operator==(const Edge& edge) const { return id == edge.id; }
     470      bool operator!=(const Edge& edge) const { return id != edge.id; }
     471      bool operator<(const Edge& edge) const { return id < edge.id; }
     472    };
     473
     474    SmartEdgeSetBase() {}
     475
     476    Edge addEdge(const Node& source, const Node& target) {
     477      int n = edges.size();
     478      edges.push_back(EdgeT());
     479      edges[n].next_in = (*nodes)[target].first_in;
     480      (*nodes)[target].first_in = n;
     481      edges[n].next_out = (*nodes)[source].first_out;
     482      (*nodes)[source].first_out = n;
     483      edges[n].source = source;
     484      edges[n].target = target;
     485      return Edge(n);
     486    }
     487
     488    void clear() {
     489      Node node;
     490      for (first(node); node != INVALID; next(node)) {
     491        (*nodes)[node].first_in = -1;
     492        (*nodes)[node].first_out = -1;
     493      }
     494      edges.clear();
     495    }
     496
     497    void first(Node& node) const {
     498      graph->first(node);
     499    }
     500
     501    void next(Node& node) const {
     502      graph->next(node);
     503    }
     504
     505    void first(Edge& edge) const {
     506      edge.id = edges.size() - 1;
     507    }
     508
     509    void next(Edge& edge) const {
     510      --edge.id;
     511    }
     512
     513    void firstOut(Edge& edge, const Node& node) const {
     514      edge.id = (*nodes)[node].first_out;   
     515    }
     516   
     517    void nextOut(Edge& edge) const {
     518      edge.id = edges[edge.id].next_out;       
     519    }
     520
     521    void firstIn(Edge& edge, const Node& node) const {
     522      edge.id = (*nodes)[node].first_in;         
     523    }
     524
     525    void nextIn(Edge& edge) const {
     526      edge.id = edges[edge.id].next_in;   
     527    }
     528
     529    int id(const Node& node) const { return graph->id(node); }
     530    int id(const Edge& edge) const { return edge.id; }
     531
     532    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
     533    Edge edgeFromId(int id) const { return Edge(id); }
     534
     535    int maxNodeId() const { return graph->maxNodeId(); };
     536    int maxEdgeId() const { return edges.size() - 1; }
     537
     538    Node source(const Edge& edge) const { return edges[edge.id].source;}
     539    Node target(const Edge& edge) const { return edges[edge.id].target;}
     540
     541    template <typename _Value>
     542    class NodeMap : public Graph::template NodeMap<_Value> {
     543    public:
     544      typedef typename _Graph::template NodeMap<_Value> Parent;
     545      explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
     546        : Parent(*edgeset.graph) { }
     547      NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
     548        : Parent(*edgeset.graph, value) { }
     549    };
     550
     551  };
     552
     553
     554  /// \ingroup semi_adaptors
     555  ///
     556  /// \brief Graph using a node set of another graph and an
     557  /// own edge set.
     558  ///
     559  /// This structure can be used to establish another graph over a node set
     560  /// of an existing one. The node iterator will go through the nodes of the
     561  /// original graph.
     562  ///
     563  /// \param _Graph The type of the graph which shares its node set with
     564  /// this class. Its interface must conform to the \ref concept::StaticGraph
     565  /// "StaticGraph" concept.
     566  ///
     567  /// In the edge extension and removing it conforms to the
     568  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
     569  template <typename _Graph>
     570  class SmartEdgeSet :
     571    public ClearableEdgeSetExtender<
     572    ExtendableEdgeSetExtender<
     573    MappableEdgeSetExtender<
     574    IterableGraphExtender<
     575    AlterableEdgeSetExtender<
     576    GraphExtender<
     577    SmartEdgeSetBase<_Graph> > > > > > > {
     578
     579  public:
     580
     581    typedef ClearableEdgeSetExtender<
     582      ExtendableEdgeSetExtender<
     583      MappableEdgeSetExtender<
     584      IterableGraphExtender<
     585      AlterableEdgeSetExtender<
     586      GraphExtender<
     587      SmartEdgeSetBase<_Graph> > > > > > > Parent;
     588   
     589    typedef typename Parent::Node Node;
     590    typedef typename Parent::Edge Edge;
     591   
     592    typedef _Graph Graph;
     593
     594    class UnsupportedOperation : public LogicError {
     595    public:
     596      virtual const char* exceptionName() const {
     597        return "lemon::SmartEdgeSet::UnsupportedOperation";
     598      }
     599    };
     600   
     601
     602
     603  protected:
     604
     605    typedef typename Parent::NodesImplBase NodesImplBase;
     606
     607    void eraseNode(const Node&) {
     608      throw UnsupportedOperation();
     609    }
     610   
     611    void clearNodes() {
     612      Parent::clear();
     613    }
     614
     615    class NodesImpl : public NodesImplBase {
     616    public:
     617      typedef NodesImplBase Parent;
     618     
     619      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
     620        : Parent(graph), _edgeset(edgeset) {}
     621
     622      virtual ~NodesImpl() {}
     623     
     624    protected:
     625
     626      virtual void erase(const Node& node) {
     627        _edgeset.eraseNode(node);
     628        Parent::erase(node);
     629      }
     630      virtual void erase(const std::vector<Node>& nodes) {
     631        for (int i = 0; i < (int)nodes.size(); ++i) {
     632          _edgeset.eraseNode(nodes[i]);
     633        }
     634        Parent::erase(nodes);
     635      }
     636      virtual void clear() {
     637        _edgeset.clearNodes();
     638        Parent::clear();
     639      }
     640
     641    private:
     642      SmartEdgeSet& _edgeset;
     643    };
     644
     645    NodesImpl nodes;
     646   
     647  public:
     648
     649    /// \brief Constructor of the adaptor.
     650    ///
     651    /// Constructor of the adaptor.
     652    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
     653      Parent::initalize(graph, nodes);
     654    }
     655   
     656  };
     657
     658  /// \ingroup semi_adaptors
     659  ///
     660  /// \brief Graph using a node set of another graph and an
     661  /// own uedge set.
     662  ///
     663  /// This structure can be used to establish another graph over a node set
     664  /// of an existing one. The node iterator will go through the nodes of the
     665  /// original graph.
     666  ///
     667  /// \param _Graph The type of the graph which shares its node set with
     668  /// this class. Its interface must conform to the \ref concept::StaticGraph
     669  /// "StaticGraph" concept.
     670  ///
     671  /// In the edge extension and removing it conforms to the
     672  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
     673  template <typename _Graph>
     674  class SmartUEdgeSet :
     675    public ClearableUEdgeSetExtender<
     676    ExtendableUEdgeSetExtender<
     677    MappableUEdgeSetExtender<
     678    IterableUGraphExtender<
     679    AlterableUEdgeSetExtender<
     680    UGraphExtender<
     681    SmartEdgeSetBase<_Graph> > > > > > > {
     682
     683  public:
     684
     685    typedef ClearableUEdgeSetExtender<
     686      ExtendableUEdgeSetExtender<
     687      MappableUEdgeSetExtender<
     688      IterableUGraphExtender<
     689      AlterableUEdgeSetExtender<
     690      UGraphExtender<
     691      SmartEdgeSetBase<_Graph> > > > > > > Parent;
     692   
     693    typedef typename Parent::Node Node;
     694    typedef typename Parent::Edge Edge;
     695   
     696    typedef _Graph Graph;
     697
     698    class UnsupportedOperation : public LogicError {
     699    public:
     700      virtual const char* exceptionName() const {
     701        return "lemon::SmartUEdgeSet::UnsupportedOperation";
     702      }
     703    };
     704
     705  protected:
     706
     707    typedef typename Parent::NodesImplBase NodesImplBase;
     708
     709    void eraseNode(const Node&) {
     710      throw UnsupportedOperation();
     711    }
     712   
     713    void clearNodes() {
     714      Parent::clear();
     715    }
     716
     717    class NodesImpl : public NodesImplBase {
     718    public:
     719      typedef NodesImplBase Parent;
     720     
     721      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
     722        : Parent(graph), _edgeset(edgeset) {}
     723
     724      virtual ~NodesImpl() {}
     725     
     726    protected:
     727
     728      virtual void erase(const Node& node) {
     729        _edgeset.eraseNode(node);
     730        Parent::erase(node);
     731      }
     732      virtual void erase(const std::vector<Node>& nodes) {
     733        for (int i = 0; i < (int)nodes.size(); ++i) {
     734          _edgeset.eraseNode(nodes[i]);
     735        }
     736        Parent::erase(nodes);
     737      }
     738      virtual void clear() {
     739        _edgeset.clearNodes();
     740        Parent::clear();
     741      }
     742
     743    private:
     744      SmartUEdgeSet& _edgeset;
     745    };
     746
     747    NodesImpl nodes;
     748   
     749  public:
     750
     751    /// \brief Constructor of the adaptor.
     752    ///
     753    /// Constructor of the adaptor.
     754    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
     755      Parent::initalize(graph, nodes);
     756    }
     757   
     758  };
     759
    396760}
    397761
  • test/Makefile.am

    r1921 r1962  
    1818        dfs_test \
    1919        dijkstra_test \
     20        edge_set_test \
    2021        graph_test \
    2122        graph_adaptor_test \
     
    5556dfs_test_SOURCES = dfs_test.cc
    5657dijkstra_test_SOURCES = dijkstra_test.cc
     58edge_set_test_SOURCES = edge_set_test.cc
    5759graph_test_SOURCES = graph_test.cc
    5860graph_utils_test_SOURCES = graph_utils_test.cc
Note: See TracChangeset for help on using the changeset viewer.