src/work/alpar/bfs-named-param.cc
author marci
Thu, 02 Sep 2004 16:59:30 +0000
changeset 789 65c5c7d37578
parent 743 efab34f23b30
child 921 818510fa3d99
permissions -rw-r--r--
.
     1 // -*- mode:C++ -*-
     2 
     3 #include <hugo/smart_graph.h>
     4 #include <hugo/maps.h>
     5 #include <vector>
     6 #include <iostream>
     7 
     8 using namespace hugo;
     9 
    10 struct _BFS_DEFAULT_VIS {};
    11 struct _BFS_CUSTOM_VIS {};
    12 
    13 template<class GT,class VT,class DVT,class PNT,class PET,class PT >
    14 class _BFS 
    15 {
    16  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   
    24   typedef typename Graph::Node Node;
    25   typedef typename Graph::OutEdgeIt OutEdgeIt;
    26 
    27   typedef DVT DefaultVisitedTag;
    28   
    29   const Graph &_graph;
    30 
    31   Node _source;
    32   
    33   Visited *_visited;
    34   PredNode _predNode;
    35   PredEdge _predEdge;
    36   Priority _priority;
    37 
    38   _BFS(const Graph &g,
    39        Node s,
    40        Visited *v,
    41        PredNode &pn,
    42        PredEdge &pe,
    43        Priority &pr) :_graph(g), _source(s),
    44 		     _visited(v), 
    45 		     _predNode(pn), _predEdge(pe), _priority(pr) { }
    46 
    47   
    48   int run(const _BFS_CUSTOM_VIS &) 
    49   {
    50     using namespace std;
    51     
    52     int N=_graph.nodeNum();
    53     vector<Node> Q(N);
    54     int Qh=0;
    55     int Qt=0;
    56     
    57     for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n))
    58       _visited->set(n,false);
    59 
    60     Q[Qh++]=_source;
    61     _visited->set(_source,true);
    62     do {
    63       Node m;
    64       Node n=Q[Qt++];
    65       for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e))
    66 	if(!(*_visited)[m=_graph.head(e)]) {
    67 	  Q[Qh++]=m;
    68 	  _visited->set(m,true);
    69 	  _predNode.set(m,n);
    70 	  _predEdge.set(m,e);	  
    71 	}
    72     } while(Qt!=Qh);
    73 
    74     return 1; //Why return 1?
    75   }
    76   int run(const _BFS_DEFAULT_VIS &) 
    77   {
    78     _visited= new Visited(_graph);
    79     int r = run(_BFS_CUSTOM_VIS());
    80     delete _visited;
    81     return r;
    82   }
    83   int run() { return run(DefaultVisitedTag());}
    84 
    85   template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
    86   setVisitMap(T &t)
    87   {
    88     return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
    89       (_graph,_source,&t,_predNode,_predEdge,_priority);
    90   }
    91 
    92   template<class T>
    93   _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
    94   setPredNodeMap(T &t)
    95   {
    96     return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
    97       (_graph,_source,
    98        _visited,
    99        t,_predEdge,_priority);
   100   }
   101 
   102   template<class T>
   103   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
   104   setPredEdgeMap(T &t)
   105   {
   106     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
   107       (_graph,_source,
   108        _visited,
   109       _predNode,t,_priority);
   110   }
   111 
   112   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
   113   setNothing()
   114   {
   115     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
   116       (_graph,_source,
   117        _visited,
   118        _predNode,_predEdge,_priority);
   119   }
   120 };
   121 
   122 
   123 template<class G>
   124 _BFS<G,
   125      typename G::template NodeMap<bool>,
   126      _BFS_DEFAULT_VIS,
   127      NullMap<typename G::Node,typename G::Node>,
   128      NullMap<typename G::Node,typename G::Edge>,
   129      NullMap<typename G::Node,int> >
   130 bfs(const G &g,typename G::Node s)
   131 {
   132   //  typename G::template NodeMap<bool> v(g);
   133 
   134   return _BFS < G,
   135     typename G::template NodeMap<bool>,
   136     _BFS_DEFAULT_VIS,
   137      NullMap<typename G::Node,typename G::Node>,
   138      NullMap<typename G::Node,typename G::Edge>,
   139     NullMap<typename G::Node,int> >
   140     (g,s,
   141      (typename G::template NodeMap<bool>*)(NULL),
   142      *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
   143      *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
   144      *((NullMap<typename G::Node,int> *)(NULL))
   145      );
   146 }
   147 
   148 
   149 class MyVisitedMap : public SmartGraph::NodeMap<bool>
   150 {
   151   const SmartGraph &_G;
   152 public:
   153   MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
   154   void set(SmartGraph::Node n,bool b)
   155   {
   156     SmartGraph::NodeMap<bool>::set(n,b);
   157     if(b) std::cout << _G.id(n) << std::endl;
   158   }
   159 };
   160 
   161 
   162 int main()
   163 {
   164   SmartGraph G;
   165   SmartGraph::Node s=G.addNode();
   166   SmartGraph::Node n1=G.addNode();
   167   SmartGraph::Node n2=G.addNode();
   168   SmartGraph::Node n3=G.addNode();
   169   SmartGraph::Node n4=G.addNode();
   170   SmartGraph::Node n5=G.addNode();
   171   SmartGraph::Node n6=G.addNode();
   172   SmartGraph::Node n7=G.addNode();
   173 
   174   G.addEdge(s,n1);G.addEdge(s,n3);G.addEdge(n1,n2);G.addEdge(n1,n3);
   175   G.addEdge(s,n4);G.addEdge(n4,n7);G.addEdge(n7,n6);G.addEdge(n4,n5);
   176   G.addEdge(n7,n2);G.addEdge(n6,n3);G.addEdge(n4,s);G.addEdge(n1,s);
   177 
   178   
   179   
   180   SmartGraph::NodeMap<SmartGraph::Node> m(G);
   181   SmartGraph::NodeMap<SmartGraph::Edge> em(G);
   182 
   183   MyVisitedMap vm(G);
   184 
   185 
   186   //Runs BFS on graph 'G' from node 's'.
   187   //(It practically does nothing, for it throws away its result.) 
   188   bfs(G,s).run(); 
   189 
   190   //Runs BFS on graph 'G' from node 's'. Puts the predessor nodes to 'm'.
   191   bfs(G,s).setPredNodeMap(m).run();
   192 
   193   //Runs BFS on graph 'G' from node 's'.
   194   //Puts the predessor nodes to 'm' and the edges of the bfs tree to 'em'.
   195   bfs(G,s).setPredNodeMap(m).setPredEdgeMap(em).run();
   196 
   197   //Runs BFS on graph 'G' from node 's'.
   198   //It uses a scpecial 'visited map' that prints out the reached nodes.
   199   bfs(G,s).setVisitMap(vm).run();
   200 
   201 }