src/work/bfsdemo.cc
author alpar
Wed, 02 Feb 2005 13:11:54 +0000
changeset 1117 5767cc417f62
parent 6 b63d1bc367f7
permissions -rw-r--r--
Bugfix
alpar@3
     1
#include <iostream>
alpar@3
     2
#include <graph.h>
alpar@3
     3
#include <bfs.h>
alpar@3
     4
alpar@3
     5
using namespace NEGRO;
alpar@3
     6
using namespace std;
alpar@3
     7
alpar@3
     8
class IGraph 
alpar@3
     9
{
alpar@3
    10
public:
alpar@3
    11
alpar@3
    12
  //  struct NodeType {bfs_node_data<TestGraph> bfs;};
alpar@3
    13
  struct NodeType {bool isVis;};
alpar@3
    14
alpar@3
    15
  vector<NodeType> nodes;
alpar@3
    16
  
alpar@3
    17
  class NodeIterator 
alpar@3
    18
  {
alpar@3
    19
  public:
alpar@3
    20
    IGraph *G;
alpar@3
    21
    int n;
alpar@3
    22
    NodeIterator &operator ++() { n++; return *this;}
alpar@3
    23
    NodeType &operator *() const { return G->nodes[n];}
alpar@3
    24
    NodeType *operator ->() const { return &(G->nodes[n]);}
alpar@3
    25
    bool isValid() const {return n<=5000;}
alpar@3
    26
    int Index() {return n;} //csak a kiirashoz kell
alpar@4
    27
alpar@4
    28
    NodeIterator() {}
alpar@4
    29
    NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this.
alpar@3
    30
  };
alpar@3
    31
  
alpar@3
    32
  void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
alpar@3
    33
alpar@3
    34
  class OutEdgeIterator 
alpar@3
    35
  {    
alpar@3
    36
  public:
alpar@3
    37
    IGraph *G;
alpar@3
    38
    int f,t;
alpar@3
    39
    int gcd() { int a=f;int b=t;int c;while((c=a%b)) {a=b;b=c;} ; return b;}
alpar@3
    40
    OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
alpar@3
    41
    bool isValid() const {return t<=5000;}
alpar@3
    42
    NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
alpar@3
    43
    NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
alpar@3
    44
    NodeIterator Anode() const {return From();}
alpar@3
    45
    NodeIterator Bnode() const {return To();}
alpar@4
    46
alpar@4
    47
    OutEdgeIterator() {}
alpar@4
    48
    OutEdgeIterator(IGraph &Gr,NodeIterator &n)  //Bfs class prefer this.
alpar@4
    49
    {G=&Gr;f=n.n;t=0;operator++();}
alpar@3
    50
  };
alpar@3
    51
alpar@3
    52
  typedef OutEdgeIterator EdgeIterator;
alpar@3
    53
  void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
alpar@3
    54
  {i.G=this;i.f=n.n;i.t=0;++i;}
alpar@3
    55
alpar@3
    56
  IGraph() : nodes(5001) {}
alpar@3
    57
};
alpar@3
    58
alpar@3
    59
class IMaps_t
alpar@3
    60
{
alpar@3
    61
public:
alpar@3
    62
//     class_element_map<IGraph::NodeIterator,
alpar@3
    63
//   		    IGraph::NodeType,
alpar@3
    64
//   		    bool,
alpar@3
    65
//   		    &IGraph::NodeType::isVis> visited;
alpar@3
    66
  struct _visited_map_t {
alpar@3
    67
    typedef bool value_type;
alpar@3
    68
    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
alpar@3
    69
    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
alpar@8
    70
    void SetG(IGraph &G) {}
alpar@3
    71
  } visited;
alpar@3
    72
  struct _tree_map_t {
alpar@3
    73
    typedef IGraph::EdgeIterator value_type;
alpar@3
    74
    void Put(const IGraph::NodeIterator &n,const value_type &t)
alpar@3
    75
    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
alpar@8
    76
    void SetG(IGraph &G) {}
alpar@3
    77
  } tree;
alpar@3
    78
  do_nothing_map dist;   //node->int (W)
alpar@3
    79
  do_nothing_map priority; //node->int (W)
alpar@3
    80
};
alpar@3
    81
alpar@4
    82
// New style bfs traits
alpar@4
    83
class BFS_T 
alpar@4
    84
{
alpar@4
    85
public:
alpar@4
    86
alpar@6
    87
  typedef IGraph Graph;
alpar@4
    88
  typedef IGraph::OutEdgeIterator SearchEdgeIterator;
alpar@4
    89
  
alpar@4
    90
  struct visited_map_t {
alpar@4
    91
    typedef bool value_type;
alpar@4
    92
    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
alpar@4
    93
    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
alpar@8
    94
    void SetG(IGraph &G) {}
alpar@4
    95
  };
alpar@4
    96
  struct tree_map_t {
alpar@4
    97
    typedef IGraph::EdgeIterator value_type;
alpar@4
    98
    void Put(const IGraph::NodeIterator &n,const value_type &t)
alpar@4
    99
    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
alpar@8
   100
    void SetG(IGraph &G) {}
alpar@4
   101
  };
alpar@4
   102
  typedef do_nothing_map dist_map_t;   //node->int (W)
alpar@4
   103
  typedef do_nothing_map priority_map_t; //node->int (W)
alpar@4
   104
};
alpar@4
   105
alpar@3
   106
alpar@3
   107
int main()
alpar@3
   108
{
alpar@3
   109
  IGraph IG;
alpar@3
   110
alpar@4
   111
//   //Function-syte calling
alpar@4
   112
//   IMaps_t IMaps;
alpar@4
   113
alpar@4
   114
//   IGraph::NodeIterator in;
alpar@4
   115
//   IG.GetFirst(in);
alpar@4
   116
//   ++in;
alpar@4
   117
//   bfs_fn(IG,in,IMaps);  
alpar@4
   118
alpar@4
   119
  //Class-style calling:
alpar@4
   120
  
alpar@3
   121
  IGraph::NodeIterator in;
alpar@3
   122
  IG.GetFirst(in);
alpar@3
   123
  ++in;
alpar@4
   124
  Bfs<BFS_T> bfs;
alpar@4
   125
  bfs.SetG(IG);
alpar@4
   126
  bfs.Init(in);
alpar@4
   127
  bfs.Run();
alpar@3
   128
}