NodeSubGraphWrapper, test, and ducumentation modifications.
3 #include <lemon/smart_graph.h>
4 #include <lemon/maps.h>
10 struct _BFS_DEFAULT_VIS {};
11 struct _BFS_CUSTOM_VIS {};
13 template<class GT,class VT,class DVT,class PNT,class PET,class PT >
22 // typedef QDT QueueData;
24 typedef typename Graph::Node Node;
25 typedef typename Graph::OutEdgeIt OutEdgeIt;
27 typedef DVT DefaultVisitedTag;
43 Priority &pr) :_graph(g), _source(s),
45 _predNode(pn), _predEdge(pe), _priority(pr) { }
48 int run(const _BFS_CUSTOM_VIS &)
52 int N=_graph.nodeNum();
57 for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n))
58 _visited->set(n,false);
61 _visited->set(_source,true);
65 for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e))
66 if(!(*_visited)[m=_graph.head(e)]) {
68 _visited->set(m,true);
74 return 1; //Why return 1?
76 int run(const _BFS_DEFAULT_VIS &)
78 _visited= new Visited(_graph);
79 int r = run(_BFS_CUSTOM_VIS());
83 int run() { return run(DefaultVisitedTag());}
85 template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
88 return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
89 (_graph,_source,&t,_predNode,_predEdge,_priority);
93 _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
96 return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
99 t,_predEdge,_priority);
103 _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
106 return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
109 _predNode,t,_priority);
112 _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
115 return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
118 _predNode,_predEdge,_priority);
125 typename G::template NodeMap<bool>,
127 NullMap<typename G::Node,typename G::Node>,
128 NullMap<typename G::Node,typename G::Edge>,
129 NullMap<typename G::Node,int> >
130 bfs(const G &g,typename G::Node s)
132 // typename G::template NodeMap<bool> v(g);
135 typename G::template NodeMap<bool>,
137 NullMap<typename G::Node,typename G::Node>,
138 NullMap<typename G::Node,typename G::Edge>,
139 NullMap<typename G::Node,int> >
141 (typename G::template NodeMap<bool>*)(NULL),
142 *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
143 *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
144 *((NullMap<typename G::Node,int> *)(NULL))
149 class MyVisitedMap : public SmartGraph::NodeMap<bool>
151 const SmartGraph &_G;
153 MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
154 void set(SmartGraph::Node n,bool b)
156 SmartGraph::NodeMap<bool>::set(n,b);
157 if(b) std::cout << _G.id(n) << std::endl;
165 SmartGraph::Node s=G.addNode();
166 SmartGraph::Node n1=G.addNode();
167 SmartGraph::Node n2=G.addNode();
168 SmartGraph::Node n3=G.addNode();
169 SmartGraph::Node n4=G.addNode();
170 SmartGraph::Node n5=G.addNode();
171 SmartGraph::Node n6=G.addNode();
172 SmartGraph::Node n7=G.addNode();
174 G.addEdge(s,n1);G.addEdge(s,n3);G.addEdge(n1,n2);G.addEdge(n1,n3);
175 G.addEdge(s,n4);G.addEdge(n4,n7);G.addEdge(n7,n6);G.addEdge(n4,n5);
176 G.addEdge(n7,n2);G.addEdge(n6,n3);G.addEdge(n4,s);G.addEdge(n1,s);
180 SmartGraph::NodeMap<SmartGraph::Node> m(G);
181 SmartGraph::NodeMap<SmartGraph::Edge> em(G);
186 //Runs BFS on graph 'G' from node 's'.
187 //(It practically does nothing, for it throws away its result.)
190 //Runs BFS on graph 'G' from node 's'. Puts the predessor nodes to 'm'.
191 bfs(G,s).setPredNodeMap(m).run();
193 //Runs BFS on graph 'G' from node 's'.
194 //Puts the predessor nodes to 'm' and the edges of the bfs tree to 'em'.
195 bfs(G,s).setPredNodeMap(m).setPredEdgeMap(em).run();
197 //Runs BFS on graph 'G' from node 's'.
198 //It uses a scpecial 'visited map' that prints out the reached nodes.
199 bfs(G,s).setVisitMap(vm).run();