COIN-OR::LEMON - Graph Library

Changeset 792:147eb3a58706 in lemon-0.x


Ignore:
Timestamp:
09/02/04 19:56:40 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1086
Message:

Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/graph_wrapper.h

    r777 r792  
    101101 
    102102    typedef typename Graph::Node Node;
    103 //     class Node : public Graph::Node {
    104 //       friend class GraphWrapper<Graph>;
    105 //     public:
    106 //       Node() { }
    107 //       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
    108 //       // /// \bug construction throughrthr multiple levels should be
    109 //       // /// handled better
    110 //       // Node(const typename ParentGraph::ParentGraph::Node& _n) :
    111 //       // Graph::Node(_n) { }
    112 //       Node(const Invalid& i) : Graph::Node(i) { }
    113 //     };
    114103    class NodeIt : public Node {
    115104      const GraphWrapper<Graph>* gw;
     
    130119    };
    131120    typedef typename Graph::Edge Edge;
    132 //     class Edge : public Graph::Edge {
    133 //       friend class GraphWrapper<Graph>;
    134 //     public:
    135 //       Edge() { }
    136 //       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
    137 //       Edge(const Invalid& i) : Graph::Edge(i) { }
    138 //     };
    139121    class OutEdgeIt : public Edge {
    140122      const GraphWrapper<Graph>* gw;
     
    278260    typedef typename GraphWrapper<Graph>::Node Node;
    279261    typedef typename GraphWrapper<Graph>::Edge Edge;
    280     //If Graph::OutEdgeIt is not defined
    281     //and we do not want to use RevGraphWrapper::InEdgeIt,
    282     //the typdef techinque does not work.
    283     //Unfortunately all the typedefs are instantiated in templates.
    284     //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
    285     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
    286 
     262    //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
     263    //because this does not work is some of them are not defined in the
     264    //original graph. The problem with this is that typedef-ed stuff
     265    //are instantiated in c++.
    287266    class OutEdgeIt : public Edge {
    288267      const RevGraphWrapper<Graph>* gw;
     
    383362
    384363    typedef typename GraphWrapper<Graph>::Node Node;
    385 //     class NodeIt {
    386 //       friend class GraphWrapper<Graph>;
    387 //       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    388 //       typename Graph::NodeIt n;
    389 //      public:
    390 //       NodeIt() { }
    391 //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    392 //       NodeIt(const Invalid& i) : n(i) { }
    393 //       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
    394 //      n(*(_G.graph)) {
    395 //      while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
    396 //        _G.graph->next(n);
    397 //       }
    398 //       operator Node() const { return Node(typename Graph::Node(n)); }
    399 //     };
    400364    class NodeIt : public Node {
    401365      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     
    561525    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    562526
    563     /// This is a linear time operation and works only if
    564     /// NodeIt is defined.
     527    /// \warning This is a linear time operation and works only if
     528    /// \c Graph::NodeIt is defined.
    565529    int nodeNum() const {
    566530      int i=0;
    567       NodeIt n;
    568       for (this->first(n); this->valid(n); this->next(n)) ++i;
     531      for (NodeIt n(*this); n!=INVALID; ++n) ++i;
    569532      return i;
    570533    }
    571534
    572     /// This is a linear time operation and works only if
    573     /// EdgeIt is defined.
     535    /// \warning This is a linear time operation and works only if
     536    /// \c Graph::EdgeIt is defined.
    574537    int edgeNum() const {
    575538      int i=0;
    576       EdgeIt e;
    577       for (this->first(e); this->valid(e); this->next(e)) ++i;
     539      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
    578540      return i;
    579541    }
     
    690652
    691653  ///\brief A wrapper for composing a subgraph of a
    692   /// bidirected graph composed from a directed one.
    693   /// experimental, for fezso's sake.
     654  /// bidirected graph made from a directed one.
    694655  ///
    695   /// A wrapper for composing a subgraps of a
    696   /// bidirected graph composed from a directed one.
    697   /// experimental, for fezso's sake.
    698   /// A bidirected graph is composed over the directed one without physical
    699   /// storage. As the oppositely directed edges are logically different ones
    700   /// the maps are able to attach different values for them.
     656  /// Suppose that for a directed graph $G=(V, A)$,
     657  /// two predicates on the edge-set, $forward_filter$, and $backward_filter$
     658  /// is given, and we are dealing with the directed graph
     659  /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$.
     660  /// The purpose of writing + instead of union is because parallel
     661  /// edges can arose.
     662  /// In other words, a subgraph of the bidirected graph obtained, which
     663  /// is given by orienting the edges of the original graph in both directions.
     664  /// An example for such a construction is the \c RevGraphWrapper where the
     665  /// forward_filter is everywhere false and the backward_filter is
     666  /// everywhere true. We note that for sake of efficiency,
     667  /// \c RevGraphWrapper is implemented in a different way.
     668  /// But BidirGraphWrapper is obtained from
     669  /// SubBidirGraphWrapper by considering everywhere true
     670  /// predicates both forward_filter and backward_filter.
     671  /// Finally, one of the most important applications of SubBidirGraphWrapper
     672  /// is ResGraphWrapper, which stands for the residual graph in directed
     673  /// flow and circulation problems.
     674  /// As wrappers usually, the SubBidirGraphWrapper implements the
     675  /// above mentioned graph structure without its physical storage,
     676  /// that is the whole stuff eats constant memory.
     677  /// As the oppositely directed edges are logical different,
     678  /// the maps are able to attach different values for them.
    701679  template<typename Graph,
    702680           typename ForwardFilterMap, typename BackwardFilterMap>
     
    708686    BackwardFilterMap* backward_filter;
    709687
    710     SubBidirGraphWrapper() : GraphWrapper<Graph>()/*,
    711                                                  capacity(0), flow(0)*/ { }
     688    SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
    712689    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
    713690      forward_filter=&_forward_filter;
     
    734711    friend class OutEdgeIt;
    735712
    736     //template<typename T> class NodeMap;   
    737713    template<typename T> class EdgeMap;
    738714
    739715    typedef typename GraphWrapper<Graph>::Node Node;
    740     //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    741716
    742717    typedef typename Graph::Edge GraphEdge;
     718    /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
     719    /// Graph::Edge. It contains an extra bool flag which shows if the
     720    /// edge is the backward version of the original edge.
    743721    class Edge : public Graph::Edge {
    744722      friend class SubBidirGraphWrapper<Graph,
    745723                                        ForwardFilterMap, BackwardFilterMap>;
    746       ///\bug ez nem is kell
    747       //template<typename T> friend class NodeMap;
    748724      template<typename T> friend class EdgeMap;
    749725    protected:
    750726      bool backward; //true, iff backward
    751 //      typename Graph::Edge e;
    752727    public:
    753728      Edge() { }
    754       ///\bug =false kell-e? zsoltnak kell az addEdge miatt
     729      /// \todo =false is needed, or causes problems?
     730      /// If \c _backward is false, then we get an edge corresponding to the
     731      /// original one, otherwise its oppositely directed pair is obtained.
    755732      Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
    756733        Graph::Edge(e), backward(_backward) { }
     
    959936      i=OutEdgeIt(*this, p); return i;
    960937    }
    961 //    FIXME not tested
    962938    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    963939      i=InEdgeIt(*this, p); return i;
     
    10531029    }
    10541030
    1055 //    int nodeNum() const { return graph->nodeNum(); }
    1056     //FIXME
    1057     void edgeNum() const { }
    1058     //int edgeNum() const { return graph->edgeNum(); }
    1059 
    1060 
    1061 //    int id(Node v) const { return graph->id(v); }
    1062 
    1063 //     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    1064 //     bool valid(Edge e) const {
    1065 //       return this->graph->valid(e);
    1066 //      //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
    1067 //     }
     1031    /// \warning This is a linear time operation and works only if
     1032    /// \c Graph::EdgeIt is defined.
     1033    int edgeNum() const {
     1034      int i=0;
     1035      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
     1036      return i;
     1037    }
    10681038
    10691039    bool forward(const Edge& e) const { return !e.backward; }
    10701040    bool backward(const Edge& e) const { return e.backward; }
    10711041
    1072 //     void augment(const Edge& e, Number a) const {
    1073 //       if (!e.backward) 
    1074 // //   flow->set(e.out, flow->get(e.out)+a);
    1075 //      flow->set(e, (*flow)[e]+a);
    1076 //       else 
    1077 // //   flow->set(e.in, flow->get(e.in)-a);
    1078 //      flow->set(e, (*flow)[e]-a);
    1079 //     }
    1080 
    1081 //     bool enabled(const Edge& e) const {
    1082 //       if (!e.backward)
    1083 // //   return (capacity->get(e.out)-flow->get(e.out));
    1084 //      //return ((*capacity)[e]-(*flow)[e]);
    1085 //      return true;
    1086 //       else
    1087 // //   return (flow->get(e.in));
    1088 //      //return ((*flow)[e]);
    1089 //      return true;
    1090 //     }
    1091 
    1092 //     Number enabled(typename Graph::OutEdgeIt out) const {
    1093 // //      return (capacity->get(out)-flow->get(out));
    1094 //       return ((*capacity)[out]-(*flow)[out]);
    1095 //     }
    1096    
    1097 //     Number enabled(typename Graph::InEdgeIt in) const {
    1098 // //      return (flow->get(in));
    1099 //       return ((*flow)[in]);
    1100 //     }
    11011042
    11021043    template <typename T>
     1044    /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
     1045    /// Graph::EdgeMap one for the forward edges and
     1046    /// one for the backward edges.
    11031047    class EdgeMap {
    11041048      typename Graph::template EdgeMap<T> forward_map, backward_map;
     
    11141058      void set(Edge e, T a) {
    11151059        if (!e.backward)
    1116           forward_map.set(e/*.out*/, a);
     1060          forward_map.set(e, a);
    11171061        else
    1118           backward_map.set(e/*.in*/, a);
     1062          backward_map.set(e, a);
    11191063      }
    11201064      T operator[](Edge e) const {
    11211065        if (!e.backward)
    1122           return forward_map[e/*.out*/];
     1066          return forward_map[e];
    11231067        else
    1124           return backward_map[e/*.in*/];
     1068          return backward_map[e];
    11251069      }
    11261070      void update() {
     
    11381082
    11391083
    1140 
    11411084  ///\brief A wrapper for composing bidirected graph from a directed one.
    1142   /// experimental, for fezso's sake.
    11431085  ///
    11441086  /// A wrapper for composing bidirected graph from a directed one.
    1145   /// experimental, for fezso's sake.
    11461087  /// A bidirected graph is composed over the directed one without physical
    11471088  /// storage. As the oppositely directed edges are logically different ones
     
    11601101  protected:
    11611102    ConstMap<typename Graph::Edge, bool> cm;
    1162     //const CapacityMap* capacity;
    1163     //FlowMap* flow;
    11641103
    11651104    BidirGraphWrapper() : Parent(), cm(true) {
     
    11671106      Parent::setBackwardFilterMap(cm);
    11681107    }
    1169 //     void setCapacityMap(const CapacityMap& _capacity) {
    1170 //       capacity=&_capacity;
    1171 //     }
    1172 //     void setFlowMap(FlowMap& _flow) {
    1173 //       flow=&_flow;
    1174 //     }
    1175 
    1176   public:
    1177 
     1108  public:
    11781109    BidirGraphWrapper(Graph& _graph) : Parent() {
    11791110      Parent::setGraph(_graph);
     
    11891120
    11901121
    1191 
     1122  // this is a direct implementation of the bidirected-graph wrapper.
     1123  // in early hugo, it was implemented that way.
    11921124  template<typename Graph>
    11931125  class OldBidirGraphWrapper : public GraphWrapper<Graph> {
     
    11951127    typedef GraphWrapper<Graph> Parent;
    11961128  protected:
    1197     //const CapacityMap* capacity;
    1198     //FlowMap* flow;
    1199 
    1200     OldBidirGraphWrapper() : GraphWrapper<Graph>()/*,
    1201                                                  capacity(0), flow(0)*/ { }
    1202 //     void setCapacityMap(const CapacityMap& _capacity) {
    1203 //       capacity=&_capacity;
    1204 //     }
    1205 //     void setFlowMap(FlowMap& _flow) {
    1206 //       flow=&_flow;
    1207 //     }
    1208 
    1209   public:
    1210 
    1211     OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
    1212                                      FlowMap& _flow*/) :
    1213       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
     1129    OldBidirGraphWrapper() : GraphWrapper<Graph>() { }
     1130
     1131  public:
     1132
     1133    OldBidirGraphWrapper(Graph& _graph) :
     1134      GraphWrapper<Graph>(_graph) { }
    12141135
    12151136    class Edge;
     
    14601381    bool backward(const Edge& e) const { return e.backward; }
    14611382
    1462 //     void augment(const Edge& e, Number a) const {
    1463 //       if (!e.backward) 
    1464 // //   flow->set(e.out, flow->get(e.out)+a);
    1465 //      flow->set(e, (*flow)[e]+a);
    1466 //       else 
    1467 // //   flow->set(e.in, flow->get(e.in)-a);
    1468 //      flow->set(e, (*flow)[e]-a);
    1469 //     }
    1470 
    14711383    bool enabled(const Edge& e) const {
    14721384      if (!e.backward)
     
    16631575    /// \brief Residual capacity map.
    16641576    ///
    1665     /// In generic residual graphs the residual capacity can be obtained as a map.
     1577    /// In generic residual graphs the residual capacity can be obtained as a map. Not tested.
    16661578    class ResCap {
    16671579    protected:
     
    20081920  /// For blocking flows.
    20091921
    2010   /// This graph wrapper is used for Dinits blocking flow computations.
     1922  /// This graph wrapper is used for on-the-fly
     1923  /// Dinits blocking flow computations.
    20111924  /// For each node, an out-edge is stored which is used when the
    20121925  /// \code
     
    20151928  /// is called.
    20161929  ///
    2017   ///\author Marton Makai
     1930  /// \author Marton Makai
    20181931  template<typename Graph, typename FirstOutEdgesMap>
    20191932  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
     
    20281941
    20291942    typedef typename GraphWrapper<Graph>::Node Node;
    2030 //     class NodeIt {
    2031 //       friend class GraphWrapper<Graph>;
    2032 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    2033 //       typename Graph::NodeIt n;
    2034 //      public:
    2035 //       NodeIt() { }
    2036 //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    2037 //       NodeIt(const Invalid& i) : n(i) { }
    2038 //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
    2039 //      n(*(_G.graph)) { }
    2040 //       operator Node() const { return Node(typename Graph::Node(n)); }
    2041 //     };
    20421943    typedef typename GraphWrapper<Graph>::Edge Edge;
    20431944    class OutEdgeIt : public Edge {
Note: See TracChangeset for help on using the changeset viewer.