Changeset 986:e997802b855c in lemon-0.x for src/work/alpar/bfs-named-param.cc
- Timestamp:
- 11/13/04 13:53:28 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/alpar/bfs-named-param.cc
r945 r986 11 11 struct _BFS_CUSTOM_VIS {}; 12 12 13 template<class GT,class VT,class DVT,class PNT,class PET,class PT > 14 class _BFS 13 14 class _Bfs_Traits 15 { 16 typedef ListGraph Graph; 17 } 18 19 template<class T> 20 class _Bfs 15 21 { 16 22 public: 17 typedef GT Graph; 18 typedef VT Visited; 19 typedef PNT PredNode; 20 typedef PET PredEdge; 21 typedef PT Priority; 22 // typedef QDT QueueData; 23 typedef typename T::Graph Graph; 24 typedef typename T::Reached Reached; 25 typedef typename T::PredNode PredNode; 26 typedef typename T::PredEdge PredEdge; 27 typedef typename T::Priority Priority; 28 29 typedef typename T::DefaultReachedTag DefaultReachedTag; 23 30 24 31 typedef typename Graph::Node Node; 25 32 typedef typename Graph::OutEdgeIt OutEdgeIt; 26 33 27 typedef DVT DefaultVisitedTag;28 29 34 const Graph &_graph; 30 35 31 36 Node _source; 32 37 33 Visited *_visited;38 Reached *_visited; 34 39 PredNode _predNode; 35 40 PredEdge _predEdge; 36 41 Priority _priority; 37 42 38 _B FS(const Graph &g,43 _Bfs(const Graph &g, 39 44 Node s, 40 Visited *v,45 Reached *v, 41 46 PredNode &pn, 42 47 PredEdge &pe, … … 46 51 47 52 48 int run(const _B FS_CUSTOM_VIS &)53 int run(const _Bfs_CUSTOM_VIS &) 49 54 { 50 55 using namespace std; … … 64 69 Node n=Q[Qt++]; 65 70 for(OutEdgeIt e(_graph,n);e!=INVALID;++e) 66 if(!(*_visited)[m=_graph. head(e)]) {71 if(!(*_visited)[m=_graph.target(e)]) { 67 72 Q[Qh++]=m; 68 73 _visited->set(m,true); … … 76 81 int run(const _BFS_DEFAULT_VIS &) 77 82 { 78 _visited= new Visited(_graph);83 _visited= new Reached(_graph); 79 84 int r = run(_BFS_CUSTOM_VIS()); 80 85 delete _visited; 81 86 return r; 82 87 } 83 int run() { return run(Default VisitedTag());}84 85 template<class T> _B FS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>88 int run() { return run(DefaultReachedTag());} 89 90 template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> 86 91 setVisitMap(T &t) 87 92 { 88 return _B FS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>93 return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> 89 94 (_graph,_source,&t,_predNode,_predEdge,_priority); 90 95 } 91 96 92 97 template<class T> 93 _B FS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>98 _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> 94 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 102 (_graph,_source, 98 103 _visited, … … 101 106 102 107 template<class T> 103 _BFS<Graph, Visited,DefaultVisitedTag,PredNode,T,Priority>108 _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> 104 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 112 (_graph,_source, 108 113 _visited, … … 110 115 } 111 116 112 _B FS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>117 _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> 113 118 setNothing() 114 119 { 115 return _B FS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>120 return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> 116 121 (_graph,_source, 117 122 _visited, … … 122 127 123 128 template<class G> 124 _B FS<G,129 _Bfs<G, 125 130 typename G::template NodeMap<bool>, 126 131 _BFS_DEFAULT_VIS, … … 132 137 // typename G::template NodeMap<bool> v(g); 133 138 134 return _B FS< G,139 return _Bfs < G, 135 140 typename G::template NodeMap<bool>, 136 141 _BFS_DEFAULT_VIS, … … 147 152 148 153 149 class My VisitedMap : public SmartGraph::NodeMap<bool>154 class MyReachedMap : public SmartGraph::NodeMap<bool> 150 155 { 151 156 const SmartGraph &_G; 152 157 public: 153 My VisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}158 MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {} 154 159 void set(SmartGraph::Node n,bool b) 155 160 { … … 181 186 SmartGraph::NodeMap<SmartGraph::Edge> em(G); 182 187 183 My VisitedMap vm(G);188 MyReachedMap vm(G); 184 189 185 190
Note: See TracChangeset
for help on using the changeset viewer.