author | alpar |
Thu, 31 Mar 2005 13:30:27 +0000 | |
changeset 1282 | 81e89e2b90d1 |
parent 6 | b63d1bc367f7 |
permissions | -rw-r--r-- |
alpar@6 | 1 |
#include <iostream> |
alpar@6 | 2 |
#include <graph.h> |
alpar@6 | 3 |
#include <bfs.h> |
alpar@6 | 4 |
|
alpar@6 | 5 |
using namespace NEGRO; |
alpar@6 | 6 |
using namespace std; |
alpar@6 | 7 |
|
alpar@6 | 8 |
typedef Graph<int,int> TestGraph; |
alpar@6 | 9 |
|
alpar@6 | 10 |
int gcd(int a,int b) {int c; while((c=a%b)) {a=b;b=c;} ; return b;} |
alpar@6 | 11 |
|
alpar@6 | 12 |
int main() |
alpar@6 | 13 |
{ |
alpar@6 | 14 |
TestGraph G; |
alpar@6 | 15 |
|
alpar@6 | 16 |
TestGraph::NodeIterator tn,n2; |
alpar@6 | 17 |
|
alpar@8 | 18 |
cout << "Create nodes\n"; |
alpar@8 | 19 |
|
alpar@8 | 20 |
for(int i=1;i<=500;i++) |
alpar@6 | 21 |
{ |
alpar@6 | 22 |
*(tn=G.AddNode())=i; |
alpar@6 | 23 |
if(i==2) n2=tn; |
alpar@6 | 24 |
} |
alpar@6 | 25 |
|
alpar@8 | 26 |
cout << "Create Edges\n"; |
alpar@8 | 27 |
|
alpar@6 | 28 |
for(TestGraph::NodeIterator n(G);n.isValid();++n) |
alpar@8 | 29 |
for(TestGraph::NodeIterator m(G);m.isValid();++m) if(n!=m) |
alpar@6 | 30 |
if(gcd(*n,*m)>1) G.AddEdge(n,m); |
alpar@6 | 31 |
|
alpar@8 | 32 |
|
alpar@8 | 33 |
cout << "Run BFS\n"; |
alpar@8 | 34 |
|
alpar@6 | 35 |
Bfs<default_bfs_T<TestGraph> > bfs; |
alpar@6 | 36 |
|
alpar@6 | 37 |
bfs.SetG(G); |
alpar@6 | 38 |
bfs.Init(n2); |
alpar@6 | 39 |
bfs.Run(); |
alpar@6 | 40 |
|
alpar@6 | 41 |
for(TestGraph::NodeIterator n(G);n.isValid();++n) |
alpar@8 | 42 |
if((*n)!=2) |
alpar@8 | 43 |
cout << (Get(bfs.dist_map,n)) << '\n'; |
alpar@6 | 44 |
|
alpar@8 | 45 |
for(TestGraph::NodeIterator n(G);n.isValid();++n) |
alpar@8 | 46 |
if(Get(bfs.dist_map,n)) |
alpar@8 | 47 |
cout << *(Get(bfs.tree_map,n).From()) << "->" |
alpar@8 | 48 |
<< *(Get(bfs.tree_map,n).To()) |
alpar@8 | 49 |
<< '\n'; |
alpar@6 | 50 |
} |