|
1 // -*- mode:C++ -*- |
|
2 |
|
3 #include <hugo/smart_graph.h> |
|
4 #include <hugo/maps.h> |
|
5 #include <vector> |
|
6 |
|
7 using namespace hugo; |
|
8 |
|
9 struct _BFS_DEFAULT_VIS {}; |
|
10 struct _BFS_CUSTOM_VIS {}; |
|
11 |
|
12 template<class GT,class VT,class DVT,class PNT,class PET,class PT > |
|
13 class _BFS |
|
14 { |
|
15 public: |
|
16 typedef GT Graph; |
|
17 typedef VT Visited; |
|
18 typedef PNT PredNode; |
|
19 typedef PET PredEdge; |
|
20 typedef PT Priority; |
|
21 // typedef QDT QueueData; |
|
22 |
|
23 typedef typename Graph::Node Node; |
|
24 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
25 |
|
26 typedef DVT DefaultVisitedTag; |
|
27 |
|
28 const Graph &_graph; |
|
29 |
|
30 Node _source; |
|
31 |
|
32 Visited *_visited; |
|
33 PredNode _predNode; |
|
34 PredEdge _predEdge; |
|
35 Priority _priority; |
|
36 |
|
37 _BFS(const Graph &g, |
|
38 Node s, |
|
39 Visited *v, |
|
40 PredNode &pn, |
|
41 PredEdge &pe, |
|
42 Priority &pr) :_graph(g), _source(s), |
|
43 _visited(v), |
|
44 _predNode(pn), _predEdge(pe), _priority(pr) { } |
|
45 |
|
46 |
|
47 int run(const _BFS_CUSTOM_VIS &) |
|
48 { |
|
49 using namespace std; |
|
50 |
|
51 int N=_graph.nodeNum(); |
|
52 vector<Node> Q(N); |
|
53 int Qh=0; |
|
54 int Qt=0; |
|
55 |
|
56 for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n)) |
|
57 _visited->set(n,false); |
|
58 |
|
59 Q[Qh++]=_source; |
|
60 _visited->set(_source,true); |
|
61 do { |
|
62 Node m; |
|
63 Node n=Q[Qt++]; |
|
64 for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e)) |
|
65 if(!(*_visited)[m=_graph.head(e)]) { |
|
66 Q[Qh++]=m; |
|
67 _visited->set(m,true); |
|
68 _predNode.set(m,n); |
|
69 _predEdge.set(m,e); |
|
70 } |
|
71 } while(Qt!=Qh); |
|
72 |
|
73 return 1; //Why return 1? |
|
74 } |
|
75 int run(const _BFS_DEFAULT_VIS &) |
|
76 { |
|
77 _visited= new Visited(_graph); |
|
78 int r = run(_BFS_CUSTOM_VIS()); |
|
79 delete _visited; |
|
80 return r; |
|
81 } |
|
82 int run() { return run(DefaultVisitedTag());} |
|
83 |
|
84 template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
|
85 setVisitMap(T &t) |
|
86 { |
|
87 return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
|
88 (_graph,_source,&t,_predNode,_predEdge,_priority); |
|
89 } |
|
90 |
|
91 template<class T> |
|
92 _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority> |
|
93 setPredNodeMap(T &t) |
|
94 { |
|
95 return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority> |
|
96 (_graph,_source, |
|
97 _visited, |
|
98 t,_predEdge,_priority); |
|
99 } |
|
100 |
|
101 template<class T> |
|
102 _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority> |
|
103 setPredEdgeMap(T &t) |
|
104 { |
|
105 return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority> |
|
106 (_graph,_source, |
|
107 _visited, |
|
108 _predNode,t,_priority); |
|
109 } |
|
110 |
|
111 _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
|
112 setNothing() |
|
113 { |
|
114 return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
|
115 (_graph,_source, |
|
116 _visited, |
|
117 _predNode,_predEdge,_priority); |
|
118 } |
|
119 }; |
|
120 |
|
121 |
|
122 template<class G> |
|
123 _BFS<G, |
|
124 typename G::template NodeMap<bool>, |
|
125 _BFS_DEFAULT_VIS, |
|
126 NullMap<typename G::Node,typename G::Node>, |
|
127 NullMap<typename G::Node,typename G::Edge>, |
|
128 NullMap<typename G::Node,int> > |
|
129 bfs(const G &g,typename G::Node s) |
|
130 { |
|
131 // typename G::template NodeMap<bool> v(g); |
|
132 |
|
133 return _BFS < G, |
|
134 typename G::template NodeMap<bool>, |
|
135 _BFS_DEFAULT_VIS, |
|
136 NullMap<typename G::Node,typename G::Node>, |
|
137 NullMap<typename G::Node,typename G::Edge>, |
|
138 NullMap<typename G::Node,int> > |
|
139 (g,s, |
|
140 (typename G::template NodeMap<bool>*)(NULL), |
|
141 *((NullMap<typename G::Node,typename G::Node>*)(NULL)), |
|
142 *((NullMap<typename G::Node,typename G::Edge> *)(NULL)), |
|
143 *((NullMap<typename G::Node,int> *)(NULL)) |
|
144 ); |
|
145 } |
|
146 |
|
147 |
|
148 int main() |
|
149 { |
|
150 SmartGraph G; |
|
151 SmartGraph::NodeIt n(G); |
|
152 SmartGraph::NodeMap<SmartGraph::Node> m(G); |
|
153 SmartGraph::NodeMap<SmartGraph::Edge> em(G); |
|
154 |
|
155 bfs(G,n).run(); |
|
156 bfs(G,n).setPredNodeMap(m).run(); |
|
157 bfs(G,n).setPredNodeMap(m).setPredEdgeMap(em).run(); |
|
158 |
|
159 } |