COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 157:ee17030e5f47 in lemon-0.x


Ignore:
Timestamp:
03/07/04 20:33:34 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@219
Message:

One more step toward the standars interface.

Location:
src/work/alpar
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed

  • src/work/alpar/emptygraph.h

    r147 r157  
    3939  class EachEdgeIt : public EdgeIt {
    4040    EachEdgeIt() {}
    41     EachEdgeIt(const EmptyGraph &, NodeIt) {}
     41    EachEdgeIt(const EmptyGraph &) {}
    4242  };
    4343

  • src/work/alpar/smart_graph.h

    r136 r157  
    44#define SMART_GRAPH_H
    55
    6 #include <iostream>
    76#include <vector>
    87#include <limits.h>
    98
     9struct _Invalid {} Invalid;
     10
    1011namespace hugo {
    1112
    1213  class SmartGraph {
    1314
    14     static const int INVALID_EDGE=-1;
    15     static const int INVALID_NODE=INT_MAX;
     15//     static const int INVALID=-1;
     16//     static const int INVALID_NODE=INT_MAX;
    1617
    1718    struct NodeT
    1819    {
    1920      int first_in,first_out;     
    20       NodeT() : first_in(INVALID_EDGE), first_out(INVALID_EDGE) {}
     21      NodeT() : first_in(-1), first_out(-1) {}
    2122    };
    2223    struct EdgeT
    … …  
    2425      int head, tail, next_in, next_out;     
    2526      //FIXME: is this necessary?
    26       EdgeT() : next_in(INVALID_EDGE), next_out(INVALID_EDGE) {} 
     27      EdgeT() : next_in(-1), next_out(-1) {} 
    2728    };
    2829
    … …  
    3839      virtual void add(const Key k) = NULL;
    3940      virtual void erase(const Key k) = NULL;
    40       DynMapBase(SmartGraph &_G) : G(&_G) {}
     41      DynMapBase(const SmartGraph &_G) : G(&_G) {}
    4142      virtual ~DynMapBase() {}
    4243      friend class SmartGraph;
    4344    };
    44 
    4545  public:
    4646    template <typename T> class DynEdgeMap;
    … …  
    5151
    5252  protected:
    53     std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
    54     std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
     53    mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
     54    mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
    5555   
    5656  public:
    … …  
    6161    class InEdgeIt;
    6262   
    63     //      class NodeIt { int n; };
     63    //     class NodeIt { int n; };
    6464    //     class EachNodeIt : public NodeIt { };
    6565    //     class EdgeIt { int n; };
    … …  
    6767    //     class OutEdgeIt : public EdgeIt {};
    6868    //     class InEdgeIt : public EdgeIt {};
    69     //    class SymEdgeIt;
     69    //     class SymEdgeIt;
    7070   
    7171    template <typename T> class NodeMap;
    … …  
    9797    NodeIt head(EdgeIt e) const { return edges[e.n].head; }
    9898
    99     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
    100     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
    101     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
    102 
    103     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
    104     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
    105     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
     99//     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
     100//     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
     101//     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
     102
     103//     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
     104//     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
     105//     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
    106106
    107107    EachNodeIt& getFirst(EachNodeIt& v) const {
    … …  
    128128    }
    129129
    130     bool valid(EdgeIt e) const { return e.n!=INVALID_EDGE; }
    131     bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
    132     bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
    133    
    134     void setInvalid(EdgeIt &e) { e.n=INVALID_EDGE; }
    135     void setInvalid(NodeIt &n) { n.n=INVALID_NODE; }
    136    
    137     template <typename It> It next(It it) const
    138       //    { It tmp(it); return goNext(tmp); }
    139     { It tmp; tmp.n=it.n+1; return tmp; }
    140 
    141     NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
    142     OutEdgeIt& goNext(OutEdgeIt& it) const
     130    bool valid(EdgeIt e) const { return e.n!=-1; }
     131    //    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
     132    bool valid(NodeIt n) const { return n.n!=-1; }
     133   
     134    void setInvalid(EdgeIt &e) { e.n=-1; }
     135    void setInvalid(NodeIt &n) { n.n=-1; }
     136   
     137    template <typename It> It getNext(It it) const
     138    { It tmp(it); return next(tmp); }
     139    //{ It tmp; tmp.n=it.n+1; return tmp; }
     140
     141    NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
     142    OutEdgeIt& next(OutEdgeIt& it) const
    143143    { it.n=edges[it.n].next_out; return it; }
    144     InEdgeIt& goNext(InEdgeIt& it) const
     144    InEdgeIt& next(InEdgeIt& it) const
    145145    { it.n=edges[it.n].next_in; return it; }
    146     EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
     146    EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
    147147
    148148    int id(NodeIt v) const { return v.n; }
    … …  
    167167
    168168      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
    169           i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
     169          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
    170170
    171171      return e;
    … …  
    187187      int n;
    188188      friend int SmartGraph::id(NodeIt v) const;
     189      NodeIt(int nn) {n=nn;}
    189190    public:
    190191      NodeIt() {}
    191       NodeIt(int nn) {n=nn;}
     192      NodeIt (_Invalid i) { n=-1; }
    192193      bool operator==(const NodeIt i) const {return n==i.n;}
    193194      bool operator!=(const NodeIt i) const {return n!=i.n;}
     195      bool operator<(const NodeIt i) const {return n<i.n;}
    194196    };
    195197   
    … …  
    197199      friend class SmartGraph;
    198200    public:
    199       EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
     201      EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
    200202      EachNodeIt() : NodeIt() { }
    201203    };
    … …  
    211213      int n;
    212214      friend int SmartGraph::id(EdgeIt e) const;
     215
     216      EdgeIt(int nn) {n=nn;}
    213217    public:
    214218      EdgeIt() { }
    215       EdgeIt(int nn) {n=nn;}
     219      EdgeIt (_Invalid i) { n=-1; }
    216220      bool operator==(const EdgeIt i) const {return n==i.n;}
    217221      bool operator!=(const EdgeIt i) const {return n!=i.n;}
     222      bool operator<(const EdgeIt i) const {return n<i.n;}
    218223    };
    219224   
    … …  
    221226      friend class SmartGraph;
    222227    public:
    223       EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
     228      EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
     229      EachEdgeIt (_Invalid i) : EdgeIt(i) { }
    224230      EachEdgeIt() : EdgeIt() { }
    225231    };
    … …  
    229235    public:
    230236      OutEdgeIt() : EdgeIt() { }
     237      OutEdgeIt (_Invalid i) : EdgeIt(i) { }
     238
    231239      OutEdgeIt(const SmartGraph& G,const NodeIt v)
    232240        : EdgeIt(G.nodes[v.n].first_out) {}
    … …  
    237245    public:
    238246      InEdgeIt() : EdgeIt() { }
     247      InEdgeIt (_Invalid i) : EdgeIt(i) { }
    239248      InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
    240249    };
    … …  
    286295      typedef NodeIt KeyType;
    287296
    288       DynNodeMap(SmartGraph &_G) :
     297      DynNodeMap(const SmartGraph &_G) :
    289298        DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
    290299      {
    … …  
    312321        if(k.n>=container.size()) container.resize(k.n+1);
    313322      }
    314       void erase(const NodeIt k)
    315       {
    316         //FIXME: Please implement me.
    317       }
     323//       void erase(const NodeIt k)
     324//       {
     325//      //FIXME: Please implement me.
     326//       }
     327//       void erase(const EdgeIt k)
     328//       {
     329//      //FIXME: Please implement me.
     330//       }
    318331     
    319332      void set(NodeIt n, T a) { container[n.n]=a; }
    … …  
    334347      typedef EdgeIt KeyType;
    335348
    336       DynEdgeMap(SmartGraph &_G) :
     349      DynEdgeMap(const SmartGraph &_G) :
    337350        DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
    338351      {
    … …  
    377390} //namespace hugo
    378391
     392
     393
     394
    379395#endif //SMART_GRAPH_H
Note: See TracChangeset for help on using the changeset viewer.