COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 774:4297098d9677 in lemon-0.x for src


Ignore:
Timestamp:
08/30/04 14:01:47 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
Message:

Merge back the whole branches/hugo++ to trunk.

Location:
src
Files:
2 added
19 edited

Legend:

Unmodified
Added
Removed

  • src/benchmark/bfs-bench.cc

    r751 r774  
    4949    Node m;
    5050    Q.pop();
    51     for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
     51    for(OutEdgeIt e(G,n);e!=INVALID;++e)
    5252      if(!visited[m=G.head(e)]) {
    5353        Q.push(m);
    … …  
    7777    Node m;
    7878    Node n=Q[Qt++];
    79     for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
     79    for(OutEdgeIt e(G,n);e!=INVALID;++e)
    8080      if(!visited[m=G.head(e)]) {
    8181        Q[Qh++]=m;
    … …  
    9292  int i=0;
    9393 
    94   for(NodeIt n(G);G.valid(n);G.next(n))
    95     for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
     94  for(NodeIt n(G);n!=INVALID;++n)
     95    for(OutEdgeIt e(G,n);e!=INVALID;++e)
    9696      i++;
    9797}

  • src/hugo/Makefile.am

    r731 r774  
    11pkginclude_HEADERS =                                                    \
     2        bfs.h                                                           \
    23        bin_heap.h                                                      \
    34        dijkstra.h                                                      \

  • src/hugo/dijkstra.h

    r758 r774  
    8585    bool local_distance;
    8686
     87    //The source node of the last execution.
     88    Node source;
     89
    8790    ///Initialize maps
    8891   
    … …  
    213216      init_maps();
    214217     
    215       for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
     218      source = s;
     219     
     220      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    216221        predecessor->set(u,INVALID);
    217222        pred_node->set(u,INVALID);
    … …  
    236241       
    237242       
    238         for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
    239           Node w=G->bNode(e);
     243        for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
     244          Node w=G->head(e);
    240245         
    241246          switch(heap.state(w)) {
    … …  
    311316
    312317    ///Returns \c true if \c v is reachable from the root.
    313     ///\warning the root node is reported to be unreached!
    314     ///\todo Is this what we want?
     318    ///\warning the root node is reported to be reached!
    315319    ///\pre \ref run() must be called before using this function.
    316320    ///
    317     bool reached(Node v) { return G->valid((*predecessor)[v]); }
     321    bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
    318322   
    319323  };

  • src/hugo/full_graph.h

    r752 r774  
    6464    Node head(Edge e) const { return e.n/NodeNum; }
    6565
    66     Node aNode(OutEdgeIt e) const { return tail(e); }
    67     Node aNode(InEdgeIt e) const { return head(e); }
    68 
    69     Node bNode(OutEdgeIt e) const { return head(e); }
    70     Node bNode(InEdgeIt e) const { return tail(e); }
    71 
    7266    NodeIt& first(NodeIt& v) const {
    7367      v=NodeIt(*this); return v; }
    … …  
    7973      e=InEdgeIt(*this,v); return e; }
    8074
    81     static bool valid(Edge e) { return e.n!=-1; }
    82     static bool valid(Node n) { return n.n!=-1; }
    83    
    84     template <typename It> It getNext(It it) const
    85     { It tmp(it); return next(tmp); }
    86 
    87     NodeIt& next(NodeIt& it) const {
    88       it.n=(it.n+2)%(NodeNum+1)-1;
    89       return it;
    90     }
    91     OutEdgeIt& next(OutEdgeIt& it) const
    92     { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }
    93     InEdgeIt& next(InEdgeIt& it) const
    94     { if(!((++it.n)%NodeNum)) it.n=-1; return it; }
    95     static EdgeIt& next(EdgeIt& it) { --it.n; return it; }
    96 
    9775    static int id(Node v) { return v.n; }
    9876    static int id(Edge e) { return e.n; }
    9977
     78    /// Finds an edge between two nodes.
     79   
     80    /// Finds an edge from node \c u to node \c v.
     81    ///
     82    /// If \c prev is \ref INVALID (this is the default value), then
     83    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     84    /// the next edge from \c u to \c v after \c prev.
     85    /// \return The found edge or INVALID if there is no such an edge.
     86    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     87    {
     88      return prev.n==-1?Edge(*this,u.n,v.n):INVALID;
     89    }
     90   
     91     
    10092    class Node {
    10193      friend class FullGraph;
    … …  
    120112   
    121113    class NodeIt : public Node {
     114      const FullGraph *G;
    122115      friend class FullGraph;
    123116    public:
    124117      NodeIt() : Node() { }
     118      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
    125119      NodeIt(Invalid i) : Node(i) { }
    126       NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }
     120      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
    127121      ///\todo Undocumented conversion Node -\> NodeIt.
    128       NodeIt(const FullGraph& G, const Node &n) : Node(n) { }
     122      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
    129123    };
    130124
    … …  
    139133      friend int FullGraph::id(Edge e);
    140134
    141       Edge(int nn) {n=nn;}
     135      Edge(int nn) : n(nn) {}
     136      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
    142137    public:
    143138      Edge() { }
    … …  
    155150      friend class FullGraph;
    156151    public:
    157       EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }
     152      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
     153      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
    158154      EdgeIt (Invalid i) : Edge(i) { }
    159155      EdgeIt() : Edge() { }
     156      EdgeIt& operator++() { --n; return *this; }
     157
    160158      ///\bug This is a workaround until somebody tells me how to
    161159      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
    … …  
    164162   
    165163    class OutEdgeIt : public Edge {
     164      const FullGraph *G;
    166165      friend class FullGraph;
    167166    public:
    168167      OutEdgeIt() : Edge() { }
     168      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
    169169      OutEdgeIt (Invalid i) : Edge(i) { }
    170170
    171       OutEdgeIt(const FullGraph& G,const Node v)
    172         : Edge(v.n) {}
     171      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
     172     
     173      OutEdgeIt& operator++()
     174      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
     175
    173176    };
    174177   
    175178    class InEdgeIt : public Edge {
     179      const FullGraph *G;
    176180      friend class FullGraph;
    177181    public:
    178182      InEdgeIt() : Edge() { }
     183      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
    179184      InEdgeIt (Invalid i) : Edge(i) { }
    180       InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}
     185      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
     186      InEdgeIt& operator++()
     187      { if(!((++n)%G->NodeNum)) n=-1; return *this; }
    181188    };
    182189
    … …  
    280287        return *this;
    281288      }
    282      
     289
    283290      void update() {}
    284291      void update(T a) {}

  • src/hugo/graph_wrapper.h

    r739 r774  
    1313#include <hugo/invalid.h>
    1414#include <hugo/maps.h>
    15 //#include <iter_map.h>
     15#include <iostream>
    1616
    1717namespace hugo {
    … …  
    9797
    9898    GraphWrapper(Graph& _graph) : graph(&_graph) { }
     99    GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
    99100//     Graph& getGraph() const { return *graph; }
    100101 
    101 //    typedef typename Graph::Node Node;
    102     class Node : public Graph::Node {
     102    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//     };
     114    class NodeIt : public Node {
     115      const GraphWrapper<Graph>* gw;
    103116      friend class GraphWrapper<Graph>;
    104     public:
    105       Node() { }
    106       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
    107       // /// \bug construction throughrthr multiple levels should be
    108       // /// handled better
    109       // Node(const typename ParentGraph::ParentGraph::Node& _n) :
    110       // Graph::Node(_n) { }
    111       Node(const Invalid& i) : Graph::Node(i) { }
    112     };
    113     class NodeIt {
    114       friend class GraphWrapper<Graph>;
    115       typename Graph::NodeIt n;
    116117     public:
    117118      NodeIt() { }
    118       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    119       NodeIt(const Invalid& i) : n(i) { }
    120       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
    121       operator Node() const { return Node(typename Graph::Node(n)); }
    122     };
    123 //    typedef typename Graph::Edge Edge;
    124     class Edge : public Graph::Edge {
     119      //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
     120      NodeIt(Invalid i) : Node(i) { }
     121      NodeIt(const GraphWrapper<Graph>& _gw) :
     122        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
     123      NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     124        Node(n), gw(&_gw) { }
     125      NodeIt& operator++() {
     126        *(static_cast<Node*>(this))=
     127          ++(typename Graph::NodeIt(*(gw->graph), *this));
     128        return *this;
     129      }
     130    };
     131    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//     };
     139    class OutEdgeIt : public Edge {
     140      const GraphWrapper<Graph>* gw;
    125141      friend class GraphWrapper<Graph>;
    126     public:
    127       Edge() { }
    128       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
    129       Edge(const Invalid& i) : Graph::Edge(i) { }
    130     };
    131     class OutEdgeIt {
     142     public:
     143      OutEdgeIt() { }
     144      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
     145      OutEdgeIt(Invalid i) : Edge(i) { }
     146      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     147        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     148      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
     149        Edge(e), gw(&_gw) { }
     150      OutEdgeIt& operator++() {
     151        *(static_cast<Edge*>(this))=
     152          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     153        return *this;
     154      }
     155    };
     156    class InEdgeIt : public Edge {
     157      const GraphWrapper<Graph>* gw;
    132158      friend class GraphWrapper<Graph>;
    133       typename Graph::OutEdgeIt e;
    134     public:
    135       OutEdgeIt() { }
    136       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    137       OutEdgeIt(const Invalid& i) : e(i) { }
    138       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
    139         e(*(_G.graph), typename Graph::Node(_n)) { }
    140       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    141     };
    142     class InEdgeIt {
     159     public:
     160      InEdgeIt() { }
     161      //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
     162      InEdgeIt(Invalid i) : Edge(i) { }
     163      InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     164        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     165      InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
     166        Edge(e), gw(&_gw) { }
     167      InEdgeIt& operator++() {
     168        *(static_cast<Edge*>(this))=
     169          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     170        return *this;
     171      }
     172    };
     173    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     174    class EdgeIt : public Edge {
     175      const GraphWrapper<Graph>* gw;
    143176      friend class GraphWrapper<Graph>;
    144       typename Graph::InEdgeIt e;
    145     public:
    146       InEdgeIt() { }
    147       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    148       InEdgeIt(const Invalid& i) : e(i) { }
    149       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
    150         e(*(_G.graph), typename Graph::Node(_n)) { }
    151       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    152     };
    153     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    154     class EdgeIt {
    155       friend class GraphWrapper<Graph>;
    156       typename Graph::EdgeIt e;
    157     public:
     177     public:
    158178      EdgeIt() { }
    159       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    160       EdgeIt(const Invalid& i) : e(i) { }
    161       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
    162       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     179      //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
     180      EdgeIt(Invalid i) : Edge(i) { }
     181      EdgeIt(const GraphWrapper<Graph>& _gw) :
     182        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
     183      EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
     184        Edge(w), gw(&_gw) { }
     185      EdgeIt& operator++() {
     186        *(static_cast<Edge*>(this))=
     187          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     188        return *this;
     189      }
    163190    };
    164191   
    … …  
    176203    }
    177204
    178     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    179     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    180     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    181     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
     205//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
     206//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
     207//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
     208//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    182209
    183210    Node tail(const Edge& e) const {
    … …  
    186213      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    187214
    188     bool valid(const Node& n) const {
    189       return graph->valid(static_cast<typename Graph::Node>(n)); }
    190     bool valid(const Edge& e) const {
    191       return graph->valid(static_cast<typename Graph::Edge>(e)); }
     215//     bool valid(const Node& n) const {
     216//       return graph->valid(static_cast<typename Graph::Node>(n)); }
     217//     bool valid(const Edge& e) const {
     218//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
    192219
    193220    int nodeNum() const { return graph->nodeNum(); }
    194221    int edgeNum() const { return graph->edgeNum(); }
    195222 
    196     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    197     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    198     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    199     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     223//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     224//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     225//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     226//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    200227 
    201228    Node addNode() const { return Node(graph->addNode()); }
    … …  
    219246      typedef typename Graph::template NodeMap<T> Parent;
    220247    public:
    221       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
    222       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
     248      NodeMap(const GraphWrapper<Graph>& gw) :  Parent(*(gw.graph)) { }
     249      NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
    223250    };
    224251
    … …  
    226253      typedef typename Graph::template EdgeMap<T> Parent;
    227254    public:
    228       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
    229       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
     255      EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
     256      EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
    230257    };
    231258  };
    … …  
    247274  public:
    248275    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
     276    RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
    249277
    250278    typedef typename GraphWrapper<Graph>::Node Node;
    … …  
    257285    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
    258286
    259     class OutEdgeIt {
     287    class OutEdgeIt : public Edge {
     288      const RevGraphWrapper<Graph>* gw;
    260289      friend class GraphWrapper<Graph>;
    261       friend class RevGraphWrapper<Graph>;
    262       typename Graph::InEdgeIt e;
    263     public:
     290     public:
    264291      OutEdgeIt() { }
    265       OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    266       OutEdgeIt(const Invalid& i) : e(i) { }
    267       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    268         e(*(_G.graph), typename Graph::Node(_n)) { }
    269       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    270     };
    271     class InEdgeIt {
     292      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
     293      OutEdgeIt(Invalid i) : Edge(i) { }
     294      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
     295        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     296      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
     297        Edge(e), gw(&_gw) { }
     298      OutEdgeIt& operator++() {
     299        *(static_cast<Edge*>(this))=
     300          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     301        return *this;
     302      }
     303    };
     304    class InEdgeIt : public Edge {
     305      const RevGraphWrapper<Graph>* gw;
    272306      friend class GraphWrapper<Graph>;
    273       friend class RevGraphWrapper<Graph>;
    274       typename Graph::OutEdgeIt e;
    275     public:
     307     public:
    276308      InEdgeIt() { }
    277       InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    278       InEdgeIt(const Invalid& i) : e(i) { }
    279       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    280         e(*(_G.graph), typename Graph::Node(_n)) { }
    281       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     309      //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
     310      InEdgeIt(Invalid i) : Edge(i) { }
     311      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
     312        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
     313      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
     314        Edge(e), gw(&_gw) { }
     315      InEdgeIt& operator++() {
     316        *(static_cast<Edge*>(this))=
     317          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     318        return *this;
     319      }
    282320    };
    283321
    … …  
    290328    }
    291329
    292     using GraphWrapper<Graph>::next;
    293     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    294     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    295 
    296     Node aNode(const OutEdgeIt& e) const {
    297       return Node(this->graph->aNode(e.e)); }
    298     Node aNode(const InEdgeIt& e) const {
    299       return Node(this->graph->aNode(e.e)); }
    300     Node bNode(const OutEdgeIt& e) const {
    301       return Node(this->graph->bNode(e.e)); }
    302     Node bNode(const InEdgeIt& e) const {
    303       return Node(this->graph->bNode(e.e)); }
     330//     using GraphWrapper<Graph>::next;
     331//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
     332//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
     333
     334//     Node aNode(const OutEdgeIt& e) const {
     335//       return Node(this->graph->aNode(e.e)); }
     336//     Node aNode(const InEdgeIt& e) const {
     337//       return Node(this->graph->aNode(e.e)); }
     338//     Node bNode(const OutEdgeIt& e) const {
     339//       return Node(this->graph->bNode(e.e)); }
     340//     Node bNode(const InEdgeIt& e) const {
     341//       return Node(this->graph->bNode(e.e)); }
    304342
    305343    Node tail(const Edge& e) const {
    … …  
    309347
    310348  };
    311 
    312 
    313349
    314350  /// A graph wrapper for hiding nodes and edges from a graph.
    … …  
    627663    typedef GraphWrapper<Graph> Parent;
    628664  protected:
    629     //const CapacityMap* capacity;
    630     //FlowMap* flow;
    631 
    632665    ForwardFilterMap* forward_filter;
    633666    BackwardFilterMap* backward_filter;
    … …  
    648681      GraphWrapper<Graph>(_graph),
    649682      forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
     683    SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
     684                         ForwardFilterMap, BackwardFilterMap>& gw) :
     685      Parent(gw),
     686      forward_filter(gw.forward_filter),
     687      backward_filter(gw.backward_filter) { }
    650688
    651689    class Edge;
    … …  
    658696
    659697    typedef typename GraphWrapper<Graph>::Node Node;
    660     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    661 
     698    //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     699
     700    typedef typename Graph::Edge GraphEdge;
    662701    class Edge : public Graph::Edge {
    663702      friend class SubBidirGraphWrapper<Graph,
    … …  
    672711      Edge() { }
    673712      ///\bug =false kell-e? zsoltnak kell az addEdge miatt
    674       Edge(const typename Graph::Edge& _e, bool _backward=false) :
    675         Graph::Edge(_e), backward(_backward) { }
    676       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
     713      Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
     714        Graph::Edge(e), backward(_backward) { }
     715      Edge(Invalid i) : Graph::Edge(i), backward(true) { }
    677716//the unique invalid iterator
    678       friend bool operator==(const Edge& u, const Edge& v) {
    679         return (v.backward==u.backward &&
    680                 static_cast<typename Graph::Edge>(u)==
     717//       friend bool operator==(const Edge& u, const Edge& v) {
     718//      return (u.backward==v.backward &&
     719//              static_cast<typename Graph::Edge>(u)==
     720//              static_cast<typename Graph::Edge>(v));
     721//       }
     722//       friend bool operator!=(const Edge& u, const Edge& v) {
     723//      return (u.backward!=v.backward ||
     724//              static_cast<typename Graph::Edge>(u)!=
     725//              static_cast<typename Graph::Edge>(v));
     726//       }
     727      bool operator==(const Edge& v) const {
     728        return (this->backward==v.backward &&
     729                static_cast<typename Graph::Edge>(*this)==
    681730                static_cast<typename Graph::Edge>(v));
    682731      }
    683       friend bool operator!=(const Edge& u, const Edge& v) {
    684         return (v.backward!=u.backward ||
    685                 static_cast<typename Graph::Edge>(u)!=
     732      bool operator!=(const Edge& v) const {
     733        return (this->backward!=v.backward ||
     734                static_cast<typename Graph::Edge>(*this)!=
    686735                static_cast<typename Graph::Edge>(v));
    687       } 
    688     };
    689 
    690     class OutEdgeIt {
     736      }
     737    };
     738
     739    class OutEdgeIt : public Edge {
    691740      friend class SubBidirGraphWrapper<Graph,
    692741                                        ForwardFilterMap, BackwardFilterMap>;
    693742    protected:
    694       typename Graph::OutEdgeIt out;
    695       typename Graph::InEdgeIt in;
    696       bool backward;
     743      const SubBidirGraphWrapper<Graph,
     744                                 ForwardFilterMap, BackwardFilterMap>* gw;
    697745    public:
    698746      OutEdgeIt() { }
    699       //FIXME
    700 //      OutEdgeIt(const Edge& e) : Edge(e) { }
    701       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     747      OutEdgeIt(Invalid i) : Edge(i) { }
    702748//the unique invalid iterator
    703749      OutEdgeIt(const SubBidirGraphWrapper<Graph,
    704                 ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
    705         backward=false;
    706         _G.graph->first(out, v);
    707         while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
    708         if (!_G.graph->valid(out)) {
    709           backward=true;
    710           _G.graph->first(in, v);
    711           while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
     750                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     751        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
     752        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     753               !(*(gw->forward_filter))[*this])
     754          *(static_cast<GraphEdge*>(this))=
     755            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     756        if (*static_cast<GraphEdge*>(this)==INVALID)
     757          *static_cast<Edge*>(this)=
     758            Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
     759        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     760               !(*(gw->backward_filter))[*this])
     761          *(static_cast<GraphEdge*>(this))=
     762            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     763      }
     764      OutEdgeIt(const SubBidirGraphWrapper<Graph,
     765                ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     766        Edge(e), gw(&_gw) { }
     767      OutEdgeIt& operator++() {
     768        if (!this->backward) {
     769          Node n=gw->tail(*this);
     770          *(static_cast<GraphEdge*>(this))=
     771            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     772          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     773                 !(*(gw->forward_filter))[*this])
     774            *(static_cast<GraphEdge*>(this))=
     775              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     776          if (*static_cast<GraphEdge*>(this)==INVALID)
     777            *static_cast<Edge*>(this)=
     778              Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
     779          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     780                 !(*(gw->backward_filter))[*this])
     781            *(static_cast<GraphEdge*>(this))=
     782              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     783        } else {
     784          *(static_cast<GraphEdge*>(this))=
     785            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     786          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     787                 !(*(gw->backward_filter))[*this])
     788            *(static_cast<GraphEdge*>(this))=
     789              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    712790        }
    713       }
    714       operator Edge() const {
    715 //      Edge e;
    716 //      e.forward=this->forward;
    717 //      if (this->forward) e=out; else e=in;
    718 //      return e;
    719         if (this->backward)
    720           return Edge(in, this->backward);
    721         else
    722           return Edge(out, this->backward);
    723       }
    724     };
    725 
    726     class InEdgeIt {
     791        return *this;
     792      }
     793    };
     794
     795    class InEdgeIt : public Edge {
    727796      friend class SubBidirGraphWrapper<Graph,
    728797                                        ForwardFilterMap, BackwardFilterMap>;
    729798    protected:
    730       typename Graph::OutEdgeIt out;
    731       typename Graph::InEdgeIt in;
    732       bool backward;
     799      const SubBidirGraphWrapper<Graph,
     800                                 ForwardFilterMap, BackwardFilterMap>* gw;
    733801    public:
    734802      InEdgeIt() { }
    735       //FIXME
    736 //      OutEdgeIt(const Edge& e) : Edge(e) { }
    737       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     803      InEdgeIt(Invalid i) : Edge(i) { }
    738804//the unique invalid iterator
    739805      InEdgeIt(const SubBidirGraphWrapper<Graph,
    740                ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
    741         backward=false;
    742         _G.graph->first(in, v);
    743         while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
    744         if (!_G.graph->valid(in)) {
    745           backward=true;
    746           _G.graph->first(out, v);
    747           while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
     806               ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     807        Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
     808        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     809               !(*(gw->forward_filter))[*this])
     810          *(static_cast<GraphEdge*>(this))=
     811            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     812        if (*static_cast<GraphEdge*>(this)==INVALID)
     813          *static_cast<Edge*>(this)=
     814            Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
     815        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     816               !(*(gw->backward_filter))[*this])
     817          *(static_cast<GraphEdge*>(this))=
     818            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     819      }
     820      InEdgeIt(const SubBidirGraphWrapper<Graph,
     821               ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     822        Edge(e), gw(&_gw) { }
     823      InEdgeIt& operator++() {
     824        if (!this->backward) {
     825          Node n=gw->head(*this);
     826          *(static_cast<GraphEdge*>(this))=
     827            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     828          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     829                 !(*(gw->forward_filter))[*this])
     830            *(static_cast<GraphEdge*>(this))=
     831              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     832          if (*static_cast<GraphEdge*>(this)==INVALID)
     833            *static_cast<Edge*>(this)=
     834              Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
     835          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     836                 !(*(gw->backward_filter))[*this])
     837            *(static_cast<GraphEdge*>(this))=
     838              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     839        } else {
     840          *(static_cast<GraphEdge*>(this))=
     841            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     842          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     843                 !(*(gw->backward_filter))[*this])
     844            *(static_cast<GraphEdge*>(this))=
     845              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    748846        }
    749       }
    750       operator Edge() const {
    751 //      Edge e;
    752 //      e.forward=this->forward;
    753 //      if (this->forward) e=out; else e=in;
    754 //      return e;
    755         if (this->backward)
    756           return Edge(out, this->backward);
    757         else
    758           return Edge(in, this->backward);
    759       }
    760     };
    761 
    762     class EdgeIt {
     847        return *this;
     848      }
     849    };
     850
     851    class EdgeIt : public Edge {
    763852      friend class SubBidirGraphWrapper<Graph,
    764853                                        ForwardFilterMap, BackwardFilterMap>;
    765854    protected:
    766       typename Graph::EdgeIt e;
    767       bool backward;
     855      const SubBidirGraphWrapper<Graph,
     856                                 ForwardFilterMap, BackwardFilterMap>* gw;
    768857    public:
    769858      EdgeIt() { }
    770       EdgeIt(const Invalid& i) : e(i), backward(true) { }
     859      EdgeIt(Invalid i) : Edge(i) { }
     860//the unique invalid iterator
    771861      EdgeIt(const SubBidirGraphWrapper<Graph,
    772              ForwardFilterMap, BackwardFilterMap>& _G) {
    773         backward=false;
    774         _G.graph->first(e);
    775         while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
    776         if (!_G.graph->valid(e)) {
    777           backward=true;
    778           _G.graph->first(e);
    779           while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
     862                ForwardFilterMap, BackwardFilterMap>& _gw) :
     863        Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
     864        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     865               !(*(gw->forward_filter))[*this])
     866          *(static_cast<GraphEdge*>(this))=
     867            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     868        if (*static_cast<GraphEdge*>(this)==INVALID)
     869          *static_cast<Edge*>(this)=
     870            Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
     871        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     872               !(*(gw->backward_filter))[*this])
     873          *(static_cast<GraphEdge*>(this))=
     874            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     875      }
     876      EdgeIt(const SubBidirGraphWrapper<Graph,
     877             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     878        Edge(e), gw(&_gw) { }
     879      EdgeIt& operator++() {
     880        if (!this->backward) {
     881          *(static_cast<GraphEdge*>(this))=
     882            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     883          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     884                 !(*(gw->forward_filter))[*this])
     885            *(static_cast<GraphEdge*>(this))=
     886              ++(typename Graph::EdgeIt(*(gw->graph), *this));
     887          if (*static_cast<GraphEdge*>(this)==INVALID)
     888            *static_cast<Edge*>(this)=
     889              Edge(typename Graph::EdgeIt(*(gw->graph)), true);
     890          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     891                 !(*(gw->backward_filter))[*this])
     892            *(static_cast<GraphEdge*>(this))=
     893              ++(typename Graph::EdgeIt(*(gw->graph), *this));
     894        } else {
     895          *(static_cast<GraphEdge*>(this))=
     896            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     897          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     898                 !(*(gw->backward_filter))[*this])
     899            *(static_cast<GraphEdge*>(this))=
     900              ++(typename Graph::EdgeIt(*(gw->graph), *this));
    780901        }
    781       }
    782       operator Edge() const {
    783         return Edge(e, this->backward);
     902        return *this;
    784903      }
    785904    };
    … …  
    800919    }
    801920 
    802     using GraphWrapper<Graph>::next;
    803 //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    804     OutEdgeIt& next(OutEdgeIt& e) const {
    805       if (!e.backward) {
    806         Node v=this->graph->aNode(e.out);
    807         this->graph->next(e.out);
    808         while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
    809           this->graph->next(e.out); }
    810         if (!this->graph->valid(e.out)) {
    811           e.backward=true;
    812           this->graph->first(e.in, v);
    813           while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    814             this->graph->next(e.in); }
    815         }
    816       } else {
    817         this->graph->next(e.in);
    818         while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    819           this->graph->next(e.in); }
    820       }
    821       return e;
    822     }
    823 //     FIXME Not tested
    824     InEdgeIt& next(InEdgeIt& e) const {
    825       if (!e.backward) {
    826         Node v=this->graph->aNode(e.in);
    827         this->graph->next(e.in);
    828         while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
    829           this->graph->next(e.in); }
    830         if (!this->graph->valid(e.in)) {
    831           e.backward=true;
    832           this->graph->first(e.out, v);
    833           while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    834             this->graph->next(e.out); }
    835         }
    836       } else {
    837         this->graph->next(e.out);
    838         while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    839           this->graph->next(e.out); }
    840       }
    841       return e;
    842     }
    843     EdgeIt& next(EdgeIt& e) const {
    844       if (!e.backward) {
    845         this->graph->next(e.e);
    846         while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
    847           this->graph->next(e.e); }
    848         if (!this->graph->valid(e.e)) {
    849           e.backward=true;
    850           this->graph->first(e.e);
    851           while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    852             this->graph->next(e.e); }
    853         }
    854       } else {
    855         this->graph->next(e.e);
    856         while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    857           this->graph->next(e.e); }
    858       }
    859       return e;
    860     }
     921//     using GraphWrapper<Graph>::next;
     922// //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
     923//     OutEdgeIt& next(OutEdgeIt& e) const {
     924//       if (!e.backward) {
     925//      Node v=this->graph->aNode(e.out);
     926//      this->graph->next(e.out);
     927//      while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
     928//        this->graph->next(e.out); }
     929//      if (!this->graph->valid(e.out)) {
     930//        e.backward=true;
     931//        this->graph->first(e.in, v);
     932//        while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
     933//          this->graph->next(e.in); }
     934//      }
     935//       } else {
     936//      this->graph->next(e.in);
     937//      while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
     938//        this->graph->next(e.in); }
     939//       }
     940//       return e;
     941//     }
     942// //     FIXME Not tested
     943//     InEdgeIt& next(InEdgeIt& e) const {
     944//       if (!e.backward) {
     945//      Node v=this->graph->aNode(e.in);
     946//      this->graph->next(e.in);
     947//      while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
     948//        this->graph->next(e.in); }
     949//      if (!this->graph->valid(e.in)) {
     950//        e.backward=true;
     951//        this->graph->first(e.out, v);
     952//        while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
     953//          this->graph->next(e.out); }
     954//      }
     955//       } else {
     956//      this->graph->next(e.out);
     957//      while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
     958//        this->graph->next(e.out); }
     959//       }
     960//       return e;
     961//     }
     962//     EdgeIt& next(EdgeIt& e) const {
     963//       if (!e.backward) {
     964//      this->graph->next(e.e);
     965//      while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
     966//        this->graph->next(e.e); }
     967//      if (!this->graph->valid(e.e)) {
     968//        e.backward=true;
     969//        this->graph->first(e.e);
     970//        while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
     971//          this->graph->next(e.e); }
     972//      }
     973//       } else {
     974//      this->graph->next(e.e);
     975//      while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
     976//        this->graph->next(e.e); }
     977//       }
     978//       return e;
     979//     }
    861980
    862981    Node tail(Edge e) const {
    … …  
    865984      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
    866985
    867     Node aNode(OutEdgeIt e) const {
    868       return ((!e.backward) ? this->graph->aNode(e.out) :
    869               this->graph->aNode(e.in)); }
    870     Node bNode(OutEdgeIt e) const {
    871       return ((!e.backward) ? this->graph->bNode(e.out) :
    872               this->graph->bNode(e.in)); }
    873 
    874     Node aNode(InEdgeIt e) const {
    875       return ((!e.backward) ? this->graph->aNode(e.in) :
    876               this->graph->aNode(e.out)); }
    877     Node bNode(InEdgeIt e) const {
    878       return ((!e.backward) ? this->graph->bNode(e.in) :
    879               this->graph->bNode(e.out)); }
     986//     Node aNode(OutEdgeIt e) const {
     987//       return ((!e.backward) ? this->graph->aNode(e.out) :
     988//            this->graph->aNode(e.in)); }
     989//     Node bNode(OutEdgeIt e) const {
     990//       return ((!e.backward) ? this->graph->bNode(e.out) :
     991//            this->graph->bNode(e.in)); }
     992
     993//     Node aNode(InEdgeIt e) const {
     994//       return ((!e.backward) ? this->graph->aNode(e.in) :
     995//            this->graph->aNode(e.out)); }
     996//     Node bNode(InEdgeIt e) const {
     997//       return ((!e.backward) ? this->graph->bNode(e.in) :
     998//            this->graph->bNode(e.out)); }
    880999
    8811000    /// Gives back the opposite edge.
    … …  
    8941013//    int id(Node v) const { return graph->id(v); }
    8951014
    896     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    897     bool valid(Edge e) const {
    898       return this->graph->valid(e);
    899         //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
    900     }
     1015//     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
     1016//     bool valid(Edge e) const {
     1017//       return this->graph->valid(e);
     1018//      //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
     1019//     }
    9011020
    9021021    bool forward(const Edge& e) const { return !e.backward; }
    … …  
    9401059      typedef Edge KeyType;
    9411060      EdgeMap(const SubBidirGraphWrapper<Graph,
    942               ForwardFilterMap, BackwardFilterMap>& _G) :
    943         forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     1061              ForwardFilterMap, BackwardFilterMap>& g) :
     1062        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
    9441063      EdgeMap(const SubBidirGraphWrapper<Graph,
    945               ForwardFilterMap, BackwardFilterMap>& _G, T a) :
    946         forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     1064              ForwardFilterMap, BackwardFilterMap>& g, T a) :
     1065        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
    9471066      void set(Edge e, T a) {
    9481067        if (!e.backward)

  • src/hugo/list_graph.h

    r722 r774  
    132132    Node head(Edge e) const { return edges[e.n].head; }
    133133
    134     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
    135     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    136 
    137     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
    138     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    139 
    140134    NodeIt& first(NodeIt& v) const {
    141135      v=NodeIt(*this); return v; }
    … …  
    147141      e=InEdgeIt(*this,v); return e; }
    148142
    149 //     template< typename It >
    150 //     It first() const { It e; first(e); return e; }
    151 
    152 //     template< typename It >
    153 //     It first(Node v) const { It e; first(e,v); return e; }
    154 
    155     static bool valid(Edge e) { return e.n!=-1; }
    156     static bool valid(Node n) { return n.n!=-1; }
    157    
    158     static void setInvalid(Edge &e) { e.n=-1; }
    159     static void setInvalid(Node &n) { n.n=-1; }
    160    
    161     template <typename It> static It getNext(It it)
    162     { It tmp(it); return next(tmp); }
    163 
    164     NodeIt& next(NodeIt& it) const {
    165       it.n=nodes[it.n].next;
    166       return it;
    167     }
    168     OutEdgeIt& next(OutEdgeIt& it) const
    169     { it.n=edges[it.n].next_out; return it; }
    170     InEdgeIt& next(InEdgeIt& it) const
    171     { it.n=edges[it.n].next_in; return it; }
    172     EdgeIt& next(EdgeIt& it) const {
    173       if(edges[it.n].next_in!=-1) {
    174         it.n=edges[it.n].next_in;
    175       }
    176       else {
    177         int n;
    178         for(n=nodes[edges[it.n].head].next;
    179             n!=-1 && nodes[n].first_in == -1;
    180             n = nodes[n].next) ;
    181         it.n = (n==-1)?-1:nodes[n].first_in;
    182       }
    183       return it;
    184     }
    185 
    186143    static int id(Node v) { return v.n; }
    187144    static int id(Edge e) { return e.n; }
    … …  
    251208      return e;
    252209    }
    253 
     210   
     211    /// Finds an edge between two nodes.
     212
     213    /// Finds an edge from node \c u to node \c v.
     214    ///
     215    /// If \c prev is \ref INVALID (this is the default value), then
     216    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     217    /// the next edge from \c u to \c v after \c prev.
     218    /// \return The found edge or INVALID if there is no such an edge.
     219    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     220    {
     221      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
     222      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
     223      prev.n=e;
     224      return prev;
     225    }
     226   
    254227  private:
    255228    void eraseEdge(int n) {
    … …  
    325298      bool operator!=(const Node i) const {return n!=i.n;}
    326299      bool operator<(const Node i) const {return n<i.n;}
     300      //      ///Validity check
     301      //      operator bool() { return n!=-1; }
    327302    };
    328303   
    329304    class NodeIt : public Node {
     305      const ListGraph *G;
    330306      friend class ListGraph;
    331307    public:
    332308      NodeIt() : Node() { }
    333309      NodeIt(Invalid i) : Node(i) { }
    334       NodeIt(const ListGraph& G) : Node(G.first_node) { }
     310      NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
    335311      ///\todo Undocumented conversion Node -\> NodeIt.
    336       NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
     312      NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
     313      NodeIt &operator++() {
     314        n=G->nodes[n].next;
     315        return *this;
     316      }
     317      //      ///Validity check
     318      //      operator bool() { return Node::operator bool(); }     
    337319    };
    338320
    … …  
    365347      ///make class \c SymListGraph::SymEdgeMap friend of Edge
    366348      int &idref() {return n;}
    367       const int &idref() const {return n;}
    368     };
     349      const int &idref() const {return n;}
     350      //      ///Validity check
     351      //      operator bool() { return n!=-1; }
     352   };
    369353   
    370354    class EdgeIt : public Edge {
     355      const ListGraph *G;
    371356      friend class ListGraph;
    372357    public:
    373       EdgeIt(const ListGraph& G) : Edge() {
     358      EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
    374359        int m;
    375         for(m=G.first_node;
    376             m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
    377         n = (m==-1)?-1:G.nodes[m].first_in;
     360        for(m=_G.first_node;
     361            m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
     362        n = (m==-1)?-1:_G.nodes[m].first_in;
    378363      }
    379364      EdgeIt (Invalid i) : Edge(i) { }
     365      EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    380366      EdgeIt() : Edge() { }
    381367      ///\bug This is a workaround until somebody tells me how to
    382368      ///make class \c SymListGraph::SymEdgeMap friend of Edge
    383369      int &idref() {return n;}
     370      EdgeIt &operator++() {
     371        if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
     372        else {
     373          int nn;
     374          for(nn=G->nodes[G->edges[n].head].next;
     375              nn!=-1 && G->nodes[nn].first_in == -1;
     376              nn = G->nodes[nn].next) ;
     377          n = (nn==-1)?-1:G->nodes[nn].first_in;
     378        }
     379        return *this;
     380      }
     381      //      ///Validity check
     382      //      operator bool() { return Edge::operator bool(); }     
    384383    };
    385384   
    386385    class OutEdgeIt : public Edge {
     386      const ListGraph *G;
    387387      friend class ListGraph;
    388388    public:
    389389      OutEdgeIt() : Edge() { }
     390      OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    390391      OutEdgeIt (Invalid i) : Edge(i) { }
    391392
    392       OutEdgeIt(const ListGraph& G,const Node v)
    393         : Edge(G.nodes[v.n].first_out) {}
     393      OutEdgeIt(const ListGraph& _G,const Node v)
     394        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
     395      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
     396      //      ///Validity check
     397      //      operator bool() { return Edge::operator bool(); }     
    394398    };
    395399   
    396400    class InEdgeIt : public Edge {
     401      const ListGraph *G;
    397402      friend class ListGraph;
    398403    public:
    399404      InEdgeIt() : Edge() { }
     405      InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    400406      InEdgeIt (Invalid i) : Edge(i) { }
    401       InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
     407      InEdgeIt(const ListGraph& _G,Node v)
     408        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
     409      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
     410      //      ///Validity check
     411      //      operator bool() { return Edge::operator bool(); }     
    402412    };
    403413
    … …  
    839849    Node head(Edge e) const { return INVALID; }
    840850
    841     Node aNode(OutEdgeIt e) const { return INVALID; }
    842     Node aNode(InEdgeIt e) const { return INVALID; }
    843 
    844     Node bNode(OutEdgeIt e) const { return INVALID; }
    845     Node bNode(InEdgeIt e) const { return INVALID; }
    846 
    847851    NodeIt& first(NodeIt& v) const {
    848852      v=NodeIt(*this); return v; }
    … …  
    854858      e=InEdgeIt(*this,v); return e; }
    855859
    856 //     template< typename It >
    857 //     It first() const { It e; first(e); return e; }
    858 
    859 //     template< typename It >
    860 //     It first(Node v) const { It e; first(e,v); return e; }
    861 
    862     bool valid(Edge e) const { return false; }
    863     bool valid(Node n) const { return n.n!=-1; }
    864    
    865     void setInvalid(Edge &e) { }
    866     void setInvalid(Node &n) { n.n=-1; }
    867    
    868     template <typename It> It getNext(It it) const
    869     { It tmp(it); return next(tmp); }
    870 
    871     NodeIt& next(NodeIt& it) const {
    872       it.n=nodes[it.n].next;
    873       return it;
    874     }
    875     OutEdgeIt& next(OutEdgeIt& it) const { return it; }
    876     InEdgeIt& next(InEdgeIt& it) const { return it; }
    877     EdgeIt& next(EdgeIt& it) const { return it; }
    878 
    879860    int id(Node v) const { return v.n; }
    880861    int id(Edge e) const { return -1; }
    … …  
    928909    }
    929910   
     911       
     912    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     913    {
     914      return INVALID;
     915    }
     916   
    930917    ///\bug Dynamic maps must be updated!
    931918    ///
    … …  
    956943   
    957944    class NodeIt : public Node {
     945      const NodeSet *G;
    958946      friend class NodeSet;
    959947    public:
    960948      NodeIt() : Node() { }
     949      NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
    961950      NodeIt(Invalid i) : Node(i) { }
    962       NodeIt(const NodeSet& G) : Node(G.first_node) { }
    963       ///\todo Undocumented conversion Node -\> NodeIt.
    964       NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
    965 
     951      NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
     952      NodeIt &operator++() {
     953        n=G->nodes[n].next;
     954        return *this;
     955      }
    966956    };
    967957
    … …  
    994984    public:
    995985      EdgeIt(const NodeSet& G) : Edge() { }
     986      EdgeIt(const NodeSet&, Edge) : Edge() { }
    996987      EdgeIt (Invalid i) : Edge(i) { }
    997988      EdgeIt() : Edge() { }
    … …  
    999990      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
    1000991      //      int idref() {return -1;}
     992      EdgeIt operator++() { return INVALID; }
    1001993    };
    1002994   
    … …  
    1005997    public:
    1006998      OutEdgeIt() : Edge() { }
     999      OutEdgeIt(const NodeSet&, Edge) : Edge() { }
    10071000      OutEdgeIt (Invalid i) : Edge(i) { }
    10081001      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
     1002      OutEdgeIt operator++() { return INVALID; }
    10091003    };
    10101004   
    … …  
    10131007    public:
    10141008      InEdgeIt() : Edge() { }
     1009      InEdgeIt(const NodeSet&, Edge) : Edge() { }
    10151010      InEdgeIt (Invalid i) : Edge(i) { }
    10161011      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
     1012      InEdgeIt operator++() { return INVALID; }
    10171013    };
    10181014
    … …  
    12001196    public:
    12011197      NodeIt() : NodeGraphType::NodeIt() { }
     1198      NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
    12021199      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
    12031200      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
    12041201      NodeIt(const typename NodeGraphType::NodeIt &n)
    12051202        : NodeGraphType::NodeIt(n) {}
    1206       ///\todo Undocumented conversion Node -\> NodeIt.
    1207       NodeIt(const EdgeSet& _G, const Node &n)
    1208         : NodeGraphType::NodeIt(_G.G,n) { }
    12091203
    12101204      operator Node() { return Node(*this);}
     1205      NodeIt &operator++()
     1206      { this->NodeGraphType::NodeIt::operator++(); return *this;}
    12111207    };
    12121208
    … …  
    13111307    Node tail(Edge e) const { return edges[e.n].tail; }
    13121308    Node head(Edge e) const { return edges[e.n].head; }
    1313 
    1314     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
    1315     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    1316 
    1317     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
    1318     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    13191309
    13201310    NodeIt& first(NodeIt& v) const {
    … …  
    13271317      e=InEdgeIt(*this,v); return e; }
    13281318
    1329 //     template< typename It >
    1330 //     It first() const { It e; first(e); return e; }
    1331 
    1332 //     template< typename It >
    1333 //     It first(Node v) const { It e; first(e,v); return e; }
    1334 
    1335     bool valid(Edge e) const { return e.n!=-1; }
    1336     bool valid(Node n) const { return G.valid(n); }
    1337    
    1338     void setInvalid(Edge &e) { e.n=-1; }
    1339     void setInvalid(Node &n) { G.setInvalid(n); }
    1340    
    1341     template <typename It> It getNext(It it) const
    1342     { It tmp(it); return next(tmp); }
    1343 
    1344     NodeIt& next(NodeIt& it) const { G.next(it); return it; }
    1345     OutEdgeIt& next(OutEdgeIt& it) const
    1346     { it.n=edges[it.n].next_out; return it; }
    1347     InEdgeIt& next(InEdgeIt& it) const
    1348     { it.n=edges[it.n].next_in; return it; }
    1349     EdgeIt& next(EdgeIt& it) const {
    1350       if(edges[it.n].next_in!=-1) {
    1351         it.n=edges[it.n].next_in;
    1352       }
    1353       else {
    1354         NodeIt n(*this,edges[it.n].head);
    1355         for(n=next(n);
    1356             valid(n) && nodes[n].first_in == -1;
    1357             next(n)) ;
    1358         it.n = (valid(n))?-1:nodes[n].first_in;
    1359       }
    1360       return it;
    1361     }
    1362 
    13631319    int id(Edge e) const { return e.n; }
    13641320
    … …  
    13991355    }
    14001356
     1357    /// Finds an edge between two nodes.
     1358
     1359    /// Finds an edge from node \c u to node \c v.
     1360    ///
     1361    /// If \c prev is \ref INVALID (this is the default value), then
     1362    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     1363    /// the next edge from \c u to \c v after \c prev.
     1364    /// \return The found edge or INVALID if there is no such an edge.
     1365    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     1366    {
     1367      int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
     1368      while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
     1369      prev.n=e;
     1370      return prev;
     1371    }
     1372   
    14011373  private:
    14021374    void eraseEdge(int n) {
    … …  
    14611433      friend class NodeIt;
    14621434    public:
    1463       ///\bug It shoud be at least protected
     1435      ///\bug It should be at least protected
    14641436      ///
    14651437      int n;
    … …  
    14841456      template <typename T> friend class EdgeMap;
    14851457   
    1486      
    1487     public:
    1488       EdgeIt(const EdgeSet& G) : Edge() {
     1458      const EdgeSet *G;
     1459    public:
     1460      EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
    14891461        //              typename NodeGraphType::Node m;
    14901462        NodeIt m;
    1491         for(G.first(m);
    1492             G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
    1493         //AJJAJ! This is a non sense!!!!!!!
    1494         this->n = G.valid(m)?-1:G.nodes[m].first_in;
    1495       }
     1463        for(G->first(m);
     1464            m!=INVALID && G->nodes[m].first_in == -1;  ++m);
     1465        ///\bug AJJAJ! This is a non sense!!!!!!!
     1466        this->n = m!=INVALID?-1:G->nodes[m].first_in;
     1467      }
     1468      EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    14961469      EdgeIt (Invalid i) : Edge(i) { }
    14971470      EdgeIt() : Edge() { }
    1498       ///\bug This is a workaround until somebody tells me how to
     1471      ///.
     1472     
     1473      ///\bug UNIMPLEMENTED!!!!!
     1474      //
     1475      EdgeIt &operator++() {
     1476        return *this;
     1477      }
     1478       ///\bug This is a workaround until somebody tells me how to
    14991479      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
    15001480      int &idref() {return this->n;}
    … …  
    15021482   
    15031483    class OutEdgeIt : public Edge {
     1484      const EdgeSet *G;
    15041485      friend class EdgeSet;
    15051486    public:
    15061487      OutEdgeIt() : Edge() { }
    15071488      OutEdgeIt (Invalid i) : Edge(i) { }
    1508 
    1509       OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
     1489      OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
     1490
     1491      OutEdgeIt(const EdgeSet& _G,const Node v) :
     1492        Edge(_G.nodes[v].first_out), G(&_G) { }
     1493      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
    15101494    };
    15111495   
    15121496    class InEdgeIt : public Edge {
     1497      const EdgeSet *G;
    15131498      friend class EdgeSet;
    15141499    public:
    15151500      InEdgeIt() : Edge() { }
    15161501      InEdgeIt (Invalid i) : Edge(i) { }
    1517       InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
     1502      InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
     1503      InEdgeIt(const EdgeSet& _G,Node v)
     1504        : Edge(_G.nodes[v].first_in), G(&_G) { }
     1505      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
    15181506    };
    15191507
    … …  
    15551543        //FIXME: What if there are empty Id's?
    15561544        //FIXME: Can I use 'this' in a constructor?
    1557         G->dyn_edge_maps.push_back(this);
     1545        this->G->dyn_edge_maps.push_back(this);
    15581546      }
    15591547      EdgeMap(const EdgeSet &_G,const T &t) :
    15601548        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    15611549      {
    1562         G->dyn_edge_maps.push_back(this);
     1550        this->G->dyn_edge_maps.push_back(this);
    15631551      }
    15641552      EdgeMap(const EdgeMap<T> &m) :
    15651553        DynMapBase<Edge>(*m.G), container(m.container)
    15661554      {
    1567         G->dyn_edge_maps.push_back(this);
     1555        this->G->dyn_edge_maps.push_back(this);
    15681556      }
    15691557
    … …  
    15731561        DynMapBase<Edge>(*m.G), container(m.container.size())
    15741562      {
    1575         G->dyn_edge_maps.push_back(this);
     1563        this->G->dyn_edge_maps.push_back(this);
    15761564        typename std::vector<TT>::const_iterator i;
    15771565        for(typename std::vector<TT>::const_iterator i=m.container.begin();
    … …  
    15821570      ~EdgeMap()
    15831571      {
    1584         if(G) {
     1572        if(this->G) {
    15851573          typename std::vector<DynMapBase<Edge>* >::iterator i;
    1586           for(i=G->dyn_edge_maps.begin();
    1587               i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
     1574          for(i=this->G->dyn_edge_maps.begin();
     1575              i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ;
    15881576          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    15891577          //A better way to do that: (Is this really important?)
    15901578          if(*i==this) {
    1591             *i=G->dyn_edge_maps.back();
    1592             G->dyn_edge_maps.pop_back();
     1579            *i=this->G->dyn_edge_maps.back();
     1580            this->G->dyn_edge_maps.pop_back();
    15931581          }
    15941582        }
    … …  
    16031591      ///\bug This doesn't work. Why?
    16041592      ///      void set(Edge n, T a) { container[n.n]=a; }
    1605       void set(Edge n, T a) { container[G->id(n)]=a; }
     1593      void set(Edge n, T a) { container[this->G->id(n)]=a; }
    16061594      //T get(Edge n) const { return container[n.n]; }
    16071595      typename std::vector<T>::reference
    16081596      ///\bug This doesn't work. Why?
    16091597      ///      operator[](Edge n) { return container[n.n]; }
    1610       operator[](Edge n) { return container[G->id(n)]; }
     1598      operator[](Edge n) { return container[this->G->id(n)]; }
    16111599      typename std::vector<T>::const_reference
    16121600      ///\bug This doesn't work. Why?
    16131601      ///      operator[](Edge n) const { return container[n.n]; }
    1614       operator[](Edge n) const { return container[G->id(n)]; }
     1602      operator[](Edge n) const { return container[this->G->id(n)]; }
    16151603
    16161604      ///\warning There is no safety check at all!

  • src/hugo/max_flow.h

    r773 r774  
    66#include <queue>
    77
    8 #include <hugo/graph_wrapper.h>
     8//#include <hugo/graph_wrapper.h>
    99#include <hugo/invalid.h>
    1010#include <hugo/maps.h>
    … …  
    6363    FlowMap* flow;
    6464    int n;      //the number of nodes of G
    65     typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
     65    //    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
    6666    //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
    67     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    68     typedef typename ResGW::Edge ResGWEdge;
     67    //    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     68    //    typedef typename ResGW::Edge ResGWEdge;
    6969    typedef typename Graph::template NodeMap<int> ReachedMap;
    7070
    … …  
    113113    StatusEnum status;
    114114
    115 //     int number_of_augmentations;
    116 
    117 
    118 //     template<typename IntMap>
    119 //     class TrickyReachedMap {
    120 //     protected:
    121 //       IntMap* map;
    122 //       int* number_of_augmentations;
    123 //     public:
    124 //       TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
    125 //      map(&_map), number_of_augmentations(&_number_of_augmentations) { }
    126 //       void set(const Node& n, bool b) {
    127 //      if (b)
    128 //        map->set(n, *number_of_augmentations);
    129 //      else
    130 //        map->set(n, *number_of_augmentations-1);
    131 //       }
    132 //       bool operator[](const Node& n) const {
    133 //      return (*map)[n]==*number_of_augmentations;
    134 //       }
    135 //     };
     115    //     int number_of_augmentations;
     116
     117
     118    //     template<typename IntMap>
     119    //     class TrickyReachedMap {
     120    //     protected:
     121    //       IntMap* map;
     122    //       int* number_of_augmentations;
     123    //     public:
     124    //       TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
     125    //  map(&_map), number_of_augmentations(&_number_of_augmentations) { }
     126    //       void set(const Node& n, bool b) {
     127    //  if (b)
     128    //    map->set(n, *number_of_augmentations);
     129    //  else
     130    //    map->set(n, *number_of_augmentations-1);
     131    //       }
     132    //       bool operator[](const Node& n) const {
     133    //  return (*map)[n]==*number_of_augmentations;
     134    //       }
     135    //     };
    136136   
    137137    ///Constructor
    … …  
    235235        }
    236236
    237         if ( !g->valid(first[b]) ) --b;
     237        if ( first[b]==INVALID ) --b;
    238238        else {
    239239          end=false;
    … …  
    290290        int l=level[v]+1;
    291291
    292         InEdgeIt e;
    293         for(g->first(e,v); g->valid(e); g->next(e)) {
     292        for(InEdgeIt e(*g,v); e!=INVALID; ++e) {
    294293          if ( (*capacity)[e] <= (*flow)[e] ) continue;
    295294          Node u=g->tail(e);
    … …  
    304303        }
    305304
    306         OutEdgeIt f;
    307         for(g->first(f,v); g->valid(f); g->next(f)) {
    308           if ( 0 >= (*flow)[f] ) continue;
    309           Node u=g->head(f);
     305        for(OutEdgeIt e(*g,v); e!=INVALID; ++e) {
     306          if ( 0 >= (*flow)[e] ) continue;
     307          Node u=g->head(e);
    310308          if ( level[u] >= n ) {
    311309            bfs_queue.push(u);
    … …  
    324322        if ( b == 0 ) break;
    325323
    326         if ( !g->valid(first[b]) ) --b;
     324        if ( first[b]==INVALID ) --b;
    327325        else {
    328326
    … …  
    352350    /// It can be called already after running \ref preflowPhase1.
    353351    Num flowValue() const {
    354 //       Num a=0;
    355 //       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
    356 //       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
    357 //       return a;
     352      //       Num a=0;
     353      //       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
     354      //       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
     355      //       return a;
    358356      return excess[t];
    359357      //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
    … …  
    375373    template<typename _CutMap>
    376374    void actMinCut(_CutMap& M) const {
    377       NodeIt v;
    378375      switch (status) {
    379       case AFTER_PRE_FLOW_PHASE_1:
    380         for(g->first(v); g->valid(v); g->next(v)) {
     376        case AFTER_PRE_FLOW_PHASE_1:
     377        for(NodeIt v(*g); v!=INVALID; ++v) {
    381378          if (level[v] < n) {
    382379            M.set(v, false);
    … …  
    386383        }
    387384        break;
    388       case AFTER_PRE_FLOW_PHASE_2:
    389       case AFTER_NOTHING:
    390       case AFTER_AUGMENTING:
    391       case AFTER_FAST_AUGMENTING:
     385        case AFTER_PRE_FLOW_PHASE_2:
     386        case AFTER_NOTHING:
     387        case AFTER_AUGMENTING:
     388        case AFTER_FAST_AUGMENTING:
    392389        minMinCut(M);
    393390        break;
    … …  
    413410        queue.pop();
    414411
    415         OutEdgeIt e;
    416         for(g->first(e,w) ; g->valid(e); g->next(e)) {
     412        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    417413          Node v=g->head(e);
    418414          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    … …  
    422418        }
    423419
    424         InEdgeIt f;
    425         for(g->first(f,w) ; g->valid(f); g->next(f)) {
    426           Node v=g->tail(f);
    427           if (!M[v] && (*flow)[f] > 0 ) {
     420        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
     421          Node v=g->tail(e);
     422          if (!M[v] && (*flow)[e] > 0 ) {
    428423            queue.push(v);
    429424            M.set(v, true);
    … …  
    443438    void maxMinCut(_CutMap& M) const {
    444439
    445       NodeIt v;
    446       for(g->first(v) ; g->valid(v); g->next(v)) {
    447         M.set(v, true);
    448       }
     440      for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true);
    449441
    450442      std::queue<Node> queue;
    … …  
    457449        queue.pop();
    458450
    459         InEdgeIt e;
    460         for(g->first(e,w) ; g->valid(e); g->next(e)) {
     451        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    461452          Node v=g->tail(e);
    462453          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    … …  
    466457        }
    467458
    468         OutEdgeIt f;
    469         for(g->first(f,w) ; g->valid(f); g->next(f)) {
    470           Node v=g->head(f);
    471           if (M[v] && (*flow)[f] > 0 ) {
     459        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
     460          Node v=g->head(e);
     461          if (M[v] && (*flow)[e] > 0 ) {
    472462            queue.push(v);
    473463            M.set(v, false);
    … …  
    519509      int newlevel=n;       //bound on the next level of w
    520510
    521       OutEdgeIt e;
    522       for(g->first(e,w); g->valid(e); g->next(e)) {
    523 
     511      for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
    524512        if ( (*flow)[e] >= (*capacity)[e] ) continue;
    525513        Node v=g->head(e);
    526514
    527515        if( lev > level[v] ) { //Push is allowed now
    528 
     516         
    529517          if ( excess[v]<=0 && v!=t && v!=s ) {
    530518            next.set(v,first[level[v]]);
    … …  
    535523          Num flo=(*flow)[e];
    536524          Num remcap=cap-flo;
    537 
     525         
    538526          if ( remcap >= exc ) { //A nonsaturating push.
    539 
     527           
    540528            flow->set(e, flo+exc);
    541529            excess.set(v, excess[v]+exc);
    … …  
    552540
    553541      if ( exc > 0 ) {
    554         InEdgeIt e;
    555         for(g->first(e,w); g->valid(e); g->next(e)) {
    556 
     542        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
     543         
    557544          if( (*flow)[e] <= 0 ) continue;
    558545          Node v=g->tail(e);
    … …  
    585572
    586573      excess.set(w, exc);
    587 
     574     
    588575      return newlevel;
    589576    }
    590 
    591 
    592 
     577   
     578   
     579   
    593580    void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
    594581                        VecNode& level_list, NNMap& left, NNMap& right)
    595582    {
    596       switch (fe) { //setting excess
     583      switch (fe) {  //setting excess
    597584        case NO_FLOW:
     585        for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0);
     586        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
     587        break;
     588        case ZERO_FLOW:
     589        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
     590        break;
     591        case GEN_FLOW:
     592        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
    598593        {
    599           EdgeIt e;
    600           for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
    601          
    602           NodeIt v;
    603           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    604           break;
    605         }
    606         case ZERO_FLOW:
    607         {
    608           NodeIt v;
    609           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    610           break;
    611         }
    612         case GEN_FLOW:
    613         {
    614           NodeIt v;
    615           for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
    616 
    617594          Num exc=0;
    618           InEdgeIt e;
    619           for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    620           OutEdgeIt f;
    621           for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
     595          for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e];
     596          for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e];
    622597          excess.set(t,exc);
    623           break;
    624         }
    625         default: break;
    626       }
    627 
    628       NodeIt v;
    629       for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
     598        }
     599        break;
     600        default:
     601        break;
     602      }
     603     
     604      for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n);
    630605      //setting each node to level n
    631606     
    … …  
    636611      case NO_FLOW:   //flow is already set to const zero
    637612      case ZERO_FLOW:
    638         {
    639           //Reverse_bfs from t, to find the starting level.
    640           level.set(t,0);
    641           bfs_queue.push(t);
    642 
    643           while (!bfs_queue.empty()) {
    644 
    645             Node v=bfs_queue.front();
    646             bfs_queue.pop();
    647             int l=level[v]+1;
    648 
    649             InEdgeIt e;
    650             for(g->first(e,v); g->valid(e); g->next(e)) {
    651               Node w=g->tail(e);
    652               if ( level[w] == n && w != s ) {
    653                 bfs_queue.push(w);
    654                 Node z=level_list[l];
    655                 if ( g->valid(z) ) left.set(z,w);
    656                 right.set(w,z);
    657                 level_list[l]=w;
    658                 level.set(w, l);
    659               }
    660             }
    661           }
    662 
    663           //the starting flow
    664           OutEdgeIt e;
    665           for(g->first(e,s); g->valid(e); g->next(e))
     613        //Reverse_bfs from t, to find the starting level.
     614        level.set(t,0);
     615        bfs_queue.push(t);
     616       
     617        while (!bfs_queue.empty()) {
     618         
     619          Node v=bfs_queue.front();
     620          bfs_queue.pop();
     621          int l=level[v]+1;
     622         
     623          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     624            Node w=g->tail(e);
     625            if ( level[w] == n && w != s ) {
     626              bfs_queue.push(w);
     627              Node z=level_list[l];
     628              if ( z!=INVALID ) left.set(z,w);
     629              right.set(w,z);
     630              level_list[l]=w;
     631              level.set(w, l);
     632            }
     633          }
     634        }
     635       
     636        //the starting flow
     637        for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e)
     638          {
     639            Num c=(*capacity)[e];
     640            if ( c <= 0 ) continue;
     641            Node w=g->head(e);
     642            if ( level[w] < n ) {
     643              if ( excess[w] <= 0 && w!=t ) //putting into the stack
     644                {
     645                  next.set(w,first[level[w]]);
     646                  first[level[w]]=w;
     647                }
     648              flow->set(e, c);
     649              excess.set(w, excess[w]+c);
     650            }
     651          }
     652        break;
     653      case GEN_FLOW:
     654        //Reverse_bfs from t in the residual graph,
     655        //to find the starting level.
     656        level.set(t,0);
     657        bfs_queue.push(t);
     658       
     659        while (!bfs_queue.empty()) {
     660         
     661          Node v=bfs_queue.front();
     662          bfs_queue.pop();
     663          int l=level[v]+1;
     664         
     665          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     666            if ( (*capacity)[e] <= (*flow)[e] ) continue;
     667            Node w=g->tail(e);
     668            if ( level[w] == n && w != s ) {
     669              bfs_queue.push(w);
     670              Node z=level_list[l];
     671              if ( z!=INVALID ) left.set(z,w);
     672              right.set(w,z);
     673              level_list[l]=w;
     674              level.set(w, l);
     675            }
     676          }
     677         
     678          for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     679            if ( 0 >= (*flow)[e] ) continue;
     680            Node w=g->head(e);
     681            if ( level[w] == n && w != s ) {
     682              bfs_queue.push(w);
     683              Node z=level_list[l];
     684              if ( z!=INVALID ) left.set(z,w);
     685              right.set(w,z);
     686              level_list[l]=w;
     687              level.set(w, l);
     688            }
     689          }
     690        }
     691       
     692        //the starting flow
     693        for(OutEdgeIt e(*g,s); e!=INVALID; ++e)
     694          {
     695            Num rem=(*capacity)[e]-(*flow)[e];
     696            if ( rem <= 0 ) continue;
     697            Node w=g->head(e);
     698            if ( level[w] < n ) {
     699              if ( excess[w] <= 0 && w!=t ) //putting into the stack
     700                {
     701                  next.set(w,first[level[w]]);
     702                  first[level[w]]=w;
     703                }   
     704              flow->set(e, (*capacity)[e]);
     705              excess.set(w, excess[w]+rem);
     706            }
     707          }
     708       
     709        for(InEdgeIt e(*g,s); e!=INVALID; ++e)
     710          {
     711            if ( (*flow)[e] <= 0 ) continue;
     712            Node w=g->tail(e);
     713            if ( level[w] < n ) {
     714              if ( excess[w] <= 0 && w!=t )
     715                {
     716                  next.set(w,first[level[w]]);
     717                  first[level[w]]=w;
     718                } 
     719              excess.set(w, excess[w]+(*flow)[e]);
     720              flow->set(e, 0);
     721            }
     722          }
     723        break;
     724      case PRE_FLOW:
     725        //Reverse_bfs from t in the residual graph,
     726        //to find the starting level.
     727        level.set(t,0);
     728        bfs_queue.push(t);
     729       
     730        while (!bfs_queue.empty()) {
     731         
     732          Node v=bfs_queue.front();
     733          bfs_queue.pop();
     734          int l=level[v]+1;
     735         
     736          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     737            if ( (*capacity)[e] <= (*flow)[e] ) continue;
     738            Node w=g->tail(e);
     739            if ( level[w] == n && w != s ) {
     740              bfs_queue.push(w);
     741              Node z=level_list[l];
     742              if ( z!=INVALID ) left.set(z,w);
     743              right.set(w,z);
     744              level_list[l]=w;
     745              level.set(w, l);
     746            }
     747          }
     748         
     749          for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
     750            if ( 0 >= (*flow)[e] ) continue;
     751            Node w=g->head(e);
     752            if ( level[w] == n && w != s ) {
     753              bfs_queue.push(w);
     754              Node z=level_list[l];
     755              if ( z!=INVALID ) left.set(z,w);
     756              right.set(w,z);
     757              level_list[l]=w;
     758              level.set(w, l);
     759            }
     760          }
     761        }
     762       
     763       
     764        //the starting flow
     765        for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) {
     766          Num rem=(*capacity)[e]-(*flow)[e];
     767          if ( rem <= 0 ) continue;
     768          Node w=g->head(e);
     769          if ( level[w] < n ) {
     770            flow->set(e, (*capacity)[e]);
     771            excess.set(w, excess[w]+rem);
     772          }
     773        }
     774       
     775        for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) {
     776          if ( (*flow)[e] <= 0 ) continue;
     777          Node w=g->tail(e);
     778          if ( level[w] < n ) {
     779            excess.set(w, excess[w]+(*flow)[e]);
     780            flow->set(e, 0);
     781          }
     782        }
     783       
     784        //computing the excess
     785        for(NodeIt w(*g); w!=INVALID; ++w) {
     786          Num exc=0;
     787         
     788          for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) exc+=(*flow)[e];
     789          for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) exc-=(*flow)[e];
     790         
     791          excess.set(w,exc);
     792         
     793          //putting the active nodes into the stack
     794          int lev=level[w];
     795            if ( exc > 0 && lev < n && Node(w) != t )
     796              ///\bug       if ( exc > 0 && lev < n && w != t ) temporarily for working with wrappers.
    666797            {
    667               Num c=(*capacity)[e];
    668               if ( c <= 0 ) continue;
    669               Node w=g->head(e);
    670               if ( level[w] < n ) {
    671                 if ( excess[w] <= 0 && w!=t ) //putting into the stack
    672                   {
    673                     next.set(w,first[level[w]]);
    674                     first[level[w]]=w;
    675                   }
    676                 flow->set(e, c);
    677                 excess.set(w, excess[w]+c);
    678               }
    679             }
    680           break;
    681         }
    682 
    683       case GEN_FLOW:
    684         {
    685           //Reverse_bfs from t in the residual graph,
    686           //to find the starting level.
    687           level.set(t,0);
    688           bfs_queue.push(t);
    689 
    690           while (!bfs_queue.empty()) {
    691 
    692             Node v=bfs_queue.front();
    693             bfs_queue.pop();
    694             int l=level[v]+1;
    695 
    696             InEdgeIt e;
    697             for(g->first(e,v); g->valid(e); g->next(e)) {
    698               if ( (*capacity)[e] <= (*flow)[e] ) continue;
    699               Node w=g->tail(e);
    700               if ( level[w] == n && w != s ) {
    701                 bfs_queue.push(w);
    702                 Node z=level_list[l];
    703                 if ( g->valid(z) ) left.set(z,w);
    704                 right.set(w,z);
    705                 level_list[l]=w;
    706                 level.set(w, l);
    707               }
    708             }
    709 
    710             OutEdgeIt f;
    711             for(g->first(f,v); g->valid(f); g->next(f)) {
    712               if ( 0 >= (*flow)[f] ) continue;
    713               Node w=g->head(f);
    714               if ( level[w] == n && w != s ) {
    715                 bfs_queue.push(w);
    716                 Node z=level_list[l];
    717                 if ( g->valid(z) ) left.set(z,w);
    718                 right.set(w,z);
    719                 level_list[l]=w;
    720                 level.set(w, l);
    721               }
    722             }
    723           }
    724 
    725           //the starting flow
    726           OutEdgeIt e;
    727           for(g->first(e,s); g->valid(e); g->next(e))
    728             {
    729               Num rem=(*capacity)[e]-(*flow)[e];
    730               if ( rem <= 0 ) continue;
    731               Node w=g->head(e);
    732               if ( level[w] < n ) {
    733                 if ( excess[w] <= 0 && w!=t ) //putting into the stack
    734                   {
    735                     next.set(w,first[level[w]]);
    736                     first[level[w]]=w;
    737                   }   
    738                 flow->set(e, (*capacity)[e]);
    739                 excess.set(w, excess[w]+rem);
    740               }
    741             }
    742 
    743           InEdgeIt f;
    744           for(g->first(f,s); g->valid(f); g->next(f))
    745             {
    746               if ( (*flow)[f] <= 0 ) continue;
    747               Node w=g->tail(f);
    748               if ( level[w] < n ) {
    749                 if ( excess[w] <= 0 && w!=t )
    750                   {
    751                     next.set(w,first[level[w]]);
    752                     first[level[w]]=w;
    753                   } 
    754                 excess.set(w, excess[w]+(*flow)[f]);
    755                 flow->set(f, 0);
    756               }
    757             }
    758           break;
    759         } //case GEN_FLOW
    760    
    761       case PRE_FLOW:
    762         {
    763           //Reverse_bfs from t in the residual graph,
    764           //to find the starting level.
    765           level.set(t,0);
    766           bfs_queue.push(t);
    767 
    768           while (!bfs_queue.empty()) {
    769 
    770             Node v=bfs_queue.front();
    771             bfs_queue.pop();
    772             int l=level[v]+1;
    773 
    774             InEdgeIt e;
    775             for(g->first(e,v); g->valid(e); g->next(e)) {
    776               if ( (*capacity)[e] <= (*flow)[e] ) continue;
    777               Node w=g->tail(e);
    778               if ( level[w] == n && w != s ) {
    779                 bfs_queue.push(w);
    780                 Node z=level_list[l];
    781                 if ( g->valid(z) ) left.set(z,w);
    782                 right.set(w,z);
    783                 level_list[l]=w;
    784                 level.set(w, l);
    785               }
    786             }
    787 
    788             OutEdgeIt f;
    789             for(g->first(f,v); g->valid(f); g->next(f)) {
    790               if ( 0 >= (*flow)[f] ) continue;
    791               Node w=g->head(f);
    792               if ( level[w] == n && w != s ) {
    793                 bfs_queue.push(w);
    794                 Node z=level_list[l];
    795                 if ( g->valid(z) ) left.set(z,w);
    796                 right.set(w,z);
    797                 level_list[l]=w;
    798                 level.set(w, l);
    799               }
    800             }
    801           }
    802 
    803 
    804           //the starting flow
    805           OutEdgeIt e;
    806           for(g->first(e,s); g->valid(e); g->next(e))
    807             {
    808               Num rem=(*capacity)[e]-(*flow)[e];
    809               if ( rem <= 0 ) continue;
    810               Node w=g->head(e);
    811               if ( level[w] < n ) {
    812                 flow->set(e, (*capacity)[e]);
    813                 excess.set(w, excess[w]+rem);
    814               }
    815             }
    816 
    817           InEdgeIt f;
    818           for(g->first(f,s); g->valid(f); g->next(f))
    819             {
    820               if ( (*flow)[f] <= 0 ) continue;
    821               Node w=g->tail(f);
    822               if ( level[w] < n ) {
    823                 excess.set(w, excess[w]+(*flow)[f]);
    824                 flow->set(f, 0);
    825               }
    826             }
    827          
    828           NodeIt w; //computing the excess
    829           for(g->first(w); g->valid(w); g->next(w)) {
    830             Num exc=0;
    831 
    832             InEdgeIt e;
    833             for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
    834             OutEdgeIt f;
    835             for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
    836 
    837             excess.set(w,exc);
    838 
    839             //putting the active nodes into the stack
    840             int lev=level[w];
    841             if ( exc > 0 && lev < n && Node(w) != t )
    842 ///\bug     if ( exc > 0 && lev < n && w != t ) tempararily for working with wrappers. in hugo 0.2 it will work. Amugy mukodik sage_graph-fal, de smart_graph-fal nem, azt hozzatennem.
    843               {
    844                 next.set(w,first[lev]);
    845                 first[lev]=w;
    846               }
    847           }
    848           break;
    849         } //case PRE_FLOW
    850       }
     798              next.set(w,first[lev]);
     799              first[lev]=w;
     800            }
     801        }
     802        break;
     803      } //switch
    851804    } //preflowPreproc
    852805
    … …  
    863816
    864817      //unlacing starts
    865       if ( g->valid(right_n) ) {
    866         if ( g->valid(left_n) ) {
     818      if ( right_n!=INVALID ) {
     819        if ( left_n!=INVALID ) {
    867820          right.set(left_n, right_n);
    868821          left.set(right_n, left_n);
    … …  
    872825        }
    873826      } else {
    874         if ( g->valid(left_n) ) {
     827        if ( left_n!=INVALID ) {
    875828          right.set(left_n, INVALID);
    876829        } else {
    … …  
    880833      //unlacing ends
    881834
    882       if ( !g->valid(level_list[lev]) ) {
     835      if ( level_list[lev]==INVALID ) {
    883836
    884837        //gapping starts
    885838        for (int i=lev; i!=k ; ) {
    886839          Node v=level_list[++i];
    887           while ( g->valid(v) ) {
     840          while ( v!=INVALID ) {
    888841            level.set(v,n);
    889842            v=right[v];
    … …  
    908861          if ( k < newlevel ) ++k;      //now k=newlevel
    909862          Node z=level_list[newlevel];
    910           if ( g->valid(z) ) left.set(z,w);
     863          if ( z!=INVALID ) left.set(z,w);
    911864          right.set(w,z);
    912865          left.set(w,INVALID);
    … …  
    919872      std::cout << "Excesses:" <<std::endl;
    920873
    921       NodeIt v;
    922       for(g->first(v); g->valid(v); g->next(v)) {
     874      for(NodeIt v(*g); v!=INVALID ; ++v) {
    923875        std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl;
    924876      }
    925877    }
    926878
    927  void printlevel() {////
     879    void printlevel() {////
    928880      std::cout << "Levels:" <<std::endl;
    929881
    930       NodeIt v;
    931       for(g->first(v); g->valid(v); g->next(v)) {
     882      for(NodeIt v(*g); v!=INVALID ; ++v) {
    932883        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
    933884      }
    934885    }
    935886
    936 void printactive() {////
     887    void printactive() {////
    937888      std::cout << "Levels:" <<std::endl;
    938889
    939       NodeIt v;
    940       for(g->first(v); g->valid(v); g->next(v)) {
     890      for(NodeIt v(*g); v!=INVALID ; ++v) {
    941891        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
    942892      }

  • src/hugo/skeletons/graph.h

    r732 r774  
    3535    public:
    3636      /// Defalult constructor.
    37       StaticGraphSkeleton() {}
     37      StaticGraphSkeleton() { }
    3838      ///Copy consructor.
    3939
    4040      ///\todo It is not clear, what we expect from a copy constructor.
    4141      ///E.g. How to assign the nodes/edges to each other? What about maps?
    42       StaticGraphSkeleton(const StaticGraphSkeleton &G) {}
    43 
    44       /// The base type of the node iterators.
    45 
    46       /// This is the base type of each node iterators,
    47       /// thus each kind of node iterator will convert to this.
     42      StaticGraphSkeleton(const StaticGraphSkeleton& g) { }
     43
     44      /// The base type of node iterators,
     45      /// or in other words, the trivial node iterator.
     46
     47      /// This is the base type of each node iterator,
     48      /// thus each kind of node iterator converts to this.
     49      /// More precisely each kind of node iterator have to be inherited
     50      /// from the trivial node iterator.
    4851      class Node {
    4952      public:
    5053        /// @warning The default constructor sets the iterator
    5154        /// to an undefined value.
    52         Node() {}   //FIXME
     55        Node() { }
     56        /// Copy constructor.
     57        Node(const Node&) { }
    5358        /// Invalid constructor \& conversion.
    5459
    5560        /// This constructor initializes the iterator to be invalid.
    5661        /// \sa Invalid for more details.
    57 
    58         Node(Invalid) {}
    59         //Node(const Node &) {}
    60 
     62        Node(Invalid) { }
    6163        /// Two iterators are equal if and only if they point to the
    6264        /// same object or both are invalid.
    … …  
    7476      /// This iterator goes through each node.
    7577      /// Its usage is quite simple, for example you can count the number
    76       /// of nodes in graph \c G of type \c Graph like this:
     78      /// of nodes in graph \c g of type \c Graph like this:
    7779      /// \code
    78       ///int count=0;
    79       ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
     80      /// int count=0;
     81      /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count;
    8082      /// \endcode
    8183      class NodeIt : public Node {
    … …  
    8385        /// @warning The default constructor sets the iterator
    8486        /// to an undefined value.
    85         NodeIt() {} //FIXME
     87        NodeIt() { }
     88        /// Copy constructor.
     89        NodeIt(const NodeIt&) { }
    8690        /// Invalid constructor \& conversion.
    8791
    88         /// Initialize the iterator to be invalid
     92        /// Initialize the iterator to be invalid.
    8993        /// \sa Invalid for more details.
    90         NodeIt(Invalid) {}
    91         /// Sets the iterator to the first node of \c G.
    92         NodeIt(const StaticGraphSkeleton &) {}
    93         /// @warning The default constructor sets the iterator
    94         /// to an undefined value.
    95         NodeIt(const NodeIt &n) : Node(n) {}
     94        NodeIt(Invalid) { }
     95        /// Sets the iterator to the first node of \c g.
     96        NodeIt(const StaticGraphSkeleton& g) { }
     97        /// Sets the iterator to the node of \c g pointed by the trivial
     98        /// iterator n. This feature necessitates that each time we
     99        /// iterate the node-set, the iteration order is the same.
     100        NodeIt(const StaticGraphSkeleton& g, const Node& n) { }
     101        /// Assign the iterator to the next node.
     102        NodeIt& operator++() { return *this; }
    96103      };
    97104   
    … …  
    102109        /// @warning The default constructor sets the iterator
    103110        /// to an undefined value.
    104         Edge() {}   //FIXME
    105         /// Initialize the iterator to be invalid
    106         Edge(Invalid) {}
     111        Edge() { }
     112        /// Copy constructor.
     113        Edge(const Edge&) { }
     114        /// Initialize the iterator to be invalid.
     115        Edge(Invalid) { }
    107116        /// Two iterators are equal if and only if they point to the
    108117        /// same object or both are invalid.
    … …  
    118127      /// Its usage is quite simple, for example you can count the number
    119128      /// of outgoing edges of a node \c n
    120       /// in graph \c G of type \c Graph as follows.
     129      /// in graph \c g of type \c Graph as follows.
    121130      /// \code
    122       ///int count=0;
    123       ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
     131      /// int count=0;
     132      /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count;
    124133      /// \endcode
    125134   
    … …  
    128137        /// @warning The default constructor sets the iterator
    129138        /// to an undefined value.
    130         OutEdgeIt() {}
    131         /// Initialize the iterator to be invalid
    132         OutEdgeIt(Invalid) {}
     139        OutEdgeIt() { }
     140        /// Copy constructor.
     141        OutEdgeIt(const OutEdgeIt&) { }
     142        /// Initialize the iterator to be invalid.
     143        OutEdgeIt(Invalid) { }
    133144        /// This constructor sets the iterator to first outgoing edge.
    134145   
    … …  
    136147        /// node
    137148        ///@param n the node
    138         ///@param G the graph
    139         OutEdgeIt(const StaticGraphSkeleton &, Node) {}
     149        ///@param g the graph
     150        OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { }
     151        /// Sets the iterator to the value of the trivial iterator \c e.
     152        /// This feature necessitates that each time we
     153        /// iterate the edge-set, the iteration order is the same.
     154        OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { }
     155        /// Assign the iterator to the next outedge of the corresponding node.
     156        OutEdgeIt& operator++() { return *this; }
    140157      };
    141158
    … …  
    146163      /// Its usage is quite simple, for example you can count the number
    147164      /// of outgoing edges of a node \c n
    148       /// in graph \c G of type \c Graph as follows.
     165      /// in graph \c g of type \c Graph as follows.
    149166      /// \code
    150       ///int count=0;
    151       ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
     167      /// int count=0;
     168      /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count;
    152169      /// \endcode
    153170
    … …  
    156173        /// @warning The default constructor sets the iterator
    157174        /// to an undefined value.
    158         InEdgeIt() {}
    159         /// Initialize the iterator to be invalid
    160         InEdgeIt(Invalid) {}
    161         InEdgeIt(const StaticGraphSkeleton &, Node) {}   
     175        InEdgeIt() { }
     176        /// Copy constructor.
     177        InEdgeIt(const InEdgeIt&) { }
     178        /// Initialize the iterator to be invalid.
     179        InEdgeIt(Invalid) { }
     180        /// .
     181        InEdgeIt(const StaticGraphSkeleton&, const Node&) { }
     182        /// .
     183        InEdgeIt(const StaticGraphSkeleton&, const Edge&) { }
     184        /// Assign the iterator to the next inedge of the corresponding node.
     185        InEdgeIt& operator++() { return *this; }
    162186      };
    163187      //  class SymEdgeIt : public Edge {};
    … …  
    167191      /// This iterator goes through each edge of a graph.
    168192      /// Its usage is quite simple, for example you can count the number
    169       /// of edges in a graph \c G of type \c Graph as follows:
     193      /// of edges in a graph \c g of type \c Graph as follows:
    170194      /// \code
    171       ///int count=0;
    172       ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
     195      /// int count=0;
     196      /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count;
    173197      /// \endcode
    174198      class EdgeIt : public Edge {
    … …  
    176200        /// @warning The default constructor sets the iterator
    177201        /// to an undefined value.
    178         EdgeIt() {}
    179         /// Initialize the iterator to be invalid
    180         EdgeIt(Invalid) {}
    181         EdgeIt(const StaticGraphSkeleton &) {}
     202        EdgeIt() { }
     203        /// Copy constructor.
     204        EdgeIt(const EdgeIt&) { }
     205        /// Initialize the iterator to be invalid.
     206        EdgeIt(Invalid) { }
     207        /// .
     208        EdgeIt(const StaticGraphSkeleton&) { }
     209        /// .
     210        EdgeIt(const StaticGraphSkeleton&, const Edge&) { }
     211        EdgeIt& operator++() { return *this; }
    182212      };
    183213
    … …  
    187217      /// \return the first node.
    188218      ///
    189       NodeIt &first(NodeIt &i) const { return i;}
     219      NodeIt& first(NodeIt& i) const { return i; }
    190220
    191221      /// The first incoming edge.
    192       InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
     222      InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
    193223      /// The first outgoing edge.
    194       OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
    195       //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
     224      OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
     225      //  SymEdgeIt& first(SymEdgeIt&, Node) const { return i; }
    196226      /// The first edge of the Graph.
    197       EdgeIt &first(EdgeIt &i) const { return i;}
     227      EdgeIt& first(EdgeIt& i) const { return i; }
    198228
    199229      //     Node getNext(Node) const {}
    … …  
    204234
    205235      /// Go to the next node.
    206       NodeIt &next(NodeIt &i) const { return i;}
     236      NodeIt& next(NodeIt& i) const { return i; }
    207237      /// Go to the next incoming edge.
    208       InEdgeIt &next(InEdgeIt &i) const { return i;}
     238      InEdgeIt& next(InEdgeIt& i) const { return i; }
    209239      /// Go to the next outgoing edge.
    210       OutEdgeIt &next(OutEdgeIt &i) const { return i;}
    211       //SymEdgeIt &next(SymEdgeIt &) const {}
     240      OutEdgeIt& next(OutEdgeIt& i) const { return i; }
     241      //SymEdgeIt& next(SymEdgeIt&) const { }
    212242      /// Go to the next edge.
    213       EdgeIt &next(EdgeIt &i) const { return i;}
     243      EdgeIt& next(EdgeIt& i) const { return i; }
    214244
    215245      ///Gives back the head node of an edge.
    … …  
    230260      ///\todo Maybe, it would be better if iterator converted to
    231261      ///bool directly, as Jacint prefers.
    232       bool valid(const Node&) const { return true;}
     262      bool valid(const Node&) const { return true; }
    233263      /// Checks if an edge iterator is valid
    234264
    235265      ///\todo Maybe, it would be better if iterator converted to
    236266      ///bool directly, as Jacint prefers.
    237       bool valid(const Edge&) const { return true;}
     267      bool valid(const Edge&) const { return true; }
    238268
    239269      ///Gives back the \e id of a node.
    … …  
    241271      ///\warning Not all graph structures provide this feature.
    242272      ///
    243       int id(const Node&) const { return 0;}
     273      int id(const Node&) const { return 0; }
    244274      ///Gives back the \e id of an edge.
    245275
    246276      ///\warning Not all graph structures provide this feature.
    247277      ///
    248       int id(const Edge&) const { return 0;}
     278      int id(const Edge&) const { return 0; }
    249279
    250280      /// Resets the graph.
    … …  
    252282      /// This function deletes all edges and nodes of the graph.
    253283      /// It also frees the memory allocated to store them.
    254       void clear() {}
    255 
    256       int nodeNum() const { return 0;}
    257       int edgeNum() const { return 0;}
    258 
     284      void clear() { }
     285
     286      int nodeNum() const { return 0; }
     287      int edgeNum() const { return 0; }
    259288
    260289
    … …  
    271300      public:
    272301
    273         class ReferenceMap<Node,T>;
    274 
    275         NodeMap(const StaticGraphSkeleton &) {}
    276         NodeMap(const StaticGraphSkeleton &, T) {}
     302        NodeMap(const StaticGraphSkeleton&) { }
     303        NodeMap(const StaticGraphSkeleton&, T) { }
    277304
    278305        ///Copy constructor
    279         template<typename TT> NodeMap(const NodeMap<TT> &) {}
     306        template<typename TT> NodeMap(const NodeMap<TT>&) { }
    280307        ///Assignment operator
    281         template<typename TT> NodeMap &operator=(const NodeMap<TT> &)
    282         {return *this;}
     308        template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
     309        { return *this; }
    283310      };
    284311
    … …  
    296323        typedef Edge KeyType;
    297324
    298         EdgeMap(const StaticGraphSkeleton &) {}
    299         EdgeMap(const StaticGraphSkeleton &, T ) {}
     325        EdgeMap(const StaticGraphSkeleton&) { }
     326        EdgeMap(const StaticGraphSkeleton&, T) { }
    300327   
    301328        ///Copy constructor
    302         template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
     329        template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
    303330        ///Assignment operator
    304         template<typename TT> EdgeMap &operator=(const EdgeMap<TT> &)
    305         {return *this;}
     331        template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
     332        { return *this; }
    306333      };
    307334    };
    … …  
    318345    public:
    319346      /// Defalult constructor.
    320       GraphSkeleton() {}
     347      GraphSkeleton() { }
    321348      ///Copy consructor.
    322349
    323350      ///\todo It is not clear, what we expect from a copy constructor.
    324351      ///E.g. How to assign the nodes/edges to each other? What about maps?
    325       GraphSkeleton(const GraphSkeleton &G) {}
     352      GraphSkeleton(const GraphSkeleton&) { }
    326353
    327354      ///Add a new node to the graph.
    … …  
    329356      /// \return the new node.
    330357      ///
    331       Node addNode() { return INVALID;}
     358      Node addNode() { return INVALID; }
    332359      ///Add a new edge to the graph.
    333360
    … …  
    335362      ///and head node \c head.
    336363      ///\return the new edge.
    337       Edge addEdge(Node, Node) { return INVALID;}
     364      Edge addEdge(Node, Node) { return INVALID; }
    338365   
    339366      /// Resets the graph.
    … …  
    342369      /// It also frees the memory allocated to store them.
    343370      /// \todo It might belong to \c EraseableGraphSkeleton.
    344       void clear() {}
     371      void clear() { }
    345372    };
    346373
    … …  
    353380    public:
    354381      /// Deletes a node.
    355       void erase(Node n) {}
     382      void erase(Node n) { }
    356383      /// Deletes an edge.
    357       void erase(Edge e) {}
     384      void erase(Edge e) { }
    358385
    359386      /// Defalult constructor.
    360       EraseableGraphSkeleton() {}
     387      EraseableGraphSkeleton() { }
    361388      ///Copy consructor.
    362       EraseableGraphSkeleton(const GraphSkeleton &G) {}
     389      EraseableGraphSkeleton(const GraphSkeleton&) { }
    363390    };
    364391

  • src/hugo/smart_graph.h

    r753 r774  
    122122    Node head(Edge e) const { return edges[e.n].head; }
    123123
    124     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
    125     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    126 
    127     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
    128     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    129 
    130124    NodeIt& first(NodeIt& v) const {
    131125      v=NodeIt(*this); return v; }
    … …  
    137131      e=InEdgeIt(*this,v); return e; }
    138132
    139 //     template< typename It >
    140 //     It first() const { It e; first(e); return e; }
    141 
    142 //     template< typename It >
    143 //     It first(Node v) const { It e; first(e,v); return e; }
    144 
    145     static bool valid(Edge e) { return e.n!=-1; }
    146     static bool valid(Node n) { return n.n!=-1; }
    147    
    148     ///\deprecated Use
    149     ///\code
    150     ///  e=INVALID;
    151     ///\endcode
    152     ///instead.
    153     static void setInvalid(Edge &e) { e.n=-1; }
    154     ///\deprecated Use
    155     ///\code
    156     ///  e=INVALID;
    157     ///\endcode
    158     ///instead.
    159     static void setInvalid(Node &n) { n.n=-1; }
    160    
    161     template <typename It> It getNext(It it) const
    162     { It tmp(it); return next(tmp); }
    163 
    164     NodeIt& next(NodeIt& it) const {
    165       it.n=(it.n+2)%(nodes.size()+1)-1;
    166       return it;
    167     }
    168     OutEdgeIt& next(OutEdgeIt& it) const
    169     { it.n=edges[it.n].next_out; return it; }
    170     InEdgeIt& next(InEdgeIt& it) const
    171     { it.n=edges[it.n].next_in; return it; }
    172     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
    173 
    174133    static int id(Node v) { return v.n; }
    175134    static int id(Edge e) { return e.n; }
    … …  
    198157    }
    199158
     159    /// Finds an edge between two nodes.
     160
     161    /// Finds an edge from node \c u to node \c v.
     162    ///
     163    /// If \c prev is \ref INVALID (this is the default value), then
     164    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     165    /// the next edge from \c u to \c v after \c prev.
     166    /// \return The found edge or INVALID if there is no such an edge.
     167    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     168    {
     169      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
     170      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
     171      prev.n=e;
     172      return prev;
     173    }
     174   
    200175    void clear() {nodes.clear();edges.clear();}
    201176
    … …  
    219194      bool operator!=(const Node i) const {return n!=i.n;}
    220195      bool operator<(const Node i) const {return n<i.n;}
     196      //      ///Validity check
     197      //      operator bool() { return n!=-1; }
    221198    };
    222199   
    223200    class NodeIt : public Node {
     201      const SmartGraph *G;
    224202      friend class SmartGraph;
    225203    public:
    226204      NodeIt() : Node() { }
     205      NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
    227206      NodeIt(Invalid i) : Node(i) { }
    228       NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
    229       ///\todo Undocumented conversion Node -\> NodeIt.
    230       NodeIt(const SmartGraph& G, const Node &n) : Node(n) { }
     207      NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
     208      NodeIt &operator++() {
     209        n=(n+2)%(G->nodes.size()+1)-1;
     210        return *this;
     211      }
     212//       ///Validity check
     213//       operator bool() { return Node::operator bool(); }     
    231214    };
    232215
    … …  
    258241      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
    259242      int &idref() {return n;}
    260       const int &idref() const {return n;}
    261     };
     243      const int &idref() const {return n;}
     244//       ///Validity check
     245//       operator bool() { return n!=-1; }
     246   };
    262247   
    263248    class EdgeIt : public Edge {
     249      const SmartGraph *G;
    264250      friend class SmartGraph;
    265251    public:
    266       EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
     252      EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
     253      EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    267254      EdgeIt (Invalid i) : Edge(i) { }
    268255      EdgeIt() : Edge() { }
    … …  
    270257      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
    271258      int &idref() {return n;}
     259      EdgeIt &operator++() { --n; return *this; }
     260//       ///Validity check
     261//       operator bool() { return Edge::operator bool(); }     
    272262    };
    273263   
    274264    class OutEdgeIt : public Edge {
     265      const SmartGraph *G;
    275266      friend class SmartGraph;
    276267    public:
    277268      OutEdgeIt() : Edge() { }
     269      OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    278270      OutEdgeIt (Invalid i) : Edge(i) { }
    279271
    280       OutEdgeIt(const SmartGraph& G,const Node v)
    281         : Edge(G.nodes[v.n].first_out) {}
     272      OutEdgeIt(const SmartGraph& _G,const Node v)
     273        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
     274      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
     275//       ///Validity check
     276//       operator bool() { return Edge::operator bool(); }     
    282277    };
    283278   
    284279    class InEdgeIt : public Edge {
     280      const SmartGraph *G;
    285281      friend class SmartGraph;
    286282    public:
    287283      InEdgeIt() : Edge() { }
     284      InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    288285      InEdgeIt (Invalid i) : Edge(i) { }
    289       InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
     286      InEdgeIt(const SmartGraph& _G,Node v)
     287        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
     288      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
     289//       ///Validity check
     290//       operator bool() { return Edge::operator bool(); }     
    290291    };
    291292

  • src/hugo/unionfind.h

    r649 r774  
    66//!\file
    77//!\brief Union-Find data structures.
     8//!
     9//!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
     10//!fails to run (Segmentation fault).
    811
    912

  • src/test/Makefile.am

    r727 r774  
    33noinst_HEADERS = test_tools.h
    44
    5 check_PROGRAMS = graph_test dijkstra_test time_measure_test error_test xy_test \
    6         test_tools_pass test_tools_fail
     5check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \
     6        error_test xy_test \
     7        unionfind_test test_tools_pass test_tools_fail
    78
    89TESTS = $(check_PROGRAMS)
    … …  
    1112graph_test_SOURCES = graph_test.cc
    1213dijkstra_test_SOURCES = dijkstra_test.cc
     14bfs_test_SOURCES = bfs_test.cc
     15unionfind_test_SOURCES = unionfind_test.cc
    1316time_measure_test_SOURCES = time_measure_test.cc
    1417error_test_SOURCES = error_test.cc

  • src/test/dijkstra_test.cc

    r585 r774  
    7676
    7777
    78   for(EdgeIt e(G); G.valid(e); G.next(e)) {
     78  for(EdgeIt e(G); e==INVALID; ++e) {
    7979    Node u=G.tail(e);
    8080    Node v=G.head(e);
    … …  
    8787
    8888  ///\bug This works only for integer lengths
    89   for(NodeIt v(G); G.valid(v); G.next(v))
     89  for(NodeIt v(G); v==INVALID; ++v)
    9090    if ( dijkstra_test.reached(v) ) {
    9191      Edge e=dijkstra_test.pred(v);

  • src/test/graph_test.cc

    r733 r774  
    77#include"test_tools.h"
    88
    9 /*
     9/**
     10\file
    1011This test makes consistency checks of list graph structures.
    1112
    12 G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head()
     13G.addNode(), G.addEdge(), G.tail(), G.head()
    1314
    1415\todo Checks for empty graphs and isolated points.
     16\todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}
     17conversion.
    1518*/
    1619
    … …  
    3033    Node i; Node j(i); Node k(INVALID);
    3134    i=j;
    32     bool b=G.valid(i); b=b;
     35    //    bool b=G.valid(i); b=b;
     36    bool b; b=b;
     37    b=(i==INVALID); b=(i!=INVALID);
    3338    b=(i==j); b=(i!=j); b=(i<j);
    3439  }
    … …  
    3742    i=j;
    3843    j=G.first(i);
    39     j=G.next(i);
    40     bool b=G.valid(i); b=b;
     44    j=++i;
     45    //    bool b=G.valid(i); b=b;
     46    bool b; b=b;
     47    b=(i==INVALID); b=(i!=INVALID);
    4148    Node n(i);
    4249    n=i;
    4350    b=(i==j); b=(i!=j); b=(i<j);
     51    //Node ->NodeIt conversion
     52    NodeIt ni(G,n);
    4453  }
    4554  {
    4655    Edge i; Edge j(i); Edge k(INVALID);
    4756    i=j;
    48     bool b=G.valid(i); b=b;
     57    //    bool b=G.valid(i); b=b;
     58    bool b; b=b;
     59    b=(i==INVALID); b=(i!=INVALID);
    4960    b=(i==j); b=(i!=j); b=(i<j);
    5061  }
    … …  
    5364    i=j;
    5465    j=G.first(i);
    55     j=G.next(i);
    56     bool b=G.valid(i); b=b;
     66    j=++i;
     67    //    bool b=G.valid(i); b=b;
     68    bool b; b=b;
     69    b=(i==INVALID); b=(i!=INVALID);
    5770    Edge e(i);
    5871    e=i;
    5972    b=(i==j); b=(i!=j); b=(i<j);
     73    //Edge ->EdgeIt conversion
     74    EdgeIt ei(G,e);
    6075  }
    6176  {
    … …  
    6479    i=j;
    6580    j=G.first(i,n);
    66     j=G.next(i);
    67     bool b=G.valid(i); b=b;
     81    j=++i;
     82    //    bool b=G.valid(i); b=b;
     83    bool b; b=b;
     84    b=(i==INVALID); b=(i!=INVALID);
    6885    Edge e(i);
    6986    e=i;
    7087    b=(i==j); b=(i!=j); b=(i<j);
     88    //Edge ->InEdgeIt conversion
     89    InEdgeIt ei(G,e);
    7190  }
    7291  {
    … …  
    7594    i=j;
    7695    j=G.first(i,n);
    77     j=G.next(i);
    78     bool b=G.valid(i); b=b;
     96    j=++i;
     97    //    bool b=G.valid(i); b=b;
     98    bool b; b=b;
     99    b=(i==INVALID); b=(i!=INVALID);
    79100    Edge e(i);
    80101    e=i;
    81102    b=(i==j); b=(i!=j); b=(i<j);
    82   }
    83 
    84   Node n,m;
    85   n=m=INVALID;
    86   Edge e;
    87   e=INVALID;
    88   n=G.tail(e);
    89   n=G.head(e);
    90 
    91   //aNode, bNode ?
    92 
     103    //Edge ->OutEdgeIt conversion
     104    OutEdgeIt ei(G,e);
     105  }
     106  {
     107    Node n,m;
     108    n=m=INVALID;
     109    Edge e;
     110    e=INVALID;
     111    n=G.tail(e);
     112    n=G.head(e);
     113  }
    93114  // id tests
    94   { int i=G.id(n); i=i; }
    95   { int i=G.id(e); i=i; }
    96  
    97   //  G.clear();
    98 
     115  { Node n; int i=G.id(n); i=i; }
     116  { Edge e; int i=G.id(e); i=i; }
    99117  //NodeMap tests
    100118  {
    101119    Node k;
    102120    typename Graph::template NodeMap<int> m(G);
    103     typename Graph::template NodeMap<int> const &cm = m;  //Const map
     121    //Const map
     122    typename Graph::template NodeMap<int> const &cm = m;
    104123    //Inicialize with default value
    105124    typename Graph::template NodeMap<int> mdef(G,12);
    106     typename Graph::template NodeMap<int> mm(cm);   //Copy
    107     typename Graph::template NodeMap<double> dm(cm); //Copy from another type
     125    //Copy
     126    typename Graph::template NodeMap<int> mm(cm);
     127    //Copy from another type
     128    typename Graph::template NodeMap<double> dm(cm);
    108129    int v;
    109130    v=m[k]; m[k]=v; m.set(k,v);
    … …  
    161182    m=dm; //Copy to another type
    162183  }
    163  
    164184}
    165185
    … …  
    178198  n=G.addNode();
    179199  m=G.addNode();
    180  
    181   G.addEdge(n,m);
     200  Edge e;
     201  e=G.addEdge(n,m);
     202 
     203  //  G.clear();
     204}
     205
     206template<class Graph> void checkCompileErase(Graph &G)
     207{
     208  typedef typename Graph::Node Node;
     209  typedef typename Graph::Edge Edge;
     210  Node n;
     211  Edge e;
     212  G.erase(n);
     213  G.erase(e);
     214}
     215
     216template<class Graph> void checkCompileEraseEdge(Graph &G)
     217{
     218  typedef typename Graph::Edge Edge;
     219  Edge e;
     220  G.erase(e);
     221}
     222
     223template<class Graph> void checkCompileFindEdge(Graph &G)
     224{
     225  typedef typename Graph::NodeIt Node;
     226  typedef typename Graph::NodeIt NodeIt;
     227
     228  G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
     229  G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 
    182230}
    183231
    … …  
    187235  typename Graph::NodeIt n(G);
    188236  for(int i=0;i<nn;i++) {
    189     check(G.valid(n),"Wrong Node list linking.");
    190     G.next(n);
    191   }
    192   check(!G.valid(n),"Wrong Node list linking.");
     237    check(n!=INVALID,"Wrong Node list linking.");
     238    ++n;
     239  }
     240  check(n==INVALID,"Wrong Node list linking.");
    193241}
    194242
    … …  
    199247  EdgeIt e(G);
    200248  for(int i=0;i<nn;i++) {
    201     check(G.valid(e),"Wrong Edge list linking.");
    202     G.next(e);
    203   }
    204   check(!G.valid(e),"Wrong Edge list linking.");
     249    check(e!=INVALID,"Wrong Edge list linking.");
     250    ++e;
     251  }
     252  check(e==INVALID,"Wrong Edge list linking.");
    205253}
    206254
    … …  
    211259  typename Graph::OutEdgeIt e(G,n);
    212260  for(int i=0;i<nn;i++) {
    213     check(G.valid(e),"Wrong OutEdge list linking.");
    214     G.next(e);
    215   }
    216   check(!G.valid(e),"Wrong OutEdge list linking.");
     261    check(e!=INVALID,"Wrong OutEdge list linking.");
     262    ++e;
     263  }
     264  check(e==INVALID,"Wrong OutEdge list linking.");
    217265}
    218266
    219267template<class Graph> void checkInEdgeList(Graph &G,
    220                                             typename Graph::Node n,
    221                                             int nn)
     268                                           typename Graph::Node n,
     269                                           int nn)
    222270{
    223271  typename Graph::InEdgeIt e(G,n);
    224272  for(int i=0;i<nn;i++) {
    225     check(G.valid(e),"Wrong InEdge list linking.");
    226     G.next(e);
    227   }
    228   check(!G.valid(e),"Wrong InEdge list linking.");
    229 }
    230 
    231 //Checks head(), tail() as well;
     273    check(e!=INVALID,"Wrong InEdge list linking.");
     274    ++e;
     275  }
     276  check(e==INVALID,"Wrong InEdge list linking.");
     277}
     278
     279///\file
     280///\todo Checks head(), tail() as well;
     281
    232282template<class Graph> void bidirPetersen(Graph &G)
    233283{
    … …  
    239289  std::vector<Edge> ee;
    240290 
    241   for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e);
     291  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
    242292
    243293  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
    … …  
    255305  checkEdgeList(G,30);
    256306
    257   for(NodeIt n(G);G.valid(n);G.next(n)) {
     307  for(NodeIt n(G);n!=INVALID;++n) {
    258308    checkInEdgeList(G,n,3);
    259309    checkOutEdgeList(G,n,3);
    260     G.next(n);
     310    ++n;
    261311  } 
    262312}
    263313
    264 template
     314//Compile GraphSkeleton
     315template
    265316void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
    266317template void checkCompile<GraphSkeleton>(GraphSkeleton &);
    267 
     318template
     319void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);
     320
     321//Compile SmartGraph
    268322template void checkCompile<SmartGraph>(SmartGraph &);
     323//Compile SymSmartGraph
    269324template void checkCompile<SymSmartGraph>(SymSmartGraph &);
     325
     326//Compile ListGraph
    270327template void checkCompile<ListGraph>(ListGraph &);
     328template void checkCompileErase<ListGraph>(ListGraph &);
     329template void checkCompileFindEdge<ListGraph>(ListGraph &);
     330
     331//Compile SymListGraph
    271332template void checkCompile<SymListGraph>(SymListGraph &);
     333template void checkCompileErase<SymListGraph>(SymListGraph &);
     334template void checkCompileFindEdge<SymListGraph>(SymListGraph &);
     335
     336//Compile FullGraph
    272337template void checkCompileStaticGraph<FullGraph>(FullGraph &);
    273 
     338template void checkCompileFindEdge<FullGraph>(FullGraph &);
     339
     340//Compile EdgeSet <ListGraph>
    274341template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
     342template
     343void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
     344template
     345void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
     346
     347//Compile EdgeSet <NodeSet>
    275348template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
     349template
     350void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
     351template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
     352
    276353
    277354int main()
    … …  
    300377  }
    301378
    302   //\todo map tests.
    303   //\todo copy constr tests.
     379  ///\file
     380  ///\todo map tests.
     381  ///\todo copy constr tests.
    304382
    305383  std::cout << __FILE__ ": All tests passed.\n";

  • src/test/test_tools.h

    r721 r774  
    2121///print this (and then exits).
    2222///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
     23///
     24///\todo It should be in \c error.h
    2325#define check(rc, msg) \
    2426  if(!(rc)) { \

  • src/test/unionfind_test.cc

    r542 r774  
    33#include <hugo/maps.h>
    44#include <hugo/unionfind.h>
     5#include "test_tools.h"
    56
    67using namespace hugo;
    78using namespace std;
    8 
    9 bool passed = true;
    10 
    11 void check(bool rc) {
    12   passed = passed && rc;
    13   if(!rc) {
    14     cout << "Test failed!" << endl;
    15   }
    16 }
    179
    1810template <typename T>
    … …  
    2315void print(UFE const &ufe) {
    2416  UFE::ClassIt cit;
    25   cout << "printing the classes of the structure:" << endl;
     17  cout << "Print the classes of the structure:" << endl;
    2618  int i = 1;
    2719  for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
    … …  
    4234  UFE U(base);
    4335
    44   print(U);
     36//   print(U);
    4537
    46   cout << "Inserting 1..." << endl;
     38  cout << "Insert 1..." << endl;
    4739  U.insert(1);
    48   print(U);
     40//   print(U);
    4941 
    50   cout << "Inserting 2..." << endl;
     42  cout << "Insert 2..." << endl;
    5143  U.insert(2);
    52   print(U);
     44//   print(U);
    5345 
    54   cout << "Joining 1 and 2..." << endl;
    55   check(U.join(1,2));
    56   print(U);
     46  cout << "Join 1 and 2..." << endl;
     47  check(U.join(1,2),"Test failed.");
     48//   print(U);
    5749
    58   cout << "Inserting 3, 4, 5, 6, 7..." << endl;
     50  cout << "Insert 3, 4, 5, 6, 7..." << endl;
    5951  U.insert(3);
    6052  U.insert(4);
    … …  
    6254  U.insert(6);
    6355  U.insert(7);
    64   print (U);
     56//   print (U);
    6557
    66   cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
    67   check(U.join(1,4));
    68   check(!U.join(2,4));
    69   check(U.join(3,5));
    70   print(U);
     58  cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
     59  check(U.join(1,4),"Test failed.");
     60  check(!U.join(2,4),"Test failed.");
     61  check(U.join(3,5),"Test failed.");
     62//   print(U);
    7163
    72   cout << "Inserting 8 to the component of 5 ..." << endl;
     64  cout << "Insert 8 to the component of 5 ..." << endl;
    7365  U.insert(8,5);
    74   print(U);
     66//   print(U);
    7567
    76   cout << "size of the class of 4: " << U.size(4) << endl;
    77   check(U.size(4) == 3);
    78   cout << "size of the class of 5: " << U.size(5) << endl;
    79   check(U.size(5) == 3);
    80   cout << "size of the class of 6: " << U.size(6) << endl;
    81   check(U.size(6) == 1);
    82   cout << "size of the class of 2: " << U.size(2) << endl;
    83   check(U.size(2) == 3);
     68  cout << "Size of the class of 4: " << U.size(4) << endl;
     69  check(U.size(4) == 3,"Test failed.");
     70  cout << "Size of the class of 5: " << U.size(5) << endl;
     71  check(U.size(5) == 3,"Test failed.");
     72  cout << "Size of the class of 6: " << U.size(6) << endl;
     73  check(U.size(6) == 1,"Test failed.");
     74  cout << "Size of the class of 2: " << U.size(2) << endl;
     75  check(U.size(2) == 3,"Test failed.");
    8476
    85   cout << "Inserting 9 ..." << endl;
     77  cout << "Insert 9 ..." << endl;
    8678  U.insert(9);
    87   print(U);
    88   cout << "Inserting 10 to the component of 9 ..." << endl;
     79//   print(U);
     80  cout << "Insert 10 to the component of 9 ..." << endl;
    8981  U.insert(10,9);
    90   print(U);
     82//   print(U);
    9183
    92   cout << "Joining 8 and 10..." << endl;
    93   check(U.join(8,10));
    94   print(U);
     84  cout << "Join 8 and 10..." << endl;
     85  check(U.join(8,10),"Test failed.");
     86//   print(U);
    9587
    9688  cout << "Move 9 to the class of 4 ..." << endl;
    97   check(U.move(9,4));
    98   print(U);
     89  check(U.move(9,4),"Test failed.");
     90//   print(U);
    9991
    10092  cout << "Move 9 to the class of 2 ..." << endl;
    101   check(!U.move(9,2));
    102   print(U);
     93  check(!U.move(9,2),"Test failed.");
     94//   print(U);
    10395
    104   cout << "size of the class of 4: " << U.size(4) << endl;
    105   check(U.size(4) == 4);
    106   cout << "size of the class of 9: " << U.size(9) << endl;
    107   check(U.size(9) == 4);
     96  cout << "Size of the class of 4: " << U.size(4) << endl;
     97  check(U.size(4) == 4,"Test failed.");
     98  cout << "Size of the class of 9: " << U.size(9) << endl;
     99  check(U.size(9) == 4,"Test failed.");
    108100 
    109101  cout << "Move 5 to the class of 6 ..." << endl;
    110   check(U.move(5,6));
    111   print(U);
     102  check(U.move(5,6),"Test failed.");
     103//   print(U);
    112104
    113   cout << "size of the class of 5: " << U.size(5) << endl;
    114   check(U.size(5) == 2);
    115   cout << "size of the class of 8: " << U.size(8) << endl;
    116   check(U.size(8) == 3);
     105  cout << "Size of the class of 5: " << U.size(5) << endl;
     106  check(U.size(5) == 2,"Test failed.");
     107  cout << "Size of the class of 8: " << U.size(8) << endl;
     108  check(U.size(8) == 3,"Test failed.");
    117109
    118110  cout << "Move 7 to the class of 10 ..." << endl;
    119   check(U.move(7,10));
    120   print(U);
     111  check(U.move(7,10),"Test failed.");
     112//   print(U);
    121113
    122   cout << "size of the class of 7: " << U.size(7) << endl;
    123   check(U.size(7) == 4);
     114  cout << "Size of the class of 7: " << U.size(7) << endl;
     115  check(U.size(7) == 4,"Test failed.");
    124116
    125   cout <<"erase 9: " << endl;
     117  cout <<"Erase 9... " << endl;
    126118  U.erase(9);
    127   print(U);
     119//   print(U);
    128120
    129   cout <<"erase 1: " << endl;
     121  cout <<"Erase 1... " << endl;
    130122  U.erase(1);
    131   print(U);
     123//   print(U);
    132124
    133   cout << "size of the class of 4: " << U.size(4) << endl;
    134   check(U.size(4) == 2);
    135   cout << "size of the class of 2: " << U.size(2) << endl;
    136   check(U.size(2) == 2);
     125  cout << "Size of the class of 4: " << U.size(4) << endl;
     126  check(U.size(4) == 2,"Test failed.");
     127  cout << "Size of the class of 2: " << U.size(2) << endl;
     128  check(U.size(2) == 2,"Test failed.");
    137129
    138130
    139   cout <<"erase 1: " << endl;
     131  cout <<"Erase 1... " << endl;
    140132  U.erase(1);
    141   print(U);
     133//   print(U);
    142134
    143   cout <<"erase 6: " << endl;
     135  cout <<"Erase 6... " << endl;
    144136  U.erase(6);
    145   print(U);
     137//   print(U);
    146138
    147   cout << "split the class of 8: " << endl;
     139  cout << "Split the class of 8... " << endl;
    148140  U.split(8);
    149   print(U);
     141//   print(U);
    150142
    151143
    152   cout << "size of the class of 4: " << U.size(4) << endl;
    153   check(U.size(4) == 2);
    154   cout << "size of the class of 3: " << U.size(3) << endl;
    155   check(U.size(3) == 1);
    156   cout << "size of the class of 2: " << U.size(2) << endl;
    157   check(U.size(2) == 2);
     144  cout << "Size of the class of 4: " << U.size(4) << endl;
     145  check(U.size(4) == 2,"Test failed.");
     146  cout << "Size of the class of 3: " << U.size(3) << endl;
     147  check(U.size(3) == 1,"Test failed.");
     148  cout << "Size of the class of 2: " << U.size(2) << endl;
     149  check(U.size(2) == 2,"Test failed.");
    158150
    159151
    160   cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
    161   check(U.join(3,4));
    162   check(!U.join(2,4));
    163   print(U);
     152  cout << "Join 3 - 4 and 2 - 4 ..." << endl;
     153  check(U.join(3,4),"Test failed.");
     154  check(!U.join(2,4),"Test failed.");
     155//   print(U);
    164156
    165157
    166   cout << "size of the class of 4: " << U.size(4) << endl;
    167   check(U.size(4) == 3);
    168   cout << "size of the class of 3: " << U.size(3) << endl;
    169   check(U.size(3) == 3);
    170   cout << "size of the class of 2: " << U.size(2) << endl;
    171   check(U.size(2) == 3);
     158  cout << "Size of the class of 4: " << U.size(4) << endl;
     159  check(U.size(4) == 3,"Test failed.");
     160  cout << "Size of the class of 3: " << U.size(3) << endl;
     161  check(U.size(3) == 3,"Test failed.");
     162  cout << "Size of the class of 2: " << U.size(2) << endl;
     163  check(U.size(2) == 3,"Test failed.");
    172164
    173   cout << "makeRep(4)" << endl;
     165  cout << "makeRep(4)..." << endl;
    174166  U.makeRep(4);
    175   print(U);
    176   cout << "makeRep(3)" << endl;
     167//   print(U);
     168  cout << "makeRep(3)..." << endl;
    177169  U.makeRep(3);
    178   print(U);
    179   cout << "makeRep(2)" << endl;
     170//   print(U);
     171  cout << "makeRep(2)..." << endl;
    180172  U.makeRep(2);
    181   print(U);
     173//   print(U);
    182174
    183   cout << "size of the class of 4: " << U.size(4) << endl;
    184   check(U.size(4) == 3);
    185   cout << "size of the class of 3: " << U.size(3) << endl;
    186   check(U.size(3) == 3);
    187   cout << "size of the class of 2: " << U.size(2) << endl;
    188   check(U.size(2) == 3);
     175  cout << "Size of the class of 4: " << U.size(4) << endl;
     176  check(U.size(4) == 3,"Test failed.");
     177  cout << "Size of the class of 3: " << U.size(3) << endl;
     178  check(U.size(3) == 3,"Test failed.");
     179  cout << "Size of the class of 2: " << U.size(2) << endl;
     180  check(U.size(2) == 3,"Test failed.");
    189181
    190182
    191183  cout << "eraseClass 4 ..." << endl;
    192184  U.eraseClass(4);
    193   print(U);
     185//   print(U);
    194186
    195187  cout << "eraseClass 7 ..." << endl;
    196188  U.eraseClass(7);
    197   print(U);
     189//   print(U);
    198190
    199   cout << "done" << endl;
    200 
    201   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    202        << endl;
    203 
    204   return passed ? 0 : 1;
     191  cout << "done." << endl;
    205192}

  • src/test/xy_test.cc

    r727 r774  
    88{
    99
    10   cout << "Testing classes xy and boundingbox." << endl;
     10  cout << "Testing classes `xy' and `boundingbox'." << endl;
    1111
    1212        typedef xy<int> XY;
    … …  
    3434        typedef BoundingBox<int> BB;
    3535        BB doboz1;
    36         check(doboz1.empty(), "empty? Should be.");
     36        check(doboz1.empty(), "It should be empty.");
    3737       
    3838        doboz1 += a;
    39         check(!doboz1.empty(), "empty? Should not be.");
     39        check(!doboz1.empty(), "It should not be empty.");
    4040        doboz1 += b;
    4141
    … …  
    4747
    4848        seged.x=2;seged.y=3;
    49         check(doboz1.inside(seged),"Inside? It should be.");
     49        check(doboz1.inside(seged),"It should be inside.");
    5050
    5151        seged.x=1;seged.y=3;
    52         check(doboz1.inside(seged),"Inside? It should be.");
     52        check(doboz1.inside(seged),"It should be inside.");
    5353
    5454        seged.x=0;seged.y=3;
    55         check(!doboz1.inside(seged),"Inside? It should not be.");
     55        check(!doboz1.inside(seged),"It should not be inside.");
    5656
    5757        BB doboz2(seged);
    5858        check(!doboz2.empty(),
    59               "empty? Should not be. Constructed from 1 point.");
     59              "It should not be empty. Constructed from 1 point.");
    6060
    6161        doboz2 += doboz1;
    6262        check(doboz2.inside(seged),
    63               "Not inside? It should be. Incremented a box with an other.");
     63              "It should be inside. Incremented a box with an other.");
    6464}

  • src/work/marci/bfs_dfs.h

    r671 r774  
    6161        bfs_queue.push(s);
    6262        graph->first(actual_edge, s);
    63         if (graph->valid(actual_edge)) {
    64           Node w=graph->bNode(actual_edge);
     63        if (actual_edge!=INVALID) {
     64          Node w=graph->head(actual_edge);
    6565          if (!reached[w]) {
    6666            bfs_queue.push(w);
    … …  
    7979    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
    8080    operator++() {
    81       if (graph->valid(actual_edge)) {
    82         graph->next(actual_edge);
    83         if (graph->valid(actual_edge)) {
    84           Node w=graph->bNode(actual_edge);
     81      if (actual_edge!=INVALID) {
     82        ++actual_edge;
     83        if (actual_edge!=INVALID) {
     84          Node w=graph->head(actual_edge);
    8585          if (!reached[w]) {
    8686            bfs_queue.push(w);
    … …  
    9595        if (!bfs_queue.empty()) {
    9696          graph->first(actual_edge, bfs_queue.front());
    97           if (graph->valid(actual_edge)) {
    98             Node w=graph->bNode(actual_edge);
     97          if (actual_edge!=INVALID) {
     98            Node w=graph->head(actual_edge);
    9999            if (!reached[w]) {
    100100              bfs_queue.push(w);
    … …  
    118118    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    119119    /// Returns if a-node is examined.
    120     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     120    bool isANodeExamined() const { return actual_edge==INVALID; }
    121121    /// Returns a-node of the actual edge, so does if the edge is invalid.
    122122    Node aNode() const { return bfs_queue.front(); }
    … …  
    238238      actual_edge=dfs_stack.top();
    239239      //actual_node=G.aNode(actual_edge);
    240       if (graph->valid(actual_edge)/*.valid()*/) {
    241         Node w=graph->bNode(actual_edge);
     240      if (actual_edge!=INVALID/*.valid()*/) {
     241        Node w=graph->head(actual_edge);
    242242        actual_node=w;
    243243        if (!reached[w]) {
    … …  
    248248          b_node_newly_reached=true;
    249249        } else {
    250           actual_node=graph->aNode(actual_edge);
    251           graph->next(dfs_stack.top());
     250          actual_node=graph->tail(actual_edge);
     251          ++dfs_stack.top();
    252252          b_node_newly_reached=false;
    253253        }
    … …  
    267267    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    268268    /// Returns if a-node is examined.
    269     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     269    bool isANodeExamined() const { return actual_edge==INVALID; }
    270270    /// Returns a-node of the actual edge, so does if the edge is invalid.
    271271    Node aNode() const { return actual_node; /*FIXME*/}

  • src/work/marci/iterator_bfs_demo.cc

    r642 r774  
    55
    66#include <sage_graph.h>
    7 //#include <smart_graph.h>
     7#include <hugo/smart_graph.h>
    88#include <bfs_dfs.h>
    99#include <hugo/graph_wrapper.h>
    … …  
    2929int main (int, char*[])
    3030{
    31   //typedef SmartGraph Graph;
    32   typedef SageGraph Graph;
     31  typedef SmartGraph Graph;
     32  //typedef SageGraph Graph;
    3333
    3434  typedef Graph::Node Node;
    … …  
    9292   
    9393    cout << "bfs and dfs iterator demo on the directed graph" << endl;
    94     for(Graph::NodeIt n(G); G.valid(n); G.next(n)) {
     94    for(Graph::NodeIt n(G); n!=INVALID; ++n) {
    9595      cout << node_name[n] << ": ";
    9696      cout << "out edges: ";
    97       for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e))
     97      for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)
    9898        cout << edge_name[e] << " ";
    9999      cout << "in edges: ";
    100       for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e))
     100      for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e)
    101101        cout << edge_name[e] << " ";
    102102      cout << endl;
    … …  
    108108    while (!bfs.finished()) {
    109109      //cout << "edge: ";
    110       if (G.valid(bfs)) {
     110      if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
    111111        cout << edge_name[bfs] << /*endl*/", " <<
    112           node_name[G.aNode(bfs)] <<
    113           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    114           node_name[G.bNode(bfs)] <<
     112          node_name[G.tail(bfs)] <<
     113          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     114          node_name[G.head(bfs)] <<
    115115          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    116116           ": is not newly reached.");
    … …  
    142142      ++dfs;
    143143      //cout << "edge: ";
    144       if (G.valid(dfs)) {
     144      if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
    145145        cout << edge_name[dfs] << /*endl*/", " <<
    146           node_name[G.aNode(dfs)] <<
    147           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    148           node_name[G.bNode(dfs)] <<
     146          node_name[G.tail(dfs)] <<
     147          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     148          node_name[G.head(dfs)] <<
    149149          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    150150           ": is not newly reached.");
    … …  
    168168   
    169169    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
    170     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
     170    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
    171171      cout << node_name[GW::Node(n)] << ": ";
    172172      cout << "out edges: ";
    173       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     173      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
    174174        cout << edge_name[e] << " ";
    175175      cout << "in edges: ";
    176       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     176      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
    177177        cout << edge_name[e] << " ";
    178178      cout << endl;
    … …  
    184184    while (!bfs.finished()) {
    185185      //cout << "edge: ";
    186       if (gw.valid(GW::OutEdgeIt(bfs))) {
     186      if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
    187187        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
    188           node_name[gw.aNode(bfs)] <<
    189           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    190           node_name[gw.bNode(bfs)] <<
     188          node_name[gw.tail(bfs)] <<
     189          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     190          node_name[gw.head(bfs)] <<
    191191          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    192192           ": is not newly reached.");
    … …  
    218218      ++dfs;
    219219      //cout << "edge: ";
    220       if (gw.valid(GW::OutEdgeIt(dfs))) {
     220      if (GW::OutEdgeIt(dfs)!=INVALID) {
    221221        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
    222           node_name[gw.aNode(dfs)] <<
    223           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    224           node_name[gw.bNode(dfs)] <<
     222          node_name[gw.tail(dfs)] <<
     223          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     224          node_name[gw.head(dfs)] <<
    225225          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    226226           ": is not newly reached.");
    … …  
    236236  }
    237237
     238//   {
     239//     typedef UndirGraphWrapper<const Graph> GW;
     240//     GW gw(G);
     241   
     242//     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
     243   
     244//     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
     245//     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
     246//       cout << node_name[GW::Node(n)] << ": ";
     247//       cout << "out edges: ";
     248//       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     249//      cout << edge_name[e] << " ";
     250//       cout << "in edges: ";
     251//       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     252//      cout << edge_name[e] << " ";
     253//       cout << endl;
     254//     }
     255// //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
     256// //       cout << edge_name.get(e) << " ";
     257// //     }
     258// //     cout << endl;
     259
     260//     cout << "bfs from t ..." << endl;
     261//     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
     262//     bfs.pushAndSetReached(t);
     263//     while (!bfs.finished()) {
     264//       //cout << "edge: ";
     265//       if (gw.valid(GW::OutEdgeIt(bfs))) {
     266//      cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
     267//        node_name[gw.aNode(bfs)] <<
     268//        (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     269//        node_name[gw.bNode(bfs)] <<
     270//        (bfs.isBNodeNewlyReached() ? ": is newly reached." :
     271//         ": is not newly reached.");
     272//       } else {
     273//      cout << "invalid" << /*endl*/", " <<
     274//        node_name[bfs.aNode()] <<
     275//        (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     276         
     277//        "invalid.";
     278//       }
     279//       cout << endl;
     280//       ++bfs;
     281//     }
     282
     283//     cout << "    /-->    ------------->            "<< endl;
     284//     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
     285//     cout << "  / |          |    /  /->     \\     "<< endl;
     286//     cout << " /  |          |   /  |    ^    \\  "<< endl;
     287//     cout << "s   |          |  /   |    |     \\->  t "<< endl;
     288//     cout << " \\  |          | /    |    |     /->  "<< endl;
     289//     cout << "  \\ |       --/ /     |    |    /     "<< endl;
     290//     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
     291//     cout << "    \\-->    ------------->         "<< endl;
     292   
     293//     cout << "dfs from t ..." << endl;
     294//     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
     295//     dfs.pushAndSetReached(t);
     296//     while (!dfs.finished()) {
     297//       ++dfs;
     298//       //cout << "edge: ";
     299//       if (gw.valid(GW::OutEdgeIt(dfs))) {
     300//      cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
     301//        node_name[gw.aNode(dfs)] <<
     302//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     303//        node_name[gw.bNode(dfs)] <<
     304//        (dfs.isBNodeNewlyReached() ? ": is newly reached." :
     305//         ": is not newly reached.");
     306//       } else {
     307//      cout << "invalid" << /*endl*/", " <<
     308//        node_name[dfs.aNode()] <<
     309//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     310         
     311//        "invalid.";
     312//       }
     313//       cout << endl;
     314//     }
     315//   }
     316
     317
     318
    238319  {
    239     typedef UndirGraphWrapper<const Graph> GW;
     320    typedef BidirGraphWrapper<const Graph> GW;
    240321    GW gw(G);
    241322   
    242323    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
    243324   
    244     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
    245     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
     325    cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
     326//     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
     327//       cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";
     328//     }
     329    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
    246330      cout << node_name[GW::Node(n)] << ": ";
    247331      cout << "out edges: ";
    248       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     332      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
    249333        cout << edge_name[e] << " ";
    250334      cout << "in edges: ";
    251       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     335      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
    252336        cout << edge_name[e] << " ";
    253337      cout << endl;
    … …  
    263347    while (!bfs.finished()) {
    264348      //cout << "edge: ";
    265       if (gw.valid(GW::OutEdgeIt(bfs))) {
     349      if (GW::OutEdgeIt(bfs)!=INVALID) {
    266350        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
    267           node_name[gw.aNode(bfs)] <<
    268           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    269           node_name[gw.bNode(bfs)] <<
     351          node_name[gw.tail(bfs)] <<
     352          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     353          node_name[gw.head(bfs)] <<
    270354          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    271355           ": is not newly reached.");
    … …  
    297381      ++dfs;
    298382      //cout << "edge: ";
    299       if (gw.valid(GW::OutEdgeIt(dfs))) {
     383      if (GW::OutEdgeIt(dfs)!=INVALID) {
    300384        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
    301           node_name[gw.aNode(dfs)] <<
    302           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    303           node_name[gw.bNode(dfs)] <<
     385          node_name[gw.tail(dfs)] <<
     386          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     387          node_name[gw.head(dfs)] <<
    304388          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    305389           ": is not newly reached.");
    … …  
    314398    }
    315399  }
    316 
    317 
    318 
    319   {
    320     typedef BidirGraphWrapper<const Graph> GW;
    321     GW gw(G);
    322    
    323     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
    324    
    325     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
    326     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
    327       cout << node_name[GW::Node(n)] << ": ";
    328       cout << "out edges: ";
    329       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
    330         cout << edge_name[e] << " ";
    331       cout << "in edges: ";
    332       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
    333         cout << edge_name[e] << " ";
    334       cout << endl;
    335     }
    336 //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
    337 //       cout << edge_name.get(e) << " ";
    338 //     }
    339 //     cout << endl;
    340 
    341     cout << "bfs from t ..." << endl;
    342     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
    343     bfs.pushAndSetReached(t);
    344     while (!bfs.finished()) {
    345       //cout << "edge: ";
    346       if (gw.valid(GW::OutEdgeIt(bfs))) {
    347         cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
    348           node_name[gw.aNode(bfs)] <<
    349           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    350           node_name[gw.bNode(bfs)] <<
    351           (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    352            ": is not newly reached.");
    353       } else {
    354         cout << "invalid" << /*endl*/", " <<
    355           node_name[bfs.aNode()] <<
    356           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    357          
    358           "invalid.";
    359       }
    360       cout << endl;
    361       ++bfs;
    362     }
    363 
    364     cout << "    /-->    ------------->            "<< endl;
    365     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
    366     cout << "  / |          |    /  /->     \\     "<< endl;
    367     cout << " /  |          |   /  |    ^    \\  "<< endl;
    368     cout << "s   |          |  /   |    |     \\->  t "<< endl;
    369     cout << " \\  |          | /    |    |     /->  "<< endl;
    370     cout << "  \\ |       --/ /     |    |    /     "<< endl;
    371     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
    372     cout << "    \\-->    ------------->         "<< endl;
    373    
    374     cout << "dfs from t ..." << endl;
    375     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
    376     dfs.pushAndSetReached(t);
    377     while (!dfs.finished()) {
    378       ++dfs;
    379       //cout << "edge: ";
    380       if (gw.valid(GW::OutEdgeIt(dfs))) {
    381         cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
    382           node_name[gw.aNode(dfs)] <<
    383           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    384           node_name[gw.bNode(dfs)] <<
    385           (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    386            ": is not newly reached.");
    387       } else {
    388         cout << "invalid" << /*endl*/", " <<
    389           node_name[dfs.aNode()] <<
    390           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    391          
    392           "invalid.";
    393       }
    394       cout << endl;
    395     }
    396   }
    397 
    398 
    399400
    400401  return 0;

  • src/work/sage_graph.h

    r642 r774  
    1010namespace hugo {
    1111
    12   template <typename It>
    13   int count(It it) {
    14     int i=0;
    15     for( ; it.valid(); ++it) { ++i; }
    16     return i;
    17   }
     12//   template <typename It>
     13//   int count(It it) {
     14//     int i=0;
     15//     for( ; it.valid(); ++it) { ++i; }
     16//     return i;
     17//   }
    1818
    1919  class SageGraph {
    … …  
    386386    public: //for everybody but marci
    387387      NodeIt(const SageGraph& G) : Node(G._first_node) { }
     388      NodeIt(const SageGraph& G, const Node& n) : Node(n) { }
    388389    public:
    389390      NodeIt() : Node() { }
    … …  
    391392    protected:
    392393      NodeIt(node_item* v) : Node(v) { }
     394    public:
    393395      NodeIt& operator++() { node=node->_next_node; return *this; }
    394396      //FIXME::
    … …  
    426428    class EdgeIt : public Edge {
    427429      friend class SageGraph;
    428       //protected:
    429     public: //for alpar
     430    public:
     431      EdgeIt() : Edge() { }
     432      EdgeIt(const Invalid& i) : Edge(i) { }
    430433      EdgeIt(const SageGraph& G) {
    431434        node_item* v=G._first_node;
    … …  
    433436        while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
    434437      }
    435     public:
    436       EdgeIt() : Edge() { }
    437       EdgeIt(const Invalid& i) : Edge(i) { }
    438     protected:
    439       EdgeIt(edge_item* _e) : Edge(_e) { }
     438      EdgeIt(const SageGraph& G, const Edge& e) : Edge(e) { }
     439//     protected:
     440//       EdgeIt(edge_item* _e) : Edge(_e) { }
     441    public:
    440442      EdgeIt& operator++() {
    441443        node_item* v=edge->_tail;
    … …  
    448450    class OutEdgeIt : public Edge {
    449451      friend class SageGraph;
    450       //node_item* v;
    451       //protected:
    452     protected: //for alpar
    453       OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
    454     public:
    455       OutEdgeIt() : Edge()/*, v(0)*/ { }
     452    public:
     453      OutEdgeIt() : Edge() { }
    456454      OutEdgeIt(const Invalid& i) : Edge(i) { }
    457       OutEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
    458     protected:
     455      OutEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_out_edge) { }
     456      OutEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
    459457      OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
    460458    protected:
    … …  
    465463    class InEdgeIt : public Edge {
    466464      friend class SageGraph;
    467       //node_item* v;
    468       //protected:
    469     protected: //for alpar
    470       InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
    471     public:
    472       InEdgeIt() : Edge()/*, v(0)*/ { }
    473       InEdgeIt(const Invalid& i) : Edge(i) { }
    474       InEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
    475     protected:
     465    public:
     466      InEdgeIt() : Edge() { }
     467      InEdgeIt(Invalid i) : Edge(i) { }
     468      InEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_in_edge) { }
     469      InEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
    476470      InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
    477471    protected:
Note: See TracChangeset for help on using the changeset viewer.