COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/bfsdemo2.cc @ 807:ce85435185c3

Last change on this file since 807:ce85435185c3 was 8:cd54905012bc, checked in by Alpar Juttner, 21 years ago

-New test: bfsdemo2.cc added

  • Graph class has a NodeMap? and an EdgeMap? member class
  • default_bfs_T uning the above Maps is added
  • a (property)map must provide a member function SetG() to attach the map to a graph
File size: 987 bytes
Line 
1#include <iostream>
2#include <graph.h>
3#include <bfs.h>
4
5using namespace NEGRO;
6using namespace std;
7
8typedef Graph<int,int> TestGraph;
9
10int gcd(int a,int b) {int c; while((c=a%b)) {a=b;b=c;} ; return b;}
11
12int 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}
Note: See TracBrowser for help on using the repository browser.