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 {
74 }
75
tree_edge(edge_descriptor e,Graph * g)76 void tree_edge(edge_descriptor e, Graph* g)
77 {
78 vertex_descriptor u = source(e, g), v = target(e, g);
79 k = d_map[u] + 1;
80 d_map[v] = k;
81 ++distance_list[k];
82 p_map[v] = u;
83 }
non_tree_edge(edge_descriptor e,Graph * g)84 void non_tree_edge(edge_descriptor e, Graph* g)
85 {
86 vertex_descriptor u = source(e, g), v = target(e, g);
87 k = d_map[u] + 1;
88 if (d_map[v] + k < girth && v != p_map[u])
89 girth = d_map[v] + k;
90 }
91
92 private:
93 std::size_t& k;
94 std::size_t& girth;
95 };
96
main()97 int main()
98 {
99 std::cout
100 << "This program explores the girth and diameter of Ramanujan graphs."
101 << std::endl;
102 std::cout
103 << "The bipartite graphs have q^3-q vertices, and the non-bipartite"
104 << std::endl;
105 std::cout << "graphs have half that number. Each vertex has degree p+1."
106 << std::endl;
107 std::cout << "Both p and q should be odd prime numbers;" << std::endl;
108 std::cout << " or you can try p = 2 with q = 17 or 43." << std::endl;
109
110 while (1)
111 {
112
113 std::cout << std::endl << "Choose a branching factor, p: ";
114 long p = 0, q = 0;
115 std::cin >> p;
116 if (p == 0)
117 break;
118 std::cout << "Ok, now choose the cube root of graph size, q: ";
119 std::cin >> q;
120 if (q == 0)
121 break;
122
123 Graph* g;
124 g = raman(p, q, 0L, 0L);
125 if (g == 0)
126 {
127 std::cerr << " Sorry, I couldn't make that graph (error code "
128 << panic_code << ")" << std::endl;
129 continue;
130 }
131 distance_list.clear();
132 distance_list.resize(boost::num_vertices(g), 0);
133
134 // obtain property maps
135 d_map = get(dist_t(), g);
136 p_map = get(pred_t(), g);
137 c_map = get(color_t(), g);
138
139 vertex_iterator i, end;
140 for (boost::tie(i, end) = boost::vertices(g); i != end; ++i)
141 d_map[*i] = 0;
142
143 std::size_t k = 0;
144 std::size_t girth = (std::numeric_limits< std::size_t >::max)();
145 diameter_and_girth_visitor vis(k, girth);
146
147 vertex_descriptor s = *boost::vertices(g).first;
148
149 boost::breadth_first_search(g, s, visitor(vis).color_map(c_map));
150
151 std::cout << "Starting at any given vertex, there are" << std::endl;
152
153 for (long d = 1; distance_list[d] != 0; ++d)
154 std::cout << distance_list[d] << " vertices at distance " << d
155 << (distance_list[d + 1] != 0 ? "," : ".") << std::endl;
156
157 std::cout << "So the diameter is " << k - 1 << ", and the girth is "
158 << girth << "." << std::endl;
159 } // end while
160
161 return 0;
162 }
163