This makes me re-use my own functions more.

I was happy to associate any class with a custom vertex (and the same for edges).

There are posts about bundled properties, but I have never seen them go to the basic level of this tutorial.

Because I got the 'my_vertex_type' property working first, I chose to use that one over bundled properties.

But I would love to have a bundled properties chapter:

• creating an empty graph with ?bundled vertex properties
• check if there is a vertex with ?bundled vertex properties
• find a vertex with ?bundled vertex properties
• get a vertex with ?bundled vertex properties
• set a vertex with ?bundled vertex properties

It doesn't work with directed graph.

I don't know why I didn't find this error when I tried compile it last time. I was sure I created a directed graph and it compiled at that time. But now it doesn't. My mind is crooked.

This simple program doesn't compile.

#include <boost/graph/adjacency_list.hpp>

int main()
{
  boost::adjacency_list<> g;
  in_edges(g);
  return 0;
}

In create_direct_neighbour_subgraph_including_in_edges_test.cpp, a directed graph is created.

Will fix this issue in a PR later.

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From mat69:

• You should also mention the complexity of operations. The way you retrieve a vertex by name is O(n). I guess in most use cases it will be more efficient to have an std::unordered_map<std::string, MyVertex> and doing a lookup instead.

This Issue is similar to http://stackoverflow.com/questions/12058366/bgl-example-of-isomorphism-with-vertex-invariants

Calling boost::is_isomorphism on two graphs without properties is easy. But let's say the vertices now have names.

Here I create these graphs:

boost::adjacency_list<
  boost::vecS,
  boost::vecS,
  boost::undirectedS,
  boost::property<
    boost::vertex_name_t, std::string
  >
>
create_named_vertices_path_graph(
  const std::vector<std::string>& names
) noexcept
{
  auto g = create_empty_undirected_named_vertices_graph();
  if (names.size() == 0) { return g; }

  auto vertex_name_map
    = get( //not boost::get
      boost::vertex_name,
      g
    );

  auto vd_1 = boost::add_vertex(g);
  vertex_name_map[vd_1] = *names.begin();
  if (names.size() == 1) return g;

  const auto j = std::end(names);
  auto i = std::begin(names);
  for (++i; i!=j; ++i) //Skip first
  {
    auto vd_2 = boost::add_vertex(g);
    vertex_name_map[vd_2] = *i;
    const auto aer = boost::add_edge(vd_1, vd_2, g);
    assert(aer.second);
    vd_1 = vd_2;
  }
  return g;
}

Here is my test:

void is_named_vertices_isomorphic_demo() noexcept
{
  const auto g = create_named_vertices_path_graph(
    { "Alpha", "Beta", "Gamma" }
  );
  const auto h = create_named_vertices_path_graph(
    { "Alpha", "Gamma", "Beta" }
  );
  assert( is_named_vertices_isomorphic(g,g));
  assert(!is_named_vertices_isomorphic(g,h));
}

Here is the code for is_named_vertices_isomorphic:

template <typename Graph>
std::string discrete_vertex_invariant(
  const typename boost::graph_traits<Graph>::vertex_descriptor& vd,
  const Graph &g
)
{
  const auto name_map = get(boost::vertex_name,g);
  return name_map[vd];
}

template <typename Graph>
class discrete_vertex_invariant_functor
{
    using vertex_t = typename boost::graph_traits<Graph>::vertex_descriptor;
    const Graph& m_graph;
public:
    using result_type = std::string;
    using argument_type = vertex_t;
    discrete_vertex_invariant_functor(const Graph &g) : m_graph(g) {}
    result_type operator()(const vertex_t& vd) const
    {
        return discrete_vertex_invariant(vd,m_graph);
    }
    result_type max() const
    {
        return "";
    }
};

//helper function to help with argument deduction
template <typename Graph>
discrete_vertex_invariant_functor<Graph> make_discrete_vertex_invariant(
  const Graph &g
)
{
  return discrete_vertex_invariant_functor<Graph>(g);
}

template <typename graph1, typename graph2>
bool is_named_vertices_isomorphic_correct(
  const graph1& g,
  const graph2& h
) noexcept
{
  auto ref_index_map = get(boost::vertex_index, g);
  using vd = typename boost::graph_traits<graph1>::vertex_descriptor;
  std::vector<vd> iso(boost::num_vertices(g));

#ifdef USE_A
  return boost::isomorphism(
    g,
    h,
    isomorphism_map(
      make_iterator_property_map(iso.begin(), ref_index_map, iso[0])
    ).vertex_invariant1(make_discrete_vertex_invariant(g))
     .vertex_invariant2(make_discrete_vertex_invariant(h))
  );
  #else
  return boost::isomorphism(g,h,
    boost::isomorphism_map(
      make_iterator_property_map(iso.begin(), ref_index_map, iso[0])
    )
  );
  #endif
}

The USE_A is close to the solution but does not compile, the not-USE_A compiles, but does not pass the test,

The Travis CI assumes this works:

./configure && make && make test

It doesn't yet.

please generate pdf with bookmark

Marked FIX_ISSUE_36

Awesome article at http://blog.hostilefork.com/boost-graph-templates-not-crazy/

struct City {
   std::string name;
   unsigned population;
};

struct Road {
   std::string name;
   float miles;
};

struct MapWithInfo {
    boost::adjacency_list<
        vecS, vecS, bidirectionalS, City, Road
    > citiesAndRoads;

    std::string title;
    int year;
}

struct MapProperties {
    std::string title;
    int year;
}

boost::adjacency_list<
    vecS, vecS, bidirectionalS, City, Road, MapProperties
> citiesAndRoadsMap;

(boost::get(graph_properties, citiesAndRoadsMap))[citiesAndRoadsMap].year 

The code is GPL 3.0, the document itself is also copy-lefted.

This should be put in more explicitly

create_all_direct_neighbour_subgraphs should use algorithms and work on undirected graphs.

But copying from the source:

  //Copy edges
  {
    const auto eip = edges(g);
    const auto j = eip.second;
    for (auto i = eip.first; i!=j; ++i)
    {
      const auto vd_from = source(*i, g);
      const auto vd_to = target(*i, g);
      if (m.find(vd_from) == std::end(m)) continue;
      if (m.find(vd_to) == std::end(m)) continue;
      const auto aer = boost::add_edge(m[vd_from],m[vd_to], h);
      assert(aer.second);
    }
  }

where the functions source and target are used. This will not compile for undirected graphs.

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From mat69:

• You often create vectors of vertices/edges/names. When using unfiltered graphs you could use reserve in combination with num_edges, num_vertices.
• Sometimes, like when retrieving all the vertex names you first retrieve a vector of vertices to then iterate over them. In this case it is way more efficient to iterate directly over vertices() and avoiding the intermediate vector alltogether.
• You are not consistent in the way you access property maps. Sometimes you use my_map[XYZ] and other times get. To have flexible code you should always use get and put. That way you can change the vertex storage from vector to something else, without having to adapt all the other code.
• You should also mention the complexity of operations. The way you retrieve a vertex by name is O(n). I guess in most use cases it will be more efficient to have an std::unordered_map<std::string, MyVertex> and doing a lookup instead.
• You could use the standard algorithms in some occasions, for example when you search for a vertex by its name (5.2):

    auto vip = vertices(g); auto it = std::find_if(vip.first, vip.second, [&](const VertexDescriptor &vd) { return get(vertex_name_map, vd) == name; });

• You do not reuse your own functions, for example, you have an own function to retrieve the out degree of a vertex and then you have the same function when just a name was provided. I think a more natural way would be to retrieve the vertex given a name and to then call the out degree function with the retrieved vertex.

From danieljh:

• Regarding the vertices and edges functions: I enjoy using Boost.Range with them, as they return a pair of first,last-iterators. Combining this with range adaptors and lambdas, Boost.Graph code can get really modern and readable, such as:

auto weights = edges(graph) | transformed(to_weights) | filtered(is_non_negative);

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.

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From mat69:

• You could use the standard algorithms in some occasions, for example when you search for a vertex by its name (5.2):

    auto vip = vertices(g); auto it = std::find_if(vip.first, vip.second, [&](const VertexDescriptor &vd) { return get(vertex_name_map, vd) == name; });

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From danieljh:

• Regarding the vertices and edges functions: I enjoy using Boost.Range with them, as they return a pair of first,last-iterators. Combining this with range adaptors and lambdas, Boost.Graph code can get really modern and readable, such as:

auto weights = edges(graph) | transformed(to_weights) | filtered(is_non_negative);

Currently, the define BOOST_GRAPH_TUTORIAL_NO_GRAPHVIZ allows for using part of this tutorial when GraphViz is absent.

Instead of using this define, I'd prefer to create two .pro files:

• boost_graph_tutorial.pri
• boost_graph_tutorial_no_graphviz.pri

Lot of work, already messed up once (thanks to git for saving me), let's do this step by step...

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From mat69:

• You are not consistent in the way you access property maps. Sometimes you use my_map[XYZ] and other times get. To have flexible code you should always use get and put. That way you can change the vertex storage from vector to something else, without having to adapt all the other code.

Up until now, I just covered the basics of using graphs. Boost.Graph has way more stuff in it.

On could argue that I bridged the gap between newbie and being able to read the Bost.Graph book. But perhaps others argue that I should extend the tutorial.

I am sure, that when I need it, I will add it naturally. Up until then, others are the ones to go first.

The tutorial did not mention anything about edges between vertices for directed graphs.

If you use the function has_edge_between_vertices(vd_1, vd_2, g) it can give a different than has_edge_between_vertices(vd_2, vd_1, g) output in a directed graph, depending on what direction the edge has.

The tutorial mentions quites a few times we should use qualified function name instead of qualifying that name with boost.

Take property map for example(in algorithm 65),

The name map is obtained from the graph using ‘get’. ‘get’ (not boost::get) allow to obtain a property map.

If I understand correctly, function name is looked up by ADL(http://en.cppreference.com/w/cpp/language/adl). The boost score name isn't required in this case, but there's nothing wrong adding it.

I just found out how I might use them....

Ugly Markov chain:

\begin{tikzpicture}   
\tikzset{ 
  VertexStyle/.append style = { shape=circle, minimum size=30pt,inner sep=10pt },
  EdgeStyle/.append style = {->, bend left} }
\SetGraphUnit{5}
\Vertex{Rainy}   
\EA(A){Sunny}   
\Edge[](A)(B)   
\Edge[](B)(A)   
\Loop[dist = 4cm, dir = NO](A.west)
\Loop[dist = 4cm, dir = SO](B.east)
\end{tikzpicture}

Nice Markov chain with error:

\usetikzlibrary{automata,arrows}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=4cm, semithick]   
\tikzstyle{every state}=[draw=none]
\node[state] (A)              {$Sunny$};   
\node[state] (B) [right of=A] {$Rainy$};   
\path (A) edge [bend  left] node {Clouds leave} (B)
      (A) edge [loop  left] node {Sun keeps shining} (A)
      (B) edge [bend  left] node {Clouds arrive} (A)
      (B) edge [loop right] node {Clouds stay} (B)
; 
\end{tikzpicture}

https://www.ctan.org/pkg/tex4ebook?lang=en

The reader of the tutorial need not read the #include guards.

Saving and loading a graph with a name, chapters 'save_graph_with_graph_name_to_dot', 'load_directed_graph_with_graph_name_from_dot' and 'load_undirected_graph_with_graph_name_from_dot'

This tutorial is intended to do only the basics. It is already very long.

Some types are hardcoded, for example the 'get_vertex_names' algorithm returns a std::vectorstd::string, where std::string is the only supported vertex' name data type. It would be better if, instead of using std::string, deduce the type of the vertex' name data type from the graph.

Additionally, some functions have functions with two template arguments: a graph type and a vertex name type, where the latter can be extracted from the graph type somehow. But how?

The algorithm is problematic for graph with self loop. The probelm is explained in comments below.

template <typename graph, typename vertex_descriptor>
graph create_direct_neighbour_subgraph(
  const vertex_descriptor& vd, 
  const graph& g
)
{
  graph h;

  std::map<vertex_descriptor,vertex_descriptor> m;
  {
    /*
     * a new vertex is added to subgraph for original vd
     */
    const auto vd_h = boost::add_vertex(h);
    m.insert(std::make_pair(vd,vd_h));
  }

  {
    const auto vdsi = boost::adjacent_vertices(vd, g); 
    std::transform(vdsi.first, vdsi.second,
      std::inserter(m,std::begin(m)),
      [&h](const vertex_descriptor& d)
      {  
        /* 
         * if there's self loop for vd, another vertex will be added to subgraph
         */
        const auto vd_h = boost::add_vertex(h);
        return std::make_pair(d,vd_h);
      }   
    );  
  }

If there's a self loop for vertex descriptor vd, we create more than one vertices in the subgraph. Here is a example, original graph g is on the left, and the subgraph h for vertex vd0 is in the middle. In the code above, a new vertex 0 is created in subgraph h for vd0. Because it's a self loop, it's found in adjacent_vertices again, and another vertex 1 was created for vd0 again. At last, vertex 2 was created for vd1. So three vertices(0, 1, 2) in subgraph h for two vertices(0, 1) in graph g.

0 --> 0
0 --> 1
1 --> 2

The solution is to detect whether map m already contains the a certain vertex, and if it does, do not add a new vertex in the subgraph. We might have to give up std::transform, or use boost::range library functions instead.

I am not familiar how CI works. Please bear with my ignorance.

When I just push request a typo fix brach, the CI need to apt install a huge amount of packages g++ textlive etc before building this tutorial. It really takes a huge amount of time to simply install packges. I feel my typo-fix pull request is simply wasting CI resources.

Is CI build machine ephemeral? Or can we custmoze it so that it install all the necessary packages beforehand. If it's not possible, can we use customized docker images to do it?

Thanks ahead.

A vertex custom type and a vertex selectedness

Here is a nice SO about it

It claims:

sudo apt-get install texlive-fonts-recommended

Now the code compiles under Qt Creator, from the boost_graph_tutorial.pro file. Maybe other users can supply and maintain other makefile formats?

Anyone else knows how to set and get a graph its name?

Compilation time is too long for https://github.com/richelbilderbeek/pbdmms

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From mat69:

• You often create vectors of vertices/edges/names. When using unfiltered graphs you could use reserve in combination with num_edges, num_vertices.

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From mat69:

• You do not reuse your own functions, for example, you have an own function to retrieve the out degree of a vertex and then you have the same function when just a name was provided. I think a more natural way would be to retrieve the vertex given a name and to then call the out degree function with the retrieved vertex.

Here is the thread:

https://www.reddit.com/r/cpp/comments/3xw5q0/a_wellconnected_c11_boostgraph_tutorial/

From mat69:

• Sometimes, like when retrieving all the vertex names you first retrieve a vector of vertices to then iterate over them. In this case it is way more efficient to iterate directly over vertices() and avoiding the intermediate vector alltogether.

I missed some edges. But I do not mind enough to fix it now...

It is better for beginners to see the type.

Shorter code, type can be observed in return type, explain how to obtain the type iff interested.

Will be v1.3

It appears that I create a graph with name incorrectly.

The function create_markov_chain_with_graph_name creates a graph that is maybe incorrect as the name (Two-state Markov chain) contains spaces.

Labeled with FIX_ISSUE_1

See e.g function load_directed_custom_and_selectable_vertices_graph_from_dot_test

There is a table somewhere that states that bundled edges cannot have private members. This is -AFAIKS- false, so it should be corrected.

@mywtfmp3 has made multiple improvements to my code and should be added in the acknowledgements section.

@mywtfmp3:

• 1. agree?
• 2. iff yes, what is your complete name?

Thanks for your help 👍

Will do so this weekend