dgl.reorder_graph

dgl.reorder_graph(g, node_permute_algo='rcmk', 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. Options are rcmk or metis or custom. rcmk is the default value.

    • 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. src is the default value.

    • src: Edges are arranged according to their source nodes.

    • dst: Edges are arranged according to their destination nodes.

  • 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, 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.

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)
>>> 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, '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.

>>> nodes_perm = torch.randperm(g.num_nodes())
>>> nodes_perm
tensor([3, 2, 0, 4, 1])
>>> rg = dgl.reorder_graph(g, 'custom', permute_config={'nodes_perm':nodes_perm})
>>> 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 according to dst edge permute algorithm and refine further according to self-generated edges permutation. Please assure to specify relabel_nodes as False to keep the nodes order.

>>> rg = dgl.reorder_graph(g, edge_permute_algo='dst')
>>> rg.edges()
(tensor([0, 3, 1, 2, 4]), tensor([1, 1, 3, 3, 3]))
>>> eg = dgl.edge_subgraph(rg, [0, 2, 4, 1, 3], relabel_nodes=False)
>>> eg.edata
{'w': tensor([[4],
        [3],
        [0],
        [2],
        [1]]), '_ID': tensor([0, 2, 4, 1, 3])}