equal
deleted
inserted
replaced
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 } |
|