Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/alpar/bfs-named-param.cc
changeset 1284 b941d044f87b
parent 945 f2ea4aac9ada
equal deleted inserted replaced
4:896491a46b44 5:1abaa4c15ab5 
     8 using namespace lemon;
 
     8 using namespace lemon;
 
     9 
     9 
    10 struct _BFS_DEFAULT_VIS {};
 
    10 struct _BFS_DEFAULT_VIS {};
 
    11 struct _BFS_CUSTOM_VIS {};
 
    11 struct _BFS_CUSTOM_VIS {};
 
    12 
    12 
    13 template<class GT,class VT,class DVT,class PNT,class PET,class PT >
 
    13 
    14 class _BFS 
    14 class _Bfs_Traits 
       
    15 {
 
       
    16   typedef ListGraph Graph;
 
       
    17 }
 
       
    18 
       
    19 template<class T>
 
       
    20 class _Bfs 
    15 {
 
    21 {
 
    16  public:
 
    22  public:
 
    17   typedef GT Graph;
 
    23   typedef typename T::Graph Graph;
 
    18   typedef VT Visited;
 
    24   typedef typename T::Reached Reached;
 
    19   typedef PNT PredNode;
 
    25   typedef typename T::PredNode PredNode;
 
    20   typedef PET PredEdge;
 
    26   typedef typename T::PredEdge PredEdge;
 
    21   typedef PT Priority;
 
    27   typedef typename T::Priority Priority;
 
    22   //  typedef QDT QueueData;
 
    28   
       
    29   typedef typename T::DefaultReachedTag DefaultReachedTag;
 
    23   
    30   
    24   typedef typename Graph::Node Node;
 
    31   typedef typename Graph::Node Node;
 
    25   typedef typename Graph::OutEdgeIt OutEdgeIt;
 
    32   typedef typename Graph::OutEdgeIt OutEdgeIt;
 
    26 
    33 
    27   typedef DVT DefaultVisitedTag;
 
       
    28   
       
    29   const Graph &_graph;
 
    34   const Graph &_graph;
 
    30 
    35 
    31   Node _source;
 
    36   Node _source;
 
    32   
    37   
    33   Visited *_visited;
 
    38   Reached *_visited;
 
    34   PredNode _predNode;
 
    39   PredNode _predNode;
 
    35   PredEdge _predEdge;
 
    40   PredEdge _predEdge;
 
    36   Priority _priority;
 
    41   Priority _priority;
 
    37 
    42 
    38   _BFS(const Graph &g,
 
    43   _Bfs(const Graph &g,
 
    39        Node s,
 
    44        Node s,
 
    40        Visited *v,
 
    45        Reached *v,
 
    41        PredNode &pn,
 
    46        PredNode &pn,
 
    42        PredEdge &pe,
 
    47        PredEdge &pe,
 
    43        Priority &pr) :_graph(g), _source(s),
 
    48        Priority &pr) :_graph(g), _source(s),
 
    44 		     _visited(v), 
    49 		     _visited(v), 
    45 		     _predNode(pn), _predEdge(pe), _priority(pr) { }
 
    50 		     _predNode(pn), _predEdge(pe), _priority(pr) { }
 
    46 
    51 
    47   
    52   
    48   int run(const _BFS_CUSTOM_VIS &) 
    53   int run(const _Bfs_CUSTOM_VIS &) 
    49   {
 
    54   {
 
    50     using namespace std;
 
    55     using namespace std;
 
    51     
    56     
    52     int N=_graph.nodeNum();
 
    57     int N=_graph.nodeNum();
 
    53     vector<Node> Q(N);
 
    58     vector<Node> Q(N);
 
    61     _visited->set(_source,true);
 
    66     _visited->set(_source,true);
 
    62     do {
 
    67     do {
 
    63       Node m;
 
    68       Node m;
 
    64       Node n=Q[Qt++];
 
    69       Node n=Q[Qt++];
 
    65       for(OutEdgeIt e(_graph,n);e!=INVALID;++e)
 
    70       for(OutEdgeIt e(_graph,n);e!=INVALID;++e)
 
    66 	if(!(*_visited)[m=_graph.head(e)]) {
 
    71 	if(!(*_visited)[m=_graph.target(e)]) {
 
    67 	  Q[Qh++]=m;
 
    72 	  Q[Qh++]=m;
 
    68 	  _visited->set(m,true);
 
    73 	  _visited->set(m,true);
 
    69 	  _predNode.set(m,n);
 
    74 	  _predNode.set(m,n);
 
    70 	  _predEdge.set(m,e);	  
    75 	  _predEdge.set(m,e);	  
    71 	}
 
    76 	}
 
    73 
    78 
    74     return 1; //Why return 1?
 
    79     return 1; //Why return 1?
 
    75   }
 
    80   }
 
    76   int run(const _BFS_DEFAULT_VIS &) 
    81   int run(const _BFS_DEFAULT_VIS &) 
    77   {
 
    82   {
 
    78     _visited= new Visited(_graph);
 
    83     _visited= new Reached(_graph);
 
    79     int r = run(_BFS_CUSTOM_VIS());
 
    84     int r = run(_BFS_CUSTOM_VIS());
 
    80     delete _visited;
 
    85     delete _visited;
 
    81     return r;
 
    86     return r;
 
    82   }
 
    87   }
 
    83   int run() { return run(DefaultVisitedTag());}
 
    88   int run() { return run(DefaultReachedTag());}
 
    84 
    89 
    85   template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
 
    90   template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
 
    86   setVisitMap(T &t)
 
    91   setVisitMap(T &t)
 
    87   {
 
    92   {
 
    88     return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
 
    93     return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
 
    89       (_graph,_source,&t,_predNode,_predEdge,_priority);
 
    94       (_graph,_source,&t,_predNode,_predEdge,_priority);
 
    90   }
 
    95   }
 
    91 
    96 
    92   template<class T>
 
    97   template<class T>
 
    93   _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
 
    98   _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>
 
    94   setPredNodeMap(T &t)
 
    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       (_graph,_source,
 
   102       (_graph,_source,
 
    98        _visited,
 
   103        _visited,
 
    99        t,_predEdge,_priority);
 
   104        t,_predEdge,_priority);
 
   100   }
 
   105   }
 
   101 
   106 
   102   template<class T>
 
   107   template<class T>
 
   103   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
 
   108   _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>
 
   104   setPredEdgeMap(T &t)
 
   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       (_graph,_source,
 
   112       (_graph,_source,
 
   108        _visited,
 
   113        _visited,
 
   109       _predNode,t,_priority);
 
   114       _predNode,t,_priority);
 
   110   }
 
   115   }
 
   111 
   116 
   112   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
 
   117   _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
 
   113   setNothing()
 
   118   setNothing()
 
   114   {
 
   119   {
 
   115     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
 
   120     return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>
 
   116       (_graph,_source,
 
   121       (_graph,_source,
 
   117        _visited,
 
   122        _visited,
 
   118        _predNode,_predEdge,_priority);
 
   123        _predNode,_predEdge,_priority);
 
   119   }
 
   124   }
 
   120 };
 
   125 };
 
   121 
   126 
   122 
   127 
   123 template<class G>
 
   128 template<class G>
 
   124 _BFS<G,
 
   129 _Bfs<G,
 
   125      typename G::template NodeMap<bool>,
 
   130      typename G::template NodeMap<bool>,
 
   126      _BFS_DEFAULT_VIS,
 
   131      _BFS_DEFAULT_VIS,
 
   127      NullMap<typename G::Node,typename G::Node>,
 
   132      NullMap<typename G::Node,typename G::Node>,
 
   128      NullMap<typename G::Node,typename G::Edge>,
 
   133      NullMap<typename G::Node,typename G::Edge>,
 
   129      NullMap<typename G::Node,int> >
 
   134      NullMap<typename G::Node,int> >
 
   130 bfs(const G &g,typename G::Node s)
 
   135 bfs(const G &g,typename G::Node s)
 
   131 {
 
   136 {
 
   132   //  typename G::template NodeMap<bool> v(g);
 
   137   //  typename G::template NodeMap<bool> v(g);
 
   133 
   138 
   134   return _BFS < G,
 
   139   return _Bfs < G,
 
   135     typename G::template NodeMap<bool>,
 
   140     typename G::template NodeMap<bool>,
 
   136     _BFS_DEFAULT_VIS,
 
   141     _BFS_DEFAULT_VIS,
 
   137      NullMap<typename G::Node,typename G::Node>,
 
   142      NullMap<typename G::Node,typename G::Node>,
 
   138      NullMap<typename G::Node,typename G::Edge>,
 
   143      NullMap<typename G::Node,typename G::Edge>,
 
   139     NullMap<typename G::Node,int> >
 
   144     NullMap<typename G::Node,int> >
 
   144      *((NullMap<typename G::Node,int> *)(NULL))
 
   149      *((NullMap<typename G::Node,int> *)(NULL))
 
   145      );
 
   150      );
 
   146 }
 
   151 }
 
   147 
   152 
   148 
   153 
   149 class MyVisitedMap : public SmartGraph::NodeMap<bool>
 
   154 class MyReachedMap : public SmartGraph::NodeMap<bool>
 
   150 {
 
   155 {
 
   151   const SmartGraph &_G;
 
   156   const SmartGraph &_G;
 
   152 public:
 
   157 public:
 
   153   MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
 
   158   MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
 
   154   void set(SmartGraph::Node n,bool b)
 
   159   void set(SmartGraph::Node n,bool b)
 
   155   {
 
   160   {
 
   156     SmartGraph::NodeMap<bool>::set(n,b);
 
   161     SmartGraph::NodeMap<bool>::set(n,b);
 
   157     if(b) std::cout << _G.id(n) << std::endl;
 
   162     if(b) std::cout << _G.id(n) << std::endl;
 
   158   }
 
   163   }
 
   178   
   183   
   179   
   184   
   180   SmartGraph::NodeMap<SmartGraph::Node> m(G);
 
   185   SmartGraph::NodeMap<SmartGraph::Node> m(G);
 
   181   SmartGraph::NodeMap<SmartGraph::Edge> em(G);
 
   186   SmartGraph::NodeMap<SmartGraph::Edge> em(G);
 
   182 
   187 
   183   MyVisitedMap vm(G);
 
   188   MyReachedMap vm(G);
 
   184 
   189 
   185 
   190 
   186   //Runs BFS on graph 'G' from node 's'.
 
   191   //Runs BFS on graph 'G' from node 's'.
 
   187   //(It practically does nothing, for it throws away its result.) 
   192   //(It practically does nothing, for it throws away its result.) 
   188   bfs(G,s).run(); 
   193   bfs(G,s).run();
lemon-0.x