Function reorder_graph

python/dgl/transforms/functional.py:3078–3341

r"""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

(
    g,
    node_permute_algo=None,
    edge_permute_algo="src",
    store_ids=True,
    permute_config=None,
)

def reorder_graph(
    g,
    node_permute_algo=None,
    edge_permute_algo="src",
    store_ids=True,
    permute_config=None,
):
    r"""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 :attr:`node_permute_algo`
    argument. For edge permutation, user can re-arrange edges according to their
    source nodes or destination nodes by the :attr:`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. If given, the options are ``rcmk`` or
        ``metis`` or ``custom``.

        * ``None``: Keep the current node order.
        * ``rcmk``: Use the `Reverse Cuthill–McKee <https://docs.scipy.org/doc/scipy/reference/
          generated/scipy.sparse.csgraph.reverse_cuthill_mckee.html#
          scipy-sparse-csgraph-reverse-cuthill-mckee>`__ from ``scipy`` to generate nodes
          permutation.
        * ``metis``: Use the :func:`~dgl.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&#x27;s nature.
        * ``custom``: Reorder the graph according to the user-provided node permutation
          array (provided in :attr:`permute_config`).
    edge_permute_algo: str, optional
        The permutation algorithm to reorder edges. Options are ``src`` or ``dst`` or
        ``custom``. ``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 in :attr:`permute_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`` 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).