Algorithm 42: get direct neighbour subgraph from a vertex descriptor

[JohnCoconut]

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.