equal
deleted
inserted
replaced
22 NodeIterator &operator ++() { n++; return *this;} |
22 NodeIterator &operator ++() { n++; return *this;} |
23 NodeType &operator *() const { return G->nodes[n];} |
23 NodeType &operator *() const { return G->nodes[n];} |
24 NodeType *operator ->() const { return &(G->nodes[n]);} |
24 NodeType *operator ->() const { return &(G->nodes[n]);} |
25 bool isValid() const {return n<=5000;} |
25 bool isValid() const {return n<=5000;} |
26 int Index() {return n;} //csak a kiirashoz kell |
26 int Index() {return n;} //csak a kiirashoz kell |
|
27 |
|
28 NodeIterator() {} |
|
29 NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this. |
27 }; |
30 }; |
28 |
31 |
29 void GetFirst(NodeIterator &i) {i.G=this;i.n=1;} |
32 void GetFirst(NodeIterator &i) {i.G=this;i.n=1;} |
30 |
33 |
31 class OutEdgeIterator |
34 class OutEdgeIterator |
38 bool isValid() const {return t<=5000;} |
41 bool isValid() const {return t<=5000;} |
39 NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;} |
42 NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;} |
40 NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;} |
43 NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;} |
41 NodeIterator Anode() const {return From();} |
44 NodeIterator Anode() const {return From();} |
42 NodeIterator Bnode() const {return To();} |
45 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++();} |
43 }; |
50 }; |
44 |
51 |
45 typedef OutEdgeIterator EdgeIterator; |
52 typedef OutEdgeIterator EdgeIterator; |
46 void GetFirst(OutEdgeIterator &i,const NodeIterator &n) |
53 void GetFirst(OutEdgeIterator &i,const NodeIterator &n) |
47 {i.G=this;i.f=n.n;i.t=0;++i;} |
54 {i.G=this;i.f=n.n;i.t=0;++i;} |
68 } tree; |
75 } tree; |
69 do_nothing_map dist; //node->int (W) |
76 do_nothing_map dist; //node->int (W) |
70 do_nothing_map priority; //node->int (W) |
77 do_nothing_map priority; //node->int (W) |
71 }; |
78 }; |
72 |
79 |
|
80 // New style bfs traits |
|
81 class BFS_T |
|
82 { |
|
83 public: |
|
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 |
73 |
102 |
74 int main() |
103 int main() |
75 { |
104 { |
76 IGraph IG; |
105 IGraph IG; |
77 IMaps_t IMaps; |
|
78 |
106 |
|
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 |
79 IGraph::NodeIterator in; |
117 IGraph::NodeIterator in; |
80 IG.GetFirst(in); |
118 IG.GetFirst(in); |
81 ++in; |
119 ++in; |
82 bfs(IG,in,IMaps); |
120 Bfs<BFS_T> bfs; |
|
121 bfs.SetG(IG); |
|
122 bfs.Init(in); |
|
123 bfs.Run(); |
83 } |
124 } |