COIN-OR::LEMON - Graph Library

Changeset 777:a82713ed19f3 in lemon-0.x


Ignore:
Timestamp:
08/31/04 19:54:22 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1070
Message:

graph_wrapper.h is ready for hugo 0.2

Location:
src
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/graph_wrapper.h

    r775 r777  
    182182        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
    183183      EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
    184         Edge(w), gw(&_gw) { }
     184        Edge(e), gw(&_gw) { }
    185185      EdgeIt& operator++() {
    186186        *(static_cast<Edge*>(this))=
     
    429429      OutEdgeIt(Invalid i) : Edge(i) { }
    430430      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
    431         Edge(typename Graph::OutEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
     431        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
    432432      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    433433             const Edge& e) :
     
    451451      InEdgeIt(Invalid i) : Edge(i) { }
    452452      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
    453         Edge(typename Graph::InEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
     453        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
    454454      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    455455             const Edge& e) :
     
    20412041//     };
    20422042    typedef typename GraphWrapper<Graph>::Edge Edge;
    2043     class OutEdgeIt {
     2043    class OutEdgeIt : public Edge {
    20442044      friend class GraphWrapper<Graph>;
    20452045      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    2046 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
    2047       typename Graph::OutEdgeIt e;
     2046      const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
    20482047    public:
    20492048      OutEdgeIt() { }
    2050       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    2051       OutEdgeIt(const Invalid& i) : e(i) { }
    2052       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
    2053                 const Node& _n) :
    2054         e((*_G.first_out_edges)[_n]) { }
    2055       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    2056     };
    2057     class InEdgeIt {
    2058       friend class GraphWrapper<Graph>;
    2059       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    2060 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
    2061       typename Graph::InEdgeIt e;
    2062     public:
    2063       InEdgeIt() { }
    2064       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    2065       InEdgeIt(const Invalid& i) : e(i) { }
    2066       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
    2067                const Node& _n) :
    2068         e(*(_G.graph), typename Graph::Node(_n)) { }
    2069       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    2070     };
     2049      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
     2050      OutEdgeIt(Invalid i) : Edge(i) { }
     2051      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
     2052                const Node& n) :
     2053        Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
     2054      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
     2055                const Edge& e) :
     2056        Edge(e), gw(&_gw) { }
     2057      OutEdgeIt& operator++() {
     2058        *(static_cast<Edge*>(this))=
     2059          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     2060        return *this;
     2061      }
     2062    };
     2063//     class InEdgeIt {
     2064//       friend class GraphWrapper<Graph>;
     2065//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
     2066// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
     2067//       typename Graph::InEdgeIt e;
     2068//     public:
     2069//       InEdgeIt() { }
     2070//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
     2071//       InEdgeIt(const Invalid& i) : e(i) { }
     2072//       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
     2073//             const Node& _n) :
     2074//      e(*(_G.graph), typename Graph::Node(_n)) { }
     2075//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     2076//     };       
    20712077    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    2072     class EdgeIt {
    2073       friend class GraphWrapper<Graph>;
    2074       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    2075 //      typedef typename Graph::EdgeIt GraphEdgeIt;
    2076       typename Graph::EdgeIt e;
    2077     public:
    2078       EdgeIt() { }
    2079       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    2080       EdgeIt(const Invalid& i) : e(i) { }
    2081       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
    2082         e(*(_G.graph)) { }
    2083       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    2084     };
     2078//     class EdgeIt {
     2079//       friend class GraphWrapper<Graph>;
     2080//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
     2081// //      typedef typename Graph::EdgeIt GraphEdgeIt;
     2082//       typename Graph::EdgeIt e;
     2083//     public:
     2084//       EdgeIt() { }
     2085//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
     2086//       EdgeIt(const Invalid& i) : e(i) { }
     2087//       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
     2088//      e(*(_G.graph)) { }
     2089//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     2090//     };
    20852091
    20862092    using GraphWrapper<Graph>::first;
     
    20912097      i=OutEdgeIt(*this, p); return i;
    20922098    }
    2093     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    2094       i=InEdgeIt(*this, p); return i;
    2095     }
    2096     EdgeIt& first(EdgeIt& i) const {
    2097       i=EdgeIt(*this); return i;
    2098     }
    2099 
    2100     using GraphWrapper<Graph>::next;
    2101 //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    2102     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    2103     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    2104     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
     2099//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     2100//       i=InEdgeIt(*this, p); return i;
     2101//     }
     2102//     EdgeIt& first(EdgeIt& i) const {
     2103//       i=EdgeIt(*this); return i;
     2104//     }
     2105
     2106//     using GraphWrapper<Graph>::next;
     2107// //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
     2108//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
     2109//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
     2110//     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
    21052111   
    2106     Node aNode(const OutEdgeIt& e) const {
    2107       return Node(this->graph->aNode(e.e)); }
    2108     Node aNode(const InEdgeIt& e) const {
    2109       return Node(this->graph->aNode(e.e)); }
    2110     Node bNode(const OutEdgeIt& e) const {
    2111       return Node(this->graph->bNode(e.e)); }
    2112     Node bNode(const InEdgeIt& e) const {
    2113       return Node(this->graph->bNode(e.e)); }
    2114 
    2115     void erase(const OutEdgeIt& e) const {
    2116       OutEdgeIt f=e;
    2117       this->next(f);
    2118       first_out_edges->set(this->tail(e), f.e);
     2112//     Node aNode(const OutEdgeIt& e) const {
     2113//       return Node(this->graph->aNode(e.e)); }
     2114//     Node aNode(const InEdgeIt& e) const {
     2115//       return Node(this->graph->aNode(e.e)); }
     2116//     Node bNode(const OutEdgeIt& e) const {
     2117//       return Node(this->graph->bNode(e.e)); }
     2118//     Node bNode(const InEdgeIt& e) const {
     2119//       return Node(this->graph->bNode(e.e)); }
     2120
     2121    void erase(const Edge& e) const {
     2122      Node n=tail(e);
     2123      typename Graph::OutEdgeIt f(*graph, n);
     2124      ++f;
     2125      first_out_edges->set(n, f);
    21192126    }
    21202127  };
  • src/work/marci/augmenting_flow.h

    r775 r777  
    1212#include <hugo/invalid.h>
    1313#include <hugo/maps.h>
    14 #include <for_each_macros.h>
     14//#include <for_each_macros.h>
    1515
    1616/// \file
     
    10831083    Num flowValue() const {
    10841084      Num a=0;
    1085       FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
    1086       FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
     1085      for (InEdgeIt e(*g, t); e!=INVALID; ++e) a+=(*flow)[e];
     1086      for (OutEdgeIt e(*g, t); e!=INVALID; ++e) a-=(*flow)[e];
    10871087      return a;
    10881088      //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
     
    11221122
    11231123    //ReachedMap level(res_graph);
    1124     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     1124    for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
    11251125    BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    11261126    bfs.pushAndSetReached(s);
     
    11331133    //searching for augmenting path
    11341134    while ( !bfs.finished() ) {
    1135       ResGWOutEdgeIt e=bfs;
     1135      ResGWEdge e=bfs;
    11361136      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
    11371137        Node v=res_graph.tail(e);
     
    11701170
    11711171    if (status!=AFTER_FAST_AUGMENTING) {
    1172       FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     1172      for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
    11731173      number_of_augmentations=1;
    11741174    } else {
     
    11901190    //searching for augmenting path
    11911191    while ( !bfs.finished() ) {
    1192       ResGWOutEdgeIt e=bfs;
     1192      ResGWEdge e=bfs;
    11931193      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
    11941194        Node v=res_graph.tail(e);
     
    12321232    //bfs for distances on the residual graph
    12331233    //ReachedMap level(res_graph);
    1234     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     1234    for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
    12351235    BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    12361236    bfs.pushAndSetReached(s);
     
    12561256
    12571257    while ( !bfs.finished() ) {
    1258       ResGWOutEdgeIt e=bfs;
     1258      ResGWEdge e=bfs;
    12591259      if (e!=INVALID) {
    12601260        if (bfs.isBNodeNewlyReached()) {
     
    12971297        if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
    12981298          if (dfs.isBNodeNewlyReached()) {
    1299             typename MG::Node v=F.aNode(dfs);
    1300             typename MG::Node w=F.bNode(dfs);
     1299            typename MG::Node v=F.tail(dfs);
     1300            typename MG::Node w=F.head(dfs);
    13011301            pred.set(w, dfs);
    13021302            if (pred[v]!=INVALID) {
     
    13461346
    13471347    //ReachedMap level(res_graph);
    1348     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     1348    for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
    13491349    BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    13501350
     
    13521352    DistanceMap<ResGW> dist(res_graph);
    13531353    while ( !bfs.finished() ) {
    1354       ResGWOutEdgeIt e=bfs;
     1354      ResGWEdge e=bfs;
    13551355      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
    13561356        dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     
    13591359    } //computing distances from s in the residual graph
    13601360
    1361       //Subgraph containing the edges on some shortest paths
     1361    //Subgraph containing the edges on some shortest paths
    13621362    ConstMap<typename ResGW::Node, bool> true_map(true);
    13631363    typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
     
    13671367    //Subgraph, which is able to delete edges which are already
    13681368    //met by the dfs
    1369     typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
     1369    typename FilterResGW::template NodeMap<typename FilterResGW::Edge>
    13701370      first_out_edges(filter_res_graph);
    13711371    typename FilterResGW::NodeIt v;
    13721372    for(filter_res_graph.first(v); v!=INVALID; ++v)
    13731373      {
    1374         typename FilterResGW::OutEdgeIt e;
    1375         filter_res_graph.first(e, v);
    1376         first_out_edges.set(v, e);
     1374        typename FilterResGW::OutEdgeIt e;
     1375        filter_res_graph.first(e, v);
     1376        first_out_edges.set(v, e);
    13771377      }
    13781378    typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
    1379       template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
     1379      template NodeMap<typename FilterResGW::Edge> > ErasingResGW;
    13801380    ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
    13811381
     
    13901390        dfs(erasing_res_graph);
    13911391      typename ErasingResGW::
    1392         template NodeMap<typename ErasingResGW::OutEdgeIt>
    1393         pred(erasing_res_graph);
     1392        template NodeMap<typename ErasingResGW::Edge> pred(erasing_res_graph);
    13941393      pred.set(s, INVALID);
    13951394      //invalid iterators for sources
     
    13991398
    14001399      dfs.pushAndSetReached
    1401         ///\bug hugo 0.2
     1400        /// \bug hugo 0.2
    14021401        (typename ErasingResGW::Node
    14031402         (typename FilterResGW::Node
     
    14061405          )
    14071406         );
     1407       
    14081408      while (!dfs.finished()) {
    14091409        ++dfs;
    1410         if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
     1410        if (typename ErasingResGW::Edge(dfs)!=INVALID)
    14111411          {
    14121412            if (dfs.isBNodeNewlyReached()) {
    14131413
    1414               typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
    1415               typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
    1416 
    1417               pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
     1414              typename ErasingResGW::Node v=erasing_res_graph.tail(dfs);
     1415              typename ErasingResGW::Node w=erasing_res_graph.head(dfs);
     1416
     1417              pred.set(w, typename ErasingResGW::Edge(dfs));
    14181418              if (pred[v]!=INVALID) {
    14191419                free1.set
    14201420                  (w, std::min(free1[v], res_graph.resCap
    1421                                (typename ErasingResGW::OutEdgeIt(dfs))));
     1421                               (typename ErasingResGW::Edge(dfs))));
    14221422              } else {
    14231423                free1.set
    14241424                  (w, res_graph.resCap
    1425                    (typename ErasingResGW::OutEdgeIt(dfs)));
     1425                   (typename ErasingResGW::Edge(dfs)));
    14261426              }
    14271427
     
    14501450        //        Num j2=a2[b2];
    14511451        Num augment_value=free1[n];
    1452         while (erasing_res_graph.valid(pred[n])) {
    1453           typename ErasingResGW::OutEdgeIt e=pred[n];
     1452        while (pred[n]!=INVALID) {
     1453          typename ErasingResGW::Edge e=pred[n];
    14541454          res_graph.augment(e, augment_value);
    14551455          n=erasing_res_graph.tail(e);
  • src/work/marci/bfs_dfs.h

    r774 r777  
    2828  protected:
    2929    typedef typename Graph::Node Node;
     30    typedef typename Graph::Edge Edge;
    3031    typedef typename Graph::OutEdgeIt OutEdgeIt;
    3132    const Graph* graph;
     
    3334    ReachedMap& reached;
    3435    bool b_node_newly_reached;
    35     OutEdgeIt actual_edge;
     36    Edge actual_edge;
    3637    bool own_reached_map;
    3738  public:
     
    5657    /// and the first out-edge is processed.
    5758    /// If the queue is not empty, then \c s is simply pushed.
    58     void pushAndSetReached(Node s) {
     59    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
    5960      reached.set(s, true);
    6061      if (bfs_queue.empty()) {
    6162        bfs_queue.push(s);
    62         graph->first(actual_edge, s);
     63        actual_edge=OutEdgeIt(*graph, s);
     64        //graph->first(actual_edge, s);
    6365        if (actual_edge!=INVALID) {
    6466          Node w=graph->head(actual_edge);
     
    7476        bfs_queue.push(s);
    7577      }
     78      return *this;
    7679    }
    7780    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
     
    8083    operator++() {
    8184      if (actual_edge!=INVALID) {
    82         ++actual_edge;
     85        actual_edge=++OutEdgeIt(*graph, actual_edge);
     86        //++actual_edge;
    8387        if (actual_edge!=INVALID) {
    8488          Node w=graph->head(actual_edge);
     
    9498        bfs_queue.pop();
    9599        if (!bfs_queue.empty()) {
    96           graph->first(actual_edge, bfs_queue.front());
     100          actual_edge=OutEdgeIt(*graph, bfs_queue.front());
     101          //graph->first(actual_edge, bfs_queue.front());
    97102          if (actual_edge!=INVALID) {
    98103            Node w=graph->head(actual_edge);
     
    114119    /// to an \c out-edge-iterator.
    115120    ///\bug Edge have to be in HUGO 0.2
    116     operator OutEdgeIt() const { return actual_edge; }
     121    operator Edge() const { return actual_edge; }
    117122    /// Returns if b-node has been reached just now.
    118123    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     
    120125    bool isANodeExamined() const { return actual_edge==INVALID; }
    121126    /// Returns a-node of the actual edge, so does if the edge is invalid.
    122     Node aNode() const { return bfs_queue.front(); }
     127    Node tail() const { return bfs_queue.front(); }
    123128    /// \pre The actual edge have to be valid.
    124     Node bNode() const { return graph->bNode(actual_edge); }
     129    Node head() const { return graph->head(actual_edge); }
    125130    /// Guess what?
    126131    /// \deprecated
     
    160165    /// in addition its pred is set to be \c INVALID, and dist to \c 0.
    161166    /// if \c s was marked previuosly, then it is simply pushed.
    162     void push(Node s) {
     167    Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) {
    163168      if (this->reached[s]) {
    164169        Parent::pushAndSetReached(s);
     
    168173        dist.set(s, 0);
    169174      }
     175      return *this;
    170176    }
    171177    /// A bfs is processed from \c s.
    172     void run(Node s) {
     178    Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
    173179      push(s);
    174180      while (!this->finished()) this->operator++();
     181      return *this;
    175182    }
    176183    /// Beside the bfs iteration, \c pred and \dist are saved in a
     
    180187      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
    181188      {
    182         pred.set(this->bNode(), this->actual_edge);
    183         dist.set(this->bNode(), dist[this->aNode()]);
     189        pred.set(this->head(), this->actual_edge);
     190        dist.set(this->head(), dist[this->tail()]);
    184191      }
    185192      return *this;
     
    202209  protected:
    203210    typedef typename Graph::Node Node;
     211    typedef typename Graph::Edge Edge;
    204212    typedef typename Graph::OutEdgeIt OutEdgeIt;
    205213    const Graph* graph;
    206214    std::stack<OutEdgeIt> dfs_stack;
    207215    bool b_node_newly_reached;
    208     OutEdgeIt actual_edge;
     216    Edge actual_edge;
    209217    Node actual_node;
    210218    ReachedMap& reached;
     
    225233    ~DfsIterator() { if (own_reached_map) delete &reached; }
    226234    /// This method markes s reached and first out-edge is processed.
    227     void pushAndSetReached(Node s) {
     235    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
    228236      actual_node=s;
    229237      reached.set(s, true);
    230       OutEdgeIt e;
    231       graph->first(e, s);
     238      OutEdgeIt e(*graph, s);
     239      //graph->first(e, s);
    232240      dfs_stack.push(e);
     241      return *this;
    233242    }
    234243    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
     
    237246    operator++() {
    238247      actual_edge=dfs_stack.top();
    239       //actual_node=G.aNode(actual_edge);
    240248      if (actual_edge!=INVALID/*.valid()*/) {
    241249        Node w=graph->head(actual_edge);
    242250        actual_node=w;
    243251        if (!reached[w]) {
    244           OutEdgeIt e;
    245           graph->first(e, w);
     252          OutEdgeIt e(*graph, w);
     253          //graph->first(e, w);
    246254          dfs_stack.push(e);
    247255          reached.set(w, true);
     
    263271    /// to an \c out-edge-iterator.
    264272    ///\bug Edge have to be in HUGO 0.2
    265     operator OutEdgeIt() const { return actual_edge; }
     273    operator Edge() const { return actual_edge; }
    266274    /// Returns if b-node has been reached just now.
    267275    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     
    269277    bool isANodeExamined() const { return actual_edge==INVALID; }
    270278    /// Returns a-node of the actual edge, so does if the edge is invalid.
    271     Node aNode() const { return actual_node; /*FIXME*/}
     279    Node tail() const { return actual_node; /*FIXME*/}
    272280    /// Returns b-node of the actual edge.
    273281    /// \pre The actual edge have to be valid.
    274     Node bNode() const { return graph->bNode(actual_edge); }
     282    Node head() const { return graph->head(actual_edge); }
    275283    /// Guess what?
    276284    /// \deprecated
     
    305313    /// in addition its pred is set to be \c INVALID.
    306314    /// if \c s was marked previuosly, then it is simply pushed.
    307     void push(Node s) {
     315    Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
    308316      if (this->reached[s]) {
    309317        Parent::pushAndSetReached(s);
     
    312320        pred.set(s, INVALID);
    313321      }
     322      return *this;
    314323    }
    315324    /// A bfs is processed from \c s.
    316     void run(Node s) {
     325    Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
    317326      push(s);
    318327      while (!this->finished()) this->operator++();
     328      return *this;
    319329    }
    320330    /// Beside the dfs iteration, \c pred is saved in a
     
    324334      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
    325335      {
    326         pred.set(this->bNode(), this->actual_edge);
     336        pred.set(this->head(), this->actual_edge);
    327337      }
    328338      return *this;
  • src/work/marci/bfsit_vs_byhand.cc

    r773 r777  
    3434  cout << g.edgeNum() << endl;
    3535
    36   Graph::NodeMap<OutEdgeIt> pred(g);
     36  Graph::NodeMap<Edge> pred(g);
    3737  cout << "iteration time of bfs written by hand..." << endl;
    3838  Timer ts;
     
    7070      ++bfs;
    7171      if (g.valid(bfs) && bfs.isBNodeNewlyReached())
    72         pred.set(bfs.bNode(), bfs);
     72        pred.set(bfs.head(), Graph::Edge(bfs));
    7373    }
    7474    std::cout << ts << std::endl;
  • src/work/marci/graph_wrapper_time.cc

    r773 r777  
    11// -*- c++ -*-
     2
     3// Use a DIMACS max flow file as follows:
     4// graph_wrapper_time dimacs_max_flow_file
    25
    36#include <iostream>
     
    2932  Timer ts;
    3033  ts.reset();
    31   cout << g.nodeNum() << endl;
    32   cout << g.edgeNum() << endl;
     34
    3335  typedef MaxFlow<Graph, int, FlowMap, FlowMap> MyMaxFlow;
    3436  MyMaxFlow max_flow(g, s, t, cap, flow);
     
    4244  typedef ListGraph Graph;
    4345  Graph g;
    44 //   cout << g.id(g.addNode()) << endl;
    45 //   cout << g.id(g.addNode()) << endl;
    46 //   cout << g.nodeNum() << endl;
    4746  timeTest<Graph>(in, g);
    4847  typedef GraphWrapper<Graph> Graph1;
    4948  Graph1 g1(g);
    50 //   g1.clear();
    51 //   cout << g.id(g1.addNode()) << endl;
    52 //   cout << g.id(g1.addNode()) << endl;
    53 //   cout << g1.nodeNum() << endl;
    54 //   g1.clear();
    5549  timeTest<Graph1>(in, g1);
    5650  typedef GraphWrapper<Graph1> Graph2;
     
    6054  Graph3 g3(g2);
    6155  timeTest<Graph3>(in, g3);
    62 //   typedef GraphWrapper<Graph3> Graph4;
    63 //   Graph4 g4(g3);
    64 //   timeTest<Graph4>(in, g4);
    65 //   typedef GraphWrapper<Graph4> Graph5;
    66 //   Graph5 g5(g4);
    67 //   timeTest<Graph5>(in, g5);
    68 //   typedef GraphWrapper<Graph5> Graph6;
    69 //   Graph6 g6(g5);
    70 //   timeTest<Graph6>(in, g6); 
    71 //   typedef GraphWrapper<Graph6> Graph7;
    72 //   Graph7 g7(g6);
    73 //   timeTest<Graph7>(in, g7);
     56  typedef GraphWrapper<Graph3> Graph4;
     57  Graph4 g4(g3);
     58  timeTest<Graph4>(in, g4);
     59  typedef GraphWrapper<Graph4> Graph5;
     60  Graph5 g5(g4);
     61  timeTest<Graph5>(in, g5);
     62  typedef GraphWrapper<Graph5> Graph6;
     63  Graph6 g6(g5);
     64  timeTest<Graph6>(in, g6); 
     65  typedef GraphWrapper<Graph6> Graph7;
     66  Graph7 g7(g6);
     67  timeTest<Graph7>(in, g7);
    7468
    7569  return 0;
  • src/work/marci/iterator_bfs_demo.cc

    r774 r777  
    1010
    1111using namespace hugo;
     12
    1213using std::cout;
    1314using std::endl;
     
    7374  cout << "    \\-->    ------------->         "<< endl;
    7475 
    75 //   typedef TrivGraphWrapper<const Graph> CGW;
    76 //   CGW gw(G);
    77 
    78 //   cout << "bfs and dfs demo on the directed graph" << endl;
    79 //   for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
    80 //     cout << n << ": ";
    81 //     cout << "out edges: ";
    82 //     for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
    83 //       cout << e << " ";
    84 //     cout << "in edges: ";
    85 //     for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
    86 //       cout << e << " ";
    87 //     cout << endl;
    88 //   }
    89 
    9076  {
    9177    EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
     
    10894    while (!bfs.finished()) {
    10995      //cout << "edge: ";
    110       if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
     96      if (Graph::Edge(bfs)!=INVALID) {
    11197        cout << edge_name[bfs] << /*endl*/", " <<
    11298          node_name[G.tail(bfs)] <<
     
    117103      } else {
    118104        cout << "invalid" << /*endl*/", " <<
    119           node_name[bfs.aNode()] <<
     105          node_name[bfs.tail()] <<
    120106          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    121107         
     
    142128      ++dfs;
    143129      //cout << "edge: ";
    144       if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
     130      if (Graph::Edge(dfs)!=INVALID) {
    145131        cout << edge_name[dfs] << /*endl*/", " <<
    146132          node_name[G.tail(dfs)] <<
     
    151137      } else {
    152138        cout << "invalid" << /*endl*/", " <<
    153           node_name[dfs.aNode()] <<
     139          node_name[dfs.tail()] <<
    154140          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    155141         
     
    184170    while (!bfs.finished()) {
    185171      //cout << "edge: ";
    186       if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
    187         cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
     172      if (GW::Edge(bfs)!=INVALID) {
     173        cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
    188174          node_name[gw.tail(bfs)] <<
    189175          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     
    193179      } else {
    194180        cout << "invalid" << /*endl*/", " <<
    195           node_name[bfs.aNode()] <<
     181          node_name[bfs.tail()] <<
    196182          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    197183         
     
    218204      ++dfs;
    219205      //cout << "edge: ";
    220       if (GW::OutEdgeIt(dfs)!=INVALID) {
    221         cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
     206      if (GW::Edge(dfs)!=INVALID) {
     207        cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
    222208          node_name[gw.tail(dfs)] <<
    223209          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     
    227213      } else {
    228214        cout << "invalid" << /*endl*/", " <<
    229           node_name[dfs.aNode()] <<
     215          node_name[dfs.tail()] <<
    230216          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    231217         
     
    347333    while (!bfs.finished()) {
    348334      //cout << "edge: ";
    349       if (GW::OutEdgeIt(bfs)!=INVALID) {
    350         cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
     335      if (GW::Edge(bfs)!=INVALID) {
     336        cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
    351337          node_name[gw.tail(bfs)] <<
    352338          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     
    356342      } else {
    357343        cout << "invalid" << /*endl*/", " <<
    358           node_name[bfs.aNode()] <<
     344          node_name[bfs.tail()] <<
    359345          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    360346         
     
    381367      ++dfs;
    382368      //cout << "edge: ";
    383       if (GW::OutEdgeIt(dfs)!=INVALID) {
    384         cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
     369      if (GW::Edge(dfs)!=INVALID) {
     370        cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
    385371          node_name[gw.tail(dfs)] <<
    386372          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     
    390376      } else {
    391377        cout << "invalid" << /*endl*/", " <<
    392           node_name[dfs.aNode()] <<
     378          node_name[dfs.tail()] <<
    393379          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    394380         
  • src/work/marci/lg_vs_sg_vs_sg.cc

    r762 r777  
    5454    {
    5555      std::cout << "physical blocking flow augmentation ..." << std::endl;
    56       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     56      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    5757      ts.reset();
    5858      int i=0;
     
    7676    {
    7777      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    78       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     78      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    7979      ts.reset();
    8080      int i=0;
     
    8787    {
    8888      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    89       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     89      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    9090      ts.reset();
    9191      int i=0;
     
    122122    {
    123123      std::cout << "preflow ..." << std::endl;
    124       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     124      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    125125      ts.reset();
    126126      max_flow_test.run();
     
    131131    {
    132132      std::cout << "physical blocking flow augmentation ..." << std::endl;
    133       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     133      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    134134      ts.reset();
    135135      int i=0;
     
    153153    {
    154154      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    155       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     155      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    156156      ts.reset();
    157157      int i=0;
     
    164164    {
    165165      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    166       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     166      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    167167      ts.reset();
    168168      int i=0;
     
    199199    {
    200200      std::cout << "preflow ..." << std::endl;
    201       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     201      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    202202      ts.reset();
    203203      max_flow_test.run();
     
    208208    {
    209209      std::cout << "physical blocking flow augmentation ..." << std::endl;
    210       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     210      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    211211      ts.reset();
    212212      int i=0;
     
    230230    {
    231231      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    232       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     232      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    233233      ts.reset();
    234234      int i=0;
     
    241241    {
    242242      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    243       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     243      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
    244244      ts.reset();
    245245      int i=0;
  • src/work/marci/max_flow_demo.cc

    r775 r777  
    11// -*- c++ -*-
     2
     3// Use a DIMACS max flow file as stdin.
     4// max_flow_demo < dimacs_max_flow_file
     5
     6
    27#include <iostream>
    38#include <fstream>
     
    1520
    1621using namespace hugo;
    17 
    18 // Use a DIMACS max flow file as stdin.
    19 // max_flow_demo < dimacs_max_flow_file
    2022
    2123int main(int, char **) {
     
    103105  }
    104106
    105 //   {
    106 //     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    107 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    108 //     ts.reset();
    109 //     int i=0;
    110 //     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
    111 //     std::cout << "elapsed time: " << ts << std::endl;
    112 //     std::cout << "number of augmentation phases: " << i << std::endl;
    113 //     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
     107  {
     108    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     109    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     110    ts.reset();
     111    int i=0;
     112    while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
     113    std::cout << "elapsed time: " << ts << std::endl;
     114    std::cout << "number of augmentation phases: " << i << std::endl;
     115    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    114116
    115 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    116 //       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    117 //      std::cout << "Slackness does not hold!" << std::endl;
    118 //       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
    119 //      std::cout << "Slackness does not hold!" << std::endl;
    120 //     }
    121 //   }
     117    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     118      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     119        std::cout << "Slackness does not hold!" << std::endl;
     120      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     121        std::cout << "Slackness does not hold!" << std::endl;
     122    }
     123  }
    122124
    123125  {
Note: See TracChangeset for help on using the changeset viewer.