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@3
|
70 |
} visited;
|
alpar@3
|
71 |
struct _tree_map_t {
|
alpar@3
|
72 |
typedef IGraph::EdgeIterator value_type;
|
alpar@3
|
73 |
void Put(const IGraph::NodeIterator &n,const value_type &t)
|
alpar@3
|
74 |
{ cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
|
alpar@3
|
75 |
} tree;
|
alpar@3
|
76 |
do_nothing_map dist; //node->int (W)
|
alpar@3
|
77 |
do_nothing_map priority; //node->int (W)
|
alpar@3
|
78 |
};
|
alpar@3
|
79 |
|
alpar@4
|
80 |
// New style bfs traits
|
alpar@4
|
81 |
class BFS_T
|
alpar@4
|
82 |
{
|
alpar@4
|
83 |
public:
|
alpar@4
|
84 |
|
alpar@6
|
85 |
typedef IGraph Graph;
|
alpar@4
|
86 |
typedef IGraph::OutEdgeIterator SearchEdgeIterator;
|
alpar@4
|
87 |
|
alpar@4
|
88 |
struct visited_map_t {
|
alpar@4
|
89 |
typedef bool value_type;
|
alpar@4
|
90 |
void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
|
alpar@4
|
91 |
value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
|
alpar@4
|
92 |
};
|
alpar@4
|
93 |
struct tree_map_t {
|
alpar@4
|
94 |
typedef IGraph::EdgeIterator value_type;
|
alpar@4
|
95 |
void Put(const IGraph::NodeIterator &n,const value_type &t)
|
alpar@4
|
96 |
{ cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
|
alpar@4
|
97 |
};
|
alpar@4
|
98 |
typedef do_nothing_map dist_map_t; //node->int (W)
|
alpar@4
|
99 |
typedef do_nothing_map priority_map_t; //node->int (W)
|
alpar@4
|
100 |
};
|
alpar@4
|
101 |
|
alpar@3
|
102 |
|
alpar@3
|
103 |
int main()
|
alpar@3
|
104 |
{
|
alpar@3
|
105 |
IGraph IG;
|
alpar@3
|
106 |
|
alpar@4
|
107 |
// //Function-syte calling
|
alpar@4
|
108 |
// IMaps_t IMaps;
|
alpar@4
|
109 |
|
alpar@4
|
110 |
// IGraph::NodeIterator in;
|
alpar@4
|
111 |
// IG.GetFirst(in);
|
alpar@4
|
112 |
// ++in;
|
alpar@4
|
113 |
// bfs_fn(IG,in,IMaps);
|
alpar@4
|
114 |
|
alpar@4
|
115 |
//Class-style calling:
|
alpar@4
|
116 |
|
alpar@3
|
117 |
IGraph::NodeIterator in;
|
alpar@3
|
118 |
IG.GetFirst(in);
|
alpar@3
|
119 |
++in;
|
alpar@4
|
120 |
Bfs<BFS_T> bfs;
|
alpar@4
|
121 |
bfs.SetG(IG);
|
alpar@4
|
122 |
bfs.Init(in);
|
alpar@4
|
123 |
bfs.Run();
|
alpar@3
|
124 |
}
|