#include <iostream>

 #include <graph.h>

 #include <bfs.h>

 using namespace NEGRO;

 using namespace std;

 typedef Graph<int,int> TestGraph;

 int gcd(int a,int b) {int c; while((c=a%b)) {a=b;b=c;} ; return b;}

 int main()

 {

   TestGraph G;

   TestGraph::NodeIterator tn,n2;

   cout << "Create nodes\n";

   for(int i=1;i<=500;i++)

     {

       *(tn=G.AddNode())=i;

       if(i==2) n2=tn;

     }

   cout << "Create Edges\n";

   for(TestGraph::NodeIterator n(G);n.isValid();++n)

     for(TestGraph::NodeIterator m(G);m.isValid();++m) if(n!=m)

       if(gcd(*n,*m)>1) G.AddEdge(n,m);

   cout << "Run BFS\n";

   Bfs<default_bfs_T<TestGraph> > bfs;

   bfs.SetG(G);

   bfs.Init(n2);

   bfs.Run();

   for(TestGraph::NodeIterator n(G);n.isValid();++n)

     if((*n)!=2)

       cout << (Get(bfs.dist_map,n)) << '\n';

   for(TestGraph::NodeIterator n(G);n.isValid();++n)

     if(Get(bfs.dist_map,n))

       cout << *(Get(bfs.tree_map,n).From()) << "->"

 	   << *(Get(bfs.tree_map,n).To())

 	   << '\n';

 }