COIN-OR::LEMON - Graph Library

Changeset 4:8009bb5ddd09 in lemon-0.x


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

a 'bfs algorithm class' proposal added

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/include/bfs.h

    r3 r4  
    1010  using namespace std;
    1111 
    12 //   template <typename G,typename> class bfs_T
    13 //   {
    14 //     typedef G Graph;
    15 //     typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
    16 //     typedef Graph::NodeIterator NodeIterator;
    17    
    18 //     class bfs_node_D
    19 //     {
    20 //       EdgeIterator Tree;
    21 //       int Dist;
    22 //       int Priority;
    23 //     }
    24    
    25 
    26 //     //    template <bfs_T<G>>
    27 //     //    void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
    28 
    29    
    30  
    31 //   template <class G>
    32 //   class bfs_maps_T
    33 //   {
    34 //     typedef visited; //node->bool (RW)
    35 //     typedef tree;    //node->EdgeIterator (W)
    36 //     typedef dist;   //node->int (W)
    37 //     typedef priority; //node->int (W)
    38 //   };
    39  
    40  
    41 //   Nem jo! Osszeakad a masik Put-tel
    42 //   class do_nothing_map {};
    43 //   template <typename V,typename T>
    44 //   void Put(const do_nothing_map &p,const V &v,const T &t) {}
     12  //   template <typename G,typename> class bfs_T
     13  //   {
     14  //     typedef G Graph;
     15  //     typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
     16  //     typedef Graph::NodeIterator NodeIterator;
     17   
     18  //     class bfs_node_D
     19  //     {
     20  //       EdgeIterator Tree;
     21  //       int Dist;
     22  //       int Priority;
     23  //     }
     24  //   }
     25   
     26
     27  //     //    template <bfs_T<G>>
     28  //     //    void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
     29
     30   
     31 
     32  //   template <class G>
     33  //   class bfs_maps_T
     34  //   {
     35  //     typedef visited; //node->bool (RW)
     36  //     typedef tree;    //node->EdgeIterator (W)
     37  //     typedef dist;   //node->int (W)
     38  //     typedef priority; //node->int (W)
     39  //   };
     40 
     41 
     42  //   Nem jo! Osszeakad a masik Put-tal
     43  //   class do_nothing_map {};
     44  //   template <typename V,typename T>
     45  //   void Put(const do_nothing_map &p,const V &v,const T &t) {}
    4546 
    4647  struct do_nothing_map {
    47   template <typename V,typename T>
    48   static void Put(V v,T t) {}
     48    template <typename V,typename T>
     49    static void Put(V v,T t) {}
    4950  };
    5051 
     
    7980
    8081  /*
    81   template <typename G,typename T, typename G::EdgeType::*M>
    82   T Get(edge_element_map p,G::EdgeIterator i)
    83   {
     82    template <typename G,typename T, typename G::EdgeType::*M>
     83    T Get(edge_element_map p,G::EdgeIterator i)
     84    {
    8485    return i->*M;
    85   };
     86    };
    8687  */
    8788 
    8889  /*
    89   template <class G>
    90   class default_bfs_maps
    91   {
    92   public:
    93     typedef typename G::NodeType NodeType;
    94    
    95     class_element_map<typename G::NodeIterator,
    96                       typename G::NodeType,
    97                       bool,&NodeType::isVis> visited; //node->bool (RW)
    98     do_nothing_map tree;   //node->EdgeIterator (W)
    99     do_nothing_map dist;   //node->int (W)
    100     do_nothing_map priority; //node->int (W)
    101   };
     90     template <class G>
     91     class default_bfs_maps
     92     {
     93     public:
     94     typedef typename G::NodeType NodeType;
     95   
     96     class_element_map<typename G::NodeIterator,
     97     typename G::NodeType,
     98     bool,&NodeType::isVis> visited; //node->bool (RW)
     99     do_nothing_map tree;   //node->EdgeIterator (W)
     100     do_nothing_map dist;   //node->int (W)
     101     do_nothing_map priority; //node->int (W)
     102     };
    102103  */
    103104
     
    118119   
    119120    /*    class_element_map<typename G::NodeIterator,
    120                       typename G::NodeType,
    121                       bfs_node_data<G>,&NT::D> n_d; //node-> data
     121          typename G::NodeType,
     122          bfs_node_data<G>,&NT::D> n_d; //node-> data
    122123    */
    123124    class
     
    197198 
    198199  template<class G,class M>
    199   void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps)
     200  void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
    200201  {
    201202    using namespace std;
     
    238239    } while(!Q.empty());
    239240  };
     241
     242  // bfs algorithm class
     243  template<class T>
     244  class Bfs
     245  {
     246  public:
     247    typedef typename T::Graph_t Graph;
     248    typedef typename Graph::NodeIterator NodeIterator;
     249    typedef typename Graph::EdgeIterator EdgeIterator;
     250   
     251    typedef typename T::SearchEdgeIterator SearchEdgeIterator;
     252   
     253    typename T::visited_map_t visited_map;
     254    typename T::tree_map_t tree_map;
     255    typename T::dist_map_t dist_map;
     256    typename T::priority_map_t priority_map;
     257   
     258    struct bfs_queue_cont
     259    {
     260      NodeIterator n;
     261      int dist;
     262    };
     263   
     264    std::queue<bfs_queue_cont> bfs_queue;
     265   
     266    int priority;
     267    Graph *G;
     268   
     269    void SetG(Graph &Gr)
     270    {
     271      G=&Gr;
     272    }
     273   
     274    void Init()
     275    {
     276      //There must be a better way to do this:
     277      while(!bfs_queue.empty()) bfs_queue.pop();
     278
     279      for(NodeIterator n(*G);n.isValid();++n)
     280        Put(visited_map,n,false);
     281     
     282      priority=0;
     283     
     284    }
     285   
     286    void AddStartNode(const NodeIterator &start_node,int dist=0)
     287    {
     288      bfs_queue_cont q;
     289      q.n=start_node;
     290      q.dist=dist;
     291      bfs_queue.push(q);
     292
     293      Put(visited_map,start_node,true);
     294      //      Put(tree_map,start_node,?????);
     295      Put(dist_map,start_node,dist);
     296      Put(priority_map,start_node,priority++);   
     297    }
     298   
     299    void Init(const NodeIterator &start_node,int dist=0)
     300    {
     301     
     302      Init();
     303      AddStartNode(start_node,dist);
     304    }
     305
     306    void Run()
     307    {
     308      NodeIterator n,m;
     309      int d;
     310
     311      bfs_queue_cont q;
     312      while(!(bfs_queue.empty()/* && other stop conditions */)) {
     313        n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
     314        bfs_queue.pop();
     315        for(SearchEdgeIterator e(*G,n);e.isValid();++e)
     316          if(!Get(visited_map,(m=e.Bnode()))) {
     317            q.n=m;
     318            q.dist=d;
     319            bfs_queue.push(q);
     320            Put(visited_map,m,true);
     321            Put(tree_map,m,e);
     322            Put(dist_map,m,d);
     323            Put(priority_map,m,priority++);
     324          }
     325      }
     326    }
     327  };
     328 
    240329}
     330 
    241331#endif
  • src/work/bfsdemo.cc

    r3 r4  
    2525    bool isValid() const {return n<=5000;}
    2626    int Index() {return n;} //csak a kiirashoz kell
     27
     28    NodeIterator() {}
     29    NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this.
    2730  };
    2831 
     
    4144    NodeIterator Anode() const {return From();}
    4245    NodeIterator Bnode() const {return To();}
     46
     47    OutEdgeIterator() {}
     48    OutEdgeIterator(IGraph &Gr,NodeIterator &n)  //Bfs class prefer this.
     49    {G=&Gr;f=n.n;t=0;operator++();}
    4350  };
    4451
     
    7178};
    7279
     80// New style bfs traits
     81class BFS_T
     82{
     83public:
     84
     85  typedef IGraph Graph_t;
     86  typedef IGraph::OutEdgeIterator SearchEdgeIterator;
     87 
     88  struct visited_map_t {
     89    typedef bool value_type;
     90    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
     91    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
     92  };
     93  struct tree_map_t {
     94    typedef IGraph::EdgeIterator value_type;
     95    void Put(const IGraph::NodeIterator &n,const value_type &t)
     96    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
     97  };
     98  typedef do_nothing_map dist_map_t;   //node->int (W)
     99  typedef do_nothing_map priority_map_t; //node->int (W)
     100};
     101
    73102
    74103int main()
    75104{
    76105  IGraph IG;
    77   IMaps_t IMaps;
    78106
     107//   //Function-syte calling
     108//   IMaps_t IMaps;
     109
     110//   IGraph::NodeIterator in;
     111//   IG.GetFirst(in);
     112//   ++in;
     113//   bfs_fn(IG,in,IMaps); 
     114
     115  //Class-style calling:
     116 
    79117  IGraph::NodeIterator in;
    80118  IG.GetFirst(in);
    81119  ++in;
    82   bfs(IG,in,IMaps); 
     120  Bfs<BFS_T> bfs;
     121  bfs.SetG(IG);
     122  bfs.Init(in);
     123  bfs.Run();
    83124}
Note: See TracChangeset for help on using the changeset viewer.