How to access the ancestor vertex during a breadth-first search with the Boost Graph Library?

Question

Hello everybody here, I'm trying to write my own version of connected components discovery using the breadth-first search algorithm included in the Boost Graph Library and I need to access the ancestor (the vertex which leads to the discovery of the current vertex) vertex from withing the discover_vertex callback of my visitor to set the component number of the current vertex. Any way it can be done easily ?

Answer 1

Create an examine_vertex callback that records the vertex being examined (popped from the queue). This vertex will be the ancestor of whatever vertex is being discovered.

From the pseudo code in BGL's BFS documentation:

vis.examine_vertex(u, g) is invoked in each vertex as it is removed from the queue.

BFS(G, s)
  for each vertex u in V[G]
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
  end for
  color[s] := GRAY 
  d[s] := 0 
  ENQUEUE(Q, s)
  while (Q != Ø) 
    u := DEQUEUE(Q)                   # `u` is recorded in examine_vertex callback 
    for each vertex v in Adj[u]
      if (color[v] = WHITE)
        color[v] := GRAY
        d[v] := d[u] + 1  
        p[v] := u  
        ENQUEUE(Q, v)                 # `v` is discovered, `u` is its ancestor.
      else
        if (color[v] = GRAY) 
          ...
        else 
          ...
    end for
    color[u] := BLACK
  end while
  return (d, p)