COIN-OR::LEMON - Graph Library

Changeset 1158:29961fa390a3 in lemon-0.x


Ignore:
Timestamp:
02/20/05 02:02:07 (15 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1559
Message:

Graph and UndirGraph? concept modifications.

  • For incidence iterators ({In,Out,Inc}EdgeIt?) there is now baseNode and runningNode functions in graph interface
  • For Edge in undir graphs: Edge(UndirGraph? const &, UndirEdge?, Node) constructor. Same for IncEdgeIt?
  • Edge(UndirEdge?, bool) constructor is no more in the public interface. (But we need it in the developpers interface).
Location:
src
Files:
6 edited

Legend:

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

    r1136 r1158  
    626626          Edge e = it1;
    627627          e = it2;
    628         }
    629 
    630         Edge& edge;
    631         Node& node;
    632         Graph& graph;
     628
     629          const_constraits();
     630        }
     631
     632        void const_constraits() {
     633          Node n = graph.baseNode(it);
     634          n = graph.runningNode(it);
     635        }
     636
     637        Edge edge;
     638        Node node;
     639        Graph graph;
     640        _GraphIncIterator it;
    633641      };
    634642    };
  • src/lemon/concept/undir_graph.h

    r1030 r1158  
    3737    /// Skeleton class which describes an edge with direction in \ref
    3838    /// UndirGraph "undirected graph".
    39     template <typename UndirEdge>
    40     class UndirGraphEdge : public UndirEdge {
     39    template <typename UndirGraph>
     40    class UndirGraphEdge : public UndirGraph::UndirEdge {
     41      typedef typename UndirGraph::UndirEdge UndirEdge;
     42      typedef typename UndirGraph::Node Node;
    4143    public:
    4244
     
    5052      UndirGraphEdge(Invalid) {}
    5153
    52       /// \brief Constructs a directed version of an undirected edge
    53       ///
    54       /// \param forward If \c true the direction of the contructed edge
    55       /// is the same as the inherent direction of the \c undir_edge; if
    56       /// \c false --- the opposite.
    57       UndirGraphEdge(UndirEdge undir_edge, bool forward) {
     54      /// \brief Directed edge from undirected edge and a source node.
     55      ///
     56      /// Constructs a directed edge from undirected edge and a source node.
     57      ///
     58      /// \note You have to specify the graph for this constructor.
     59      UndirGraphEdge(const UndirGraph &g,
     60                     UndirEdge undir_edge, Node n) {
    5861        ignore_unused_variable_warning(undir_edge);
    59         ignore_unused_variable_warning(forward);
     62        ignore_unused_variable_warning(g);
     63        ignore_unused_variable_warning(n);
    6064      }
    6165
     
    7478      struct Constraints {
    7579        void constraints() {
     80          const_constraints();
     81        }
     82        void const_constraints() const {
    7683          /// \bug This should be is_base_and_derived ...
    7784          UndirEdge ue = e;
    7885          ue = e;
    79           Edge forward(ue, true);
    80           Edge backward(ue, false);
    81 
    82           ignore_unused_variable_warning(forward);
    83           ignore_unused_variable_warning(backward);
     86
     87          Edge e_with_source(graph,ue,n);
     88          ignore_unused_variable_warning(e_with_source);
    8489        }
    8590        Edge e;
     91        UndirEdge ue;
     92        UndirGraph graph;
     93        Node n;
    8694      };
    8795    };
     
    100108          checkConcept<BaseIterableGraphComponent, Graph>();
    101109          checkConcept<GraphItem<>, UndirEdge>();
    102           checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
     110          checkConcept<UndirGraphEdge<Graph>, Edge>();
    103111
    104112          graph.first(ue);
     
    235243      /// Type describing an UndirEdge with direction
    236244#ifndef DOXYGEN
    237       typedef UndirGraphEdge<UndirEdge> Edge;
     245      typedef UndirGraphEdge<UndirGraph> Edge;
    238246#else
    239247      typedef UndirGraphEdge Edge;
     
    431439
    432440
     441      /// Base node of the iterator
     442      ///
     443      /// Returns the base node (the source in this case) of the iterator
     444      Node baseNode(OutEdgeIt e) const {
     445        return source(e);
     446      }
     447      /// Running node of the iterator
     448      ///
     449      /// Returns the running node (the target in this case) of the
     450      /// iterator
     451      Node runningNode(OutEdgeIt e) const {
     452        return target(e);
     453      }
     454
     455      /// Base node of the iterator
     456      ///
     457      /// Returns the base node (the target in this case) of the iterator
     458      Node baseNode(InEdgeIt e) const {
     459        return target(e);
     460      }
     461      /// Running node of the iterator
     462      ///
     463      /// Returns the running node (the source in this case) of the
     464      /// iterator
     465      Node runningNode(InEdgeIt e) const {
     466        return source(e);
     467      }
     468
     469      /// Base node of the iterator
     470      ///
     471      /// Returns the base node of the iterator
     472      Node baseNode(IncEdgeIt e) const {
     473        return INVALID;
     474      }
     475      /// Running node of the iterator
     476      ///
     477      /// Returns the running node of the iterator
     478      Node runningNode(IncEdgeIt e) const {
     479        return INVALID;
     480      }
     481
     482
    433483      template <typename Graph>
    434484      struct Constraints {
  • src/lemon/iterable_graph_extender.h

    r1030 r1158  
    111111    };
    112112
     113    /// Base node of the iterator
     114    ///
     115    /// Returns the base node (ie. the source in this case) of the iterator
     116    ///
     117    /// \todo Document in the concept!
     118    Node baseNode(const OutEdgeIt &e) const {
     119      return source(e);
     120    }
     121    /// Running node of the iterator
     122    ///
     123    /// Returns the running node (ie. the target in this case) of the
     124    /// iterator
     125    ///
     126    /// \todo Document in the concept!
     127    Node runningNode(const OutEdgeIt &e) const {
     128      return target(e);
     129    }
     130
     131    /// Base node of the iterator
     132    ///
     133    /// Returns the base node (ie. the target in this case) of the iterator
     134    ///
     135    /// \todo Document in the concept!
     136    Node baseNode(const InEdgeIt &e) const {
     137      return target(e);
     138    }
     139    /// Running node of the iterator
     140    ///
     141    /// Returns the running node (ie. the source in this case) of the
     142    /// iterator
     143    ///
     144    /// \todo Document in the concept!
     145    Node runningNode(const InEdgeIt &e) const {
     146      return source(e);
     147    }
     148
    113149    using Parent::first;
    114150
     
    125161
    126162  };
     163
     164
     165
     166
     167
    127168 
    128169  template <typename _Base>
     
    170211      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
    171212
    172       explicit IncEdgeIt(const Graph& _graph, const Node &n)
     213      IncEdgeIt(const Graph& _graph, const Node &n)
    173214        : graph(&_graph)
    174215      {
     
    176217      }
    177218
    178       // FIXME: Do we need this type of constructor here?
    179       // IncEdgeIt(const Graph& _graph, const Edge& e) :
    180       //   UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { }
    181       // or
    182       // IncEdgeIt(const Graph& _graph, const Node& n,
    183       //    Const UndirEdge &e) ... ?
     219      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
     220        : graph(&_graph), UndirEdge(ue)
     221      {
     222        forward = (_graph.source(ue) == n);
     223      }
    184224
    185225      IncEdgeIt& operator++() {
     
    189229    };
    190230
    191     Node source(const IncEdgeIt &e) const {
     231    using Parent::baseNode;
     232    using Parent::runningNode;
     233
     234    /// Base node of the iterator
     235    ///
     236    /// Returns the base node of the iterator
     237    Node baseNode(const IncEdgeIt &e) const {
    192238      return _dirSource(e);
    193239    }
    194 
    195     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    196     /// or something???
    197     using Parent::source;
    198 
    199     /// Target of the given Edge.
    200     Node target(const IncEdgeIt &e) const {
     240    /// Running node of the iterator
     241    ///
     242    /// Returns the running node of the iterator
     243    Node runningNode(const IncEdgeIt &e) const {
    201244      return _dirTarget(e);
    202245    }
    203 
    204     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    205     /// or something???
    206     using Parent::target;
    207246
    208247  };
  • src/lemon/max_matching.h

    r1093 r1158  
    181181          Node u=_mate[v];
    182182          for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
    183             if ( g.target(e) == u ) {
     183            if ( g.runningNode(e) == u ) {
    184184              map.set(u,e);
    185185              map.set(v,e);
     
    228228          Node u=_mate[v];
    229229          for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
    230             if ( g.target(e) == u ) {
     230            if ( g.runningNode(e) == u ) {
    231231              map.set(e,true);
    232232              todo.set(u,false);
     
    333333       
    334334      for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
    335         Node y=g.target(e);
     335        Node y=g.runningNode(e);
    336336
    337337        if ( position[y] == D && blossom.find(x) != blossom.find(y) ) {
     
    389389       
    390390      for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
    391         Node y=g.target(e);
     391        Node y=g.runningNode(e);
    392392             
    393393        switch ( position[y] ) {
     
    454454      if ( _mate[v]==INVALID ) {
    455455        for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
    456           Node y=g.target(e);
     456          Node y=g.runningNode(e);
    457457          if ( _mate[y]==INVALID && y!=v ) {
    458458            _mate.set(v,y);
     
    485485                                        UFE& blossom, UFE& tree, std::queue<Node>& Q) {
    486486    for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
    487       Node y=g.target(e);
     487      Node y=g.runningNode(e);
    488488       
    489489      if ( position[y]==C ) {
  • src/lemon/undir_graph_extender.h

    r1060 r1158  
    4545    public:
    4646      Edge() {}
    47       /// Construct a direct edge from undirect edge and a direction.
     47
     48      /// \brief Directed edge from undirected edge and a direction.
     49      ///
     50      /// This constructor is not a part of the concept interface of
     51      /// undirected graph, so please avoid using it if possible!
    4852      Edge(const UndirEdge &ue, bool _forward) :
    49         UndirEdge(ue), forward(_forward) {}
     53        UndirEdge(ue), forward(_forward) {}
     54
     55      /// \brief Directed edge from undirected edge and a source node.
     56      ///
     57      /// Constructs a directed edge from undirected edge and a source node.
     58      ///
     59      /// \note You have to specify the graph for this constructor.
     60      Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
     61        UndirEdge(ue) { forward = (g.source(ue) == n); }
     62
    5063      /// Invalid edge constructor
    5164      Edge(Invalid i) : UndirEdge(i), forward(true) {}
     
    6477
    6578
    66     /// \brief Returns the Edge of opposite direction.
    67     ///
    68     /// \bug Is this a good name for this? Or "reverse" is better?
     79    /// \brief Edge of opposite direction.
     80    ///
     81    /// Returns the Edge of opposite direction.
    6982    Edge opposite(const Edge &e) const {
    7083      return Edge(e,!e.forward);
     
    118131    }
    119132
     133    /// Directed edge from an undirected edge and a source node.
     134    ///
     135    /// Returns a (directed) Edge corresponding to the specified UndirEdge
     136    /// and source Node.
     137    ///
     138    ///\todo Do we need this?
     139    ///
     140    ///\todo Better name...
     141    Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
     142      return Edge(*this, eu, s);
     143    }
    120144
    121145    using Parent::first;
  • src/test/max_matching_test.cc

    r1101 r1158  
    160160        Q.pop();
    161161        for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
    162           Node u=g.target(e);
     162          Node u=g.runningNode(e);
    163163          if ( pos[u]==max_matching.D && todo[u] ) {
    164164            ++comp_size;
Note: See TracChangeset for help on using the changeset viewer.