dgl.line_graph

dgl.line_graph(g, backtracking=True, shared=False)[source]

Return the line graph of this graph.

The line graph L(G) of a given graph G is defined as another graph where the nodes in L(G) maps to the edges in G. For any pair of edges (u, v) and (v, w) in G, the corresponding node of edge (u, v) in L(G) will have an edge connecting to the corresponding node of edge (v, w).

Parameters
  • g (DGLGraph) – Input graph. Must be homogeneous.

  • backtracking (bool, optional) –

    If False, the line graph node corresponding to edge (u, v) will not have an edge connecting to the line graph node corresponding to edge (v, u).

    Default: True.

  • shared (bool, optional) – Whether to copy the edge features of the original graph as the node features of the result line graph.

Returns

G – The line graph of this graph.

Return type

DGLGraph

Notes

  • If shared is True, the node features of the resulting graph share the same storage with the edge features of the input graph. Hence, users should try to avoid in-place operations which will be visible to both graphs.

  • The function supports input graph on GPU but copies it to CPU during computation.

Examples

Assume that the graph has the following adjacency matrix:

A = [[0, 0, 1],
     [1, 0, 1],
     [1, 1, 0]]
>>> g = dgl.graph(([0, 1, 1, 2, 2],[2, 0, 2, 0, 1]), 'user', 'follows')
>>> lg = g.line_graph()
>>> lg
Graph(num_nodes=5, num_edges=8,
ndata_schemes={}
edata_schemes={})
>>> lg.edges()
(tensor([0, 0, 1, 2, 2, 3, 4, 4]), tensor([3, 4, 0, 3, 4, 0, 1, 2]))
>>> lg = g.line_graph(backtracking=False)
>>> lg
Graph(num_nodes=5, num_edges=4,
ndata_schemes={}
edata_schemes={})
>>> lg.edges()
(tensor([0, 1, 2, 4]), tensor([4, 0, 3, 1]))