dgl.traversal.dfs_edges_generator

dgl.traversal.dfs_edges_generator(graph, source, reverse=False)[source]

Edge frontiers generator using depth-first-search (DFS).

Multiple source nodes can be specified to start the DFS traversal. One needs to make sure that each source node belongs to different connected component, so the frontiers can be easily merged. Otherwise, the behavior is undefined.

Parameters
  • graph (DGLHeteroGraph) – The graph object.

  • source (list, tensor of nodes) – Source nodes.

  • reverse (bool, optional) – If True, traverse following the in-edge direction.

Returns

Each edge frontier is a list or tensor of edge ids.

Return type

list of edge frontiers

Examples

Given a graph (directed, edges from small node id to large):

      2 - 4
     / \
0 - 1 - 3 - 5

Edge addition order [(0, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 5)]

>>> g = dgl.graph(([0, 1, 1, 2, 2, 3], [1, 2, 3, 3, 4, 5]))
>>> list(dgl.dfs_edges_generator(g, 0))
[tensor([0]), tensor([1]), tensor([3]), tensor([5]), tensor([4])]