src/work/bfsdemo2.cc
author alpar
Tue, 16 Dec 2003 18:17:51 +0000
changeset 8 cd54905012bc
parent 6 b63d1bc367f7
permissions -rw-r--r--
-New test: bfsdemo2.cc added
- Graph class has a NodeMap and an EdgeMap member class
- default_bfs_T uning the above Maps is added
- a (property)map must provide a member function SetG() to attach the map
to a graph
     1 #include <iostream>
     2 #include <graph.h>
     3 #include <bfs.h>
     4 
     5 using namespace NEGRO;
     6 using namespace std;
     7 
     8 typedef Graph<int,int> TestGraph;
     9 
    10 int gcd(int a,int b) {int c; while((c=a%b)) {a=b;b=c;} ; return b;}
    11 
    12 int main()
    13 {
    14   TestGraph G;
    15   
    16   TestGraph::NodeIterator tn,n2;
    17   
    18   cout << "Create nodes\n";
    19 
    20   for(int i=1;i<=500;i++)
    21     {
    22       *(tn=G.AddNode())=i;
    23       if(i==2) n2=tn;
    24     }
    25   
    26   cout << "Create Edges\n";
    27   
    28   for(TestGraph::NodeIterator n(G);n.isValid();++n)
    29     for(TestGraph::NodeIterator m(G);m.isValid();++m) if(n!=m)
    30       if(gcd(*n,*m)>1) G.AddEdge(n,m);
    31   
    32   
    33   cout << "Run BFS\n";
    34 
    35   Bfs<default_bfs_T<TestGraph> > bfs;
    36 
    37   bfs.SetG(G);
    38   bfs.Init(n2);
    39   bfs.Run();
    40 
    41   for(TestGraph::NodeIterator n(G);n.isValid();++n)
    42     if((*n)!=2)
    43       cout << (Get(bfs.dist_map,n)) << '\n';
    44 
    45   for(TestGraph::NodeIterator n(G);n.isValid();++n)
    46     if(Get(bfs.dist_map,n))
    47       cout << *(Get(bfs.tree_map,n).From()) << "->"
    48 	   << *(Get(bfs.tree_map,n).To())
    49 	   << '\n';
    50 }