1.1 --- a/src/work/alpar/bfs-named-param.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,206 +0,0 @@
1.4 -// -*- mode:C++ -*-
1.5 -
1.6 -#include <lemon/smart_graph.h>
1.7 -#include <lemon/maps.h>
1.8 -#include <vector>
1.9 -#include <iostream>
1.10 -
1.11 -using namespace lemon;
1.12 -
1.13 -struct _BFS_DEFAULT_VIS {};
1.14 -struct _BFS_CUSTOM_VIS {};
1.15 -
1.16 -
1.17 -class _Bfs_Traits
1.18 -{
1.19 - typedef ListGraph Graph;
1.20 -}
1.21 -
1.22 -template<class T>
1.23 -class _Bfs
1.24 -{
1.25 - public:
1.26 - typedef typename T::Graph Graph;
1.27 - typedef typename T::Reached Reached;
1.28 - typedef typename T::PredNode PredNode;
1.29 - typedef typename T::PredEdge PredEdge;
1.30 - typedef typename T::Priority Priority;
1.31 -
1.32 - typedef typename T::DefaultReachedTag DefaultReachedTag;
1.33 -
1.34 - typedef typename Graph::Node Node;
1.35 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.36 -
1.37 - const Graph &_graph;
1.38 -
1.39 - Node _source;
1.40 -
1.41 - Reached *_visited;
1.42 - PredNode _predNode;
1.43 - PredEdge _predEdge;
1.44 - Priority _priority;
1.45 -
1.46 - _Bfs(const Graph &g,
1.47 - Node s,
1.48 - Reached *v,
1.49 - PredNode &pn,
1.50 - PredEdge &pe,
1.51 - Priority &pr) :_graph(g), _source(s),
1.52 - _visited(v),
1.53 - _predNode(pn), _predEdge(pe), _priority(pr) { }
1.54 -
1.55 -
1.56 - int run(const _Bfs_CUSTOM_VIS &)
1.57 - {
1.58 - using namespace std;
1.59 -
1.60 - int N=_graph.nodeNum();
1.61 - vector<Node> Q(N);
1.62 - int Qh=0;
1.63 - int Qt=0;
1.64 -
1.65 - for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
1.66 - _visited->set(n,false);
1.67 -
1.68 - Q[Qh++]=_source;
1.69 - _visited->set(_source,true);
1.70 - do {
1.71 - Node m;
1.72 - Node n=Q[Qt++];
1.73 - for(OutEdgeIt e(_graph,n);e!=INVALID;++e)
1.74 - if(!(*_visited)[m=_graph.target(e)]) {
1.75 - Q[Qh++]=m;
1.76 - _visited->set(m,true);
1.77 - _predNode.set(m,n);
1.78 - _predEdge.set(m,e);
1.79 - }
1.80 - } while(Qt!=Qh);
1.81 -
1.82 - return 1; //Why return 1?
1.83 - }
1.84 - int run(const _BFS_DEFAULT_VIS &)
1.85 - {
1.86 - _visited= new Reached(_graph);
1.87 - int r = run(_BFS_CUSTOM_VIS());
1.88 - delete _visited;
1.89 - return r;
1.90 - }
1.91 - int run() { return run(DefaultReachedTag());}
1.92 -
1.93 - template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
1.94 - setVisitMap(T &t)
1.95 - {
1.96 - return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
1.97 - (_graph,_source,&t,_predNode,_predEdge,_priority);
1.98 - }
1.99 -
1.100 - template<class T>
1.101 - _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>
1.102 - setPredNodeMap(T &t)
1.103 - {
1.104 - return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>
1.105 - (_graph,_source,
1.106 - _visited,
1.107 - t,_predEdge,_priority);
1.108 - }
1.109 -
1.110 - template<class T>
1.111 - _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>
1.112 - setPredEdgeMap(T &t)
1.113 - {
1.114 - return _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>
1.115 - (_graph,_source,
1.116 - _visited,
1.117 - _predNode,t,_priority);
1.118 - }
1.119 -
1.120 - _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
1.121 - setNothing()
1.122 - {
1.123 - return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
1.124 - (_graph,_source,
1.125 - _visited,
1.126 - _predNode,_predEdge,_priority);
1.127 - }
1.128 -};
1.129 -
1.130 -
1.131 -template<class G>
1.132 -_Bfs<G,
1.133 - typename G::template NodeMap<bool>,
1.134 - _BFS_DEFAULT_VIS,
1.135 - NullMap<typename G::Node,typename G::Node>,
1.136 - NullMap<typename G::Node,typename G::Edge>,
1.137 - NullMap<typename G::Node,int> >
1.138 -bfs(const G &g,typename G::Node s)
1.139 -{
1.140 - // typename G::template NodeMap<bool> v(g);
1.141 -
1.142 - return _Bfs < G,
1.143 - typename G::template NodeMap<bool>,
1.144 - _BFS_DEFAULT_VIS,
1.145 - NullMap<typename G::Node,typename G::Node>,
1.146 - NullMap<typename G::Node,typename G::Edge>,
1.147 - NullMap<typename G::Node,int> >
1.148 - (g,s,
1.149 - (typename G::template NodeMap<bool>*)(NULL),
1.150 - *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
1.151 - *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
1.152 - *((NullMap<typename G::Node,int> *)(NULL))
1.153 - );
1.154 -}
1.155 -
1.156 -
1.157 -class MyReachedMap : public SmartGraph::NodeMap<bool>
1.158 -{
1.159 - const SmartGraph &_G;
1.160 -public:
1.161 - MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
1.162 - void set(SmartGraph::Node n,bool b)
1.163 - {
1.164 - SmartGraph::NodeMap<bool>::set(n,b);
1.165 - if(b) std::cout << _G.id(n) << std::endl;
1.166 - }
1.167 -};
1.168 -
1.169 -
1.170 -int main()
1.171 -{
1.172 - SmartGraph G;
1.173 - SmartGraph::Node s=G.addNode();
1.174 - SmartGraph::Node n1=G.addNode();
1.175 - SmartGraph::Node n2=G.addNode();
1.176 - SmartGraph::Node n3=G.addNode();
1.177 - SmartGraph::Node n4=G.addNode();
1.178 - SmartGraph::Node n5=G.addNode();
1.179 - SmartGraph::Node n6=G.addNode();
1.180 - SmartGraph::Node n7=G.addNode();
1.181 -
1.182 - G.addEdge(s,n1);G.addEdge(s,n3);G.addEdge(n1,n2);G.addEdge(n1,n3);
1.183 - G.addEdge(s,n4);G.addEdge(n4,n7);G.addEdge(n7,n6);G.addEdge(n4,n5);
1.184 - G.addEdge(n7,n2);G.addEdge(n6,n3);G.addEdge(n4,s);G.addEdge(n1,s);
1.185 -
1.186 -
1.187 -
1.188 - SmartGraph::NodeMap<SmartGraph::Node> m(G);
1.189 - SmartGraph::NodeMap<SmartGraph::Edge> em(G);
1.190 -
1.191 - MyReachedMap vm(G);
1.192 -
1.193 -
1.194 - //Runs BFS on graph 'G' from node 's'.
1.195 - //(It practically does nothing, for it throws away its result.)
1.196 - bfs(G,s).run();
1.197 -
1.198 - //Runs BFS on graph 'G' from node 's'. Puts the predessor nodes to 'm'.
1.199 - bfs(G,s).setPredNodeMap(m).run();
1.200 -
1.201 - //Runs BFS on graph 'G' from node 's'.
1.202 - //Puts the predessor nodes to 'm' and the edges of the bfs tree to 'em'.
1.203 - bfs(G,s).setPredNodeMap(m).setPredEdgeMap(em).run();
1.204 -
1.205 - //Runs BFS on graph 'G' from node 's'.
1.206 - //It uses a scpecial 'visited map' that prints out the reached nodes.
1.207 - bfs(G,s).setVisitMap(vm).run();
1.208 -
1.209 -}