Count the number of levels in an undirected graph

[JohnCoconut]

Algorithm 53 - "Count the number of levels in an undirected graph", take a single parameter graph.

What does number of levels of a graph mean in the tutorial? The only definition I can find is https://en.wikipedia.org/wiki/Level_structure.

However, the definition on wiki takes a graph and a root vertex.

[richelbilderbeek]

Great feedback, thanks!

I assume the algorithm either uses the first vertex as a root vertex, or counts the maximum distance without self-loops possible.

As I think this is too much hand-waving, I will check this on Saturday.

[richelbilderbeek]

Feel ill, will postpone to tomorrow.

[JohnCoconut]

@richelbilderbeek take care. It's no hurry. There's no project leader after us.

[richelbilderbeek]

I checked. What it does: from a starting vertex, it looks how many levels of neighbouring vertices there are.

• Level 0: the initial vertex
• Level 1: the neightbours of level 0
• Level 2: the neightbours of level 1
• etc...

template <typename graph>
int count_ undirected_graph_levels(
typename boost::graph_traits<graph>::vertex_descriptor
vd,
const graph& g
) noexcept

I will improve the wording in the documentation.

[JohnCoconut]

This problem can be solved with breadth_first_search algorithm in boost graph library. The algorithm has a connvinience template function record_distance, that can record distances of all vertices connected to the root.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <unordered_map>

template <typename graph>
int count_undirected_graph_levels(
  typename boost::graph_traits<graph>::vertex_descriptor vd, 
  const graph& g) noexcept
{
  using vertex_descriptor = typename boost::graph_traits<graph>::vertex_descriptor;

  std::unordered_map<vertex_descriptor, vertex_descriptor> distance;
  auto distance_map = boost::make_assoc_property_map(distance);

  boost::breadth_first_search(g, vd, 
    boost::visitor(boost::make_bfs_visitor(
      boost::record_distances(distance_map, boost::on_tree_edge()))));

  typename boost::graph_traits<graph>::vertices_size_type level = 0;
  for (const auto p : distance)
    level = std::max(level, p.second);

  return level;
}

[richelbilderbeek]

Hmmm, I would not mind using that algorithm instead 😉

[JohnCoconut]

If using breadth_first_search instead, we can convey more information than number of levels. It can return level structure as in wikipedia, showing which vertex belongs to which level. Shall we change the signature of this function to return more information?

[richelbilderbeek]

I appreciate the suggestion, but I think a function called 'count_undirected_graph_levels` should return the number of levels (and that number only). Sure, it will return less info, but -for most users- less suoperfluous info. Additionally, it simplifies/focuses writing about it.

Would there be a function like e.g. collect_vertex_depths, sure, that function should return that information.

Do you agree with these ideas?

[JohnCoconut]

I wasn't clear. I am thinking of creating a new function like collection_vertex_depths and use this function to return number of levels.

[JohnCoconut]

BTW, how do you organize the code in your git repo? From what I see,

*.h has nothing exept function sigature, *.impl contains actually implementation.

[richelbilderbeek]

I wasn't clear. I am thinking of creating a new function like collection_vertex_depths
and use this function to return number of levels.

Sounds brilliant!

[richelbilderbeek]

BTW, how do you organize the code in your git repo? From what I see,

*.h has nothing exept function sigature, *.impl contains actually implementation.

This is documented in CONTRIBUTING.md. In short: the code in .impl is shown in the tutorial. This makes the code displayed as clean as possible.

[JohnCoconut]

Thanks for ur clarification. I wasn't too sure because I saw some *.h file didn't include *.impl file. Here is create_empty_directed_graph.h in the tutorial. I am surprised it hasn't generated a compiler error. Perhaps it needs a include directive here?

#ifndef CREATE_EMPTY_DIRECTED_GRAPH_H
#define CREATE_EMPTY_DIRECTED_GRAPH_H

#include <boost/graph/adjacency_list.hpp>

boost::adjacency_list<> create_empty_directed_graph() noexcept;

#endif // CREATE_EMPTY_DIRECTED_GRAPH_H

[richelbilderbeek]

That header files looks fine. I like to do a forward declaration whenever possible. In this case, as all types are known, it can be done. This speeds up compile times.