COIN-OR::LEMON - Graph Library

Changeset 8:cd54905012bc in lemon-0.x


Ignore:
Timestamp:
12/16/03 19:17:51 (16 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@21
Message:

-New test: bfsdemo2.cc added

  • Graph class has a NodeMap? and an EdgeMap? member class
  • default_bfs_T uning the above Maps is added
  • a (property)map must provide a member function SetG() to attach the map to a graph
Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/include/bfs.h

    r6 r8  
    4646 
    4747  struct do_nothing_map {
    48     template <typename V,typename T>
    49     static void Put(V v,T t) {}
     48    template <typename V,typename T> static void Put(V v,T t) {}
     49    template <typename G> void SetG(G &g) {}
    5050  };
    5151 
     
    283283    Graph *G;
    284284   
     285    //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
     286    Bfs() {}
     287
    285288    void SetG(Graph &Gr)
    286289    {
    287290      G=&Gr;
     291      visited_map.SetG(Gr);
     292      tree_map.SetG(Gr);
     293      dist_map.SetG(Gr);
     294      priority_map.SetG(Gr);
    288295    }
    289296   
  • src/include/graph.h

    r6 r8  
    7676      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
    7777     
    78       int Index() { return n; } //If the nodes are indexable
     78      int Index() const { return n; } //If the nodes are indexable
    7979      friend class Graph;
    8080      friend class EdgeIterator;
     
    120120      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
    121121       
    122       int Index() { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
     122      int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
    123123      //If the edges are indexable
    124124
     
    402402    public:
    403403      typedef T value_type;
    404       void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
    405       T &Get(NodeIterator i) {return map[i.Index()];}
    406       T &operator[](NodeIterator i) {return map[i.Index()];}
    407 
    408       void update() { map.resize(G->OldGraph<N,E>::NodeMax());}
    409 
    410       NodeMap(Graph<N,E> &Gr) : map(Gr.OldGraph<N,E>::NodeMax()) { G=&Gr ;}
    411      
     404      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
     405      T Get(const NodeIterator i) const {return map[i.Index()];}
     406      T operator[](NodeIterator i) {return map[i.Index()];}
     407
     408      void update() { map.resize(G->MaxNode());}
     409
     410      NodeMap() {}
     411      void SetG(Graph<N,E> &Gr) { G=&Gr; update();}     
    412412    };
    413413
     
    419419    public:
    420420      typedef T value_type;
    421       void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
    422       T &Get(NodeIterator i) {return map[i.Index()];}
     421      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
     422      T &Get(const NodeIterator i) {return map[i.Index()];}
    423423      T &operator[](NodeIterator i) {return map[i.Index()];}
    424424     
    425425      void update()
    426         { map.resize(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE);}
    427      
    428       EdgeMap(Graph<N,E> &Gr)
    429         :map(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE)
    430         { G=&Gr ;}
    431      
    432     };
     426        { map.resize(G->MaxEdge());}
     427     
     428      EdgeMap() {}
     429      void SetG(Graph<N,E> &Gr)
     430      { G=&Gr ;update();}
     431     
     432    };
     433   
     434
     435    int MaxNode() { return OldGraph<N,E>::MaxNode();}
     436    int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
    433437   
    434438  };
  • src/work/bfsdemo.cc

    r6 r8  
    6868    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
    6969    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
     70    void SetG(IGraph &G) {}
    7071  } visited;
    7172  struct _tree_map_t {
     
    7374    void Put(const IGraph::NodeIterator &n,const value_type &t)
    7475    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
     76    void SetG(IGraph &G) {}
    7577  } tree;
    7678  do_nothing_map dist;   //node->int (W)
     
    9092    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
    9193    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
     94    void SetG(IGraph &G) {}
    9295  };
    9396  struct tree_map_t {
     
    9598    void Put(const IGraph::NodeIterator &n,const value_type &t)
    9699    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
     100    void SetG(IGraph &G) {}
    97101  };
    98102  typedef do_nothing_map dist_map_t;   //node->int (W)
  • src/work/bfsdemo2.cc

    r6 r8  
    1616  TestGraph::NodeIterator tn,n2;
    1717 
    18   for(int i=1;i<=5000;i++)
     18  cout << "Create nodes\n";
     19
     20  for(int i=1;i<=500;i++)
    1921    {
    2022      *(tn=G.AddNode())=i;
     
    2224    }
    2325 
     26  cout << "Create Edges\n";
     27 
    2428  for(TestGraph::NodeIterator n(G);n.isValid();++n)
    25     for(TestGraph::NodeIterator m(G);m.isValid();++m)
     29    for(TestGraph::NodeIterator m(G);m.isValid();++m) if(n!=m)
    2630      if(gcd(*n,*m)>1) G.AddEdge(n,m);
    2731 
     32 
     33  cout << "Run BFS\n";
     34
    2835  Bfs<default_bfs_T<TestGraph> > bfs;
    2936
     
    3340
    3441  for(TestGraph::NodeIterator n(G);n.isValid();++n)
    35     cout << Get(bfs.tree_map,n).From() << "->" << Get(bfs.tree_map,n).To()
    36         << '\n';
     42    if((*n)!=2)
     43      cout << (Get(bfs.dist_map,n)) << '\n';
    3744
     45  for(TestGraph::NodeIterator n(G);n.isValid();++n)
     46    if(Get(bfs.dist_map,n))
     47      cout << *(Get(bfs.tree_map,n).From()) << "->"
     48           << *(Get(bfs.tree_map,n).To())
     49           << '\n';
    3850}
Note: See TracChangeset for help on using the changeset viewer.