COIN-OR::LEMON - Graph Library

Changeset 64:72bd463289a9 in lemon-0.x


Ignore:
Timestamp:
02/05/04 16:06:45 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@79
Message:

.

Location:
src/work
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r58 r64  
    406406  public:
    407407    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
    408     void pushAndSetReached(const NodeIt s) {
     408    void pushAndSetReached(NodeIt s) {
    409409      reached.set(s, true);
    410410      if (bfs_queue.empty()) {
     
    445445        if (!bfs_queue.empty()) {
    446446          actual_edge=bfs_queue.front();
    447         } else {
    448           actual_edge=OutEdgeIt();
    449         }
    450         if (actual_edge.valid()) {
    451           NodeIt w=G.bNode(actual_edge);
    452           if (!reached.get(w)) {
    453             bfs_queue.push(G.template first<OutEdgeIt>(w));
    454             reached.set(w, true);
    455             b_node_newly_reached=true;
    456           } else {
    457             b_node_newly_reached=false;
     447          if (actual_edge.valid()) {
     448            NodeIt w=G.bNode(actual_edge);
     449            if (!reached.get(w)) {
     450              bfs_queue.push(G.template first<OutEdgeIt>(w));
     451              reached.set(w, true);
     452              b_node_newly_reached=true;
     453            } else {
     454              b_node_newly_reached=false;
     455            }
    458456          }
    459457        }
     
    469467 };
    470468
    471 
    472469} // namespace marci
    473470
  • src/work/edmonds_karp.hh

    r59 r64  
    4242      }
    4343      bool valid() const { return sym.valid(); }
    44       void augment(const T a) const {
     44      void augment(T a) const {
    4545        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    4646          resG->flow.set(sym, resG->flow.get(sym)+a);
     
    5757      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    5858    private:
    59       OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) {
     59      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {
    6060        resG=&_resG;
    6161        sym=resG->G.template first<OldSymEdgeIt>(v);
     
    7070    };
    7171
    72     void getFirst(OutEdgeIt& e, const NodeIt v) const {
     72    void getFirst(OutEdgeIt& e, NodeIt v) const {
    7373      e=OutEdgeIt(*this, v);
    7474    }
     
    8383
    8484    template< typename It >
    85     It first(const NodeIt v) const {
     85    It first(NodeIt v) const {
    8686      It e;
    8787      getFirst(e, v);
     
    8989    }
    9090
    91     NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); }
    92     NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); }
    93 
    94     NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); }
    95     NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); }
    96 
    97     int id(const NodeIt v) const { return G.id(v); }
     91    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
     92    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
     93
     94    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
     95    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
     96
     97    int id(NodeIt v) const { return G.id(v); }
    9898
    9999    template <typename ValueType>
     
    102102    public:
    103103      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    104       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
    105       void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
    106       ValueType get(const NodeIt nit) const { return node_map.get(nit); }
     104      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { }
     105      void set(NodeIt nit, ValueType a) { node_map.set(nit, a); }
     106      ValueType get(NodeIt nit) const { return node_map.get(nit); }
    107107    };
    108108
     
    117117    typedef typename Graph::InEdgeIt InEdgeIt;
    118118    const Graph& G;
    119     const NodeIt s;
    120     const NodeIt t;
     119    NodeIt s;
     120    NodeIt t;
    121121    FlowMap& flow;
    122122    const CapacityMap& capacity;
     
    125125    typedef typename AugGraph::EdgeIt AugEdgeIt;
    126126  public:
    127     MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
     127    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
    128128    bool augment() {
    129129      AugGraph res_graph(G, flow, capacity);
  • src/work/list_graph.hh

    r59 r64  
    4141    public:
    4242      NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
    43       NodeMap(const ListGraph& _G, const ValueType a) :
     43      NodeMap(const ListGraph& _G, ValueType a) :
    4444        G(_G), container(_G.node_id, a) { }
    45       void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
    46       ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
     45      void set(NodeIt nit, ValueType a) { container[G.id(nit)]=a; }
     46      ValueType get(NodeIt nit) const { return container[G.id(nit)]; }
    4747    };
    4848
     
    5353    public:
    5454      EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
    55       EdgeMap(const ListGraph& _G, const ValueType a) :
     55      EdgeMap(const ListGraph& _G, ValueType a) :
    5656        G(_G), container(_G.edge_id, a) { }
    57       void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
    58       ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
     57      void set(EdgeIt eit, ValueType a) { container[G.id(eit)]=a; }
     58      ValueType get(EdgeIt eit) const { return container[G.id(eit)]; }
    5959    };
    6060
     
    227227    //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
    228228    //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
    229     NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
    230     NodeIt head(const EdgeIt e) const { return e.headNode(); }
     229    NodeIt tail(EdgeIt e) const { return e.tailNode(); }
     230    NodeIt head(EdgeIt e) const { return e.headNode(); }
    231231
    232232    NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); }
     
    249249    void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
    250250    void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
    251     void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
    252     void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
    253     void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); }
    254     void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
    255     void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
    256 
    257     void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }
    258     void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }
    259     void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }
    260     void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }
    261     void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }
    262     void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }
     251    void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); }
     252    void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); }
     253    void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); }
     254    //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
     255    //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
     256
     257    //void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }
     258    //void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }
     259    //void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }
     260    //void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }
     261    //void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }
     262    //void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }
    263263    //void get_invalid(NodeIt& n) { n=NodeIt(); }
    264264    //void get_invalid(EdgeIt& e) { e=EdgeIt(); }
     
    275275
    276276    template< typename It >
    277     It first(const NodeIt v) const {
     277    It first(NodeIt v) const {
    278278      It e;
    279279      getFirst(e, v);
     
    284284    /* these are important for the implementation of property vectors */
    285285
    286     int id(const NodeIt v) const { return v.node->id; }
    287     int id(const EdgeIt e) const { return e.edge->id; }
     286    int id(NodeIt v) const { return v.node->id; }
     287    int id(EdgeIt e) const { return e.edge->id; }
    288288
    289289    /* adding nodes and edges */
    290290
    291291    NodeIt addNode() { return NodeIt(_add_node()); }
    292     EdgeIt addEdge(const NodeIt u, const NodeIt v) {
     292    EdgeIt addEdge(NodeIt u, NodeIt v) {
    293293      return EdgeIt(_add_edge(u.node, v.node));
    294294    }
    295295
    296     void deleteNode(const NodeIt i) {
     296    void deleteNode(NodeIt i) {
    297297      while (first<OutEdgeIt>(i).valid()) deleteEdge(first<OutEdgeIt>(i));
    298298      while (first<InEdgeIt>(i).valid()) deleteEdge(first<InEdgeIt>(i));
     
    300300    }
    301301 
    302     void deleteEdge(const EdgeIt e) { _delete_edge(e.edge); }
    303 
    304     void setTail(const EdgeIt e, const NodeIt tail) {
     302    void deleteEdge(EdgeIt e) { _delete_edge(e.edge); }
     303
     304    void setTail(EdgeIt e, NodeIt tail) {
    305305      _set_tail(e.edge, tail.node);
    306306    }
    307307
    308     void setHead(const EdgeIt e, const NodeIt head) {
     308    void setHead(EdgeIt e, NodeIt head) {
    309309      _set_head(e.edge, head.node);
    310310    }
     
    329329    protected:
    330330      node_item* node;
    331       friend int ListGraph::id(const NodeIt v) const;
     331      friend int ListGraph::id(NodeIt v) const;
    332332    public:
    333333      NodeIt() : node(0) { }
     
    361361    protected:
    362362      edge_item* edge;
    363       friend int ListGraph::id(const EdgeIt e) const;
     363      friend int ListGraph::id(EdgeIt e) const;
    364364    public:
    365365      EdgeIt() : edge(0) { }
     
    407407    public:
    408408      OutEdgeIt() : EdgeIt(), v(0) { }
    409       OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
     409      OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
    410410      OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
    411411    protected:
     
    422422    public:
    423423      InEdgeIt() : EdgeIt(), v(0) { }
    424       InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
     424      InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
    425425      InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
    426426    protected:
     
    442442    public:
    443443      SymEdgeIt() : EdgeIt(), v(0) { }
    444       SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) {
     444      SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) {
    445445        out_or_in=1;
    446446        edge=v->_first_out_edge;
Note: See TracChangeset for help on using the changeset viewer.