1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/alpar/bfs-named-param.cc	Tue Jul 27 16:04:21 2004 +0000
     1.3 @@ -0,0 +1,159 @@
     1.4 +// -*- mode:C++ -*-
     1.5 +
     1.6 +#include <hugo/smart_graph.h>
     1.7 +#include <hugo/maps.h>
     1.8 +#include <vector>
     1.9 +
    1.10 +using namespace hugo;
    1.11 +
    1.12 +struct _BFS_DEFAULT_VIS {};
    1.13 +struct _BFS_CUSTOM_VIS {};
    1.14 +
    1.15 +template<class GT,class VT,class DVT,class PNT,class PET,class PT >
    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 +  
    1.26 +  typedef typename Graph::Node Node;
    1.27 +  typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.28 +
    1.29 +  typedef DVT DefaultVisitedTag;
    1.30 +  
    1.31 +  const Graph &_graph;
    1.32 +
    1.33 +  Node _source;
    1.34 +  
    1.35 +  Visited *_visited;
    1.36 +  PredNode _predNode;
    1.37 +  PredEdge _predEdge;
    1.38 +  Priority _priority;
    1.39 +
    1.40 +  _BFS(const Graph &g,
    1.41 +       Node s,
    1.42 +       Visited *v,
    1.43 +       PredNode &pn,
    1.44 +       PredEdge &pe,
    1.45 +       Priority &pr) :_graph(g), _source(s),
    1.46 +		     _visited(v), 
    1.47 +		     _predNode(pn), _predEdge(pe), _priority(pr) { }
    1.48 +
    1.49 +  
    1.50 +  int run(const _BFS_CUSTOM_VIS &) 
    1.51 +  {
    1.52 +    using namespace std;
    1.53 +    
    1.54 +    int N=_graph.nodeNum();
    1.55 +    vector<Node> Q(N);
    1.56 +    int Qh=0;
    1.57 +    int Qt=0;
    1.58 +    
    1.59 +    for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n))
    1.60 +      _visited->set(n,false);
    1.61 +
    1.62 +    Q[Qh++]=_source;
    1.63 +    _visited->set(_source,true);
    1.64 +    do {
    1.65 +      Node m;
    1.66 +      Node n=Q[Qt++];
    1.67 +      for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e))
    1.68 +	if(!(*_visited)[m=_graph.head(e)]) {
    1.69 +	  Q[Qh++]=m;
    1.70 +	  _visited->set(m,true);
    1.71 +	  _predNode.set(m,n);
    1.72 +	  _predEdge.set(m,e);	  
    1.73 +	}
    1.74 +    } while(Qt!=Qh);
    1.75 +
    1.76 +    return 1; //Why return 1?
    1.77 +  }
    1.78 +  int run(const _BFS_DEFAULT_VIS &) 
    1.79 +  {
    1.80 +    _visited= new Visited(_graph);
    1.81 +    int r = run(_BFS_CUSTOM_VIS());
    1.82 +    delete _visited;
    1.83 +    return r;
    1.84 +  }
    1.85 +  int run() { return run(DefaultVisitedTag());}
    1.86 +
    1.87 +  template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
    1.88 +  setVisitMap(T &t)
    1.89 +  {
    1.90 +    return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
    1.91 +      (_graph,_source,&t,_predNode,_predEdge,_priority);
    1.92 +  }
    1.93 +
    1.94 +  template<class T>
    1.95 +  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority>
    1.96 +  setPredNodeMap(T &t)
    1.97 +  {
    1.98 +    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority>
    1.99 +      (_graph,_source,
   1.100 +       _visited,
   1.101 +       t,_predEdge,_priority);
   1.102 +  }
   1.103 +
   1.104 +  template<class T>
   1.105 +  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority>
   1.106 +  setPredEdgeMap(T &t)
   1.107 +  {
   1.108 +    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority>
   1.109 +      (_graph,_source,
   1.110 +       _visited,
   1.111 +      _predNode,t,_priority);
   1.112 +  }
   1.113 +
   1.114 +  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
   1.115 +  setNothing()
   1.116 +  {
   1.117 +    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
   1.118 +      (_graph,_source,
   1.119 +       _visited,
   1.120 +       _predNode,_predEdge,_priority);
   1.121 +  }
   1.122 +};
   1.123 +
   1.124 +
   1.125 +template<class G>
   1.126 +_BFS<G,
   1.127 +     typename G::template NodeMap<bool>,
   1.128 +     _BFS_DEFAULT_VIS,
   1.129 +     NullMap<typename G::Node,typename G::Node>,
   1.130 +     NullMap<typename G::Node,typename G::Edge>,
   1.131 +     NullMap<typename G::Node,int> >
   1.132 +bfs(const G &g,typename G::Node s)
   1.133 +{
   1.134 +  //  typename G::template NodeMap<bool> v(g);
   1.135 +
   1.136 +  return _BFS < G,
   1.137 +    typename G::template NodeMap<bool>,
   1.138 +    _BFS_DEFAULT_VIS,
   1.139 +     NullMap<typename G::Node,typename G::Node>,
   1.140 +     NullMap<typename G::Node,typename G::Edge>,
   1.141 +    NullMap<typename G::Node,int> >
   1.142 +    (g,s,
   1.143 +     (typename G::template NodeMap<bool>*)(NULL),
   1.144 +     *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
   1.145 +     *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
   1.146 +     *((NullMap<typename G::Node,int> *)(NULL))
   1.147 +     );
   1.148 +}
   1.149 +
   1.150 +
   1.151 +int main()
   1.152 +{
   1.153 +  SmartGraph G;
   1.154 +  SmartGraph::NodeIt n(G);
   1.155 +  SmartGraph::NodeMap<SmartGraph::Node> m(G);
   1.156 +  SmartGraph::NodeMap<SmartGraph::Edge> em(G);
   1.157 +  
   1.158 +  bfs(G,n).run();
   1.159 +  bfs(G,n).setPredNodeMap(m).run();
   1.160 +  bfs(G,n).setPredNodeMap(m).setPredEdgeMap(em).run();
   1.161 +
   1.162 +}