dgl.reorder_graph

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

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

目前仅支持同构图。

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

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

参数:

g (DGLGraph) – 同构图。
node_permute_algo (str, optional) –
用于重新排序节点的置换算法。如果给定，选项包括 rcmk 或 metis 或 custom。
- None: 保持当前节点顺序。
- rcmk: 使用来自 scipy 的 Reverse Cuthill–McKee 生成节点置换。
- 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 中分别以 dgl.NID 和 dgl.EID 为名称存储原始节点和边 ID。
permute_config (dict, optional) –
指定置换算法的额外键值配置数据。
- 对于 rcmk，不需要此参数。
- 对于 metis，用户应指定分区数 k（例如，permute_config={'k':10} 将图划分为 10 个簇）。
- 对于 custom 节点重新排序，用户应提供一个节点置换数组 nodes_perm。该数组必须是整数列表或与输入图在同一设备上的张量。
- 对于 custom 边重新排序，用户应提供一个边置换数组 edges_perm。该数组必须是整数列表或与输入图在同一设备上的张量。

返回:

重新排序后的图。

返回类型:

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

根据 'custom' 置换算法和用户提供的 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])}

节点根据 '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])}

节点未重新排序，但边根据 'custom' 置换算法和用户提供的 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])}