COIN-OR::LEMON - Graph Library

Changeset 1021:fd1d073b6557 in lemon-0.x for src/lemon


Ignore:
Timestamp:
11/25/04 15:48:24 (19 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1411
Message:

Advances in UndirGraph?.

Location:
src/lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/concept/graph_component.h

    r989 r1021  
    506506    /// InEdgeIt you should instantiate it with character 'i' and for
    507507    /// OutEdgeIt with 'o'.
    508     /// \todo check the name of the concept GraphIncEdgeIterator
    509     template <typename _Graph, char _selector>
    510     class GraphIncEdgeIterator : public _Graph::Edge {
     508    /// \todo Is this a good name for this concept?
     509    template <typename Graph,
     510              typename Edge = typename Graph::Edge,
     511              char _selector = '0'>
     512    class GraphIncIterator : public Edge {
    511513    public:
    512514      /// Default constructor.
     
    514516      /// @warning The default constructor sets the iterator
    515517      /// to an undefined value.
    516       GraphIncEdgeIterator() {}
     518      GraphIncIterator() {}
    517519      /// Copy constructor.
    518520     
    519521      /// Copy constructor.
    520522      ///
    521       GraphIncEdgeIterator(GraphIncEdgeIterator const&) {}
     523      GraphIncIterator(GraphIncIterator const&) {}
    522524      /// Sets the iterator to the first edge incoming into or outgoing from the node.
    523525     
    524526      /// Sets the iterator to the first edge incoming into or outgoing from the node.
    525527      ///
    526       explicit GraphIncEdgeIterator(const _Graph&, const typename _Graph::Node&) {}
     528      explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
    527529      /// Invalid constructor \& conversion.
    528530
    529531      /// This constructor initializes the item to be invalid.
    530532      /// \sa Invalid for more details.
    531       GraphIncEdgeIterator(Invalid) {}
     533      GraphIncIterator(Invalid) {}
    532534      /// Assign operator for nodes.
    533535
    534536      /// The nodes are assignable.
    535537      ///
    536       GraphIncEdgeIterator& operator=(GraphIncEdgeIterator const&) { return *this; }     
     538      GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }     
    537539      /// Next edge.
    538540
    539541      /// Assign the iterator to the next node.
    540542      ///
    541       GraphIncEdgeIterator& operator++() { return *this; }
     543      GraphIncIterator& operator++() { return *this; }
     544
    542545      //        Node operator*() const { return INVALID; }
     546
    543547      /// Equality operator
    544548
    545549      /// Two iterators are equal if and only if they point to the
    546550      /// same object or both are invalid.
    547       bool operator==(const GraphIncEdgeIterator&) const { return true;}
     551      bool operator==(const GraphIncIterator&) const { return true;}
     552
    548553      /// Inequality operator
    549554       
    550555      /// \sa operator==(Node n)
    551556      ///
    552       bool operator!=(const GraphIncEdgeIterator&) const { return true;}
    553 
    554       template <typename _GraphIncEdgeIterator>
    555       struct Constraints {
    556         typedef typename _Graph::Node Node;
    557         typedef typename _Graph::Edge Edge;
    558         void constraints() {
    559           checkConcept<GraphItem<'e'>, _GraphIncEdgeIterator>();
    560           _GraphIncEdgeIterator it1(graph, node);
     557      bool operator!=(const GraphIncIterator&) const { return true;}
     558
     559      template <typename _GraphIncIterator>
     560      struct Constraints {
     561        typedef typename Graph::Node Node;
     562        void constraints() {
     563          checkConcept<GraphItem<'e'>, _GraphIncIterator>();
     564          _GraphIncIterator it1(graph, node);
    561565          /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
    562           //    _GraphIncEdgeIterator it2(edge);
    563           _GraphIncEdgeIterator it2;
     566          //    _GraphIncIterator it2(edge);
     567          _GraphIncIterator it2;
    564568
    565569          it2 = ++it1;
     
    572576        Edge& edge;
    573577        Node& node;
    574         _Graph& graph;
    575       };
    576     };
     578        Graph& graph;
     579      };
     580    };
     581
     582
    577583    /// An empty iterable base graph class.
    578584 
     
    603609      /// This iterator goes trough the \e inccoming edges of a certain node
    604610      /// of a graph.
    605       typedef GraphIncEdgeIterator<Graph, 'i'> InEdgeIt;
     611      typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
    606612      /// This iterator goes trough the outgoing edges of a node.
    607613
    608614      /// This iterator goes trough the \e outgoing edges of a certain node
    609615      /// of a graph.
    610       typedef GraphIncEdgeIterator<Graph, 'o'> OutEdgeIt;
     616      typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
    611617    };
    612618   
     
    618624        checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
    619625        checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
    620         checkConcept<GraphIncEdgeIterator<_Graph, 'i'>, typename _Graph::InEdgeIt >();
    621         checkConcept<GraphIncEdgeIterator<_Graph, 'o'>, typename _Graph::OutEdgeIt >();
     626        checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
     627        checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
    622628      }
    623629    };
  • src/lemon/concept/undir_graph.h

    r989 r1021  
    6868        typedef typename Graph::UndirEdge UndirEdge;
    6969        typedef typename Graph::UndirEdgeIt UndirEdgeIt;
     70        typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
    7071
    7172        checkConcept< GraphIterator<Graph, UndirEdge>, UndirEdgeIt >();
     73
     74        checkConcept<
     75          GraphIncIterator<Graph, UndirEdge>,
     76          UndirIncEdgeIt >();
    7277      }
    7378    };
  • src/lemon/iterable_graph_extender.h

    r962 r1021  
    132132    typedef IterableGraphExtender<_Base> Parent;
    133133    typedef IterableUndirGraphExtender<_Base> Graph;
     134    typedef typename Parent::Node Node;
    134135
    135136    typedef typename Parent::UndirEdge UndirEdge;
     
    157158    };
    158159
     160    class UndirIncEdgeIt : public UndirEdge {
     161      const Graph* graph;
     162      bool forward;
     163      friend class IterableUndirGraphExtender;
     164      template <typename G>
     165      friend class UndirGraphExtender;
     166    public:
     167
     168      UndirIncEdgeIt() { }
     169
     170      UndirIncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
     171
     172      explicit UndirIncEdgeIt(const Graph& _graph, const Node &n)
     173        : graph(&_graph)
     174      {
     175        _graph._dirFirstOut(*this, n);
     176      }
     177
     178      // FIXME: Do we need this type of constructor here?
     179      // UndirIncEdgeIt(const Graph& _graph, const UndirEdge& e) :
     180      //   UndirEdge(e), graph(&_graph) { }
     181
     182      UndirIncEdgeIt& operator++() {
     183        graph->_dirNextOut(*this);
     184        return *this;
     185      }
     186    };
     187
     188    Node source(const UndirIncEdgeIt &e) const {
     189      return _dirSource(e);
     190    }
     191
     192    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
     193    /// or something???
     194    using Parent::source;
     195
     196    /// Target of the given Edge.
     197    Node target(const UndirIncEdgeIt &e) const {
     198      return _dirTarget(e);
     199    }
     200
     201    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
     202    /// or something???
     203    using Parent::target;
    159204
    160205  };
  • src/lemon/undir_graph_extender.h

    r986 r1021  
    7171    }
    7272
    73     /// Source of the given Edge.
    74     Node source(const Edge &e) const {
     73  protected:
     74
     75    template <typename E>
     76    Node _dirSource(const E &e) const {
    7577      return e.forward ? Parent::source(e) : Parent::target(e);
    7678    }
    7779
     80    template <typename E>
     81    Node _dirTarget(const E &e) const {
     82      return e.forward ? Parent::target(e) : Parent::source(e);
     83    }
     84
     85  public:
    7886    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    7987    /// or something???
    8088    using Parent::source;
    8189
    82     /// Target of the given Edge.
    83     Node target(const Edge &e) const {
    84       return e.forward ? Parent::target(e) : Parent::source(e);
     90    /// Source of the given Edge.
     91    Node source(const Edge &e) const {
     92      return _dirSource(e);
    8593    }
    8694
     
    8896    /// or something???
    8997    using Parent::target;
     98
     99    /// Target of the given Edge.
     100    Node target(const Edge &e) const {
     101      return _dirTarget(e);
     102    }
    90103
    91104    /// Returns whether the given directed edge is same orientation as the
     
    123136    }
    124137
    125     void firstOut(Edge &e, const Node &n) const {
     138   
     139  protected:
     140
     141    template <typename E>
     142    void _dirFirstOut(E &e, const Node &n) const {
    126143      Parent::firstOut(e,n);
    127144      if( UndirEdge(e) != INVALID ) {
     
    133150      }
    134151    }
    135     void firstIn(Edge &e, const Node &n) const {
     152    template <typename E>
     153    void _dirFirstIn(E &e, const Node &n) const {
    136154      Parent::firstIn(e,n);
    137155      if( UndirEdge(e) != INVALID ) {
     
    144162    }
    145163
    146     void nextOut(Edge &e) const {
     164    template <typename E>
     165    void _dirNextOut(E &e) const {
    147166      if( e.forward ) {
    148167        Parent::nextOut(e);
     
    156175      }
    157176    }
    158     void nextIn(Edge &e) const {
     177    template <typename E>
     178    void _dirNextIn(E &e) const {
    159179      if( e.forward ) {
    160180        Parent::nextIn(e);
     
    169189    }
    170190
     191  public:
     192
     193    void firstOut(Edge &e, const Node &n) const {
     194      _dirFirstOut(e, n);
     195    }
     196    void firstIn(Edge &e, const Node &n) const {
     197      _dirFirstIn(e, n);
     198    }
     199
     200    void nextOut(Edge &e) const {
     201      _dirNextOut(e);
     202    }
     203    void nextIn(Edge &e) const {
     204      _dirNextIn(e);
     205    }
     206
    171207    // Miscellaneous stuff:
    172208
     
    174210    /// Extender
    175211
    176     using Parent::id;
     212    // using Parent::id;
     213    // Using "using" is not a good idea, cause it could be that there is
     214    // no "id" in Parent...
     215
     216    int id(const Node &n) const {
     217      return Parent::id(n);
     218    }
     219
     220    int id(const UndirEdge &e) const {
     221      return Parent::id(e);
     222    }
    177223
    178224    int id(const Edge &e) const {
     
    180226    }
    181227
    182     int maxId(Edge = INVALID) const {
     228
     229    int maxId(Node n) const {
     230      return Parent::maxId(Node());
     231    }
     232
     233    int maxId(Edge) const {
    183234      return 2 * Parent::maxId(typename Parent::Edge()) + 1;
    184235    }
    185     int maxId(UndirEdge = INVALID) const {
     236    int maxId(UndirEdge) const {
    186237      return Parent::maxId(typename Parent::Edge());
    187238    }
Note: See TracChangeset for help on using the changeset viewer.