COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
08/30/04 14:01:47 (17 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/hugo
Files:
1 added
9 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.