#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';
}