From 483eb2f56657e8e7f419ab1a4fab8dce9ade8609 Mon Sep 17 00:00:00 2001
From: Daniel Baumann <daniel.baumann@progress-linux.org>
Date: Sat, 27 Apr 2024 20:24:20 +0200
Subject: Adding upstream version 14.2.21.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
---
 src/boost/libs/graph/example/girth.cpp | 160 +++++++++++++++++++++++++++++++++
 1 file changed, 160 insertions(+)
 create mode 100644 src/boost/libs/graph/example/girth.cpp

(limited to 'src/boost/libs/graph/example/girth.cpp')

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;
+}
-- 
cgit v1.2.3