1.1 --- a/src/include/bfs.h Tue Dec 16 17:52:52 2003 +0000
1.2 +++ b/src/include/bfs.h Tue Dec 16 18:17:51 2003 +0000
1.3 @@ -45,8 +45,8 @@
1.4 // void Put(const do_nothing_map &p,const V &v,const T &t) {}
1.5
1.6 struct do_nothing_map {
1.7 - template <typename V,typename T>
1.8 - static void Put(V v,T t) {}
1.9 + template <typename V,typename T> static void Put(V v,T t) {}
1.10 + template <typename G> void SetG(G &g) {}
1.11 };
1.12
1.13
1.14 @@ -282,9 +282,16 @@
1.15 int priority;
1.16 Graph *G;
1.17
1.18 + //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
1.19 + Bfs() {}
1.20 +
1.21 void SetG(Graph &Gr)
1.22 {
1.23 G=&Gr;
1.24 + visited_map.SetG(Gr);
1.25 + tree_map.SetG(Gr);
1.26 + dist_map.SetG(Gr);
1.27 + priority_map.SetG(Gr);
1.28 }
1.29
1.30 void Init()
2.1 --- a/src/include/graph.h Tue Dec 16 17:52:52 2003 +0000
2.2 +++ b/src/include/graph.h Tue Dec 16 18:17:51 2003 +0000
2.3 @@ -75,7 +75,7 @@
2.4 bool operator==(const NodeIterator &i) const {return n==i.n;}
2.5 bool operator!=(const NodeIterator &i) const {return n!=i.n;}
2.6
2.7 - int Index() { return n; } //If the nodes are indexable
2.8 + int Index() const { return n; } //If the nodes are indexable
2.9 friend class Graph;
2.10 friend class EdgeIterator;
2.11 friend class InEdgeIterator;
2.12 @@ -119,7 +119,7 @@
2.13 bool operator==(const EdgeIterator &i) const {return e==i.e;}
2.14 bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
2.15
2.16 - int Index() { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
2.17 + int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
2.18 //If the edges are indexable
2.19
2.20 friend class Graph;
2.21 @@ -401,14 +401,14 @@
2.22
2.23 public:
2.24 typedef T value_type;
2.25 - void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
2.26 - T &Get(NodeIterator i) {return map[i.Index()];}
2.27 - T &operator[](NodeIterator i) {return map[i.Index()];}
2.28 + void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
2.29 + T Get(const NodeIterator i) const {return map[i.Index()];}
2.30 + T operator[](NodeIterator i) {return map[i.Index()];}
2.31
2.32 - void update() { map.resize(G->OldGraph<N,E>::NodeMax());}
2.33 + void update() { map.resize(G->MaxNode());}
2.34
2.35 - NodeMap(Graph<N,E> &Gr) : map(Gr.OldGraph<N,E>::NodeMax()) { G=&Gr ;}
2.36 -
2.37 + NodeMap() {}
2.38 + void SetG(Graph<N,E> &Gr) { G=&Gr; update();}
2.39 };
2.40
2.41 template<class T> class EdgeMap
2.42 @@ -418,19 +418,23 @@
2.43
2.44 public:
2.45 typedef T value_type;
2.46 - void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
2.47 - T &Get(NodeIterator i) {return map[i.Index()];}
2.48 + void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
2.49 + T &Get(const NodeIterator i) {return map[i.Index()];}
2.50 T &operator[](NodeIterator i) {return map[i.Index()];}
2.51
2.52 void update()
2.53 - { map.resize(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE);}
2.54 + { map.resize(G->MaxEdge());}
2.55
2.56 - EdgeMap(Graph<N,E> &Gr)
2.57 - :map(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE)
2.58 - { G=&Gr ;}
2.59 + EdgeMap() {}
2.60 + void SetG(Graph<N,E> &Gr)
2.61 + { G=&Gr ;update();}
2.62
2.63 };
2.64
2.65 +
2.66 + int MaxNode() { return OldGraph<N,E>::MaxNode();}
2.67 + int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
2.68 +
2.69 };
2.70
2.71 /* Ez itt a fiam kommentje:
3.1 --- a/src/work/bfsdemo.cc Tue Dec 16 17:52:52 2003 +0000
3.2 +++ b/src/work/bfsdemo.cc Tue Dec 16 18:17:51 2003 +0000
3.3 @@ -67,11 +67,13 @@
3.4 typedef bool value_type;
3.5 void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
3.6 value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
3.7 + void SetG(IGraph &G) {}
3.8 } visited;
3.9 struct _tree_map_t {
3.10 typedef IGraph::EdgeIterator value_type;
3.11 void Put(const IGraph::NodeIterator &n,const value_type &t)
3.12 { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
3.13 + void SetG(IGraph &G) {}
3.14 } tree;
3.15 do_nothing_map dist; //node->int (W)
3.16 do_nothing_map priority; //node->int (W)
3.17 @@ -89,11 +91,13 @@
3.18 typedef bool value_type;
3.19 void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
3.20 value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
3.21 + void SetG(IGraph &G) {}
3.22 };
3.23 struct tree_map_t {
3.24 typedef IGraph::EdgeIterator value_type;
3.25 void Put(const IGraph::NodeIterator &n,const value_type &t)
3.26 { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
3.27 + void SetG(IGraph &G) {}
3.28 };
3.29 typedef do_nothing_map dist_map_t; //node->int (W)
3.30 typedef do_nothing_map priority_map_t; //node->int (W)
4.1 --- a/src/work/bfsdemo2.cc Tue Dec 16 17:52:52 2003 +0000
4.2 +++ b/src/work/bfsdemo2.cc Tue Dec 16 18:17:51 2003 +0000
4.3 @@ -15,16 +15,23 @@
4.4
4.5 TestGraph::NodeIterator tn,n2;
4.6
4.7 - for(int i=1;i<=5000;i++)
4.8 + cout << "Create nodes\n";
4.9 +
4.10 + for(int i=1;i<=500;i++)
4.11 {
4.12 *(tn=G.AddNode())=i;
4.13 if(i==2) n2=tn;
4.14 }
4.15
4.16 + cout << "Create Edges\n";
4.17 +
4.18 for(TestGraph::NodeIterator n(G);n.isValid();++n)
4.19 - for(TestGraph::NodeIterator m(G);m.isValid();++m)
4.20 + for(TestGraph::NodeIterator m(G);m.isValid();++m) if(n!=m)
4.21 if(gcd(*n,*m)>1) G.AddEdge(n,m);
4.22
4.23 +
4.24 + cout << "Run BFS\n";
4.25 +
4.26 Bfs<default_bfs_T<TestGraph> > bfs;
4.27
4.28 bfs.SetG(G);
4.29 @@ -32,7 +39,12 @@
4.30 bfs.Run();
4.31
4.32 for(TestGraph::NodeIterator n(G);n.isValid();++n)
4.33 - cout << Get(bfs.tree_map,n).From() << "->" << Get(bfs.tree_map,n).To()
4.34 - << '\n';
4.35 + if((*n)!=2)
4.36 + cout << (Get(bfs.dist_map,n)) << '\n';
4.37
4.38 + for(TestGraph::NodeIterator n(G);n.isValid();++n)
4.39 + if(Get(bfs.dist_map,n))
4.40 + cout << *(Get(bfs.tree_map,n).From()) << "->"
4.41 + << *(Get(bfs.tree_map,n).To())
4.42 + << '\n';
4.43 }