dgl.reorder_graph

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

返回一个新图，根据指定的置换算法重新排序/重新标记节点和边。

目前仅支持同构图。

重新排序有两个步骤：首先重新排序节点，然后重新排序边。

对于节点排列，用户可以通过node_permute_algo参数重新排序。对于边排列，用户可以通过edge_permute_algo参数根据源节点或目标节点重新排列边。一些排列算法仅在CPU上实现，因此如果输入图在GPU上，它将首先被复制到CPU。图中节点和边特征的存储顺序也会相应地进行排列。

Parameters:

g (DGLGraph) – 同构图。
node_permute_algo (str, optional) –
用于重新排序节点的置换算法。如果提供，选项为 rcmk 或 metis 或 custom。
- None: 保持当前节点顺序。
- rcmk: 使用 Reverse Cuthill–McKee 从 scipy 生成节点置换。
- metis: 使用 metis_partition_assignment() 函数对输入图进行分区，该函数给出每个节点的集群分配。 DGL 然后对分配数组进行排序，以便新的节点顺序将同一集群的节点放在一起。请注意，由于算法的性质，metis 生成的节点置换是非确定性的。
- custom: 根据用户提供的节点置换数组（在 permute_config 中提供）重新排序图。
edge_permute_algo (str, optional) –
用于重新排序边的置换算法。选项为 src 或 dst 或 custom。src 是默认值。
- src: 边根据其源节点排列。
- dst: 边根据其目标节点排列。
- custom: 边根据用户提供的边置换数组排列（在 permute_config 中提供）。
store_ids (bool, optional) – 如果为True，DGL将分别在ndata和edata中存储原始节点和边的ID，名称为dgl.NID和dgl.EID。
permute_config (dict, optional) –
用于指定置换算法的额外键值配置数据。
- 对于 rcmk，不需要此参数。
- 对于 metis，用户应指定分区数量 k（例如， permute_config={'k':10} 将图划分为10个集群）。
- 对于 custom 节点重新排序，用户应提供一个节点置换数组 nodes_perm。该数组必须是一个整数列表或与输入图相同设备的张量。
- 对于 custom 边重新排序，用户应提供一个边置换数组 edges_perm。该数组必须是一个整数列表或与输入图相同设备的张量。

Returns:

重新排序后的图表。

Return type:

DGLGraph

示例

>>> 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]])}

根据'rcmk'置换算法重新排序。

>>> 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])}

根据'metis'置换算法重新排序。

>>> 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])}

根据用户提供的 nodes_perm 使用 'custom' 排列算法重新排序。

>>> 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])}

根据'rcmk'重新排序节点，并根据dst边置换算法重新排序边。

>>> 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])}

节点不会被重新排序，但边会根据用户提供的edges_perm按照'custom'排列算法重新排序。

>>> 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])}