summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/graph/example/girth.cpp
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-27 18:24:20 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-27 18:24:20 +0000
commit483eb2f56657e8e7f419ab1a4fab8dce9ade8609 (patch)
treee5d88d25d870d5dedacb6bbdbe2a966086a0a5cf /src/boost/libs/graph/example/girth.cpp
parentInitial commit. (diff)
downloadceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.tar.xz
ceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.zip
Adding upstream version 14.2.21.upstream/14.2.21upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/boost/libs/graph/example/girth.cpp')
-rw-r--r--src/boost/libs/graph/example/girth.cpp160
1 files changed, 160 insertions, 0 deletions
diff --git a/src/boost/libs/graph/example/girth.cpp b/src/boost/libs/graph/example/girth.cpp
new file mode 100644
index 00000000..9c9cc23c
--- /dev/null
+++ b/src/boost/libs/graph/example/girth.cpp
@@ -0,0 +1,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;
+}