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 theedge_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
ormetis
orcustom
.None
: Keep the current node order.rcmk
: Use the Reverse Cuthill–McKee fromscipy
to generate nodes permutation.metis
: Use themetis_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 ofmetis
is non-deterministic due to algorithm’s nature.custom
: Reorder the graph according to the user-provided node permutation array (provided inpermute_config
).
edge_permute_algo (str, optional) –
The permutation algorithm to reorder edges. Options are
src
ordst
orcustom
.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 inpermute_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
anddgl.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 partitionsk
(e.g.,permute_config={'k':10}
to partition the graph to 10 clusters).For
custom
node reordering, users should provide a node permutation arraynodes_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 arrayedges_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
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 todst
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])}