8 using namespace lemon; |
8 using namespace lemon; |
9 |
9 |
10 struct _BFS_DEFAULT_VIS {}; |
10 struct _BFS_DEFAULT_VIS {}; |
11 struct _BFS_CUSTOM_VIS {}; |
11 struct _BFS_CUSTOM_VIS {}; |
12 |
12 |
13 template<class GT,class VT,class DVT,class PNT,class PET,class PT > |
13 |
14 class _BFS |
14 class _Bfs_Traits |
|
15 { |
|
16 typedef ListGraph Graph; |
|
17 } |
|
18 |
|
19 template<class T> |
|
20 class _Bfs |
15 { |
21 { |
16 public: |
22 public: |
17 typedef GT Graph; |
23 typedef typename T::Graph Graph; |
18 typedef VT Visited; |
24 typedef typename T::Reached Reached; |
19 typedef PNT PredNode; |
25 typedef typename T::PredNode PredNode; |
20 typedef PET PredEdge; |
26 typedef typename T::PredEdge PredEdge; |
21 typedef PT Priority; |
27 typedef typename T::Priority Priority; |
22 // typedef QDT QueueData; |
28 |
|
29 typedef typename T::DefaultReachedTag DefaultReachedTag; |
23 |
30 |
24 typedef typename Graph::Node Node; |
31 typedef typename Graph::Node Node; |
25 typedef typename Graph::OutEdgeIt OutEdgeIt; |
32 typedef typename Graph::OutEdgeIt OutEdgeIt; |
26 |
33 |
27 typedef DVT DefaultVisitedTag; |
|
28 |
|
29 const Graph &_graph; |
34 const Graph &_graph; |
30 |
35 |
31 Node _source; |
36 Node _source; |
32 |
37 |
33 Visited *_visited; |
38 Reached *_visited; |
34 PredNode _predNode; |
39 PredNode _predNode; |
35 PredEdge _predEdge; |
40 PredEdge _predEdge; |
36 Priority _priority; |
41 Priority _priority; |
37 |
42 |
38 _BFS(const Graph &g, |
43 _Bfs(const Graph &g, |
39 Node s, |
44 Node s, |
40 Visited *v, |
45 Reached *v, |
41 PredNode &pn, |
46 PredNode &pn, |
42 PredEdge &pe, |
47 PredEdge &pe, |
43 Priority &pr) :_graph(g), _source(s), |
48 Priority &pr) :_graph(g), _source(s), |
44 _visited(v), |
49 _visited(v), |
45 _predNode(pn), _predEdge(pe), _priority(pr) { } |
50 _predNode(pn), _predEdge(pe), _priority(pr) { } |
46 |
51 |
47 |
52 |
48 int run(const _BFS_CUSTOM_VIS &) |
53 int run(const _Bfs_CUSTOM_VIS &) |
49 { |
54 { |
50 using namespace std; |
55 using namespace std; |
51 |
56 |
52 int N=_graph.nodeNum(); |
57 int N=_graph.nodeNum(); |
53 vector<Node> Q(N); |
58 vector<Node> Q(N); |
73 |
78 |
74 return 1; //Why return 1? |
79 return 1; //Why return 1? |
75 } |
80 } |
76 int run(const _BFS_DEFAULT_VIS &) |
81 int run(const _BFS_DEFAULT_VIS &) |
77 { |
82 { |
78 _visited= new Visited(_graph); |
83 _visited= new Reached(_graph); |
79 int r = run(_BFS_CUSTOM_VIS()); |
84 int r = run(_BFS_CUSTOM_VIS()); |
80 delete _visited; |
85 delete _visited; |
81 return r; |
86 return r; |
82 } |
87 } |
83 int run() { return run(DefaultVisitedTag());} |
88 int run() { return run(DefaultReachedTag());} |
84 |
89 |
85 template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
90 template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
86 setVisitMap(T &t) |
91 setVisitMap(T &t) |
87 { |
92 { |
88 return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
93 return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
89 (_graph,_source,&t,_predNode,_predEdge,_priority); |
94 (_graph,_source,&t,_predNode,_predEdge,_priority); |
90 } |
95 } |
91 |
96 |
92 template<class T> |
97 template<class T> |
93 _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority> |
98 _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> |
94 setPredNodeMap(T &t) |
99 setPredNodeMap(T &t) |
95 { |
100 { |
96 return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority> |
101 return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> |
97 (_graph,_source, |
102 (_graph,_source, |
98 _visited, |
103 _visited, |
99 t,_predEdge,_priority); |
104 t,_predEdge,_priority); |
100 } |
105 } |
101 |
106 |
102 template<class T> |
107 template<class T> |
103 _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority> |
108 _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> |
104 setPredEdgeMap(T &t) |
109 setPredEdgeMap(T &t) |
105 { |
110 { |
106 return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority> |
111 return _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> |
107 (_graph,_source, |
112 (_graph,_source, |
108 _visited, |
113 _visited, |
109 _predNode,t,_priority); |
114 _predNode,t,_priority); |
110 } |
115 } |
111 |
116 |
112 _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority> |
117 _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> |
113 setNothing() |
118 setNothing() |
114 { |
119 { |
115 return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority> |
120 return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> |
116 (_graph,_source, |
121 (_graph,_source, |
117 _visited, |
122 _visited, |
118 _predNode,_predEdge,_priority); |
123 _predNode,_predEdge,_priority); |
119 } |
124 } |
120 }; |
125 }; |
121 |
126 |
122 |
127 |
123 template<class G> |
128 template<class G> |
124 _BFS<G, |
129 _Bfs<G, |
125 typename G::template NodeMap<bool>, |
130 typename G::template NodeMap<bool>, |
126 _BFS_DEFAULT_VIS, |
131 _BFS_DEFAULT_VIS, |
127 NullMap<typename G::Node,typename G::Node>, |
132 NullMap<typename G::Node,typename G::Node>, |
128 NullMap<typename G::Node,typename G::Edge>, |
133 NullMap<typename G::Node,typename G::Edge>, |
129 NullMap<typename G::Node,int> > |
134 NullMap<typename G::Node,int> > |
130 bfs(const G &g,typename G::Node s) |
135 bfs(const G &g,typename G::Node s) |
131 { |
136 { |
132 // typename G::template NodeMap<bool> v(g); |
137 // typename G::template NodeMap<bool> v(g); |
133 |
138 |
134 return _BFS < G, |
139 return _Bfs < G, |
135 typename G::template NodeMap<bool>, |
140 typename G::template NodeMap<bool>, |
136 _BFS_DEFAULT_VIS, |
141 _BFS_DEFAULT_VIS, |
137 NullMap<typename G::Node,typename G::Node>, |
142 NullMap<typename G::Node,typename G::Node>, |
138 NullMap<typename G::Node,typename G::Edge>, |
143 NullMap<typename G::Node,typename G::Edge>, |
139 NullMap<typename G::Node,int> > |
144 NullMap<typename G::Node,int> > |