COIN-OR::LEMON - Graph Library

Changeset 3:272a5677bd6d in lemon-0.x for src/include


Ignore:
Timestamp:
12/13/03 16:44:50 (17 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@15
Message:
  • Marci type iterator constructors
  • src/demo/bfsdemo.cc: demo for bfs.h
  • cosmetical changes
Location:
src/include
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/include/bfs.h

    r2 r3  
    3939 
    4040 
    41 //   Nem jo! Osszeakad a masik Set-tel
     41//   Nem jo! Osszeakad a masik Put-tel
    4242//   class do_nothing_map {};
    4343//   template <typename V,typename T>
    44 //   void Set(const do_nothing_map &p,const V &v,const T &t) {}
     44//   void Put(const do_nothing_map &p,const V &v,const T &t) {}
    4545 
    4646  struct do_nothing_map {
    4747  template <typename V,typename T>
    48   static void Set(V v,T t) {}
     48  static void Put(V v,T t) {}
    4949  };
    5050 
     
    5454  public:
    5555    typedef T value_type;
    56     static void Set(const I &i, const T &t) {(*i).*M=t;}
     56    static void Put(const I &i, const T &t) {(*i).*M=t;}
    5757    static T Get(const I i) {return (*i).*M;}
    5858    T &operator[](I i) {return (*i).*M;}
     
    6161  /*
    6262     template <typename C,typename I,typename T, T C::*M>
    63      void Set(class_element_map<C,T,M> p,I i, T t)
     63     void Put(class_element_map<C,T,M> p,I i, T t)
    6464     {
    6565     i->*M=t;   
     
    6868
    6969  template <typename P,typename I,typename T>
    70   inline void Set(P &p,const I &i, const T &t)
    71   {
    72     p.Set(i,t);   
     70  inline void Put(P &p,const I &i, const T &t)
     71  {
     72    p.Put(i,t);   
    7373  };
    7474  template <typename P,typename I>
     
    126126      bfs_node_data<G> NodeType::*d;
    127127      typedef bool value_type;
    128       void Set(typename G::NodeIterator &i, const value_type &t)
     128      void Put(typename G::NodeIterator &i, const value_type &t)
    129129      {((*i).*d).visited=t;}
    130130      value_type Get(const typename G::NodeIterator &i) const
     
    137137      bfs_node_data<G> NodeType::*d;
    138138      typedef typename G::EdgeIterator value_type;
    139       void Set(typename G::NodeIterator &i, const value_type &t)
     139      void Put(typename G::NodeIterator &i, const value_type &t)
    140140      {((*i).*d).tree=t;}
    141141      value_type Get(const typename G::NodeIterator &i) const
     
    148148      bfs_node_data<G> NodeType::*d;
    149149      typedef int value_type;
    150       void Set(typename G::NodeIterator &i, const value_type &t)
     150      void Put(typename G::NodeIterator &i, const value_type &t)
    151151      {((*i).*d).dist=t;}
    152152      value_type Get(const typename G::NodeIterator &i) const
     
    159159      bfs_node_data<G> NodeType::*d;
    160160      typedef int value_type;
    161       void Set(typename G::NodeIterator &i,  const value_type &t)
     161      void Put(typename G::NodeIterator &i,  const value_type &t)
    162162      {((*i).*d).priority=t;}
    163163      value_type Get(const typename G::NodeIterator &i) const
     
    176176    bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
    177177    {
    178       SetDataField(dd);
     178      PutDataField(dd);
    179179    }
    180180   
     
    211211   
    212212    for(Gr.GetFirst(n);n.isValid();++n)
    213       Set(maps.visited,n,false);
     213      Put(maps.visited,n,false);
    214214   
    215215    queue<Q_T> Q;
     
    218218    q.dist=0;
    219219    Q.push(q);
    220     Set(maps.visited,start_node,true);
    221     //      Set(maps::tree,start_node,?????);
    222     Set(maps.dist,start_node,0);
    223     Set(maps.priority,start_node,pr++);
     220    Put(maps.visited,start_node,true);
     221    //      Put(maps::tree,start_node,?????);
     222    Put(maps.dist,start_node,0);
     223    Put(maps.priority,start_node,pr++);
    224224   
    225225    do {
     
    231231          q.dist=d;
    232232          Q.push(q);
    233           Set(maps.visited,m,true);
    234           Set(maps.tree,m,e);
    235           Set(maps.dist,m,d);
    236           Set(maps.priority,m,pr++);
     233          Put(maps.visited,m,true);
     234          Put(maps.tree,m,e);
     235          Put(maps.dist,m,d);
     236          Put(maps.priority,m,pr++);
    237237        }
    238238    } while(!Q.empty());
  • src/include/graph.h

    r2 r3  
    5858     
    5959      NodeIterator() {;}
     60      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
     61      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
    6062      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
    6163     
     
    149151    {
    150152    public:
     153      InEdgeIterator() {}
     154      InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
     155      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
     156
    151157      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
    152158      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
     
    170176    {
    171177    public:
     178      OutEdgeIterator() {}
     179      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
     180      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
     181
    172182      OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
    173183      OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
     
    193203     
    194204    public:
     205      SymEdgeIterator() {}
     206      SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
     207      { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
     208
    195209      SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
    196210      SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
     
    217231     
    218232    public:
     233      AllEdgeIterator() {}
     234      AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
     235      {
     236        e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
     237      } 
     238
    219239      AllEdgeIterator &GoNext()
    220240      {
     
    249269    typedef SymEdgeIterator DeletingSymEdgeIterator;
    250270   
    251     const NodeIterator &FirstNode()
     271    const NodeIterator FirstNode()
    252272    {
    253273      NodeIterator i;
     
    285305   
    286306    //Vagy beginnode()?
    287     const DeletingEdgeIterator &FirstOut(const NodeIterator &n)
     307    const DeletingEdgeIterator FirstOut(const NodeIterator &n)
    288308    {
    289309      EdgeIterator i;
     
    291311      return i;
    292312    }
    293     const DeletingEdgeIterator &FirstIn(const NodeIterator &n)
     313    const DeletingEdgeIterator FirstIn(const NodeIterator &n)
    294314    {
    295315      EdgeIterator i;
     
    297317      return i;
    298318    }
    299     const DeletingSymEdgeIterator &FirstSym(const NodeIterator &n)
     319    const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
    300320    {
    301321      EdgeIterator i;
     
    369389   
    370390    int NodeNum() { OldGraph<N,E>::NodeNum(); }
    371     int Clean() { OldGraph<N,E>::Clean(); }
     391    void Clean() { OldGraph<N,E>::Clean(); }
    372392
    373393    Graph() : _FST(this) {}
  • src/include/oldgraph.h

    r1 r3  
    112112  int NodeNum() {return nodenum;};
    113113  int EdgeNum();
    114   int MaxNode() {return nodes_size;};
    115   int FirstNode() {return firstnode;};
    116   int NextNode(int n) {return nodes[n].next;};
    117   int PrevNode(int n) {return nodes[n].prev;};
    118   N& operator()(int n) {return *(N*)(nodes[n].data);};
    119   N& Data      (int n) {return *(N*)(nodes[n].data);};
     114  int MaxNode() const {return nodes_size;};
     115  int FirstNode() const {return firstnode;};
     116  int NextNode(int n) const {return nodes[n].next;};
     117  int PrevNode(int n) const {return nodes[n].prev;};
     118  N& operator()(int n) const {return *(N*)(nodes[n].data);};
     119  N& Data      (int n) const {return *(N*)(nodes[n].data);};
    120120  int AddNode();
    121   void AddNodeBlock(int n) {for(int i=0;i<n;i++) AddNode();}
     121  void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}
    122122  int AddNode(int n);
    123123  void Delete(int n);
    124   int isaNode(int n) {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
    125  
    126   int InDeg(int n) {return nodes[n].indeg;};
    127   int OutDeg(int n) {return nodes[n].outdeg;};
    128   EdgePoint FirstIn(int n) {return nodes[n].firstin;};
    129   EdgePoint FirstOut(int n) {return nodes[n].firstout;};
    130 
    131   E& operator()(EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
    132   E& Data      (EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
    133   int From(EdgePoint e) {return e->from;};
    134   int To(EdgePoint e) {return e->to;};
    135   EdgePoint NextIn(EdgePoint e)
     124  int isaNode(int n) const
     125        {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
     126 
     127  int InDeg(int n) const {return nodes[n].indeg;};
     128  int OutDeg(int n) const {return nodes[n].outdeg;};
     129  EdgePoint FirstIn(int n) const {return nodes[n].firstin;};
     130  EdgePoint FirstOut(int n) const {return nodes[n].firstout;};
     131
     132  E& operator()(EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
     133  E& Data      (EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
     134  int From(EdgePoint e) const {return e->from;};
     135  int To(EdgePoint e) const {return e->to;};
     136  EdgePoint NextIn(EdgePoint e) const
    136137    {return e->nextin;};
    137   EdgePoint NextOut(EdgePoint e)
     138  EdgePoint NextOut(EdgePoint e)const
    138139    {return e->nextout;};
    139140  EdgePoint AddEdge(int f, int t);
     
    142143  //  EdgePoint Edge(E &d)
    143144  //    {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
    144   E& operator()(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
    145   E& Data(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
     145  E& operator()(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
     146  E& Data(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
    146147  void Delete(int f, int t) {Delete(Edge(f,t));};
    147148  void Reverse(EdgePoint e);
     
    149150  // Functions for EdgeIndex
    150151 
    151   EdgePoint Edge(EdgeIndex i)
     152  EdgePoint Edge(EdgeIndex i) const
    152153    { return (EdgePoint)(edges[i.block]->fields+i.index);};
    153   EdgeIndex Index(EdgePoint e) { return e->index;};
    154   EdgeIndex Index(int f, int t) { EdgePoint e; return Edge(f,t)->index; }
     154  EdgeIndex Index(EdgePoint e) const { return e->index;};
     155  EdgeIndex Index(int f, int t) const { EdgePoint e; return Edge(f,t)->index; }
    155156  void Delete(EdgeIndex i) { Delete(Edge(i));};
    156   E& operator()(EdgeIndex i)
     157  E& operator()(EdgeIndex i) const
    157158     {return *(E*)(edges[i.block]->fields[i.index].data);};
    158   E& Data(EdgeIndex i)
     159  E& Data(EdgeIndex i) const
    159160     {return *(E*)(edges[i.block]->fields[i.index].data);};
    160161  EdgePoint AddEdge(int f, int t,EdgeIndex in);
     
    164165  // Operators for symmetric graphs:
    165166
    166   EdgePoint FirstEdge(int n)
     167  EdgePoint FirstEdge(int n) const
    167168    { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
    168   EdgePoint NextEdge(int n,EdgePoint e)
     169  EdgePoint NextEdge(int n,EdgePoint e) const
    169170    { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
    170   int Opposite(EdgePoint e,int n)
     171  int Opposite(EdgePoint e,int n) const
    171172    { return From(e)+To(e)-n; };
    172173 
     
    223224template<class N, class E> void OldGraph<N,E>::destroy()
    224225{
    225   edge_block *oe;
    226226  int i;
    227227 
Note: See TracChangeset for help on using the changeset viewer.