Why DFS `discoveres` the vertex, that it should not?

i have a very simple directed graph:
V0 -> V2
V1 -> V2

i use BFS and DFS algorithms starting from V0 and get different results from
`discover_vertex` function:
for BFS it does not discover V1, that is correct - there is no path from V0
to V1
but for DFS it does discover V1

directed graph
0 2 BFS visited 2 // correct
0 2 1 DFS visited 3 // wrong

undirected graph
0 2 1 BFS visited 3 // correct
0 2 1 DFS visited 3 // correct


import graph_tool.all as gt

class BFSCheck(gt.BFSVisitor):
  def __init__(self):
    self.visited = 0

  def discover_vertex(self, u):
    self.visited += 1
    print u,

class DFSCheck(gt.DFSVisitor):
  def __init__(self):
    self.visited = 0

  def discover_vertex(self, u):
    self.visited += 1
    print u,

def Cmp(graph):
  v0 = graph.add_vertex()
  v1 = graph.add_vertex()
  v2 = graph.add_vertex()

  e0 = graph.add_edge(v0, v2)
  e1 = graph.add_edge(v1, v2)

  bfs_check = BFSCheck()
  gt.bfs_search(graph, v0, bfs_check)
  print "BFS visited %d" % bfs_check.visited

  dfs_check = DFSCheck()
  gt.dfs_search(graph, v0, dfs_check)
  print "DFS visited %d" % dfs_check.visited

graph_u = gt.Graph(directed = False)
graph_d = gt.Graph(directed = True)

print "directed graph"

print "undirected graph"

This seems to be the default behavior of the depth_first_search()
function in boost. See:


Note that in this function _all_ vertices are eventually visited, not
only the (out-)component from the source! I don't really understand why
it was done like this, since, as you observed, it is inconsistent with
BFS. I have modified the code in graph-tool to use the function
depth_first_visit() instead, where this is avoided, and the expected
behavior is obtained. Just try the current git version.

Thanks for the very simple example.