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