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 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. Options are
rcmk
ormetis
orcustom
.rcmk
is the default value.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
.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
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
, 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.
- 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) >>> 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 specifyrelabel_nodes
asFalse
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])}