1 //=======================================================================
2 // Copyright 2002 Indiana University.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 /*
11 Adapted from the GIRTH program of the Stanford GraphBase.
12
13 Sample output:
14
15 This program explores the girth and diameter of Ramanujan graphs.
16 The bipartite graphs have q^3-q vertices, and the non-bipartite
17 graphs have half that number. Each vertex has degree p+1.
18 Both p and q should be odd prime numbers;
19 or you can try p = 2 with q = 17 or 43.
20
21 Choose a branching factor, p: 2
22 Ok, now choose the cube root of graph size, q: 17
23 Starting at any given vertex, there are
24 3 vertices at distance 1,
25 6 vertices at distance 2,
26 12 vertices at distance 3,
27 24 vertices at distance 4,
28 46 vertices at distance 5,
29 90 vertices at distance 6,
30 169 vertices at distance 7,
31 290 vertices at distance 8,
32 497 vertices at distance 9,
33 634 vertices at distance 10,
34 521 vertices at distance 11,
35 138 vertices at distance 12,
36 13 vertices at distance 13,
37 3 vertices at distance 14,
38 1 vertices at distance 15.
39 So the diameter is 15, and the girth is 9.
40
41 */
42
43 #include <boost/config.hpp>
44 #include <vector>
45 #include <list>
46 #include <iostream>
47 #include <boost/limits.hpp>
48 #include <boost/graph/stanford_graph.hpp>
49 #include <boost/graph/breadth_first_search.hpp>
50 #include <boost/graph/graph_utility.hpp>
51
52 typedef boost::graph_traits<Graph*> Traits;
53 typedef Traits::vertex_descriptor vertex_descriptor;
54 typedef Traits::edge_descriptor edge_descriptor;
55 typedef Traits::vertex_iterator vertex_iterator;
56
57 std::vector<std::size_t> distance_list;
58
59 typedef boost::v_property<long> dist_t;
60 boost::property_map<Graph*, dist_t>::type d_map;
61
62 typedef boost::u_property<vertex_descriptor> pred_t;
63 boost::property_map<Graph*, pred_t>::type p_map;
64
65 typedef boost::w_property<long> color_t;
66 boost::property_map<Graph*, color_t>::type c_map;
67
68 class diameter_and_girth_visitor : public boost::bfs_visitor<>
69 {
70 public:
diameter_and_girth_visitor(std::size_t & k_,std::size_t & girth_)71 diameter_and_girth_visitor(std::size_t& k_, std::size_t& girth_)
72 : k(k_), girth(girth_) { }
73
tree_edge(edge_descriptor e,Graph * g)74 void tree_edge(edge_descriptor e, Graph* g) {
75 vertex_descriptor u = source(e, g), v = target(e, g);
76 k = d_map[u] + 1;
77 d_map[v] = k;
78 ++distance_list[k];
79 p_map[v] = u;
80 }
non_tree_edge(edge_descriptor e,Graph * g)81 void non_tree_edge(edge_descriptor e, Graph* g) {
82 vertex_descriptor u = source(e, g), v = target(e, g);
83 k = d_map[u] + 1;
84 if (d_map[v] + k < girth && v != p_map[u])
85 girth = d_map[v]+ k;
86 }
87 private:
88 std::size_t& k;
89 std::size_t& girth;
90 };
91
92
93 int
main()94 main()
95 {
96 std::cout <<
97 "This program explores the girth and diameter of Ramanujan graphs."
98 << std::endl;
99 std::cout <<
100 "The bipartite graphs have q^3-q vertices, and the non-bipartite"
101 << std::endl;
102 std::cout <<
103 "graphs have half that number. Each vertex has degree p+1."
104 << std::endl;
105 std::cout << "Both p and q should be odd prime numbers;" << std::endl;
106 std::cout << " or you can try p = 2 with q = 17 or 43." << std::endl;
107
108 while (1) {
109
110 std::cout << std::endl
111 << "Choose a branching factor, p: ";
112 long p = 0, q = 0;
113 std::cin >> p;
114 if (p == 0)
115 break;
116 std::cout << "Ok, now choose the cube root of graph size, q: ";
117 std::cin >> q;
118 if (q == 0)
119 break;
120
121 Graph* g;
122 g = raman(p, q, 0L, 0L);
123 if (g == 0) {
124 std::cerr << " Sorry, I couldn't make that graph (error code "
125 << panic_code << ")" << std::endl;
126 continue;
127 }
128 distance_list.clear();
129 distance_list.resize(boost::num_vertices(g), 0);
130
131 // obtain property maps
132 d_map = get(dist_t(), g);
133 p_map = get(pred_t(), g);
134 c_map = get(color_t(), g);
135
136 vertex_iterator i, end;
137 for (boost::tie(i, end) = boost::vertices(g); i != end; ++i)
138 d_map[*i] = 0;
139
140 std::size_t k = 0;
141 std::size_t girth = (std::numeric_limits<std::size_t>::max)();
142 diameter_and_girth_visitor vis(k, girth);
143
144 vertex_descriptor s = *boost::vertices(g).first;
145
146 boost::breadth_first_search(g, s, visitor(vis).color_map(c_map));
147
148 std::cout << "Starting at any given vertex, there are" << std::endl;
149
150 for (long d = 1; distance_list[d] != 0; ++d)
151 std::cout << distance_list[d] << " vertices at distance " << d
152 << (distance_list[d+1] != 0 ? "," : ".") << std::endl;
153
154 std::cout << "So the diameter is " << k - 1
155 << ", and the girth is " << girth
156 << "." << std::endl;
157 } // end while
158
159 return 0;
160 }
161