dgl.reorder_graph¶

dgl.reorder_graph(g, node_permute_algo=None, edge_permute_algo='src', store_ids=True, permute_config=None)[source]¶

Return a new graph with nodes and edges re-ordered/re-labeled according to the specified permute algorithm.

Support homogeneous graph only for the moment.

The re-ordering has two 2 steps: first re-order nodes and then re-order edges.

For node permutation, users can re-order by the node_permute_algo argument. For edge permutation, user can re-arrange edges according to their source nodes or destination nodes by the edge_permute_algo argument. Some of the permutation algorithms are only implemented in CPU, so if the input graph is on GPU, it will be copied to CPU first. The storage order of the node and edge features in the graph are permuted accordingly.

Parameters

g (DGLGraph) – The homogeneous graph.
node_permute_algo (str, optional) –
The permutation algorithm to re-order nodes. If given, the options are rcmk or metis or custom.
- None: Keep the current node order.
- rcmk: Use the Reverse Cuthill–McKee from scipy to generate nodes permutation.
- metis: Use the metis_partition_assignment() function to partition the input graph, which gives a cluster assignment of each node. DGL then sorts the assignment array so the new node order will put nodes of the same cluster together. Please note that the generated nodes permutation of metis is non-deterministic due to algorithm’s nature.
- custom: Reorder the graph according to the user-provided node permutation array (provided in permute_config).
edge_permute_algo (str, optional) –
The permutation algorithm to reorder edges. Options are src or dst or custom. src is the default value.
- src: Edges are arranged according to their source nodes.
- dst: Edges are arranged according to their destination nodes.
- custom: Edges are arranged according to the user-provided edge permutation array (provided in permute_config).
store_ids (bool, optional) – If True, DGL will store the original node and edge IDs in the ndata and edata of the resulting graph under name dgl.NID and dgl.EID, respectively.
permute_config (dict, optional) –
Additional key-value config data for the specified permutation algorithm.
- For rcmk, this argument is not required.
- For metis, users should specify the number of partitions k (e.g., permute_config={'k':10} to partition the graph to 10 clusters).
- For custom node reordering, users should provide a node permutation array nodes_perm. The array must be an integer list or a tensor with the same device of the input graph.
- For custom edge reordering, users should provide an edge permutation array edges_perm. The array must be an integer list or a tensor with the same device of the input graph.

Returns

The re-ordered graph.

Return type

DGLGraph

Examples

>>> import dgl
>>> import torch
>>> g = dgl.graph((torch.tensor([0, 1, 2, 3, 4]), torch.tensor([2, 2, 3, 2, 3])))
>>> g.ndata['h'] = torch.arange(g.num_nodes() * 2).view(g.num_nodes(), 2)
>>> g.edata['w'] = torch.arange(g.num_edges() * 1).view(g.num_edges(), 1)
>>> g.ndata
{'h': tensor([[0, 1],
        [2, 3],
        [4, 5],
        [6, 7],
        [8, 9]])}
>>> g.edata
{'w': tensor([[0],
        [1],
        [2],
        [3],
        [4]])}

Reorder according to 'rcmk' permute algorithm.

>>> rg = dgl.reorder_graph(g, node_permute_algo='rcmk')
>>> rg.ndata
{'h': tensor([[8, 9],
        [6, 7],
        [2, 3],
        [4, 5],
        [0, 1]]), '_ID': tensor([4, 3, 1, 2, 0])}
>>> rg.edata
{'w': tensor([[4],
        [3],
        [1],
        [2],
        [0]]), '_ID': tensor([4, 3, 1, 2, 0])}

Reorder according to 'metis' permute algorithm.

>>> rg = dgl.reorder_graph(g, node_permute_algo='metis', permute_config={'k':2})
>>> rg.ndata
{'h': tensor([[4, 5],
        [2, 3],
        [0, 1],
        [8, 9],
        [6, 7]]), '_ID': tensor([2, 1, 0, 4, 3])}
>>> rg.edata
{'w': tensor([[2],
        [1],
        [0],
        [4],
        [3]]), '_ID': tensor([2, 1, 0, 4, 3])}

Reorder according to 'custom' permute algorithm with user-provided nodes_perm.

>>> rg = dgl.reorder_graph(g, node_permute_algo='custom',
...                        permute_config={'nodes_perm': [3, 2, 0, 4, 1]})
>>> rg.ndata
{'h': tensor([[6, 7],
        [4, 5],
        [0, 1],
        [8, 9],
        [2, 3]]), '_ID': tensor([3, 2, 0, 4, 1])}
>>> rg.edata
{'w': tensor([[3],
        [2],
        [0],
        [4],
        [1]]), '_ID': tensor([3, 2, 0, 4, 1])}

Reorder nodes according to 'rcmk' and reorder edges according to dst edge permute algorithm.

>>> rg = dgl.reorder_graph(g, node_permute_algo='rcmk', edge_permute_algo='dst')
>>> print(rg.ndata)
{'h': tensor([[8, 9],
        [6, 7],
        [2, 3],
        [4, 5],
        [0, 1]]), '_ID': tensor([4, 3, 1, 2, 0])}
>>> print(rg.edata)
{'w': tensor([[4],
        [2],
        [3],
        [1],
        [0]]), '_ID': tensor([4, 2, 3, 1, 0])}

Nodes are not reordered but edges are reordered according to 'custom' permute algorithm with user-provided edges_perm.

>>> rg = dgl.reorder_graph(g, edge_permute_algo='custom',
...                        permute_config={'edges_perm': [1, 2, 3, 4, 0]})
>>> print(rg.ndata)
{'h': tensor([[0, 1],
        [2, 3],
        [4, 5],
        [6, 7],
        [8, 9]]), '_ID': tensor([0, 1, 2, 3, 4])}
>>> print(rg.edata)
{'w': tensor([[1],
        [2],
        [3],
        [4],
        [0]]), '_ID': tensor([1, 2, 3, 4, 0])}