alpar@3: #include <iostream>
alpar@3: #include <graph.h>
alpar@3: #include <bfs.h>
alpar@3: 
alpar@3: using namespace NEGRO;
alpar@3: using namespace std;
alpar@3: 
alpar@3: class IGraph 
alpar@3: {
alpar@3: public:
alpar@3: 
alpar@3:   //  struct NodeType {bfs_node_data<TestGraph> bfs;};
alpar@3:   struct NodeType {bool isVis;};
alpar@3: 
alpar@3:   vector<NodeType> nodes;
alpar@3:   
alpar@3:   class NodeIterator 
alpar@3:   {
alpar@3:   public:
alpar@3:     IGraph *G;
alpar@3:     int n;
alpar@3:     NodeIterator &operator ++() { n++; return *this;}
alpar@3:     NodeType &operator *() const { return G->nodes[n];}
alpar@3:     NodeType *operator ->() const { return &(G->nodes[n]);}
alpar@3:     bool isValid() const {return n<=5000;}
alpar@3:     int Index() {return n;} //csak a kiirashoz kell
alpar@4: 
alpar@4:     NodeIterator() {}
alpar@4:     NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this.
alpar@3:   };
alpar@3:   
alpar@3:   void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
alpar@3: 
alpar@3:   class OutEdgeIterator 
alpar@3:   {    
alpar@3:   public:
alpar@3:     IGraph *G;
alpar@3:     int f,t;
alpar@3:     int gcd() { int a=f;int b=t;int c;while((c=a%b)) {a=b;b=c;} ; return b;}
alpar@3:     OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
alpar@3:     bool isValid() const {return t<=5000;}
alpar@3:     NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
alpar@3:     NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
alpar@3:     NodeIterator Anode() const {return From();}
alpar@3:     NodeIterator Bnode() const {return To();}
alpar@4: 
alpar@4:     OutEdgeIterator() {}
alpar@4:     OutEdgeIterator(IGraph &Gr,NodeIterator &n)  //Bfs class prefer this.
alpar@4:     {G=&Gr;f=n.n;t=0;operator++();}
alpar@3:   };
alpar@3: 
alpar@3:   typedef OutEdgeIterator EdgeIterator;
alpar@3:   void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
alpar@3:   {i.G=this;i.f=n.n;i.t=0;++i;}
alpar@3: 
alpar@3:   IGraph() : nodes(5001) {}
alpar@3: };
alpar@3: 
alpar@3: class IMaps_t
alpar@3: {
alpar@3: public:
alpar@3: //     class_element_map<IGraph::NodeIterator,
alpar@3: //   		    IGraph::NodeType,
alpar@3: //   		    bool,
alpar@3: //   		    &IGraph::NodeType::isVis> visited;
alpar@3:   struct _visited_map_t {
alpar@3:     typedef bool value_type;
alpar@3:     void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
alpar@3:     value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
alpar@8:     void SetG(IGraph &G) {}
alpar@3:   } visited;
alpar@3:   struct _tree_map_t {
alpar@3:     typedef IGraph::EdgeIterator value_type;
alpar@3:     void Put(const IGraph::NodeIterator &n,const value_type &t)
alpar@3:     { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
alpar@8:     void SetG(IGraph &G) {}
alpar@3:   } tree;
alpar@3:   do_nothing_map dist;   //node->int (W)
alpar@3:   do_nothing_map priority; //node->int (W)
alpar@3: };
alpar@3: 
alpar@4: // New style bfs traits
alpar@4: class BFS_T 
alpar@4: {
alpar@4: public:
alpar@4: 
alpar@6:   typedef IGraph Graph;
alpar@4:   typedef IGraph::OutEdgeIterator SearchEdgeIterator;
alpar@4:   
alpar@4:   struct visited_map_t {
alpar@4:     typedef bool value_type;
alpar@4:     void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
alpar@4:     value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
alpar@8:     void SetG(IGraph &G) {}
alpar@4:   };
alpar@4:   struct tree_map_t {
alpar@4:     typedef IGraph::EdgeIterator value_type;
alpar@4:     void Put(const IGraph::NodeIterator &n,const value_type &t)
alpar@4:     { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
alpar@8:     void SetG(IGraph &G) {}
alpar@4:   };
alpar@4:   typedef do_nothing_map dist_map_t;   //node->int (W)
alpar@4:   typedef do_nothing_map priority_map_t; //node->int (W)
alpar@4: };
alpar@4: 
alpar@3: 
alpar@3: int main()
alpar@3: {
alpar@3:   IGraph IG;
alpar@3: 
alpar@4: //   //Function-syte calling
alpar@4: //   IMaps_t IMaps;
alpar@4: 
alpar@4: //   IGraph::NodeIterator in;
alpar@4: //   IG.GetFirst(in);
alpar@4: //   ++in;
alpar@4: //   bfs_fn(IG,in,IMaps);  
alpar@4: 
alpar@4:   //Class-style calling:
alpar@4:   
alpar@3:   IGraph::NodeIterator in;
alpar@3:   IG.GetFirst(in);
alpar@3:   ++in;
alpar@4:   Bfs<BFS_T> bfs;
alpar@4:   bfs.SetG(IG);
alpar@4:   bfs.Init(in);
alpar@4:   bfs.Run();
alpar@3: }