[graph-tool] Why DFS `discoveres` the vertex, that it should not?

4 Mar 2013


      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

output:
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

code:

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"
Cmp(graph_d)

print
print "undirected graph"
Cmp(graph_u)


--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/...
Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

[graph-tool] Why DFS `discoveres` the vertex, that it should not?

shpavel