dgl.traversal.dfs_labeled_edges_generator¶

dgl.traversal.dfs_labeled_edges_generator(graph, source, reverse=False, has_reverse_edge=False, has_nontree_edge=False, return_labels=True)[source]¶

Produce edges in a depth-first-search (DFS) labeled by type.

There are three labels: FORWARD(0), REVERSE(1), NONTREE(2)

A FORWARD edge is one in which u has been visited but v has not. A REVERSE edge is one in which both u and v have been visited and the edge is in the DFS tree. A NONTREE edge is one in which both u and v have been visited but the edge is NOT in the DFS tree.

See networkx’s dfs_labeled_edges for more details.

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 (DGLGraph) – The graph object.
source (list, tensor of nodes) – Source nodes.
reverse (bool, optional) – If true, traverse following the in-edge direction.
has_reverse_edge (bool, optional) – True to include reverse edges.
has_nontree_edge (bool, optional) – True to include nontree edges.
return_labels (bool, optional) – True to return the labels of each edge.

Returns:

list of edge frontiers – Each edge frontier is a list or tensor of edge ids.
list of list of int – Label of each edge, organized in the same order as the 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.DGLGraph([(0, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 5)])
>>> list(dgl.dfs_labeled_edges_generator(g, 0, has_nontree_edge=True))
(tensor([0]), tensor([1]), tensor([3]), tensor([5]), tensor([4]), tensor([2])),
(tensor([0]), tensor([0]), tensor([0]), tensor([0]), tensor([0]), tensor([2]))