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 |
}
|