1.1 --- a/src/work/alpar/bfs-named-param.cc Sat Nov 13 12:24:01 2004 +0000
1.2 +++ b/src/work/alpar/bfs-named-param.cc Sat Nov 13 12:53:28 2004 +0000
1.3 @@ -10,34 +10,39 @@
1.4 struct _BFS_DEFAULT_VIS {};
1.5 struct _BFS_CUSTOM_VIS {};
1.6
1.7 -template<class GT,class VT,class DVT,class PNT,class PET,class PT >
1.8 -class _BFS
1.9 +
1.10 +class _Bfs_Traits
1.11 +{
1.12 + typedef ListGraph Graph;
1.13 +}
1.14 +
1.15 +template<class T>
1.16 +class _Bfs
1.17 {
1.18 public:
1.19 - typedef GT Graph;
1.20 - typedef VT Visited;
1.21 - typedef PNT PredNode;
1.22 - typedef PET PredEdge;
1.23 - typedef PT Priority;
1.24 - // typedef QDT QueueData;
1.25 + typedef typename T::Graph Graph;
1.26 + typedef typename T::Reached Reached;
1.27 + typedef typename T::PredNode PredNode;
1.28 + typedef typename T::PredEdge PredEdge;
1.29 + typedef typename T::Priority Priority;
1.30 +
1.31 + typedef typename T::DefaultReachedTag DefaultReachedTag;
1.32
1.33 typedef typename Graph::Node Node;
1.34 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.35
1.36 - typedef DVT DefaultVisitedTag;
1.37 -
1.38 const Graph &_graph;
1.39
1.40 Node _source;
1.41
1.42 - Visited *_visited;
1.43 + Reached *_visited;
1.44 PredNode _predNode;
1.45 PredEdge _predEdge;
1.46 Priority _priority;
1.47
1.48 - _BFS(const Graph &g,
1.49 + _Bfs(const Graph &g,
1.50 Node s,
1.51 - Visited *v,
1.52 + Reached *v,
1.53 PredNode &pn,
1.54 PredEdge &pe,
1.55 Priority &pr) :_graph(g), _source(s),
1.56 @@ -45,7 +50,7 @@
1.57 _predNode(pn), _predEdge(pe), _priority(pr) { }
1.58
1.59
1.60 - int run(const _BFS_CUSTOM_VIS &)
1.61 + int run(const _Bfs_CUSTOM_VIS &)
1.62 {
1.63 using namespace std;
1.64
1.65 @@ -63,7 +68,7 @@
1.66 Node m;
1.67 Node n=Q[Qt++];
1.68 for(OutEdgeIt e(_graph,n);e!=INVALID;++e)
1.69 - if(!(*_visited)[m=_graph.head(e)]) {
1.70 + if(!(*_visited)[m=_graph.target(e)]) {
1.71 Q[Qh++]=m;
1.72 _visited->set(m,true);
1.73 _predNode.set(m,n);
1.74 @@ -75,44 +80,44 @@
1.75 }
1.76 int run(const _BFS_DEFAULT_VIS &)
1.77 {
1.78 - _visited= new Visited(_graph);
1.79 + _visited= new Reached(_graph);
1.80 int r = run(_BFS_CUSTOM_VIS());
1.81 delete _visited;
1.82 return r;
1.83 }
1.84 - int run() { return run(DefaultVisitedTag());}
1.85 + int run() { return run(DefaultReachedTag());}
1.86
1.87 - template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
1.88 + template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
1.89 setVisitMap(T &t)
1.90 {
1.91 - return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
1.92 + return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
1.93 (_graph,_source,&t,_predNode,_predEdge,_priority);
1.94 }
1.95
1.96 template<class T>
1.97 - _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
1.98 + _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>
1.99 setPredNodeMap(T &t)
1.100 {
1.101 - return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
1.102 + return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>
1.103 (_graph,_source,
1.104 _visited,
1.105 t,_predEdge,_priority);
1.106 }
1.107
1.108 template<class T>
1.109 - _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
1.110 + _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>
1.111 setPredEdgeMap(T &t)
1.112 {
1.113 - return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
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,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
1.121 + _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
1.122 setNothing()
1.123 {
1.124 - return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
1.125 + return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
1.126 (_graph,_source,
1.127 _visited,
1.128 _predNode,_predEdge,_priority);
1.129 @@ -121,7 +126,7 @@
1.130
1.131
1.132 template<class G>
1.133 -_BFS<G,
1.134 +_Bfs<G,
1.135 typename G::template NodeMap<bool>,
1.136 _BFS_DEFAULT_VIS,
1.137 NullMap<typename G::Node,typename G::Node>,
1.138 @@ -131,7 +136,7 @@
1.139 {
1.140 // typename G::template NodeMap<bool> v(g);
1.141
1.142 - return _BFS < G,
1.143 + return _Bfs < G,
1.144 typename G::template NodeMap<bool>,
1.145 _BFS_DEFAULT_VIS,
1.146 NullMap<typename G::Node,typename G::Node>,
1.147 @@ -146,11 +151,11 @@
1.148 }
1.149
1.150
1.151 -class MyVisitedMap : public SmartGraph::NodeMap<bool>
1.152 +class MyReachedMap : public SmartGraph::NodeMap<bool>
1.153 {
1.154 const SmartGraph &_G;
1.155 public:
1.156 - MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
1.157 + MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
1.158 void set(SmartGraph::Node n,bool b)
1.159 {
1.160 SmartGraph::NodeMap<bool>::set(n,b);
1.161 @@ -180,7 +185,7 @@
1.162 SmartGraph::NodeMap<SmartGraph::Node> m(G);
1.163 SmartGraph::NodeMap<SmartGraph::Edge> em(G);
1.164
1.165 - MyVisitedMap vm(G);
1.166 + MyReachedMap vm(G);
1.167
1.168
1.169 //Runs BFS on graph 'G' from node 's'.