[741] | 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 | } |
---|