1.1 --- a/src/include/bfs.h	Mon Dec 15 17:46:22 2003 +0000
     1.2 +++ b/src/include/bfs.h	Tue Dec 16 16:19:08 2003 +0000
     1.3 @@ -240,11 +240,27 @@
     1.4    };
     1.5  
     1.6    // bfs algorithm class
     1.7 +
     1.8 +  template<class G>  //the default traits
     1.9 +  class default_bfs_T
    1.10 +  {
    1.11 +  public:
    1.12 +    
    1.13 +    typedef G Graph;
    1.14 +    typedef typename G::OutEdgeIterator SearchEdgeIterator;
    1.15 +    
    1.16 +    typedef typename G::NodeMap<bool> visited_map_t;
    1.17 +    typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
    1.18 +    
    1.19 +    typedef typename G::NodeMap<int> dist_map_t;   //node->int (W)
    1.20 +    typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
    1.21 +};
    1.22 +
    1.23    template<class T>
    1.24    class Bfs
    1.25    {
    1.26    public:
    1.27 -    typedef typename T::Graph_t Graph;
    1.28 +    typedef typename T::Graph Graph;
    1.29      typedef typename Graph::NodeIterator NodeIterator;
    1.30      typedef typename Graph::EdgeIterator EdgeIterator;
    1.31      

     2.1 --- a/src/include/graph.h	Mon Dec 15 17:46:22 2003 +0000
     2.2 +++ b/src/include/graph.h	Tue Dec 16 16:19:08 2003 +0000
     2.3 @@ -4,6 +4,7 @@
     2.4  
     2.5  //inline void *operator new(size_t s, void *p) { return p; }
     2.6  #include <new>
     2.7 +#include <vector>
     2.8  
     2.9  namespace NEGRO 
    2.10  {
    2.11 @@ -40,7 +41,7 @@
    2.12      class SymEdgeIterator;
    2.13      class AllEdgeIterator;
    2.14      
    2.15 -    class FirstAnythingTypeNode;
    2.16 +    class FirstAnythingTypeNode; //Required by the unified First() function.
    2.17  
    2.18      friend class NodeIterator;
    2.19      friend class EdgeIterator;
    2.20 @@ -391,6 +392,45 @@
    2.21      void Clean() { OldGraph<N,E>::Clean(); }
    2.22  
    2.23      Graph() : _FST(this) {}
    2.24 +
    2.25 +    // MAPS:
    2.26 +    template<class T> class NodeMap
    2.27 +    {
    2.28 +      Graph<N,E> *G;
    2.29 +      vector<T> map;
    2.30 +
    2.31 +    public:
    2.32 +      typedef T value_type;
    2.33 +      void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
    2.34 +      T &Get(NodeIterator i) {return map[i.Index()];}
    2.35 +      T &operator[](NodeIterator i) {return map[i.Index()];}
    2.36 +
    2.37 +      void update() { map.resize(G->OldGraph<N,E>::NodeMax());}
    2.38 +
    2.39 +      NodeMap(Graph<N,E> &Gr) : map(Gr.OldGraph<N,E>::NodeMax()) { G=&Gr ;}
    2.40 +      
    2.41 +    };
    2.42 +
    2.43 +    template<class T> class EdgeMap
    2.44 +    {
    2.45 +      Graph<N,E> *G;
    2.46 +      vector<T> map;
    2.47 +
    2.48 +    public:
    2.49 +      typedef T value_type;
    2.50 +      void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
    2.51 +      T &Get(NodeIterator i) {return map[i.Index()];}
    2.52 +      T &operator[](NodeIterator i) {return map[i.Index()];}
    2.53 +      
    2.54 +      void update()
    2.55 +	{ map.resize(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE);}
    2.56 +      
    2.57 +      EdgeMap(Graph<N,E> &Gr) 
    2.58 +	:map(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE)
    2.59 +	{ G=&Gr ;}
    2.60 +      
    2.61 +    };
    2.62 +    
    2.63    };
    2.64    
    2.65    /*   Ez itt a fiam kommentje:

     3.1 --- a/src/work/bfsdemo.cc	Mon Dec 15 17:46:22 2003 +0000
     3.2 +++ b/src/work/bfsdemo.cc	Tue Dec 16 16:19:08 2003 +0000
     3.3 @@ -82,7 +82,7 @@
     3.4  {
     3.5  public:
     3.6  
     3.7 -  typedef IGraph Graph_t;
     3.8 +  typedef IGraph Graph;
     3.9    typedef IGraph::OutEdgeIterator SearchEdgeIterator;
    3.10    
    3.11    struct visited_map_t {

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/work/bfsdemo2.cc	Tue Dec 16 16:19:08 2003 +0000
     4.3 @@ -0,0 +1,38 @@
     4.4 +#include <iostream>
     4.5 +#include <graph.h>
     4.6 +#include <bfs.h>
     4.7 +
     4.8 +using namespace NEGRO;
     4.9 +using namespace std;
    4.10 +
    4.11 +typedef Graph<int,int> TestGraph;
    4.12 +
    4.13 +int gcd(int a,int b) {int c; while((c=a%b)) {a=b;b=c;} ; return b;}
    4.14 +
    4.15 +int main()
    4.16 +{
    4.17 +  TestGraph G;
    4.18 +  
    4.19 +  TestGraph::NodeIterator tn,n2;
    4.20 +  
    4.21 +  for(int i=1;i<=5000;i++)
    4.22 +    {
    4.23 +      *(tn=G.AddNode())=i;
    4.24 +      if(i==2) n2=tn;
    4.25 +    }
    4.26 +  
    4.27 +  for(TestGraph::NodeIterator n(G);n.isValid();++n)
    4.28 +    for(TestGraph::NodeIterator m(G);m.isValid();++m)
    4.29 +      if(gcd(*n,*m)>1) G.AddEdge(n,m);
    4.30 +  
    4.31 +  Bfs<default_bfs_T<TestGraph> > bfs;
    4.32 +
    4.33 +  bfs.SetG(G);
    4.34 +  bfs.Init(n2);
    4.35 +  bfs.Run();
    4.36 +
    4.37 +  for(TestGraph::NodeIterator n(G);n.isValid();++n)
    4.38 +    cout << Get(bfs.tree_map,n).From() << "->" << Get(bfs.tree_map,n).To()
    4.39 +	 << '\n';
    4.40 +
    4.41 +}